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

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

Abstract

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

CLC Number:

TP309.7

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

Figures/Tables 10

符号	含义
$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)

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

攻击方法	攻击轮数/轮	时间复杂度/次
中间相遇攻击^[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 ²⁸

Quantum cryptanalysis of lightweight block cipher Piccolo

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Wei LI, Chun LIU, Dawu GU, Wenqian SUN, Jianning GAO, Mengyang QIN. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short [J]. Journal on Communications, 2023, 44(4): 167-175.
[2]	Hua REN, Shaozhang NIU, Ruyong REN, Zhen YUE. Research on meaningful image encryption algorithm based on 2-dimensional compressive sensing [J]. Journal on Communications, 2022, 43(5): 45-57.
[3]	Xiaodong YANG, Tian TIAN, Jiaqi WANG, Meijuan LI, Caifen WANG. Certificateless ciphertext retrieval scheme with multi-user and multi-keyword based on cloud-edge collaboration [J]. Journal on Communications, 2022, 43(5): 144-154.
[4]	Changgen PENG, Ting GAO, Huilan LIU, Hongfa DING. PCA-based membership inference attack for machine learning models [J]. Journal on Communications, 2022, 43(1): 149-160.
[5]	Xiaodong YANG, Wanting XI, Jiaqi WANG, Aijia CHEN, Caifen WANG. Electronic evidence sharing scheme of Internet of vehicles based on signcryption and blockchain [J]. Journal on Communications, 2021, 42(12): 236-246.
[6]	Ruiqi LI, Chunfu JIA, Yafei WANG. Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application [J]. Journal on Communications, 2021, 42(3): 11-22.
[7]	Wei LI, Menglin WANG, Dawu GU, Jiayao LI, Tianpei CAI, Guangwei XU. Ciphertext-only fault analysis of the TWINE lightweight cryptogram algorithm [J]. Journal on Communications, 2021, 42(3): 135-149.
[8]	Shufen NIU,Wenke LIU,Lixia CHEN,Caifen WANG,Xiaoni DU. Electronic medical record data sharing scheme based on searchable encryption via consortium blockchain [J]. Journal on Communications, 2020, 41(8): 204-214.
[9]	Yiliang HAN,Zhong WANG. Code-based generalized signcryption scheme with multi-receiver [J]. Journal on Communications, 2020, 41(1): 53-65.
[10]	Youliang TIAN,Kedi YANG,Zuan WANG,Tao FENG. Algorithm of blockchain data provenance based on ABE [J]. Journal on Communications, 2019, 40(11): 101-111.
[11]	Wei LI,Yixin WU,Dawu GU,Jiayao LI,Shan CAO,Menglin WANG,Tianpei CAI,Xiangwu DING,Zhiqiang LIU. Ciphertext-only fault analysis of the SIMON lightweight cipher [J]. Journal on Communications, 2019, 40(11): 122-137.
[12]	Xiaodong YANG,Yutong LI,Jinli WANG,Tingchun MA,Caifen WANG. Revocable identity-based proxy re-signature scheme in the standard model [J]. Journal on Communications, 2019, 40(5): 153-162.
[13]	Yu SHEN,Wei LI,Dawu GU,Yixin WU,Shan CAO,Ya LIU,Zhiqiang LIU,Zhihong ZHOU. Integral fault analysis of the ARIA cipher [J]. Journal on Communications, 2019, 40(2): 164-173.
[14]	Hongyu YANG,Zaiming WANG. Android collusion attack detection model [J]. Journal on Communications, 2018, 39(6): 27-36.
[15]	Bin XIAO,Wenming SHI,Weisheng LI,Jianfeng MA. Image encryption method based on multiple-order fractional discrete Tchebichef transform and generating sequence [J]. Journal on Communications, 2018, 39(5): 1-10.