S盒NPNP等价匹配算法

作     者：贾皓珑 曾骁 张菊玲 杨国武 JIA Hao-Long;ZENG Xiao;ZHANG Ju-Ling;YANG Guo-Wu

作者机构：电子科技大学计算机科学与工程学院成都611731 新疆财经大学网络空间安全学院乌鲁木齐830000 

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

出 版 物：《密码学报（中英文）》 (Journal of Cryptologic Research)

年 卷 期：2024年第11卷第4期

页      码：845-860页

摘      要：根据S盒和布尔函数的相关性,S盒可以看作向量布尔函数.本文在基于布尔函数的NP等价匹配算法的基础上,设计了一个基于深度优先搜索的S盒NPNP等价匹配算法,用于判断两个不同的S盒是否NPNP等价,若等价则同时计算出NPNP变换方式.此算法的深度优先搜索结构基于树,且在进入深度优先搜索之前根据规则仅生成了部分可能存在解的路径,并在计算过程中实时判断以当前结点为新起点的剩余路径是否可能存在解,若不存在就直接剪枝并回溯避免了继续计算的时间开销,故其时间复杂度取决于树结点的个数.不同于仿射变换,本文提出的算法对于判断非可逆S盒是否NPNP等价的计算复杂度与判断可逆S盒是否NPNP等价的计算复杂度一致.实验方面,本文使用现在各个密码算法中常用的S盒进行实验,实验结果证实了本文方法的有效性,且计算过程远远优于直接搜索.

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

学科分类：08[工学] 0839[0839] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13868/j.cnki.jcr.000712

馆 藏 号：203141491...