基于F_G(q)上纠错码的校验矩阵的验证方案

An identification scheme based on a parity check matrix of error correcting codes over F G(q)

Ｊ．Ｓｔｅｒｎ 在“公钥验证的一个新范例”中基于ＦＧ（２） 上纠错码的校验矩阵提出了一个验证方案，该文将其加以推广，给出了基于ＦＧ（ｑ） （ｑ 为素数）上纠错码的校验矩阵的一个新验证方案，将Ｊ．Ｓｔｅｒｎ 的方案中对秘密数据ｓ 的重量限制改为对ｓ的码元分布情况的限制；证明了在随机预言模型中给出的协议是零知识交互证明，并显示出通过参数的适当选取，此方案比Ｊ．Ｓｔｅｒｎ 的方案更安全．

An identification scheme based on a parity check matrix of error correcting codes over F G(2) was proposed in the paper “A New Paradigm for Public Key Identification” by J.Stern. The identification scheme of J.Stern is generalized in this paper, and a new identification scheme based on a parity check matrix of error correcting codes over F G(q) (q is a prime) is proposed. The limitation on the weight of mysterious datum s is changed into the limitation on the distribution of code elements of s. It is proved that the given protocol is a zero knowledge interactive proof in the random oracle model, and it is shown that the scheme is more secure than the scheme of J.Stern when parameters are selected properly.