S盒NPNP等价匹配算法  

NPNP Equivalence Matching Algorithm for S-Boxes

作　　者：贾皓珑 曾骁 张菊玲 杨国武[1] JIA Hao-Long;ZENG Xiao;ZHANG Ju-Ling;YANG Guo-Wu(School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China;Cyberspace Security College,Xinjiang University of Finance and Economics,Urumqi 830000,China)

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731 [2]新疆财经大学网络空间安全学院,乌鲁木齐830000

出　　处：《密码学报（中英文）》2024年第4期845-860,共16页Journal of Cryptologic Research

基　　金：国家自然科学基金(62172075);成都创新科技项目(2021-YF05-02414-GX)。

摘　　要：根据S盒和布尔函数的相关性,S盒可以看作向量布尔函数.本文在基于布尔函数的NP等价匹配算法的基础上,设计了一个基于深度优先搜索的S盒NPNP等价匹配算法,用于判断两个不同的S盒是否NPNP等价,若等价则同时计算出NPNP变换方式.此算法的深度优先搜索结构基于树,且在进入深度优先搜索之前根据规则仅生成了部分可能存在解的路径,并在计算过程中实时判断以当前结点为新起点的剩余路径是否可能存在解,若不存在就直接剪枝并回溯避免了继续计算的时间开销,故其时间复杂度取决于树结点的个数.不同于仿射变换,本文提出的算法对于判断非可逆S盒是否NPNP等价的计算复杂度与判断可逆S盒是否NPNP等价的计算复杂度一致.实验方面,本文使用现在各个密码算法中常用的S盒进行实验,实验结果证实了本文方法的有效性,且计算过程远远优于直接搜索.According to the correlation between S-boxes and Boolean functions,S-boxes can be re-garded as vector Boolean functions.Based on the method of Boolean NP matching,an algorithm based on depth-first search is proposed to determine whether two different S-boxes are NPNP equivalent.If the two S-boxes are equivalent,the corresponding NPNP transformations will be recovered.This searching algorithm is based on the tree structure.Before entering the depth-first search,we eliminate the paths that cannot correspond to solutions according to some necessary conditions.Whenever the algorithm visits a node,it checks whether the remaining path with the current node as the root node has a solution.If not,the algorithm directly prunes this subtree and backtrack to reduce computational cost,so the time complexity depends on the number of visited nodes on the tree.Different from affine transformation,the computational complexities of the algorithm for judging NPNP equivalence are the same regardless whether the S-box is invertible or not.Some experiments are carried out based on the commonly used S-boxes in various cryptographic algorithms,and the results show that the proposed algorithm is effective,and the calculation process is more efficient than direct search.

关 键 词：S盒NPNP等价匹配 布尔匹配 深度优先搜索 剪枝回溯 

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