密码学报（中英文）2024，Vol.11Issue(4)：845-860,16.DOI:10.13868/j.cnki.jcr.000712
S盒NPNP等价匹配算法
NPNP Equivalence Matching Algorithm for S-Boxes
摘要
Abstract
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等价匹配/布尔匹配/深度优先搜索/剪枝回溯Key words
S-box NPNP equivalent matching/Boolean matching/depth-first search/prune and backtrack分类
信息技术与安全科学引用本文复制引用
贾皓珑,曾骁,张菊玲,杨国武..S盒NPNP等价匹配算法[J].密码学报（中英文）,2024,11(4):845-860,16.基金项目
国家自然科学基金(62172075) （62172075）
成都创新科技项目(2021-YF05-02414-GX)National Natural Science Foundation of China(62172075) （2021-YF05-02414-GX）
Chengdu Innovation and Technology Project(2021-YF05-02414-GX) （2021-YF05-02414-GX）
