Improved KLEIN algorithm and its quantum analysis

doi:10.11772/j.issn.1001-9081.2023091333

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 LI¹^,², Yaodong GE², Qi WANG²(), Weiguo ZHANG², Chen LIU¹

^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.中国电子科技集团公司第十五研究所信息产业信息安全测评中心, 北京 100083
^2.北京电子科技学院密码科学与技术系, 北京 100070

通讯作者: 王琦
作者简介:李艳俊（1979—），女，山西阳城人，副教授，博士，主要研究方向：密码分析与测评
葛耀东（1997—），男，河北邯郸人，硕士研究生，主要研究方向：基于量子模型的分组密码
张伟国（1998—），男，陕西渭南人，硕士研究生，主要研究方向：有限域、S盒
刘琛（1990—），男，河北昌黎人，硕士研究生，主要研究方向：密码测评。
基金资助:
北京市自然科学基金资助项目(4234084);河南省网络密码技术重点实验室研究课题(LNCT2021-A09)

Abstract

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:

TP309.7

Yanjun LI, Yaodong GE, Qi WANG, Weiguo ZHANG, Chen LIU. Improved KLEIN algorithm and its quantum analysis[J]. Journal of Computer Applications, 2024, 44(9): 2810-2817.

李艳俊, 葛耀东, 王琦, 张伟国, 刘琛. 改进的KLEIN算法及其量子分析[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2810-2817.

Figures/Tables 13

Tab. 1 Key lengths and encryption rounds of N-KLEIN

算法	分组长度/b	密钥长度/b	加密轮数
N-KLEIN-64	64	64	12
N-KLEIN-80	64	80	16
N-KLEIN-96	64	96	20

Fig. 1 Encryption process in N-KLEIN algorithm

Fig. 2 One round encryption process of N-KLEIN

Tab. 2 N-KLEIN’s S-box truth table

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

Fig. 3 ANF evaluation of S-box

Fig. 4 S-box quantum circuit implemented by in-place method

Tab. 3 Quantum resource consumption of S-box

方法	量子位（qubit）	CNOT门数	Toffoli门数	X门数
ANF	15	15	12	3
in-place	4	3	7	2

Tab. 4 Quantum resource consumption of key expansion structure

算法	量子位（qubit）	CNOT门数	Toffoli门数	X门数	电路深度
N-KLEIN-64	64	58	84	24	121
N-KLEIN-80	80	81	112	32	165
N-KLEIN-96	96	122	140	40	209

Tab. 5 Comparison between improved key expansion and original key expansion

算法	安全性	CNOT门数	Toffoli门数	X门数	电路深度
KLEIN-64	×	1 496	2 464	704	121
KLEIN-80	×	2 160	3 360	960	165
KLEIN-96	×	2 888	4 256	1 216	209
N-KLEIN-64	√	58	84	24	121
N-KLEIN-80	√	81	112	32	165
N-KLEIN-96	√	122	140	40	209

Tab. 6 Quantum resource consumption of N-KLEIN algorithm

算法	量子位（qubit）	CNOT门数	Toffoli门数	X门数
N-KLEIN-64	128	8 050	1 428	408
N-KLEIN-80	160	10 737	1 904	544
N-KLEIN-96	192	13 442	2 380	680

Tab. 7 Comparison of quantum resource consumption among different algorithms

算法	CNOT门数	X门数	Toffoli门数	T深度	量子位（qubit）	电路深度
KLEIN-64	8 264	1 088	3 808	216	128	612
N-KLEIN-64	8 050	408	1 428	81	128	288
PRESENT-64^［28］	4 838	1 164	2 232	N/A	192	311
PIPO-64^［29］	2 248	1 477	1 248	N/A	192	248
HIGHT-64^［9］	22 614	4 496	5 824	N/A	228	2 479
CHAM-64^［9］	12 285	240	2 400	N/A	196	N/A
LBlock-80^［30］	16 747	877	2 040	N/A	144	1 740

Fig. 5 Quantum implementation of operator Uf in N-KLEIN-64 algorithm

Tab. 8 Quantum resources of N-KLEIN using Grover algorithm under three key lengths

算法	总门数	总深度	总消耗	安全级别
N-KLEIN-64	$1.01 × 247$	$1.04 × 243$	$1.05 × 290$	未达到级别1
N-KLEIN-80	$1.47 × 247$	$1.36 × 243$	$1.01 × 291$	未达到级别1
N-KLEIN-96	$1.67 × 247$	$1.68 × 243$	$1.40 × 291$	未达到级别1

Tab. 8 Quantum resources of N-KLEIN using Grover algorithm under three key lengths

算法	总门数	总深度	总消耗	安全级别
N-KLEIN-64	$1.01 × 247$	$1.04 × 243$	$1.05 × 290$	未达到级别1
N-KLEIN-80	$1.47 × 247$	$1.36 × 243$	$1.01 × 291$	未达到级别1
N-KLEIN-96	$1.67 × 247$	$1.68 × 243$	$1.40 × 291$	未达到级别1

References 36

1	HANKERSON D， MENEZES A， VANSTONE S. Elliptic curve arithmetic ［M］// Guide to Elliptic Curve Cryptography. New York： Springer， 2004： 75-152.
2	SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer ［J］. SIAM Review， 1999， 41（2）： 303-332.
3	KUWAKADO H， MORII M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation ［C］// Proceedings of the 2010 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2010： 2682-2685.
4	KUWAKADO H， MORII M. Security on the quantum-type Even-Mansour cipher ［C］// Proceedings of the 2012 International Symposium on Information Theory and its Applications. Piscataway： IEEE， 2012： 312-316.
5	KAPLAN M， LEURENT G， LEVERRIER A， et al. Breaking symmetric cryptosystems using quantum period finding ［C］// Advances in Cryptology — EUROCRYPT 2016. Cham： Springer， 2016： 207-237.
6	梁敏，罗宜元，刘凤梅.抗量子计算对称密码研究进展概述［J］.密码学报， 2021， 8（6）： 925-947.
	LIANG M， LUO Y Y， LIU F M. A survey on quantum-secure symmetric cryptography ［J］. Journal of Cryptologic Research， 2021， 8（6）： 925-947.
7	KIM P， HAN D， JEONG K C. Time-space complexity of quantum search algorithms in symmetric cryptanalysis： applying to AES and SHA-2 ［J］. Quantum Information Processing， 2018， 17（12）： 339.
8	JAQUES S， NAEHRIG M， ROETTELER M， et al. Implementing Grover oracles for quantum key search on AES and LowMC ［C］// Advances in Cryptology — EUROCRYPT 2020. Cham： Springer， 2020： 280-310.
9	JANG K B， CHOI S J， KWON H D， et al. Grover on Korean block ciphers ［J］. Applied Sciences， 2020， 10（18）： 6407.
10	SCHLIEPER L. In-place implementation of Quantum-Gimli ［EB/OL］. ［2022-06-14］. .
11	JANG K B， CHOI S J， KWON H D， et al. Grover on SPECK： quantum resource estimates ［J］. Cryptology ePrint Archive， 2020， 2020： 640.
12	ANAND R， MAITRA A， MUKHOPADHYAY S. Grover on SIMON ［J］. Quantum Information Processing， 2020， 19（9）： 340.
13	JANG K， BAKSI A， BREIER J， et al. Quantum implementation and analysis of DEFAULT ［J］. Cryptology ePrint Archive， 2022， 2022： 647.
14	SONG G， JANG K， KIM H， et al. SPEEDY quantum circuit for Grover’s algorithm ［J］. Applied Sciences， 2022， 12（14）： 6870.
15	JEAN J， PEYRIN T， SIM S M， et al. Optimizing implementations of lightweight building blocks ［J］. IACR Transactions on Symmetric Cryptology， 2017， 2017（4）： 130-168.
16	BAKSI A， JANG K， SONG G， et al. Quantum implementation and resource estimates for rectangle and knot ［J］. Quantum Information Processing， 2021， 20（12）： 395.
17	XIANG Z， ZENG X， LIN D， et al. Optimizing implementations of linear layers ［J］. IACR Transactions on Symmetric Cryptology， 2020， 2020（2）： 120-145.
18	HUANG Z， SUN S. Synthesizing quantum circuits of AES with lower t-depth and less qubits ［C］// Advances in Cryptology —ASIACRYPT 2022. Cham： Springer， 2023： 614-644.
19	GRASSL M， LANGENBERG B， ROETTELER M， et al. Applying Grover’s algorithm to AES： quantum resource estimates［C］// Proceedings of the 7th International Workshop on Post-Quantum Cryptography. Cham： Springer， 2016： 29-43.
20	GONG Z， NIKOVA S， LAW Y W. KLEIN： a new family of lightweight block ciphers ［C］// Proceedings of the 7th International Workshop on RFID Security and Privacy. Cham： Springer， 2011： 1-18.
21	LALLEMAND V， NAYA-PLASENCIA M. Cryptanalysis of KLEIN［C］// Proceedings of the 21st International Workshop on Fast Software Encryption. Cham： Springer， 2014： 451-470.
22	BOGDANOV A， KNUDSEN L R， LEANDER G， et al. PRESENT： an ultra-lightweight block cipher ［C］// Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems. Cham： Springer， 2007： 450-466.
23	YU X， WU W， LI Y， et al. Cryptanalysis of reduced-round KLEIN block cipher ［C］// Proceedings of the 7th International Conference on Information Security and Cryptology. Cham： Springer， 2012： 237-250.
24	J-P AUMASSON， NAYA-PLASENCIA M， SAARINEN M-J O. Practical attack on 8 rounds of the lightweight block cipher KLEIN［C］// Proceedings of the 12th International Conference on Cryptology in India. Cham： Springer， 2011： 134-145.
25	CUCCARO S A， DRAPER T G， KUTIN S A， et al. A new quantum ripple-carry addition circuit ［EB/OL］. ［2023-07-23］. .
26	DRAPER T G， KUTIN S A， RAINS E M， et al. A logarithmic-depth quantum carry-lookahead adder ［EB/OL］. ［2023-04-14］. .
27	TAKAHASHI Y， TANI S， KUNIHIRO N. Quantum addition circuits and unbounded fan-out ［EB/OL］. ［2023-08-13］. .
28	JANG K， SONG G， KIM H， et al. Efficient implementation of PRESENT and GIFT on quantum computers ［J］. Applied Sciences， 2021， 11（11）： 4776.
29	JANG K， SONG G， KWON H， et al. Grover on PIPO ［J］. Electronics， 2021， 10（10）： 1194.
30	JING X Y， LI Y J， ZHAO G Y， et al. Quantum circuit implementation and resource analysis of LBlock and LiCi ［J］. Quantum Information Processing， 2023， 22： 347.
31	LANGENBERG B， PHAM H， STEINWANDT R. Reducing the cost of implementing the advanced encryption standard as a quantum circuit ［J］. IEEE Transactions on Quantum Engineering， 2020， 1： 1-12.
32	AMY M， DI MATTEO O， GHEORGHIU V， et al. Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3［C］// Proceedings of the 23rd International Conference on Selected Areas in Cryptography. Cham： Springer， 2017： 317-337.
33	WIEBE N， ROETTELER M. Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits ［EB/OL］. ［2022-10-02］. .
34	BOYER M， BRASSARD G， HØYER P， et al. Tight bounds on quantum searching ［J］. Fortschritte der Physik： Progress of Physics， 1998， 46（4/5）： 493-505.
35	Submission requirements and evaluation criteria for the post-quantum cryptography standardization process： NIST Interagency/Internal Report （NISTIR） — 8105 ［S/OL］. ［S.l.］： National Institute of Standards and Technology， 2016 ［2023-09-01］. .
36	JANG K， BAKSI A， KIM H， et al. Quantum analysis of AES ［J］. Cryptology ePrint Archive， 2022， 2022： 683.

[1]	Runlian ZHANG, Mi ZHANG, Xiaonian WU, Rui SHU. Differential property evaluation method based on GPU for large-state cryptographic S-boxes [J]. Journal of Computer Applications, 2024, 44(9): 2785-2790.
[2]	Feiyu ZHAI, Handa MA. Hybrid classical-quantum classification model based on DenseNet [J]. Journal of Computer Applications, 2024, 44(6): 1905-1910.
[3]	Yanjun LI, Xiaoyu JING, Huiqin XIE, Yong XIANG. Security analysis of PFP algorithm under quantum computing model [J]. Journal of Computer Applications, 2024, 44(4): 1166-1171.
[4]	Lingling GUO, Zhiqiang LI, Menghuan DUAN. Application of quantum approximate optimization algorithm in exact cover problems [J]. Journal of Computer Applications, 2024, 44(3): 849-854.
[5]	Yong XIANG, Yanjun LI, Dingyun HUANG, Yu CHEN, Huiqin XIE. Differential and linear characteristic analysis of full-round Shadow algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3839-3843.
[6]	Yipeng SHI, Jie LIU, Jinyuan ZU, Tao ZHANG, Guoqun ZHANG. Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model [J]. Journal of Computer Applications, 2023, 43(5): 1504-1510.
[7]	Jinwei PU, Qingjian GAO, Xin ZHENG, Yinghui XU. SM4 resistant differential power analysis lightweight threshold implementation [J]. Journal of Computer Applications, 2023, 43(11): 3490-3496.
[8]	Shanshan HUO, Yanjun LI, Jian LIU, Yinshuang LI. Design and implementation of cipher component security criteria testing tool [J]. Journal of Computer Applications, 2023, 43(10): 3156-3161.
[9]	Jingwen CAI, Yongzhuang WEI, Zhenghong LIU. GPU-based method for evaluating algebraic properties of cryptographic S-boxes [J]. Journal of Computer Applications, 2022, 42(9): 2750-2756.
[10]	Geng ZHAO, Senmin ZHANG, Yingjie MA, Shirui GAO. Design and analysis of dynamic S-box based on anti-degradation chaotic system [J]. Journal of Computer Applications, 2022, 42(10): 3069-3073.
[11]	LIU Zongfu, YUAN Zheng, ZHAO Chenxi, ZHU Liang. Integral attack on PICO algorithm based on division property [J]. Journal of Computer Applications, 2020, 40(10): 2967-2972.
[12]	ZHAO Ying, YE Tao, WEI Yongzhuang. New security analysis of several kinds of high-level cryptographical S-boxes [J]. Journal of Computer Applications, 2017, 37(9): 2572-2575.
[13]	MA Yunfei, WANG Tao, CHEN Hao, HUANG Changyang. Algebraic fault attack on lightweight block ciphers SIMON [J]. Journal of Computer Applications, 2017, 37(7): 1953-1959.
[14]	HU Zhihua, YAN Shuo, XIONG Kuanjiang. Dynamic S-box construction method and dynamic cryptography property analysis [J]. Journal of Computer Applications, 2016, 36(5): 1257-1261.
[15]	QIN Guanjie, MA Jianshe, CHENG Xuemin. Method for increasing S-box nonlinearity based on combination of hill climbing [J]. Journal of Computer Applications, 2015, 35(8): 2195-2198.

Improved KLEIN algorithm and its quantum analysis

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 36

Related Articles 15

Recommended Articles

Metrics

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05