高级搜索

后量子对称密码的研究现状与发展趋势

眭晗 吴文玲

引用本文: 眭晗, 吴文玲. 后量子对称密码的研究现状与发展趋势[J]. 电子与信息学报, 2020, 42(2): 287-294. doi: 10.11999/JEIT190667 shu
Citation:  Han SUI, Wenling WU. Research Status and Development Trend of Post-quantum Symmetric Cryptography[J]. Journal of Electronics and Information Technology, 2020, 42(2): 287-294. doi: 10.11999/JEIT190667 shu

后量子对称密码的研究现状与发展趋势

    作者简介: 眭晗: 女,1986年生,助理研究员,研究方向为可证明安全理论、认证加密算法的设计与分析;
    吴文玲: 女,1966年生,研究员,博士生导师,主要研究方向为对称密码的设计与分析
    通讯作者: 眭晗,suihan@tca.iscas.ac.cn
  • 基金项目: 国家自然科学基金(61672509)

摘要: 经典对称密码算法的安全性在量子环境下面临严峻的挑战,促使研究者们开始探寻在经典和量子环境下均具有安全性的密码算法,后量子对称密码研究应运而生。该领域的研究目前仍处于初级阶段,尚未形成完整的体系。该文对现有的研究成果进行归类,从量子算法、密码分析方法、安全性分析、可证明安全4个方面对后量子对称密码领域的研究现状进行介绍。在分析研究现状的基础上,对后量子对称密码的发展趋势进行预测,为对称密码在量子环境下的分析和设计提供参考。

English

    1. [1]

      FEYNMAN R P. Simulating physics with computers[J]. International Journal of Theoretical Physics, 1982, 21(6/7): 467–488.

    2. [2]

      DEUTSCH D. Quantum theory, the Church-Turing principle and the universal quantum computer[J]. Proceedings of the Royal Society A Mathematical, Physical and Engineering Sciences, 1985, 400(1818): 97–117. doi: 10.1098/rspa.1985.0070

    3. [3]

      SHOR P W. Algorithms for quantum computation: Discrete logarithms and factoring[C]. The 35th Annual Symposium on Foundations of Computer Science, Santa Fe, USA, 1994: 124–134.

    4. [4]

      SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. doi: 10.1137/S0097539795293172

    5. [5]

      GROVER L K. A fast quantum mechanical algorithm for database search[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 212–219.

    6. [6]

      KUWAKADO H and MORII M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation[C]. 2010 IEEE International Symposium on Information Theory, Austin, USA, 2010: 2682–2685.

    7. [7]

      KUWAKADO H and MORII M. Security on the quantum-type Even-Mansour cipher[C]. 2012 International Symposium on Information Theory and Its Applications, Honolulu, USA, 2012: 312–316.

    8. [8]

      KAPLAN M, LEURENT G, LEVERRIER A, et al. Breaking symmetric cryptosystems using quantum period finding[J]. arXiv: 1602.05973, 2016.

    9. [9]

      SIMON D R. On the power of quantum computation[C]. The 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994: 116–123.

    10. [10]

      BRASSARD G and HOYER P. An exact quantum polynomial-time algorithm for Simon's problem[C]. The Fifth Israeli Symposium on Theory of Computing and Systems, Ramat-Gan, Israel, 1997: 12–23.

    11. [11]

      LONG Guilu. Grover algorithm with zero theoretical failure rate[J]. Physical Review A, 2001, 64(2): 022307. doi: 10.1103/PhysRevA.64.022307

    12. [12]

      TOYAMA F M, VAN DIJK W, and NOGAMI Y. Quantum search with certainty based on modified Grover algorithms: Optimum choice of parameters[J]. Quantum Information Processing, 2013, 12(5): 1897–1914. doi: 10.1007/s11128-012-0498-0

    13. [13]

      LEANDER G and MAY A. Grover meets Simon - Quantumly attacking the FX-construction[C]. Proceedings of the 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017: 161–178.

    14. [14]

      BRASSARD G, HØYER P, and TAPP A. Quantum cryptanalysis of hash and claw-free functions[C]. Theoretical Informatics: Third Latin American Symposium, Campinas, Brazil, 1998: 163–169.

    15. [15]

      AMBAINIS A. Quantum walk algorithm for element distinctness[J]. SIAM Journal on Computing, 2007, 37(1): 210–239. doi: 10.1137/S0097539705447311

    16. [16]

      AARONSON S and SHI Yaoyun. Quantum lower bounds for the collision and the element distinctness problems[J]. Journal of the ACM, 2004, 51(4): 595–605. doi: 10.1145/1008731.1008735

    17. [17]

      AMBAINIS A. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range[J]. Theory of Computing-An Open Access Electronic Journal in Theoretical Computer Science, 2005, 1(1): 37–46.

    18. [18]

      KUTIN S. Quantum lower bound for the collision problem with small range[J]. Theory of Computing-An Open Access Electronic Journal in Theoretical Computer Science, 2005, 1(1): 29–36.

    19. [19]

      YUEN H. A quantum lower bound for distinguishing random functions from random permutations[J]. Quantum Information & Computation, 2014, 14(13/14): 1089–1097.

    20. [20]

      ZHANDRY M. A note on the quantum collision and set equality problems[J]. Quantum Information & Computation, 2015, 15(7/8): 557–567.

    21. [21]

      HOSOYAMADA A, SASAKI Y, and XAGAWA K. Quantum multicollision-finding algorithm[C]. The 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017: 179–210.

    22. [22]

      LIU Qipeng and ZHANDRY M. On finding quantum multi-collisions[C]. The 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, 2019: 189–218.

    23. [23]

      GRASSL M, LANGENBERG B, ROETTELER M, et al. Applying Grover's algorithm to AES: Quantum resource estimates[J]. arXiv: 1512.04965, 2015.

    24. [24]

      FOWLER A G, DEVITT S J, and JONES C. Surface code implementation of block code state distillation[J]. Scientific Reports, 2013, 3(1): 1939. doi: 10.1038/srep01939

    25. [25]

      FOWLER A G and DEVITT S J. A bridge to lower overhead quantum computation[J]. arXiv: 1209.0510, 2012.

    26. [26]

      DEVITT S J, STEPHENS A M, MUNRO W J, et al. Requirements for fault-tolerant factoring on an atom-optics quantum computer[J]. Nature Communications, 2013, 4(1): 2524. doi: 10.1038/ncomms3524

    27. [27]

      CHAILLOUX A, NAYA-PLASENCIA M, SCHROTTENLOHER A, et al. An efficient quantum collision search algorithm and implications on symmetric cryptography[C]. The 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017: 211–240.

    28. [28]

      BERNSTEIN E and VAZIRANI U. Quantum complexity theory[C]. The 28th Annual ACM Symposium on Theory of Computing, San Diego, USA, 1993: 11–20.

    29. [29]

      LI Hongwei and YANG Li. Quantum differential cryptanalysis to the block ciphers[C]. The 6th International Conference on Applications and Techniques in Information Security, Beijing, China, 2015: 44–51.

    30. [30]

      XIE Huiqin and YANG Li. Quantum impossible differential and truncated differential cryptanalysis[J]. arXiv: 1712.06997, 2017.

    31. [31]

      XIE Huiqin and YANG Li. Using Bernstein-Vazirani algorithm to attack block ciphers[J]. Designs, Codes and Cryptography, 2019, 87(5): 1161–1182. doi: 10.1007/s10623-018-0510-5

    32. [32]

      ZHOU Qing, LU Songfeng, ZHANG Zhigang, et al. Quantum differential cryptanalysis[J]. Quantum Information Processing, 2015, 14(6): 2101–2109. doi: 10.1007/s11128-015-0983-3

    33. [33]

      KAPLAN M, LEURENT G, LEVERRIER A, et al. Quantum differential and linear cryptanalysis[J]. arXiv: 1510.05836, 2015.

    34. [34]

      CHEN Yuao and GAO Xiaoshan. Quantum algorithms for Boolean equation solving and quantum algebraic attack on cryptosystems[J]. arXiv: 1712.06239, 2017.

    35. [35]

      BONNETAIN X, NAYA-PLASENCIA M, SCHROTTENLOHER A, et al. On quantum slide attacks[R]. 2018/1067, 2018.

    36. [36]

      DONG Xiaoyang, DONG Bingyou, WANG Xiaoyun, et al. Quantum attacks on some Feistel block ciphers[R]. 2018/504, 2018.

    37. [37]

      MONTANARO A. Quantum search with advice[C]. The 5th Conference on Theory of Quantum Computation, Communication, and Cryptography, Leeds, UK, 2010: 77–93.

    38. [38]

      MARTIN D, MONTANARO A, and OSWALD E. Quantum key search with side channel advice[C]. The 24th International Conference on Selected Areas in Cryptography, Ottawa, Canada, 2017: 407–422.

    39. [39]

      DONG Xiaoyang and WANG Xiaoyun. Quantum key-recovery attack on Feistel structures[J]. Science China Information Sciences, 2018, 61(10): 102501. doi: 10.1007/s11432-017-9468-y

    40. [40]

      ITO G, HOSOYAMADA A, MATSUMOTO R, et al. Quantum chosen-ciphertext attacks against feistel ciphers[C]. The Cryptographers’ Track at the RSA Conference, San Francisco, USA, 2019: 391–411.

    41. [41]

      HOSOYAMADA A and SASAKI Y. Quantum Demiric-Selçuk meet-in-the-middle attacks: Applications to 6-round generic feistel constructions[C]. The 11th International Conference on Security and Cryptography, Amalfi, Italy, 2018: 386–403.

    42. [42]

      DONG Xiaoyang, LI Zheng, WANG Xiaoyun, et al. Quantum cryptanalysis on some generalized Feistel schemes[J]. Science China Information Sciences, 2019, 62(2): 22501. doi: 10.1007/s11432-017-9436-7

    43. [43]

      HOSOYAMADA A and AOKI K. On quantum related-key attacks on iterated Even-Mansour ciphers[C]. The 12th International Workshop on Security, Hiroshima, Japan, 2017: 3–18.

    44. [44]

      BONNETAIN X. Quantum key-recovery on full AEZ[C]. The 24th International Conference on Selected Areas in Cryptography, Ottawa, Canada, 2018: 394–406.

    45. [45]

      BONEH D, DAGDELEN Ö, FISCHLIN M, et al. Random oracles in a quantum world[C]. The 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 2011: 41–69.

    46. [46]

      ZHANDRY M. How to construct quantum random functions[C]. The 53rd Annual Symposium on Foundations of Computer Science, New Brunswick, USA, 2012: 679–687.

    47. [47]

      SONG Fang and YUN A. Quantum security of NMAC and related constructions[C]. The 37th International Cryptology Conference, Santa Barbara, USA, 2017: 283–309.

    48. [48]

      HOSOYAMADA A and YASUDA K. Building quantum-one-way functions from block ciphers: Davies-Meyer and Merkle-Damgård constructions[C]. The 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia, 2018: 275–304.

    49. [49]

      ZHANDRY M. How to record quantum queries, and applications to quantum indifferentiability[C]. The 39th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2019: 239–268.

    1. [1]

      贾艳艳, 胡予濮, 杨文峰, 高军涛. 2轮Trivium的多线性密码分析. 电子与信息学报, 2011, 33(1): 223-227.

    2. [2]

      孙瑾, 胡予濮. 双系统密码技术下的身份型广播加密方案. 电子与信息学报, 2011, 33(5): 1266-1270.

    3. [3]

      胡学先, 魏江宏, 叶茂. 对一个强安全的认证密钥交换协议的分析. 电子与信息学报, 2013, 35(9): 2278-2282.

    4. [4]

      李顺波, 胡予濮, 王艳. 针对流密码HC-256'的区分攻击. 电子与信息学报, 2012, 34(4): 807-811.

    5. [5]

      郭瑞, 金晨辉. 低轮FOX64算法的零相关-积分分析. 电子与信息学报, 2015, 37(2): 417-422.

    6. [6]

      谢天元, 李昊宇, 朱熠铭, 潘彦斌, 刘珍, 杨照民. FatSeal:一种基于格的高效签名算法. 电子与信息学报, 2020, 42(2): 333-340.

    7. [7]

      任炯炯, 李航, 陈少真. 减轮Simeck算法的积分攻击. 电子与信息学报, 2019, 41(9): 2156-2163.

    8. [8]

      罗伟, 郭建胜. Eagle-128算法的相关密钥-矩形攻击. 电子与信息学报, 2014, 36(6): 1520-1524.

    9. [9]

      郭建胜, 崔竞一, 罗伟, 刘翼鹏. MD-64算法的相关密钥-矩形攻击. 电子与信息学报, 2015, 37(12): 2845-2851.

    10. [10]

      詹英杰, 关杰, 丁林, 张中亚. 对简化版LBLock算法的相关密钥不可能差分攻击. 电子与信息学报, 2012, 34(9): 2161-2166.

    11. [11]

      孙银霞, 李晖, 李小青. 无证书体制下的多接收者签密密钥封装机制. 电子与信息学报, 2010, 32(9): 2249-2252.

    12. [12]

      孙瑾, 王小静, 王尚平, 任利利. 支持属性撤销的可验证多关键词搜索加密方案. 电子与信息学报, 2019, 41(1): 53-60.

    13. [13]

      凡如亚, 金晨辉, 崔霆. Lai-Massey结构平均差分概率和平均线性链概率的上界估计. 电子与信息学报, 2018, 40(12): 2986-2991.

    14. [14]

      张斌, 金晨辉. 基于回溯法的逆推攻击. 电子与信息学报, 2008, 30(10): 2464-2467.

    15. [15]

      李峥, 马智, 吕欣, 冯登国. 基于量子CSS纠错码的量子公钥密码和消息认证. 电子与信息学报, 2006, 28(3): 537-541.

    16. [16]

      韩立东, 刘明洁, 毕经国. 两种背包型的公钥密码算法的安全性分析. 电子与信息学报, 2010, 32(6): 1485-1488.

    17. [17]

      王念平, 金晨辉, 李云强. 一类非平衡Feistel网络的差分可证明安全性分析. 电子与信息学报, 2005, 27(6): 870-873.

    18. [18]

      张玉磊, 王欢, 马彦丽, 刘文静, 王彩芬. 可证安全的传统公钥密码-无证书公钥密码异构聚合签密方案. 电子与信息学报, 2018, 40(5): 1079-1086.

    19. [19]

      倪博煜, 董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用. 电子与信息学报, 2020, 42(2): 295-306.

    20. [20]

      王保仓, 胡予濮. 公钥密码Naccache-Stern的安全性分析. 电子与信息学报, 2007, 29(10): 2448-2450.

  • 加载中
计量
  • PDF下载量:  31
  • 文章访问数:  399
  • HTML全文浏览量:  303
文章相关
  • 通讯作者:  眭晗, suihan@tca.iscas.ac.cn
  • 收稿日期:  2019-09-02
  • 录用日期:  2019-10-18
  • 网络出版日期:  2019-11-18
  • 刊出日期:  2020-02-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章