Investigating Security of a Few Schemes Based on Public Primitives

Abstract

Random oracles are cryptographers’ conceptions of what an ’ideal’ hash function should be.Put succinctly, a random oracle is a perfectly random function that you can evaluate quickly. Random functions are beautiful not just because the output is random-looking (of course) but also because they’re automatically collision-resistant and pre-image resistant. However, we know of nothing in the ’real’ world that can approximate them. When cryptographers try to analyse their schemes with random functions, they enter an imaginary fantasy world called the ’random oracle model’. In 2004, Maurer, Renner, and Holenstein gave us a powerful tool for answering this question. What they showed is that it’s always possible to replace functionality A (e.g., a random oracle) with another functionality B (e.g., an ideal compression function) provided that the following rules are satisfied: We can ’construct’ something ’like’ A out of B. We can ’simulate’ something ’like’ B using A. An attacker who interacts with constructed A-like thing, B cannot tell the difference (i.e., can’t differentiate it) from A, simulated B-like thing.The notion of indifferentiability is very helpful for investigating the security of cryptographic schemes based on public primitives. The public permutation model is another model that helps to scrutinise the security of schemes based on public primitives. In this model, rather than simulating, the adversary also has direct access to the underlying primitives in the ideal world. This model is generally used to analyse keyed constructions as opposed to unkeyed constructions in indifferentiability. In this thesis, we look at indifferentiability and related security notions in detail. We look back at the definitions and then look at some constructions that achieve the desired security goals. Specifically: • We look at the 3-round tweakable random permutation-based cipher introduced by Coron et al. in [1] and improve their security results by a factor of 2. • We also look at the security of Even-Mansour-based key-alternating ciphers in the public permutation model. We show that 5-round Even-Mansour-based key alternating ciphers achieve beyond birthday security (2n/3−bits). • Finally, we dive deeper into the notion of crooked indifferentiability introduced by Russell et al. in [2]. crooked indifferentiability is a novel concept that can be used to build secure constructions from subverted primitives. Russell et al. showed that the enveloped xor construction is crooked indifferentiable from a random oracle. We found some mistakes in their proofs and then corrected them. We also develop a new technique to analyse crooked indifferentiability and then use it to show the security of the Sponge and the Merkle- Damg˚ard constructions, both of which are easier to implement and less costly in memory uses than the enveloped xor construction.