抗量子密码体制发展研究
Development Analysis of Post Quantum Cryptography
摘要: 量子计算的快速发展带给经典密码的巨大冲击使得人们将目光投向了抗量子密码体制的研究。随着量子时代的迫近，抗量子密码体制的研究步伐也在不断加快。本文回顾了以多变量公钥密码体制、基于Hash函数的数字签名、基于编码的密码体制和基于格的密码四类抗量子密码的发展历程，并结合迄今为止的八届国际抗量子密码年会展示了抗量子密码体制的最新进展。这些对今后抗量子密码的研究具有重要的参考价值。
Abstract: Since the rapid development of quantum computing brings great impacts to classical cryptography, people set their sights on the research of post quantum cryptography. Along with the approach of the quantum era, the pace of research on post quantum cryptography is accelerating. This paper reviews the development of four types of post quantum cryptography, which are multivariate public key cryptography, Hash-based digital signature, code-based cryptography and lattice-based cryptography. And then the latest progress of post quantum cryptography is presented based on all the eight International Workshops on Post-Quantum Cryptography. These are of great value as reference for future research on quantum cryptography.
文章引用：李强, 程庆丰, 李宏欣, 张军琪. 抗量子密码体制发展研究[J]. 计算机科学与应用, 2017, 7(11): 1089-1100. https://doi.org/10.12677/CSA.2017.711123

参考文献

[1] Shor, P.W. (1999) Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Siam Review, 41, 303-332.
https://doi.org/10.1137/S0036144598347011
[2] Chen, L., Liu, Y.-K., Jordan, S., Moody, D., Peralta, R., Perlner, R. and Smith-Tone, D. (2016) Report on Post-Quantum Cryptography. NISTIR 8105, Draft.
https://doi.org/10.6028/NIST.IR.8105
[3] Bernstein, D.J., Buchmann, J. 抗量子计算密码[M]. 北京: 清华大学出版社, 2015.
[4] Matsumoto, T. and Imai, H. (1988) Public Quadratic Polynomial-Tuples for Efficient Signature Verification and Message-Encryption. Advances in Cryptology—EUROCRYPT’1988, 419-545.
[5] 管海明. 有理分式公钥密码体制[C]//第五届中国信息和通信安全学术会议论文集, 2007.
[6] 王后珍, 张焕国, 王张宜, 等. 一类具有安全加密功能的扩展MQ公钥密码体制[J]. 中国科学: 信息科学, 2011, 41(11): 1297-1309.
[7] Merkle, R.C. (1989) A Certified Digital Signature. Advances in Cryptology—CRYPTO’89 Proceedings, LNCS 435, Springer, Berlin, 218-238.
[8] Mceliece, R J. (1978) A Public-Key Cryptosystem Based on Algebraic Coding Theory. Deep Space Network Progress Report, 114-116.
[9] 王新梅, 李元兴. McEliece公钥体制的修正[J]. 电子学报, 1994(4): 90-92.
[10] Xinmei, W. (1990) Digital Signature Scheme Based on Error-Correcting Codes. Electronics Letters, 26, 898-899.
https://doi.org/10.1049/el:19900586
[11] 李元兴, 成坚, 王新梅. 一种基于代数编码理论的签名, 加密和纠错公钥体制[J]. 电子与信息学报, 1991, 13(4): 359-364.
[12] Hoffstein, J., Pipher, J. and Silverman, J.H. (1996) NTRU: A High Speed Public Key Cryptosystem. PrePrint Presented at He Hump Session of Euro Crypt 96.
[13] Stern, J. (2006) Post-Quantum Multivariate-Quadratic Public Key Schemes. In: International Workshop on Post-Quantum Cryptography, Springer-Verlag, 25-26.
[14] Gouget, A. and Patarin, J. (2006) Probabilistic Multivariate Cryptography. In: International Conference on Cryptology in Vietnam. Springer-Verlag, 1-18.
[15] Ding, J., Wolf, C. and Yang, B.Y. (2007) Invertible Cycles for Multivariate Quadratic (MQ) Public Key Cryptography. In: International Conference on Practice and Theory in Public-Key Cryptography, Springer-Verlag, 266-281.
[16] Wolf, C. and Preneel, B. (2011) Equivalent Keys in Multivariate Quadratic Public Key Systems. Journal of Mathematical Cryptology, 2005, 375-415.
[17] Chen, I.T., Chen, C.H.O., Chen, M.S., et al. (2008) Practical-Sized Instances of Multivariate PKCs: Rainbow, TTS, and ℓIC-Derivatives. In: Post-Quantum Cryptography, Springer Berlin Heidelberg, 95-108.
[18] Ding, J., Hu, L., Nie, X., et al. (2007) High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems. In: International Workshop on Public Key Cryptography, Springer, Berlin, Heidelberg, 233-248.
[19] Chia-Hsin, C., Bo-Yin, Y. and Jiun-Ming, C. (2006) The Limit of XL Implemented with Sparse Matrices. In: International Conference on Cryptology in Vietnam, Springer-Verlag, 215-225.
[20] Ding, J., Gower, J.E. and Schmidt, D. (2006) Zhuang-Zi: A New Algorithm for Solving Multivariate Polynomial Equations over a Finite Field. Iacr Cryptology Eprint Archive.
[21] Ding, J. and Wagner, J. (2007) Cryptanalysis of Rational Multivariate Public Key Cryptosystems. Vol. 5299, 124-136.
[22] Mohamed, M.S.E., Mohamed, W.S.A.E., Ding, J., et al. (2008) MXL2: Solving Polynomial Equations over GF(2) using an Improved Mutant Strategy. In: Post-Quantum Cryptography, Springer Berlin Heidelberg, 203-215.
[23] Clough, C.L. and Ding, J. (2010) Secure Variants of the Square Encryption Scheme. In: International Conference on Post-Quantum Cryptography, Springer-Verlag, 153-164.
[24] Tsujii, S., Gotaishi, M., Tadaki, K., et al. (2010) Proposal of a Signature Scheme Based on STS Trapdoor. In: Post-Quantum Cryptography, Springer Berlin Heidelberg, 201-217.
https://doi.org/10.1007/978-3-642-12929-2_15
[25] Cheng, C.M., Hashimoto, Y., Miura, H., et al. (2014) A Polynomial-Time Algorithm for Solving a Class of Underdetermined Multivariate Quadratic Equations over Fields of Odd Characteristics. In: Post-Quantum Cryptography, Springer International Publishing, 40-58.
[26] Daniels, T. and Smith-Tone, D. (2014) Differential Properties of the HFE Cryptosystem. In: Post-Quantum Cryptography, Springer International Publishing, 59-75.
[27] Porras, J., Baena, J. and Ding, J. (2014) ZHFE, a New Multivariate Public Key Encryption Scheme. In: Post-Quantum Cryptography, 229-245.
https://doi.org/10.1007/978-3-319-11659-4_14
[28] Perlner, R. and Smith-Tone, D. (2016) Security Analysis and Key Modification for ZHFE. In: Post-Quantum Cryptography, Springer International Publishing.
[29] Petzoldt, A., Chen, M.S., Ding, J., et al. (2017) HMFEv—An Efficient Multivariate Signature Scheme. In: Post-Quantum Cryptography.
https://doi.org/10.1007/978-3-319-59879-6_12
[30] Yasuda, T., Takagi, T. and Sakurai, K. (2013) Multivariate Signature Scheme using Quadratic Forms. In: Post-Quantum Cryptography, Springer Berlin Heidelberg, 243-258.
https://doi.org/10.1007/978-3-642-38616-9_17
[31] Buchmann, J., Dahmen, E. and Schneider, M. (2008) Merkle Tree Traversal Revisited. 2nd International Workshop on Post-Quantum Cryptography, Cincinnati, 17-19 October 2008, 63-78.
[32] Dahmen, E., Takagi, T., Takagi, T., et al. (2008) Digital Signatures Out of Second-Preimage Resistant Hash Functions. International Workshop on Post-Quantum Cryptography, Springer-Verlag, 109-123.
[33] Buchmann, J., Dahmen, E. and Hülsing, A. (2011) XMSS—A Practical forward Secure Signature Scheme Based on Minimal Security Assumptions. Post-Quantum Cryptography, Taipei, 29 November-2 December 2011, 17-129.
[34] Targhi, E.E., Tabia, G.N. and Unruh, D. (2016) Quantum Collision-Resistance of Non-Uniformly Distributed Functions. In: International Workshop on Post-Quantum Cryptography, Springer-Verlag, New York, 79-85.
[35] Bernstein, D.J., Lange, T. and Peters, C. (2008) Attacking and Defending the McEliece Cryptosystem. In: Post-Quantum Cryptography, Springer Berlin Heidelberg, 31-46.
https://doi.org/10.1007/978-3-540-88403-3_3
[36] Biswas, B. and Sendrier, N. (2008) McEliece Cryptosystem Implementation: Theory and Practice. In: International Workshop on Post-Quantum Cryptography, Springer-Verlag, 47-62.
[37] Heyse, S. (2011) Implementation of McEliece Based on Quasi-Dyadic Goppa Codes for Embedded Devices. International Workshop Post-Quantum Cryptography, Taipei, 29 November-2 December 2011, 143-162.
[38] Bernstein, D.J. (2010) Grover vs. McEliece. In: International Conference on Post-Quantum Cryptography, Springer-Verlag, 73-80.
[39] Peters, C. (2002) Information-Set Decoding for Linear Codes over F, q. Introduction to Statistics for the Behavioral Sciences. Saunders, 3759-3763.
[40] Strenzke, F. (2010) A Timing Attack against the Secret Permutation in the McEliece PKC. Vol. 6061, 95-107.
[41] Heyse, S., Moradi, A. and Paar, C. (2010) Practical Power Analysis Attacks on Software Implementations of McEliece. In: 3rd International Workshop Post-Quantum Cryptography, Darmstadt, 25-28 May 2010, 108-125.
[42] Sendrier, N. (2011) Decoding One Out of Many.
[43] Landais, G. and Tillich, J.P. (2013) An Efficient Attack of a McEliece Cryptosystem Variant Based on Convolutional Codes. In: International Workshop on Post-Quantum Cryptography, Springer Berlin Heidelberg, 102-117.
[44] Phesso, A. and Tillich, J.P. (2016) An Efficient Attack on a Code-Based Signature Scheme. In: Post-Quantum Cryptography, Springer International Publishing.
[45] Aguilar Melchor, C., Cayrel, P., Gaborit, P., et al. (2008) A New Efficient Threshold Ring Signature Scheme Based on Coding Theory. In: International Workshop on Post-Quantum Cryptography, Springer Berlin Heidelberg, 1-16.
[46] Barreto, P.S.L.M., Lindner, R. and Misoczki, R. (2011) Monoidic Codes in Cryptography. In: International Conference on Post-Quantum Cryptography, Springer-Verlag, 179-199.
[47] Gaborit, P., Ruatta, O., Schrek, J., et al. (2014) Rank Sign: An Efficient Signature Algorithm Based on the Rank Metric. Vol. 8772, 88-107.
[48] Hoffstein, J., Howgrave-Graham, N., Pipher, J., et al. (2006) NTRUEncrypt and NTRUSign: Efficient Public Key Algorithms for a Post-Quantum World. Proceedings of the International Workshop on Post-Quantum Cryptography, 71-77.
[49] Buchmann, J., Lindner, R. and Rückert, M. (2008) Explicit Hard Instances of the Shortest Vector Problem. In: International Workshop on Post-Quantum Cryptography, Springer-Verlag, 79-94.
[50] Rückert, M. (2010) Strongly Unforgeable Signatures and Hierarchical Identity-Based Signatures from Lattices without Random Oracles. In: Post-Quantum Cryptography, Springer Berlin Heidelberg, 182-200.
https://doi.org/10.1007/978-3-642-12929-2_14
[51] Bettaieb, S. and Schrek, J. (2013) Improved Lattice-Based Threshold Ring Signature Scheme. In: International Workshop on Post-Quantum Cryptography, Springer Berlin Heidelberg, 34-51.
[52] Bouillaguet, C., Delaplace, C., Fouque, P.A., et al. (2017) Fast Lattice-Based Encryption: Stretching Spring. In: Post-Quantum Cryptography.
[53] Laarhoven, T., Mosca, M. and Pol, J.V.D. (2013) Solving the Shortest Vector Problem in Lattices Faster using Quantum Search. In: International Workshop on Post-Quantum Cryptography, Springer, Berlin, Heidelberg, 83-101.
[54] Gong, B. and Zhao, Y. (2017) Cryptanalysis of RLWE-Based One-Pass Authenticated Key Exchange. In: International Workshop on Post-Quantum Cryptography, Springer, Cham, 163-183.
[55] Göpfert, F., Vredendaal, C.V. and Wunderer, T. (2017) A Hybrid Lattice Basis Reduction and Quantum Search Attack on LWE. In: International Workshop on Post-Quantum Cryptography, Springer, Cham, 184-202.
[56] Kashefia, E. and Kerenidisc, I. (2012) Statistical Zero Knowledge and Quantum One-Way Functions. Theoretical Computer Science, 378, 101-116.
https://doi.org/10.1016/j.tcs.2007.03.013
[57] Mosca, M., Stebila, D. and Ustaoğlu, B. (2012) Quantum Key Distribution in the Classical Authenticated Key Exchange Framework. International Journal of Urban & Regional Research, 7932, 136-154.
[58] Jao, D. and Soukharev, V. (2014) Isogeny-Based Quantum-Resistant Undeniable Signatures. In: Post-Quantum Cryptography, Springer International Publishing, 160-179.
[59] Gélin, A. and Wesolowski, B. (2017) Loop-Abort Faults on Supersingular Isogeny Cryptosystems. In: Post-Quantum Cryptography.
https://doi.org/10.1007/978-3-319-59879-6_6
[60] Yan, B.T. (2017) Fault Attack on Supersingular Isogeny Cryptosystems. In: International Workshop on Post-Quantum Cryptography, Springer, Cham, 107-122.