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
Yanjun LI1,2, Yaodong GE2, Qi WANG2(), Weiguo ZHANG2, Chen LIU1
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.Supported by:
李艳俊1,2, 葛耀东2, 王琦2(), 张伟国2, 刘琛1
通讯作者:
王琦
作者简介:
李艳俊(1979—),女,山西阳城人,副教授,博士,主要研究方向:密码分析与测评基金资助:
CLC Number:
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.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2023091333
算法 | 分组长度/b | 密钥长度/b | 加密轮数 |
---|---|---|---|
N-KLEIN-64 | 64 | 64 | 12 |
N-KLEIN-80 | 64 | 80 | 16 |
N-KLEIN-96 | 64 | 96 | 20 |
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 |
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 |
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 |
方法 | 量子位(qubit) | CNOT门数 | Toffoli门数 | X门数 |
---|---|---|---|---|
ANF | 15 | 15 | 12 | 3 |
in-place | 4 | 3 | 7 | 2 |
Tab. 3 Quantum resource consumption of S-box
方法 | 量子位(qubit) | CNOT门数 | Toffoli门数 | X门数 |
---|---|---|---|---|
ANF | 15 | 15 | 12 | 3 |
in-place | 4 | 3 | 7 | 2 |
算法 | 量子位(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. 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 |
算法 | 安全性 | 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. 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 |
算法 | 量子位(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. 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 |
算法 | 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[ | 4 838 | 1 164 | 2 232 | N/A | 192 | 311 |
PIPO-64[ | 2 248 | 1 477 | 1 248 | N/A | 192 | 248 |
HIGHT-64[ | 22 614 | 4 496 | 5 824 | N/A | 228 | 2 479 |
CHAM-64[ | 12 285 | 240 | 2 400 | N/A | 196 | N/A |
LBlock-80[ | 16 747 | 877 | 2 040 | N/A | 144 | 1 740 |
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[ | 4 838 | 1 164 | 2 232 | N/A | 192 | 311 |
PIPO-64[ | 2 248 | 1 477 | 1 248 | N/A | 192 | 248 |
HIGHT-64[ | 22 614 | 4 496 | 5 824 | N/A | 228 | 2 479 |
CHAM-64[ | 12 285 | 240 | 2 400 | N/A | 196 | N/A |
LBlock-80[ | 16 747 | 877 | 2 040 | N/A | 144 | 1 740 |
算法 | 总门数 | 总深度 | 总消耗 | 安全级别 |
---|---|---|---|---|
N-KLEIN-64 | 未达到级别1 | |||
N-KLEIN-80 | 未达到级别1 | |||
N-KLEIN-96 | 未达到级别1 |
Tab. 8 Quantum resources of N-KLEIN using Grover algorithm under three key lengths
算法 | 总门数 | 总深度 | 总消耗 | 安全级别 |
---|---|---|---|---|
N-KLEIN-64 | 未达到级别1 | |||
N-KLEIN-80 | 未达到级别1 | |||
N-KLEIN-96 | 未达到级别1 |
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. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||