Paper 2018/115

An Improved Affine Equivalence Algorithm for Random Permutations

Itai Dinur

Abstract

In this paper we study the affine equivalence problem, where given two functions $\vec{F},\vec{G}: \{0,1\}^n \rightarrow \{0,1\}^n$, the goal is to determine whether there exist invertible affine transformations $A_1,A_2$ over $GF(2)^n$ such that $\vec{G} = A_2 \circ \vec{F} \circ A_1$. Algorithms for this problem have several well-known applications in the design and analysis of Sboxes, cryptanalysis of white-box ciphers and breaking a generalized Even-Mansour scheme. We describe a new algorithm for the affine equivalence problem and focus on the variant where $\vec{F},\vec{G}$ are permutations over $n$-bit words, as it has the widest applicability. The complexity of our algorithm is about $n^3 2^n$ bit operations with very high probability whenever $\vec{F}$ (or $\vec{G})$ is a random permutation. This improves upon the best known algorithms for this problem (published by Biryukov et al. at EUROCRYPT 2003), where the first algorithm has time complexity of $n^3 2^{2n}$ and the second has time complexity of about $n^3 2^{3n/2}$ and roughly the same memory complexity. Our algorithm is based on a new structure (called a \emph{rank table}) which is used to analyze particular algebraic properties of a function that remain invariant under invertible affine transformations. Besides its standard application in our new algorithm, the rank table is of independent interest and we discuss several of its additional potential applications.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Keywords
Affine equivalence problemblock cipherEven-Mansour ciphercryptanalysisrank table.
Contact author(s)
dinuri @ cs bgu ac il
History
2018-01-31: received
Short URL
https://ia.cr/2018/115
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/115,
      author = {Itai Dinur},
      title = {An Improved Affine Equivalence Algorithm for Random Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2018/115},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/115}},
      url = {https://eprint.iacr.org/2018/115}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.