RESUMEN
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 GF (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 GF (216) which may be significantly smaller than alternatives.
RESUMEN
A necessary condition for the security of cryptographic functions is to be "sufficiently distant" from linear, and cryptographers have proposed several measures for this distance. In this paper, we show that six common measures, nonlinearity, algebraic degree, annihilator immunity, algebraic thickness, normality, and multiplicative complexity, are incomparable in the sense that for each pair of measures, µ1, µ2, there exist functions f1, f2 with f1 being more nonlinear than f2 according to µ1, but less nonlinear according to µ2. We also present new connections between two of these measures. Additionally, we give a lower bound on the multiplicative complexity of collision-free functions.
