H‐coefficients Technique
Yannick Seurin · 2023
This chapter is an introduction to the H-coefficients technique, a proof method allowing to upper bound the advantage of a computationally unbounded adversary in distinguishing between two random systems. It presents the Even-Mansour construction which defines a block cipher from a single permutation, and applies the H-coefficients technique to prove its security in the random permutation model. The Even-Mansour construction is minimal in the sense that removing any component makes it insecure. The analysis is carried in the random permutation model, meaning that the inner permutation P on which the construction is based is modeled as a uniformly random permutation to which the distinguisher has two-sided black-box access: a random permutation oracle. The Even-Mansour construction can be generalized to multiple rounds. The iterated Even-Mansour construction captures the high-level structure of so-called key-alternating ciphers such as advanced encryption standard.