轻量级分组密码Piccolo的量子密码分析

doi:10.11959/j.issn.1000-436x.2023109

通信学报 ›› 2023, Vol. 44 ›› Issue (6): 175-182.doi: 10.11959/j.issn.1000-436x.2023109

轻量级分组密码Piccolo的量子密码分析

杜小妮¹^,², 王香玉¹, 梁丽芳¹, 李锴彬³

¹ 西北师范大学数学与统计学院，甘肃兰州 730070
² 西北师范大学密码技术与数据分析重点实验室，甘肃兰州 730070
³ 西北师范大学计算机科学与工程学院，甘肃兰州 730070

修回日期:2023-04-08 出版日期:2023-06-25 发布日期:2023-06-01
作者简介:杜小妮（1972- ），女，甘肃庆阳人，博士，西北师范大学教授、博士生导师，主要研究方向为密码学与信息安全等
王香玉（1997- ），女，河南开封人，西北师范大学硕士生，主要研究方向为密码学与信息安全等
梁丽芳（1995- ），女，甘肃定西人，西北师范大学硕士生，主要研究方向为密码学与信息安全等
李锴彬（1997- ），男，甘肃天水人，西北师范大学硕士生，主要研究方向为密码学与信息安全等
基金资助:
国家自然科学基金资助项目(62172337);甘肃省自然科学基金重点资助项目(23JRRA685)

Quantum cryptanalysis of lightweight block cipher Piccolo

Xiaoni DU¹^,², Xiangyu WANG¹, Lifang LIANG¹, Kaibin LI³

¹ College of Mathematics and Statistic, Northwest Normal University, Lanzhou 730070, China
² Key Laboratory of Cryptography and Data Analytics, Northwest Normal University, Lanzhou 730070, China
³ College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China

Revised:2023-04-08 Online:2023-06-25 Published:2023-06-01
Supported by:
The National Natural Science Foundation of China(62172337);Key Project of Gansu Natural Science Foundation(23JRRA685)

摘要/Abstract

摘要：

根据Piccolo算法RP置换的结构特点，提出3轮量子区分器，并用Grover meets Simon算法进行6轮量子密钥恢复攻击。分析结果表明，该攻击可恢复密钥56 bit，时间复杂度为2²⁸，共需量子比特数为464；当攻击轮数大于6 轮时，时间复杂度为2^28+16(r-6)，降至Grover量子暴力搜索的 $\frac{1}{2^{68}}$ 。与传统差分和线性分析相比，所提攻击方法时间复杂度更低，且较Grover暴力搜索的时间复杂度大幅降低，为后续轻量级分组密码的量子攻击的研究奠定了基础。

关键词: 量子密码分析, Piccolo算法, Grover算法, Simon算法

Abstract:

By taking the characteristics of the structure of Piccolo algorithm RP permutation into consideration, a 3-round quantum distinguisher was proposed.Based on Grover meets Simon algorithm, the 6-round of quantum key recovery attack was given.The results show that the key can be recovered 56 bit with the time complexity 2 ²⁸ and the occupation of 464 qubit.Moreover, if attack rounds r＞6，the time complexity is 2 ^28+16(r-6), which is $\frac{1}{2^{68}}$ of Grover quantum brute-force search.The time complexity of the proposed attack method is significantly reduced compared with Grover search and is also better than that of traditional cryptanalysis, which lays a foundation for the subsequent research on quantum attacks of lightweight block ciphers.

Key words: quantum cryptanalysis, Piccolo algorithm, Grover algorithm, Simon algorithm

中图分类号:

TP309.7

杜小妮, 王香玉, 梁丽芳, 李锴彬. 轻量级分组密码Piccolo的量子密码分析[J]. 通信学报, 2023, 44(6): 175-182.

Xiaoni DU, Xiangyu WANG, Lifang LIANG, Kaibin LI. Quantum cryptanalysis of lightweight block cipher Piccolo[J]. Journal on Communications, 2023, 44(6): 175-182.

图/表 10

表1

主要符号及其含义"

符号	含义
$X_{0}^{j}$	第 j分支的输入
$X_{i}^{j}$	第i轮输出后第 j分支上的值
X₍₆₄₎	输入的64 bit明文
Y₍₆₄₎	输出的64 bit密文
Z₍₆₄₎	RP置换的64 bit输出
F	轮函数
F_i	第i轮的轮函数
x_j	RP置换第 j字节输入
z_j	RP置换第 j字节输出
x ^ji	第i+1轮第 j分支的输入
k_i	第i轮的轮子密钥
rk_m	轮子密钥(0≤m≤2r,r为迭代轮次)
wk_l	白化密钥(l=0,1,2,3)

表1

图1

表2

图2

图3

图4

图5

图6

图7

图8

参考文献 24

[1]	SHIBUTANI K , ISOBE T , HIWATARI H ,et al. Piccolo:an ultra-lightweight blockcipher[C]// International Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2011: 342-357.
[2]	ISOBE T , SHIBUTANI K . Security analysis of the lightweight block ciphers XTEA,LED and Piccolo[C]// Proceedings of Australasian Conference on Information Security and Privacy. Berlin:Springer, 2012: 71-86.
[3]	AZIMI S A , AHMADIAN Z , MOHAJERI J ,et al. Impossible differential cryptanalysis of Piccolo lightweight block cipher[C]// Proceedings of 2014 11th International ISC Conference on Information Security and Cryptology. Piscataway:IEEE Press, 2014: 89-94.
[4]	FU L S , JIN C H , LI X R . Multidimensional zero-correlation linear cryptanalysis of lightweight block cipher Piccolo-128[J]. Security and Communication Networks, 2016,9(17): 4520-4535.
[5]	TOLBA M , ABDELKHALEK A , YOUSSEF A M . Meet-in-the-middle attacks on reduced round piccolo[C]// Proceedings of Lightweight Cryptography for Security and Privacy. Berlin:Springer, 2016: 3-20.
[6]	LIU Y , CHENG L , LIU Z Q ,et al. Improved meet-in-the-middle attacks on reduced-round Piccolo[J]. Science China Information Sciences, 2017,61(3): 1-13.
[7]	ASHUR T , DUNKELMAN O , MASALHA N . Linear cryptanalysis reduced round of piccolo-80[C]// Proceedings of Cyber Security Cryptography and Machine Learning. Berlin:Springer, 2019: 16-32.
[8]	LIU Y , CHENG L , ZHAO F Y ,et al. New analysis of reduced-version of piccolo in the single-key scenario[J]. KSII Transactions on Internet and Information Systems, 2019,13(9): 4727-4741.
[9]	GROVER L K . A fast quantum mechanical algorithm for database search[C]// Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. New York:ACM Press, 1996: 212-219.
[10]	SIMON D . On the power of quantum computation[J]. SIAM Journal on Computing, 1997,26(5): 1474-1483.
[11]	ZHANDRY M . How to construct quantum random functions[C]// Proceedings of 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 2012: 679-687.
[12]	KAPLAN M , LEURENT G , LEVERRIER A ,et al. Quantum differential and linear cryptanalysis[J]. IACR Transactions on Symmetric Cryptology, 2016,1: 71-94.
[13]	KUWAKADO H , MORII M . Quantum distinguisher between the 3-round Feistel cipher and the random permutation[C]// Proceedings of 2010 IEEE International Symposium on Information Theory. Piscataway:IEEE Press, 2010: 2682-2685.
[14]	LEANDER G , MAY A . Grover meets Simon-quantumly attacking the FX-construction[C]// Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2017: 161-178.
[15]	DONG X Y , WANG X Y . Quantum key-recovery attack on Feistel structures[J]. Science China Information Sciences, 2018,61(10): 1-7.
[16]	DONG X Y , LI Z , WANG X Y . Quantum cryptanalysis on some generalized Feistel schemes[J]. Science China Information Sciences, 2019,62(2): 1-12.
[17]	DONG X Y , DONG B Y , WANG X Y . Quantum attacks on some Feistel block ciphers[J]. Designs,Codes and Cryptography, 2020,88(6): 1179-1203.
[18]	倪博煜, 董晓阳 . 改进的 Type-1 型广义 Feistel 结构的量子攻击及其在分组密码 CAST-256 上的应用[J]. 电子与信息学报, 2020,42(2): 295-306.
	NI B Y , DONG X Y . Improved quantum attack on type-1 generalized feistel schemes and its application to CAST-256[J. Journal of Electronics ＆ Information Technology, 2020,42(2): 295-306.
[19]	尤启迪, 钱新, 周旋 ,等. SMS4-like 结构以及 NBC 算法的量子算法攻击研究[J]. 密码学报, 2020,7(6): 864-874.
	YOU Q D , QIAN X , ZHOU X ,et al. Research on quantum cryptanalysis on SMS4-like structure and NBC algorithm[J. Journal of Cryptologic Research, 2020,7(6): 864-874.
[20]	于博, 孙兵, 刘国强 ,等. 若干广义非平衡 Feistel 结构的量子分析研究[J]. 密码学报, 2021,8(6): 960-973.
	YU B , SUN B , LIU G Q ,et al. Quantum cryptanalysis on some generalized unbalanced feistel networks[J. Journal of Cryptologic Research, 2021,8(6): 960-973.
[21]	钱新, 尤启迪, 周旋 ,等. MARS-like Feistel结构的量子攻击[J]. 密码学报, 2021,8(3): 417-431.
	QIAN X , YOU Q D , ZHOU X ,et al. Quantum attack on MARS-like feistel schemes[J. Journal of Cryptologic Research, 2021,8(3): 417-431.
[22]	李艳俊, 林昊, 易子晗 ,等. MIBS 算法量子密码分析[J]. 密码学报, 2021,8(6): 989-998.
	LI Y J , LIN H , YI Z H ,et al. Quantum cryptanalysis of MIBS[J. Journal of Cryptologic Research, 2021,8(6): 989-998.
[23]	LI Y J , LIN H , LIANG M ,et al. A new quantum cryptanalysis method on block cipher Camellia[J]. IET Information Security, 2021,15(6): 487-495.
[24]	李艳俊, 易子晗, 汪振 ,等. 轻量级密码 TWINE-128 的量子密码分析[J]. 密码学报, 2022,9(4): 633-643.
	LI Y J , YI Z H , WANG Z ,et al. Quantum cryptanalysis of lightweight cipher TWINE-128[J. Journal of Cryptologic Research, 2022,9(4): 633-643.

攻击方法	攻击轮数/轮	时间复杂度/次
中间相遇攻击^[2]	14	2 ⁷³
不可能差分分析^[3]	12	2 ^55.18
中间相遇攻击^[5]	14	2 ^75.39
改进的中间相遇攻击^[6]	14	2 ^67.44
线性分析^[7]	8	2 ⁷⁰
中间相遇攻击^[8]	13	2 ^67.39
量子攻击	6	2 ²⁸

轻量级分组密码Piccolo的量子密码分析

Quantum cryptanalysis of lightweight block cipher Piccolo

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 24

相关文章 1

Metrics

推荐阅读 0