Goppa编码

加密兼纠错

C = u*G， G 为 k x n 生成矩阵，将k长的u转换为n长的C

奇偶校验矩阵 H，满足 G*H’ = 0 ，其中H’为H的转置

c = mG + e，e为random t-error vector

s = cH’ = mGH’ + eH’ = eH’

逆推可求得e

再 c - e，解得m

McEliece

公钥为Goppa码的生成矩阵G1

私钥为t-bounnded decoder，记为p(x)

加密： y = xG1 + e，e为汉明weight <= t的随机项

解密： p(y)G’，其中G1*G’ = 1

细节：

k -> n ，原文编码到目标空间

G1 = SGP , S 为k x k 可逆, G 为 k x n 不可约生成矩阵，P 为 n x n 置换

公钥为G1

y = xSGP + e

解密： y1 = y(P^-1) = xSG + e(P^-1)

由于 e(P^-1) 的汉明weight = t，因此，可消解求得 xS

再乘以S^-1，恢复x

公钥为奇偶校验矩阵H

私钥为t-bounnded H-syndrome decode，记为p(x)

加密： eH’，其中H’为H的转置

解密：p(y) = p(eH’) = e

25 January 2020