Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (9): 2810-2817.DOI: 10.11772/j.issn.1001-9081.2023091333

• Advanced computing • Previous Articles     Next Articles

Improved KLEIN algorithm and its quantum analysis

Yanjun LI1,2, Yaodong GE2, Qi WANG2(), Weiguo ZHANG2, Chen LIU1   

  1. 1.Information Industry Information Security Evaluation Center,The 15th Research Institute of China Electronics Technology Group Corporation,Beijing 100083,China
    2.Department of Cryptographic Science and Technology,Beijing Electronic Science and Technology Institute,Beijing 100070,China
  • Received:2023-09-27 Revised:2023-11-16 Accepted:2023-11-20 Online:2023-12-01 Published:2024-09-10
  • Contact: Qi WANG
  • About author:LI Yanjun, born in 1979, Ph. D., associate professor. Her research interests include cryptographic analysis and evaluation.
    GE Yaodong, born in 1997, M. S. candidate. His research interests include block ciphers based on quantum model.
    ZHANG Weiguo, born in 1998, M. S. candidate. His research interests include finite fields, S-box.
    LIU Chen, born in 1990, M. S. candidate. His research interests include cryptographic evaluation.
  • Supported by:
    Beijing Natural Science Foundation(4234084);Research Project of Henan Key Laboratory of Network Cryptography Technology(LNCT2021-A09)

改进的KLEIN算法及其量子分析

李艳俊1,2, 葛耀东2, 王琦2(), 张伟国2, 刘琛1   

  1. 1.中国电子科技集团公司第十五研究所 信息产业信息安全测评中心, 北京 100083
    2.北京电子科技学院 密码科学与技术系, 北京 100070
  • 通讯作者: 王琦
  • 作者简介:李艳俊(1979—),女,山西阳城人,副教授,博士,主要研究方向:密码分析与测评
    葛耀东(1997—),男,河北邯郸人,硕士研究生,主要研究方向:基于量子模型的分组密码
    张伟国(1998—),男,陕西渭南人,硕士研究生,主要研究方向:有限域、S盒
    刘琛(1990—),男,河北昌黎人,硕士研究生,主要研究方向:密码测评。
  • 基金资助:
    北京市自然科学基金资助项目(4234084);河南省网络密码技术重点实验室研究课题(LNCT2021-A09)

Abstract:

KLEIN has experienced attacks such as truncated difference cryptanalysis and integral cryptanalysis since it was proposed. Its encryption structure has actual security, but the vulnerability of the key expansion algorithm leads to full-round key recovery attacks. Firstly, the key expansion algorithm was modified and an improved algorithm N-KLEIN was proposed. Secondly, an efficient quantum circuit was implemented on the S-box using the in-place method, which reduced the width and depth of the circuit and improved the implementation efficiency of the quantum circuit. Thirdly, the quantization of obfuscation operations was achieved using LUP decomposition technology. Then, an efficient quantum circuit was designed for N-KLEIN, and an efficient quantum circuit for all round N-KLEIN was proposed. Finally, the resource occupation for the quantum implementation of full-round N-KLEIN was evaluated and compared with the resources occupied by existing quantum implementations of lightweight block ciphers such as PRESENT and HIGHT. At the same time, an in-depth study was conducted on the cost of key search attacks based on Grover algorithm, and the cost of N-KLEIN-{64,80,96} using Grover algorithm to search for keys under the Clifford+T model was given, and then the quantum security of N-KLEIN was evaluated. Comparative results indicate that the quantum implementation cost of N-KLEIN algorithm is significantly lower.

Key words: lightweight block cipher, KLEIN, quantum circuit, S-box, Grover algorithm

摘要:

KLEIN自提出之后经历了截断差分分析、积分分析等攻击,加密结构具有实际安全性,但是由于密钥扩展算法的脆弱性导致了全轮密钥恢复攻击。首先,修改密钥扩展算法,提出一种改进后的算法N-KLEIN;其次,采用in-place方法对S盒进行高效量子电路实现,减小了电路的宽度和深度,提高了量子电路的实现效率;再次,使用LUP分解技术实现混淆操作的量子化;继次,对N-KLEIN进行量子电路设计,提出全轮N-KLEIN的高效量子电路。最后,评估N-KLEIN算法量子实现的资源占用,并与PRESENT、HIGHT等现有的轻量级分组密码的量子实现占用资源进行对比;同时,基于Grover算法对密钥搜索攻击所需要的代价进行深入研究,给出Clifford+T模型下N-KLEIN-{64,80,96}使用Grover算法搜索密钥需要的代价,并评估了N-KLEIN的量子安全性。对比结果表明,N-KLEIN算法量子实现的成本明显较低。

关键词: 轻量级分组密码, KLEIN, 量子电路, S盒, Grover算法

CLC Number: