Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions $F$ and $G$ such that there exist two affine permutations $A$, $B$, and an affine function $C$ satisfying $G = A \circ F \circ B + C$. While a priori simple, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants: EA-testing deals with figuring out whether the two functions can be EA-equivalent, and EA-recovery is about recovering the tuple $(A,B,C)$ if it exists. In this paper, we present a new efficient algorithm that efficiently solves the EA-recovery problem for quadratic functions. Though its worst-case complexity is obtained when dealing with APN functions, it supersedes all previously known algorithms in terms of performance, even in this case. This approach is based on the Jacobian matrix of the functions, a tool whose study in this context can be of independent interest. In order to tackle EA-testing efficiently, the best approach in practice relies on class invariants. We provide an overview of the literature on said invariants along with a new one based on the \emph{ortho-derivative} which is applicable to quadratic APN functions, a specific type of functions that is of great interest, and of which tens of thousands need to be sorted into distinct EA-classes. Our ortho-derivative-based invariant is both very fast to compute, and highly discriminating.


翻译:伸缩等同( EA) 是两个矢量布林函数之间的等值关系 。 问题有两个变式 : EA 测试处理如何确定两个函数是否相当于 EA- 等值, EA- 恢复处理是如何在存在的情况下恢复 tuple $( A, B, C) 。 在本文中, 我们展示了一种新的高效算法, 有效解决 EA- 回收问题 $ G = A = cic F\ cic B + C 美元。 虽然在处理 APN 函数时, 其最坏的复杂程度可以取代所有先前已知的运算法, 即便在此情况下, 也很难测试两个函数是否相当于 EA- 等值; EA- 测试处理两个函数是否相当于 EA- 等值, EA- B, C 和 等值是 等值 。 为了有效处理 EA- 等值 $ ( A, B, B, C) 和 等值 等值中, 最佳算法是快速 。

0
下载
关闭预览

相关内容

专知会员服务
38+阅读 · 2020年9月6日
【Manning新书】现代Java实战,592页pdf
专知会员服务
98+阅读 · 2020年5月22日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年4月21日
Arxiv
0+阅读 · 2021年4月19日
Arxiv
0+阅读 · 2021年4月16日
VIP会员
相关VIP内容
专知会员服务
38+阅读 · 2020年9月6日
【Manning新书】现代Java实战,592页pdf
专知会员服务
98+阅读 · 2020年5月22日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员