以多项式求值制造冗余
多项式插值可由足够多的值重构共享的秘密。同一个根数界也可构造能容忍符号丢失或损坏的码,但纠错和保密是不同目标。
定义 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 码 讨论多项式求值、最小距离及译码。