基于MILP的PICO算法差分和线性区分器的搜索  

MILP-Based Search for Differential and Linear Distinguishers of PICO Algorithm

作　　者：石康康 任炯炯 陈少真 SHI Kang-Kang;REN Jiong-Jiong;CHEN Shao-Zhen(University of PLA Information Engineering,Zhengzhou 450001,China)

机构地区：[1]战略支援部队信息工程大学,郑州450001

出　　处：《密码学报》2023年第5期910-921,共12页Journal of Cryptologic Research

基　　金：国家自然科学基金(62206312)。

摘　　要：PICO算法是由Bansod等人在2016年提出的一种基于替换和排列的SPN网络的轻量级分组密码.目前针对PICO算法抵抗差分和线性分析的能力还有待进一步评估.本文基于MILP模型,首先利用不等式组对各组件的差分特征和线性掩码的传播规律进行了精细的刻画,其次针对密码算法的结构特点及S盒特性,对该模型进行了优化,缩小了搜索空间,并提出了针对PICO算法有效的两步搜索算法.最后利用该算法,搜索到了3条新的概率为2−63的21轮差分区分器,并首次搜索到了3条相关度为2−30的20轮线性区分器,为当前公开发表的最长线性区分器.The PICO algorithm is a lightweight packet cipher based on substitution and permutation SPN networks proposed by Bansod et al.in 2016.The ability of the PICO algorithm to resist differential and linear analysis is yet to be further evaluated.Based on the MILP model,this paper describes the differential characteristics of the components and the propagation law of the linear mask using a set of inequalities,optimizes the model for the structural characteristics of the cryptographic algorithm and the S-box properties,narrows the search space,and proposes an effective two-step search algorithm for the PICO algorithm.Using this algorithm,three new 21-round differential distinguishers with probability 2−63 are found,and three 20-round linear distinguishers with correlation 2−30 are found,which are the longest linear distinguishers known so far.

关 键 词：分组密码 差分分析 线性分析 MILP模型 PICO算法 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]