< Back to previous page

Publication

Pseudorandom Permutations and Functions for Lightweight Applications

Book - Dissertation

The security of symmetric-key cryptographic constructions is often studied based on the assumption that underlying primitives are secure. Hence, well-analyzed primitives are extremely important for the design of efficient and secure cryptographic schemes and protocols. Unfortunately, only a few types of dedicated primitive designs have received sufficient attention from the cryptanalysts. Therefore, it is necessary to build generic building blocks from these dedicated primitives. Several types of generic building blocks can be used to construct more complex cryptographic schemes and protocols for various applications. In addition, the design structures used for dedicated primitives can be studied in a generic way using the ideal permutation model; this allows us to look into the box and to improve our understanding of the inner workings of dedicated primitives. This thesis studies the generic design of pseudorandom permutations and functions, that are symmetric-key building blocks used in various cryptographic applications. The thesis makes contributions to the following three objectives. -Pseudorandom Permutations. We study the reflection ciphers for the first time in the provable security setting. We first introduce the key-alternating reflection cipher, which represents the inner design structure used in most reflection ciphers. Furthermore, we present a generic key-length extension method for reflection ciphers using the FX structure (such as PRINCE), and we show that a small modification to these reflection ciphers will result in a big improvement in the security bound. We also propose a new proof technique, called ``harmonic permutation primitives'', and use these special primitives to prove the ``beyond birthday bound'' security of the LDT length doubler that was proposed in the author's master thesis. -Pseudorandom Functions. We study three types of algorithms that share a similar security notion. We design ``beyond birthday bound'' secure pseudorandom function SoEM, and a tweakable circular correlation robust hash function FPTP, each using two public permutation calls. We also categorize all nonce-based MAC algorithms that can be built using two block cipher calls and one universal hash function call. -Generic Permutation-Based Proof Technique. Due to the trend of modern permutation-based cryptography, many constructions are designed using public random permutations. We generalize Patarin's mirror theory to the public permutation-based setting, such that the security of the constructions using two permutation calls can be obtained in a modular way. Using this new modular approach, we are able to detect bugs in the security proofs of existing constructions. We showcase this on the two permutation variant of the nEHtM_p MAC algorithm by Dutta and Nandi (AFRICACRYPT '20). More importantly, we can ensure that security proofs can be derived in a simpler and less error-prone way in the future.
Publication year:2022
Accessibility:Embargoed