Identification Scheme Based on Supersingular Isogenies
LIN Qi-Ping1,2, GAO Sheng1,2
1. Data Communication Science and Technology Research Institute, Beijing 100191, China
2. Xingtang Telecommunications Technology Co. Ltd., Beijing 100191, China
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 Pl\^{u}t'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 zero-knowledge proof, post-quantum cryptography algorithms need to be used. Compared with other post-quantum 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 Pl\^{u}t's scheme. However, the zero-knowledge proof constructed by De Feo, Jao, and Pl\^{u}t'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 Pl\^{u}t's scheme to get 2 bit security in each round of the interactive proof.
林齐平 高胜. 基于超奇异同源的鉴别方案[J]. 密码学报, 2018, 5(5): 510-515.
LIN Q P, GAO S. Identification Scheme Based on Supersingular Isogenies. Journal of Cryptologic Research, 2018, 5(5): 510-515.
\bibitem{1}V\'{E}LU J. Isog\'{e}nies entre courbes elliptiques[J]. C. R. Acad. Sc. Paris, S\'{e}rie A., 273, 1971: 238–241.
\bibitem{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]
\bibitem{3}KOHEL D. Endomorphism Rings of Elliptic Curves over Finite Fields[D]. [Ph.D. Dissertation]. Berkeley, CA, USA. University of California Berkeley, 1996.
\bibitem{4}BLAKE I, SEROUSSI G, SMART N. Elliptic Curves in Cryptography[M]. Cambridge University Press, UK. 1999. [DOI: 10.1112/S0024609300247371]
\bibitem{5}DE FEO L, JAO D, PL\^{U}T 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]
\bibitem{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]
\bibitem{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]
\bibitem{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]
\bibitem{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]
\bibitem{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]
\bibitem{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.
\bibitem{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.
\bibitem{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]
\bibitem{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.
2018, Vol. 5 
