基于超奇异同源的鉴别方案

Identification Scheme Based on Supersingular Isogenies

在本文中,我们构造了一种基于超奇异椭圆曲线同源的身份识别方案,该方案可用于构造基于同源的零知识证明,进一步用于设计基于同源的抗量子数字签名方案和基于同源的区块链抗量子密码方案.我们的方案是De Feo, Jao和Pl(?)t的方案的推广,是一种交互的零知识证明方案.我们的方案同样也可以使用Unruh的构造方法把交互零知识证明转换为非交互零知识证明.零知识证明可用于区块链的隐私保护,为了获得抗量子安全的零知识证明,需要使用抗量子密码算法.截止到目前为止,与其它抗量子密码算法相比,其中基于同源的抗量子密码在相同的安全水平下,公钥长度和通信量是最小的.因此我们尝试寻找基于同源的零知识证明方案和数字签名方案.目前基于同源的数字签名方案都依赖于De Feo, Jao和Pl(?)t的方案.但是使用De Feo, Jao和Pl(?)t的方案设计的零知识证明效率很低,每一次交互过程只能确认1比特的安全性.我们的方案在De Feo, Jao和Pl(?)t的方案的基础上推广到一次交互过程可以确认2比特的安全性.

This paper presents an identification scheme based on supersingular isogenies. The proposed scheme can be used to construct zero-knowledge proof based on isogenies. Furthermore, it can be used to design post-quantum digital signature schemes and post-quantum block chain cryptography schemes based on isogenies. The proposed scheme is a generalization of De Feo, Jao, and Plut＇s scheme,and is an interactive zero-knowledge proof scheme. The proposed scheme can use Unruh＇s construction to transform the interactive zero-knowledge proof into a non-interactive one. Zero-knowledge proof can be used to protect the privacy in block chain. In order to have the post-quantum security zeroknowledge proof, post-quantum cryptography algorithms need to be used. Compared with other postquantum cryptography algorithms known so far, at the same security level, the cryptography based on isogeny has the shortest public key length and the least communication cost. Thus we try to find the zero-knowledge proof schemes and digital signature schemes based on isogeny. By far, the digital signature schemes based on isogeny all depend on the De Feo, Jao, and Plut＇s scheme. However, the zero-knowledge proof constructed by De Feo, Jao, and Plut＇s scheme is noneffective, because it can only validate 1 bit security in each round of the interactive proof. We generalize the De Feo, Jao, and Plut＇s scheme to get 2 bit security in each round of the interactive proof.