基于超奇异同源的鉴别方案
|
摘要
在本文中,我们构造了一种基于超奇异椭圆曲线同源的身份识别方案,该方案可用于构造基于同源的零知识证明,进一步用于设计基于同源的抗量子数字签名方案和基于同源的区块链抗量子密码方案.我们的方案是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.
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.
引文
[1]VELU J. Isogénies entre courbes elliptiques[J]. C. R. Acad. Sc. Paris, S6rie A., 273, 1971:238-241.
[2]BOSTAN A, MORAIN F, SALVY B, et al. Fast algorithms for computing isogenies between elliptic curves[J].Mathematics of Computation, 77, 2008:1755-1778.[DOI:10.1090/S0025-5718-08-02066-8]
[3]KOHEL D. Endomorphism Rings of Elliptic Curves over Finite Fields[D].[Ph.D. Dissertation]. Berkeley, CA,USA. University of California Berkeley, 1996.
[4]BLAKE I, SEROUSSI G, SMART N. Elliptic Curves in Cryptography[M]. Cambridge University Press, UK. 1999.[DOI:10.1112/S0024609300247371]
[5]DE FEO L, JAO D, PLUT J. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[J]. Journal of Mathematical Cryptology, 2014, 8(3):209-247.[DOI:10.1515/jmc-2012-0015]
[6]SUN X, TIAN H B, WANG Y M. Toward quantum-resistant strong designated verifier signature from isogenies[C].In:2012 Fourth International Conference on Intelligent Networking and Collaborative Systems(INCoS 2012).IEEE, 2012:292-296.[DOI:10.1109/iNCoS.2012.70]
[7]GALBRAITH S D, PETIT C, SILVA J. Identification protocols and signature schemes based on supersingular isogeny problems[C]. In:Advances in Cryptology—ASIACRYPT 2017, Part I. Springer Cham, 2017:3-33.[DOI:10.1007/978-3-319-70694-8_1]
[8]YOO Y, AZARDERAKHSH R, JALALI A, et al. A post-quantum digital signature scheme based on supersingular isogenies[C]. In:Financial Cryptography and Data Security—FC 2017. Springer Cham, 2017:163-181.[DOI:10.1007/978-3-319-70972-7_9]
[9]JAO D, SOUKHAREV V. Isogeny-based quantum-resistant undeniable signatures[C]. In:Post-Quantum Cryptography—PQCrypto 2014. Springer Cham, 2014:160-179.[DOI:10.1007/978-3-319-11659-4_10]
[10]AZARDERAKHSH R, JAO D, KALACH K, et al. Key compression for isogeny-based cryptosystems[C]. In:Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography. ACM, 2016:1-10.[DOI:10.1145/2898420.2898421]
[11]COSTELLO C, LONGA P, NAEHRIG M. Efficient algorithms for supersingular isogeny Diffie-Hellman[C]. In:Advances in Cryptology—CRYPTO 2016, Part I. Springer Berlin Heidelberg, 2016:572-601.[DOI:10.1007/978-3-662-53018-4_21]
[12]TORRES W A A, STEINFELD R, SAKZAD A, et al. Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain(Lattice RingCT v1.0)[J]. IACR Cryptology ePrint Archive, 2018:2018/379. https://eprint.iacr.org/2018/379.
[13]BAUM C, BOOTLE J, CERULLI A, et al. Sub-linear-based zero-knowledge arguments for arithmetic circuits[J].IACR Cryptology ePrint Archive, 2018:2018/560. https://eprint.iacr.org/2018/560.
[14]UNRUH D. Non-interactive zero-knowledge proofs in the quantum random oracle model[C]. In:Advances in Cryptology—EUROCRYPT 2015, Part II. Springer Berlin Heidelberg, 2015:755-784.[DOI:10.1007/978-3-662-46803-6_25]
[15]ZHANG H, ZHANG F G, TIAN H B, et al. Anonymous post-quantum cryptocash[J]. IACR Cryptology ePrint Archive, 2017:2017/716. https://eprint.iacr.org/2017/716.
[2]BOSTAN A, MORAIN F, SALVY B, et al. Fast algorithms for computing isogenies between elliptic curves[J].Mathematics of Computation, 77, 2008:1755-1778.[DOI:10.1090/S0025-5718-08-02066-8]
[3]KOHEL D. Endomorphism Rings of Elliptic Curves over Finite Fields[D].[Ph.D. Dissertation]. Berkeley, CA,USA. University of California Berkeley, 1996.
[4]BLAKE I, SEROUSSI G, SMART N. Elliptic Curves in Cryptography[M]. Cambridge University Press, UK. 1999.[DOI:10.1112/S0024609300247371]
[5]DE FEO L, JAO D, PLUT J. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[J]. Journal of Mathematical Cryptology, 2014, 8(3):209-247.[DOI:10.1515/jmc-2012-0015]
[6]SUN X, TIAN H B, WANG Y M. Toward quantum-resistant strong designated verifier signature from isogenies[C].In:2012 Fourth International Conference on Intelligent Networking and Collaborative Systems(INCoS 2012).IEEE, 2012:292-296.[DOI:10.1109/iNCoS.2012.70]
[7]GALBRAITH S D, PETIT C, SILVA J. Identification protocols and signature schemes based on supersingular isogeny problems[C]. In:Advances in Cryptology—ASIACRYPT 2017, Part I. Springer Cham, 2017:3-33.[DOI:10.1007/978-3-319-70694-8_1]
[8]YOO Y, AZARDERAKHSH R, JALALI A, et al. A post-quantum digital signature scheme based on supersingular isogenies[C]. In:Financial Cryptography and Data Security—FC 2017. Springer Cham, 2017:163-181.[DOI:10.1007/978-3-319-70972-7_9]
[9]JAO D, SOUKHAREV V. Isogeny-based quantum-resistant undeniable signatures[C]. In:Post-Quantum Cryptography—PQCrypto 2014. Springer Cham, 2014:160-179.[DOI:10.1007/978-3-319-11659-4_10]
[10]AZARDERAKHSH R, JAO D, KALACH K, et al. Key compression for isogeny-based cryptosystems[C]. In:Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography. ACM, 2016:1-10.[DOI:10.1145/2898420.2898421]
[11]COSTELLO C, LONGA P, NAEHRIG M. Efficient algorithms for supersingular isogeny Diffie-Hellman[C]. In:Advances in Cryptology—CRYPTO 2016, Part I. Springer Berlin Heidelberg, 2016:572-601.[DOI:10.1007/978-3-662-53018-4_21]
[12]TORRES W A A, STEINFELD R, SAKZAD A, et al. Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain(Lattice RingCT v1.0)[J]. IACR Cryptology ePrint Archive, 2018:2018/379. https://eprint.iacr.org/2018/379.
[13]BAUM C, BOOTLE J, CERULLI A, et al. Sub-linear-based zero-knowledge arguments for arithmetic circuits[J].IACR Cryptology ePrint Archive, 2018:2018/560. https://eprint.iacr.org/2018/560.
[14]UNRUH D. Non-interactive zero-knowledge proofs in the quantum random oracle model[C]. In:Advances in Cryptology—EUROCRYPT 2015, Part II. Springer Berlin Heidelberg, 2015:755-784.[DOI:10.1007/978-3-662-46803-6_25]
[15]ZHANG H, ZHANG F G, TIAN H B, et al. Anonymous post-quantum cryptocash[J]. IACR Cryptology ePrint Archive, 2017:2017/716. https://eprint.iacr.org/2017/716.