code based cryptography
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
解密： \(y_1 = yP^(-1) = xSG + eP^(-1)\)
由于 \(eP^(-1)\) 的汉明weight = t，因此，可消解求得 xS
再乘以 \(S^(-1)\) ，恢复x
Niederreiter
公钥为奇偶校验矩阵H
私钥为t-bounnded H-syndrome decode，记为p(x)
加密： eH’，其中H’为H的转置
解密：p(y) = p(eH’) = e