以多項式求值製造冗餘
多項式插值可由足夠多的值重建分享的秘密。同一個根數界也可構造能容忍符號遺失或損壞的碼,但糾錯和保密是不同目標。
定義 9.1.1
(多項式求值碼)
令 為質數,在 上運算。取整數 和互異求值點 。把係數向量 編碼:先構造 ,再傳送
每個座標是一個域符號,不一定是一個位元。碼 是所有這類字組成的集合。
這些多項式求值碼是 Reed–Solomon 碼的標準構造;求值點不必排除零。集合 是線性的,因為求值保持加法和純量乘法。次數小於 的非零多項式不能在全部 個互異點為零,因此求值映射為單射,且 。
精確最小距離
定理 9.1.2
(求值碼的距離)
上述構造的最小漢明(Hamming)距離為 。
證明
(以根數得下界,以因子乘積達到等號)
對兩個次數小於 的不同多項式 ,其非零差多項式至多有 個根。因此兩個求值碼字至多在 個位置相同,至少在 個位置不同。下界可以達到:任選 個求值點,令 為相應因子 的乘積; 時空乘積為 。它的次數為 ,恰好在所選位置為零,所以 和零多項式的碼字距離為 。
常見錯誤
(求值點必須互異)
根數界計算的是互異的根,所以重複的求值點會破壞距離公式。在 上取 和求值點 ,次數為二的多項式 的碼字是 ,重量為二,而不是 。
遺失與錯誤的符號
定義 9.1.3
(擦除與錯誤)
擦除是被標示為值不可用的位置;錯誤是未標記、卻收到錯誤值的位置。
以下是唯一性保證,並非有效率的解碼算法。
定理 9.1.4
(混合錯誤與擦除)
假設傳送的碼字有 個位置被擦除,且未擦除的位置至多有 個錯誤。若 ,它是唯一在未擦除位置與接收值相差至多 處的碼字。對此碼,條件等價於 。
證明
(兩個候選碼字會過於接近)
若另一碼字也在未擦除位置與接收值相差至多 處,兩碼字在這些位置至多相差 處。它們在擦除位置至多還有 處不同,總距離便至多為 ,與最小距離矛盾。根據假設,傳送的碼字存在且符合條件。各量都是整數,故 等價於 。
證明透視
為何界中一個錯誤佔兩個位置
關鍵一步是只在未擦除位置上用三角不等式:兩個候選碼字可能在不同位置與同一個可見接收字不符,所以兩組錯誤位置都可能計入它們在那裏的距離,至多 。擦除位置沒有觀察值可比較,每個這樣的位置對兩碼字距離至多貢獻一。假設 只用了一次,用來與最小距離矛盾;合格候選的存在性並非證明所得,而是假設,因為傳送的碼字就是一個。論證除了 的值以外沒有用到多項式,所以同樣的計數適用於任何最小距離為 的碼。
當 ,至多 個擦除仍留下至少 個已知值,可用插值重建 。有錯誤時,定理在所述界內證明唯一性,卻沒有給出有效率的尋找算法。超出此界,證明不提供普遍保證;解碼器可能失敗或作出錯誤修正。
例題 9.1.5
( 上長度為五的碼)
取 、、,求值點為 。對 ,各值為 、、、、,所以模七下碼字為 。此時 :任意兩個擦除可恢復,或一個未標記的符號錯誤可唯一糾正。
例題 9.1.6
(以插值填補兩個擦除)
假設求值點 和 的位置被擦除,餘下 三對。這些值關於 對稱,故試 ;由 得 。展開得 ,正是 。被擦除的值為 與 。三對點與值唯一確定次數至多二的多項式,所以沒有其他碼字吻合。
例題 9.1.7
(以試探插值定位一個錯誤)
假設收到 ,沒有擦除,至多一個錯誤。用求值點 的值插值再次得到 ,而 在 處的值 也吻合;它只在 處與接收字不同,所以由定理它是唯一答案。包含錯誤位置的插值會被排除。經過 時,條件 與 給出 、,故 ,而 、。它與接收字在兩個位置不符,超出一個錯誤的範圍。
常見錯誤
(錯誤不如擦除便宜)
規則 會錯誤地聲稱 時一個錯誤加一個擦除總能處理。取 的碼字 及 的碼字 。擦除最後一個位置,收到 。可見的值與 的碼字只在 處不同,與 的碼字只在 處不同,所以兩者都與一個錯誤相容。正確的要求是 ,此處 ,並不成立。
反例模式
超出保證半徑
令 ,其碼字為 。若傳送 的碼字卻收到 ,便有兩個符號損壞。接收字與傳送字的距離為二,與 的碼字距離為一。因此最近碼字規則會選錯。知道允許的錯誤界很重要;僅有冗餘不能識別每種損壞。
同一插值的不同用途
在門檻秘密分享中,隨機係數使少數份額不能透露秘密。此處整個係數向量都是訊息,沒有加入隨機遮蔽。特別是如果求值點包含 ,就會直接透露 。距離證明提供抗錯能力,並不提供保密性。實際部署也需要具體編碼、解碼器和完整性模型;單靠距離公式不能提供這些。
習題
快速檢查
(在 上,計算 在 的值,並求 的 。)
解答 · 答案
碼字為 ,且 。
快速檢查
(此碼中,一個錯誤加一個擦除是否在唯一性保證內?兩個擦除又如何?)
解答 · 答案
一個錯誤加一個擦除給出 ,定理不提供保證。兩個擦除給出 ,在保證內。
快速檢查
(若 、,求最小距離和無錯誤時保證可恢復的最多擦除數。)
解答 · 答案
,可恢復 個擦除;假設域有至少六個互異求值點。
快速檢查
(為何求值點包含 ,便不能用此未遮蔽編碼向持有該座標的人隱藏 ?)
解答 · 答案
該符號就是 ,直接透露此係數。
延伸閱讀
麻省理工開放式課程第 20 講:Reed–Solomon 碼 討論多項式求值、最小距離及解碼。