高级搜索

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

眭晗 吴文玲

引用本文: 眭晗, 吴文玲. 后量子对称密码的研究现状与发展趋势[J]. 电子与信息学报, 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, 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]. 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 Twenty-Eighth 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]. 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]. 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]. 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]

      ZOU Jian, DONG Le, Liu Ximeng, et al. An efficient quantum multi-collision search algorithm[J]. Engineering & Technology, 2019.

    29. [29]

      BERNSTEIN E and VAZIRANI U. Quantum complexity theory[C]. Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, 1993: 11–20.

    30. [30]

      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, 2015: 44–51.

    31. [31]

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

    32. [32]

      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

    33. [33]

      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

    34. [34]

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

    35. [35]

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

    36. [36]

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

    37. [37]

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

    38. [38]

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

    39. [39]

      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, 2017: 407–422.

    40. [40]

      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

    41. [41]

      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, 2019: 391–411.

    42. [42]

      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, 2018: 386–403.

    43. [43]

      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

    44. [44]

      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.

    45. [45]

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

    46. [46]

      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.

    47. [47]

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

    48. [48]

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

    49. [49]

      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, 2018: 275–304.

    50. [50]

      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, 2019: 239–268.

    1. [1]

      任炯炯, 李航, 陈少真. 减轮Simeck算法的积分攻击. 电子与信息学报,

    2. [2]

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

    3. [3]

      谢敏, 曾琦雅. 轻量级分组密码算法ESF的相关密钥不可能差分分析. 电子与信息学报,

    4. [4]

      韦永壮, 史佳利, 李灵琛. LiCi分组密码算法的不可能差分分析. 电子与信息学报,

    5. [5]

      赵军, 曾学文, 郭志川. 支持国产密码算法的高速PCIe密码卡的设计与实现. 电子与信息学报,

    6. [6]

      戴紫彬, 尹安琪, 曲彤洲, 南龙梅. 面向众核密码处理器的高效负载均衡技术. 电子与信息学报,

    7. [7]

      牛淑芬, 杨喜艳, 王彩芬, 田苗, 杜小妮. 基于异构密码系统的混合群组签密方案. 电子与信息学报,

    8. [8]

      王彩芬, 许钦百, 刘超, 成玉丹, 赵冰. 无证书公钥密码体制→传统公钥基础设施异构环境下部分盲签密方案. 电子与信息学报,

    9. [9]

      逯志宇, 王建辉, 秦天柱, 巴斌. 基于对称旋转不变性的非圆相干分布源直接定位算法. 电子与信息学报,

    10. [10]

      赵建, 高海英, 胡斌. 基于容错学习的属性基加密方案的具体安全性分析. 电子与信息学报,

    11. [11]

      曹素珍, 郎晓丽, 刘祥震, 张玉磊, 王彩芬. 一种可证安全的PKI和IBC双向匿名异构签密方案的改进. 电子与信息学报,

    12. [12]

      杨小东, 麻婷春, 陈春霖, 王晋利, 王彩芬. 面向车载自组网的无证书聚合签名方案的安全性分析与改进. 电子与信息学报,

    13. [13]

      张玉磊, 刘祥震, 郎晓丽, 张永洁, 王彩芬. 一种异构混合群组签密方案的安全性分析与改进. 电子与信息学报,

    14. [14]

      刘彩霞, 胡鑫鑫, 刘树新, 游伟, 赵宇. 基于Lowe分类法的5G网络EAP-AKA$ ' $协议安全性分析. 电子与信息学报,

    15. [15]

      沈璇, 孙兵, 刘国强, 李超. 数字视频广播通用加扰算法的不可能差分分析. 电子与信息学报,

    16. [16]

      严迎建, 刘敏, 邱钊洋. 一种面向粗粒度可重构阵列的硬件木马检测算法的设计与实现. 电子与信息学报,

    17. [17]

      刘仁争, 田康生, 彭富强, 李浩. 基于非对称贴近度的预警雷达情报质量评估. 电子与信息学报,

    18. [18]

      杨若男, 张伟涛, 楼顺天. 基于平行因子分析的SIMO-OFDM系统盲信道与符号联合估计算法. 电子与信息学报,

    19. [19]

      寇广, 王硕, 张达. 基于深度堆栈编码器和反向传播算法的网络安全态势要素识别. 电子与信息学报,

    20. [20]

      叶磊, 王勇, 杨强, 邓维波. 基于对数行列式散度与对称对数行列式散度的高频地波雷达目标检测器. 电子与信息学报,

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

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

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

/

返回文章