Boyar Joan, Find Magnus Gausdal, Peralta René
Department of Mathematics and Computer Science University of Southern Denmark,
Information Technology Laboratory, National Institute of Standards and Technology,
Cryptogr Commun. 2019;11. doi: 10.1007/s12095-018-0296-3.
We present techniques to obtain small circuits which also have low depth. The techniques apply to typical cryptographic functions, as these are often specified over the field (2), and they produce circuits containing only AND, XOR and XNOR gates. The emphasis is on the linear components (those portions containing no AND gates). A new heuristic, DCLO (for depth-constrained linear optimization), is used to create small linear circuits given depth constraints. DCLO is repeatedly used in a See-Saw method, alternating between optimizing the upper linear component and the lower linear component. The depth constraints specify both the depth at which each input arrives and restrictions on the depth for each output. We apply our techniques to cryptographic functions, obtaining new results for the S-Box of the Advanced Encryption Standard, for multiplication of binary polynomials, and for multiplication in finite fields. Additionally, we constructed a 16-bit S-Box using inversion in (2) which may be significantly smaller than alternatives.
我们提出了获得小规模且深度较低电路的技术。这些技术适用于典型的密码函数，因为这些函数通常是在域(2)上指定的，并且它们产生的电路仅包含与门、异或门和同或门。重点在于线性组件（即不包含与门的部分）。一种新的启发式方法DCLO（用于深度受限线性优化）用于在给定深度约束的情况下创建小规模线性电路。DCLO在跷跷板方法中反复使用，在优化上部线性组件和下部线性组件之间交替进行。深度约束既指定了每个输入到达的深度，也对每个输出的深度进行了限制。我们将我们的技术应用于密码函数，在高级加密标准的S盒、二元多项式乘法以及有限域乘法方面获得了新的结果。此外，我们使用(2)中的求逆构造了一个16位S盒，它可能比其他方案小得多。
