公钥密码的实际安全性发展研究

摘要/Abstract

摘要： 公钥密码是网络时代的重要原语，是保护网络空间中的数据和通信的重要工具.目前，公钥密码的三大类基础算法：公钥加密、数字签名、密钥交换，在各类数据系统和网络协议中被广泛使用.介绍了这3类基础公钥密码算法的定义和安全性概念，尤其是安全性概念从理论到实际应用的发展；着重介绍了一些具有代表性的方案，例如RSA加密和RSA签名这种具有里程碑意义的方案；CramerShoup混合加密这种高效实用的方案；RSAOAEP，NTRU，DSA这种被标准化的方案；以及Kyber，Frodo这种具有潜力的后量子安全方案，以期对该领域的研究者有所帮助.

关键词: 公钥密码学, 公钥加密, 数字签名, 密钥交换, 可证明安全

Abstract: Public key cryptography is an important primitive in the era of internet, and also is an important tool for protecting the data and communication in cyberspace. Currently, the three basic public key cryptographic algorithms, namely, public key encryption, digital signature and key exchange, are extensively used in various kinds of data systems and network protocols. In this paper, we introduce the definitions and security notions of the three basic public key cryptographic algorithms, especially the development of security notions from theory to practice; we also introduce several representative public key cryptosystems, for example, schemes which are considered as milestones, such as RSA encryption and RSA signature; efficient and practical schemes, such as the CramerShoup hybrid encryption scheme; standardized schemes, such as RSAOAEP, NTRU, DSA; and promising schemes with postquantum security, such as Kyber and Frodo. We hope that the paper will benefit the researchers in the area of public key cryptology.

Key words: public key cryptology, public key encryption, digital signature, key exchange, provable security

刘亚敏薛海洋张道德. 公钥密码的实际安全性发展研究[J]. 信息安全研究, 2019, 5(1): 29-38.

参考文献

[1] Diffie W, Hellman M E. New directions in cryptography [J]. IEEE Trans on Information Theory, 1976, 22(6):644–654 [2] Goldwasser S, Micali S. Probabilistic encryption [J]. Special issue of Journal of Computer and Systems Sciences, 1984, 28(2):270-299 [3] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring [C] //Proc of FOCS 1994. Piscataway, NJ: IEEE, 1994:124-134 [4] Ajtai A. Generating hard instances of lattice problems [C] //Proc of STOC 1996. New York: ACM, 1996:99-108 [5] Berlekamp, McEliece R, and van Tilborg H. On the inherent intractability of certain coding problems [J]. IEEE Trans on Information Theory, 1978, 24(3):384-386 [6] Merkle R C. Secrecy, authentication, and public key systems [D]. Electrical Engineering, Palo Alto: Stanford, 1979 [7] Patarin J. Hidden field equations (hfe) and isomorphisms of polynomials (ip): two new families of asymmetric algorithms [G] // LNCS 1070: Proc of Eurocrypt 1996. Berlin: Springer, 1996:33-48 [8] Feo L D, Jao D, and Plût J. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies [J]. Journal of Mathematical Cryptology, 2014, 8(3):209-247 [9] Rivest R L, Shamir A, Adleman L M. A method for obtaining digital signatures and public-key cryptosystems [J]. Communications of the ACM, 1978, 21(2):120-126 [10] 毛文波. 现代密码学理论与实践 [M]. 北京:电子工业出版社, 2004 [11] Rabin M.O. Digitalized signatures and public-key functions as intractable as factorization [R]. Cambridge: MIT Press, 1979 [12] El Gamal T. A public key cryptosystem and a signature scheme based on discrete logarithms [G] // LNCS 196: Proc of CRYPTO 1984. Berlin: Springer, 1984:10-18 [13] Regev O. On lattices, learning with errors, random linear codes, and cryptography [C] // Proc of STOC 2005. New York: ACM, 2005:84-93 [14] Naor M, Yung M. Public-key cryptosystems provably secure against chosen ciphertext attacks [C] // Proc of STOC 1990. New York: ACM, 1990:427-437 [15] Rackoff C, Simon D R. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack [G] // LNCS 576: Proc of CRYPTO 1991. Berlin: Springer, 1991:433-444 [16] Bleichenbacher D. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 [G] // LNCS 1462: Proc of CRYPTO 1998. Berlin:Springer, 1998:1-12 [17] Bellare M, Rogaway P. Optimal asymmetric encryption: how to encrypt with RSA [G] // LNCS 950: Proc of EUROCRYPT 1994. Berlin: Springer, 1995:92-111 [18] Bellare M, Rogaway P. Random oracles are practical:A paradigm for designing efficient protocols [C] // Proc of ACM CCS 1993. New York: ACM, 1993:62-73 [19] Hoffstein J, Pipher J, Silverman J H. NTRU: A new high speed public key cryptosystem [G] // LNCS 1423: Proc of Algorithmic Number Theory (ANTS III). Berlin: Springer, 1998:267-288 [20] Chen Cong, Hoffstein J, Whyte W, et al. NIST PQ Submission: NTRUEncrypt - A lattice based encryption algorithm [EB/OL]. (2017-11-30)[2018-10-30]. https://www.onboardsecurity.com/nist-post-quantum-crypto-submission [21] Cramer R, Shoup V. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack [G] // LNCS 1462: Proc of CRYPTO 1998. Berlin: Springer, 1998:13-25 [22] Bos J W, Ducas L, Kiltz E, et al. Crystals-kyber:A cca-secure module-lattice-based kem [EB/OL]. 2017[2018-10-30]. IACR Cryptology ePrint Archive 2017, 634（网址，一校时再说） [23] Bos J W, Costello C, Ducas L, et al. Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE [C] // Proc of ACM CCS 2016. New York: ACM, 2016: 1006-1018 [24] Zhao Yunlei, Jin Zhengzhong, Gong Boru,et al. KCL: Key Consensus from Lattice [EB/OL]. 2017[2018-10-30]. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions [25] Yu Yu, Zhang Jiang. Lepton: LPN-based KEMs with Post-Quantum Security [EB/OL]. 2017[2018-10-30]. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions [26] Lu Xianhui, Liu Yamin, Jia Dinging, et al. LAC [EB/OL]. 2017[2018-10-30]. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions [27] Fiat A, Shamir A. How to prove yourself: practical solutions to identification and signature problems [G] // LNCS 263: Proc of CRYPTO 1986.Berlin: Springer, 1986:186-194 [28] Schnorr C. Efficient identification and signatures for smart cards [G] // LNCS 435: Proc of CRYPTO 1989. Berlin: Springer, 1989:239-252 [29] Goldwasser S, Micali S, Rivest R L. A digital signature scheme secure against adaptive chosen-message attacks [J]. SIAM Journal of Computing, 1988, 17(2):281-308 [30] Bellare M, Rogaway P. The exact security of digital signatures — How to sign with RSA and Rabin [G] // LNCS 1070: Proc of EUROCRYPT 1996. Berlin: Springer, 1996:399–416 [31] Coron J. On the exact security of full domain hash [G] // LNCS 1880: Proc of CRYPTO 2000. Berlin: Springer, 2000:229-235 [32] Pointcheval D, Stern J. Security proofs for signature schemes [G] // LNCS 1070: Proc of EUROCRYPT 1996. Berlin: Springer, 1996:387–398 [33] Seurin Y. On the exact security of Schnorr-type signatures in the random oracle model [G] // LNCS 7237: Proc of EUROCRYPT 2012. Berlin: Springer, 2012:554–571, 2012 [34] Lamport L. Constructing digital signatures from a one-way function, CSL-98 [R]. Menlo Park: SRI International, 1978 [35] Naor M, Yung M. Universal one-way hash functions and their cryptographic applications [C] // Proc of STOC 1989. New York: ACM, 1989:33–43 [36] Rompel J. One-way functions are necessary and sufficient for secure signatures [C] // Proc of STOC 1990. New York: ACM, 1990:387–394 [37] Merkle R C. A certified digital signature [G] // LNCS 435: Proc of CRYPTO 1989. Berlin: Springer, 1989:218–238 [38] Diffie W, van Oorschot P, Wiener M, Authentication and authenticated key exchanges [J]. Designs, Codes and Cryptography, 1992(2):107–125 [39] Matsumoto T, Takashima Y, Imai H. On seeking smart public-key distribution systems [J]. Trans on IECE of Japan, 1986, E69(2):99-106 [40] Law L, Menezes A, Qu M, et al. An efficient protocol for authenticated key agreement [J]. Designs, Codes and Cryptography, 2003(28):119-134 [41] Krawczyk H. HMQV: A high-performance secure Diffie-Hellman protocol [G] // LNCS 3621: Proc of CRYPTO 2005. Berlin: Springer, 2005:546-566 [42] Yao Andrew Chi-Chih, Zhao Yunlei. OAKE: A new family of implicitly authenticated Diffie-Hellman protocols [C] // Proc ACM CCS 2013. New York: ACM, 2013:1113-1128 [43] Bellare M, Rogaway P. Entity authentication and key distribution [G] // LNCS 773: Proc of CRYPTO 1993. Berlin: Springer, 1993:273-289 [44] Canetti R, Krawczyk H. Security analysis of IKEs signature-based key-exchange protocol [G] // LNCS 2442: Proc of CRYPTO 2002. Berlin: Springer, 2002:143–161 [45] Lamacchia B, Lauter K, Mityagin A, Stronger security of authenticated key exchange [G] // LNCS 4784, Proc of ProvSec 2006. Berlin: Springer, 2006:1-16 [46] Fujioka A, Koutarou S, Xagawa K, et al. Strongly secure authenticated key exchange from factoring, codes, and lattices [G] // LNCS 7293: Proc of PKC 2012. Berlin: Springer, 2012: 467–484 [47] Peikert C. Lattice cryptography for the internet [G] // LNCS 8772: Proc of PQCrypto 2014. Berlin: Springer, 2014:197-219 [48] Stebila D, Mosca M. Post-quantum key exchange for the internet and the open quantum safe project [EB/OL]. 2016[2018-10-30]. http://eprint.iacr.org/2016/1017 [49] Ding Jintai, Xie Xiang, Lin Xiaodong. A simple provably secure key exchange scheme based on the learning with errors problem [EB/OL]. 2012[2018-10-30]. Cryptology ePrint Archive, Report 2012/688 [50] Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange - a new hope [C] // Proc of USENIX Security 2016. Berkeley: USENIX, 2016: 327-343 [51] Alkim E, Ducas L, Pöppelmann T, et al. Newhope without reconciliation [EB/OL]. 2016[2018-10-30]. http://eprint.iacr.org/2016/1157 [52] Zhang Jiang, Zhang Zhenfeng, Ding Jintai, et al. Authenticated key exchange from ideal lattices [G] // LNCS 9057: Proc of EUROCRYPT 2015, Part II. Berlin: Springer, 2015:719-751 [53] Bellovin M, Merritt M. Encrypted key exchange: Password-based protocols secure against dictionary attacks [C] // Proc of SP 1992. Piscataway, NJ: IEEE, 1992:72-84 [54] Boyko V, MacKenzie P, Patel S. Provably secure password authenticated key exchange using Diffie-Hellman [G] // LNCS 1807: EUROCRYPT 2000. Berlin: Springer, 2000:156-171 [55] Abdalla M, Pointcheval D. Simple password-based encrypted key exchange protocols [G] // LNCS 3376: Proc of CT-RSA 2005. Berlin: Springer, 2005:191-208 [56] Goldreich O, Lindell Y. Session-key generation using human passwords only [G] // LNCS 2139: Proc of CRYPTO 2001. Berlin: Springer, 2001:408-432 [57] Katz J, Ostrovsky R, Yung M. Effcient password-authenticated key exchange using human-memorable passwords[G] // LNCS 2045, Proc of EUROCRYPT 2001. Berlin: Springer, 2001:475-494 [58] Gennaro R, Lindell Y. A framework for password-based authenticated key exchange [G] // LNCS 2656: Proc of EUROCRYPT 2003. Berlin: Springer, 2003:524-543 [59] Jiang Shaoquan, Gong Guang. Password based key exchange with mutual authentication[G] // LNCS 3357: Proc of SAC 2004. Berlin: Springer, 2004:267-279 [60] Groce A, Katz J. A new framework for effcient password-based authenticated key exchange [C]//Proc of ACM CCS 2010. New York: ACM, 2010:516-525