The indifferentiability framework has become a standard methodology that enables us to study the security of cryptographic constructions in idealized models of computation. Unfortunately, while indifferentiability provides strong guarantees whenever the security of a construction is captured by a ``single-stage'' security game, it may generally provide no meaningful guarantees when the security is captured by a ``multi-stage'' one. In particular, the indifferentiability framework does not...

Indifferentiability is a popular cryptographic paradigm for analyzing the security of ideal objects---both in a classical as well as in a quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction (e.g., a cryptographic hash function) to be ``as good as'' an ideal object (e.g., a random oracle). Despite its strength, indifferentiability is not known to offer security against pre-processin} attacks in which...

The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks---that is, adversarial subversion---of the component round functions. Specifically, we establish that a Feistel-based construction with more than $337n/\log(1/\epsilon)$ rounds can transform a subverted random function---which disagrees with the original one at a small...

Ever since the seminal work of Diffie and Hellman, cryptographic (cyclic) groups have served as a fundamental building block for constructing cryptographic schemes and protocols. The security of these constructions can often be based on the hardness of (cyclic) group-based computational assumptions. Then, the generic group model (GGM) has been studied as an idealized model (Shoup, EuroCrypt 1997), which justifies the hardness of many (cyclic) group-based assumptions and shows the limits of...

Recently, Masny and Rindal [MR19] formalized a notion called Endemic Oblivious Transfer (EOT), and they proposed a generic transformation from Non-Interactive Key Exchange (NIKE) to EOT with standalone security in the random oracle (RO) model. However, from the model level, the relationship between idealized NIKE and idealized EOT and the relationship between idealized elementary public key primitives have been rarely researched. In this work, we investigate the relationship between ideal...

In this paper, we study the security definitions of various threshold symmetric primitives. Namely, we analyze the security definitions for threshold pseudorandom functions, threshold message authentication codes and threshold symmetric encryption. In each case, we strengthen the existing security definition, and we present a scheme that satisfies our stronger notion of security. In particular, we propose indifferentiability definition and IND-CCA2 definition for a threshold pseudorandom...

Cryptographic hash functions are said to be the work-horses of modern cryptography. One of the strongest approaches to assess a cryptographic hash function's security is indifferentiability. Informally, indifferentiability measures to what degree the function resembles a random oracle when instantiated with an ideal underlying primitive. However, proving the indifferentiability security of hash functions has been challenging due to complex simulator designs and proof arguments. The Sponge...

Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This property underpins the security of various cryptographic applications, making it crucial to understand its complexity. The complexity of this problem is well-understood in the classical setting and $\Theta(N^{1/2})$ queries are needed to find a collision. However, the advent of quantum computing has introduced new...

In this work, we initiate a new conceptual line of attack on the fundamental question of how to generate hard problems. Motivated by the need for one-way functions in cryptography, we propose an information-theoretic framework to study the question of generating new provably hard one-way functions by composing functions that are easy to invert and evaluate, where each such easy function is modeled as a random oracles paired with another oracle that implements an inverse function.

The random oracle model is an instrument used for proving that protocol has no structural flaws when settling with standard hash properties is impossible or fairly difficult. In practice, however, random oracles have to be instantiated with some specific hash functions, which are not random oracles. Hence, in the real world, an adversary has broader capabilities than considered in the random oracle proof — it can exploit the peculiarities of a specific hash function to achieve its goal. In a...

The sum of two $n$-bit pseudorandom permutations is known to behave like a pseudorandom function with $n$ bits of security. A recent line of research has investigated the security of two public $n$-bit permutations and its degree of indifferentiability. Mandal et al. (INDOCRYPT 2010) proved $2n/3$-bit security, Mennink and Preneel (ACNS 2015) pointed out a non-trivial flaw in their analysis and re-proved $(2n/3-\log_2(n))$-bit security. Bhattacharya and Nandi (EUROCRYPT 2018) eventually...

We provide security foundations for SAFE, a recently introduced API framework for sponge-based hash functions tailored to prime-field-based protocols. SAFE aims to provide a robust and foolproof interface, has been implemented in the Neptune hash framework and some zero-knowledge proof projects, but currently lacks any security proof. In this work we identify the SAFECore as versatile variant sponge construction underlying SAFE, we prove indifferentiability of SAFECore for all (binary and...

We consider a transform, called Derive-then-Derandomize, that hardens a given signature scheme against randomness failure and implementation error. We prove that it works. We then give a general lemma showing indifferentiability of Shrink-MD, a class of constructions that apply a shrinking output transform to an MD-style hash function. Armed with these tools, we give new proofs for the widely standardized and used EdDSA signature scheme, improving prior work in two ways: (1) we give proofs...

Virtually all modern blockciphers are iterated. In this paper, we ask: to construct a secure iterated blockcipher "non-trivially", how many calls to random functions and permutations are necessary? When security means indistinguishability from a random permutation, optimality is achieved by the Even-Mansour scheme using 1 call to a public permutation. We seek for the arguably strongest security indifferentiability from an ideal cipher, a notion introduced by Maurer et al. (TCC 2004) and...

Verifiable random functions (VRFs) are essentially pseudorandom functions for which selected outputs can be proved correct and unique, without compromising the security of other outputs. VRFs have numerous applications across cryptography, and in particular they have recently been used to implement committee selection in the Algorand protocol. Elliptic Curve VRF (ECVRF) is an elegant construction, originally due to Papadopoulos et al., that is now under consideration by the Internet...

The sponge construction is a popular method for hashing. Quickly after its introduction, the sponge was proven to be tightly indifferentiable from a random oracle up to $ \approx 2^{c/2}$ queries, where $c$ is the capacity. However, this bound is not tight when the number of message blocks absorbed is restricted to $\ell <\lceil \frac{c}{2(b-c)}\rceil 1$ (but still an arbitrary number of blocks can be squeezed). In this work, we show that this restriction leads to indifferentiability from...

Iterated Even-Mansour (IEM) schemes consist of a small number of fixed permutations separated by round key additions. They enjoy provable security, assuming the permutations are public and random. In particular, regarding chosen-key security in the sense of sequential indifferentiability (seq-indifferentiability), Cogliati and Seurin (EUROCRYPT 2015) showed that without key schedule functions, the 4-round Even-Mansour with Independent Permutations and no key schedule $EMIP_4(k,u) = k \oplus...

Incompressibility is one of the most fundamental security goals in white-box cryptography. Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock, we demonstrate the feasibility of reducing incompressible AEAD modes to incompressible block ciphers. We first observe that several existing AEAD modes of operation, including CCM, GCM(-SIV), and OCB, would be all insecure against white-box adversaries even when used with an...

Hashing arbitrary values to points on an elliptic curve is a required step in many cryptographic constructions, and a number of techniques have been proposed to do so over the years. One of the first ones was due to Shallue and van de Woestijne (ANTS-VII), and it had the interesting property of applying to essentially all elliptic curves over finite fields. It did not, however, have the desirable property of being indifferentiable from a random oracle when composed with a random oracle to...

Indifferentiability is a powerful notion in cryptography. If a construction is proven to be indifferentiable from an ideal object, it can under certain assumptions instantiate that ideal object in higher-level constructions. Indifferentiability is a particularly useful model for cryptographic hash functions, and myriad results are known proving that a hash function behaves like a random oracle under the assumption that the underlying primitive (typically a compression function, a block...

First of all we take a thorough look at an error in a paper by Daemen et al. (ToSC 2018) which looks at minimal requirements for tree-based hashing based on multiple primitives, including block ciphers. This reveals that the error is more fundamental than previously shown by Gunsing et al. (ToSC 2020), which is mainly interested in its effect on the security bounds. It turns out that the cause for the error is due to an essential oversight in the interaction between the different oracles...

The pre-shared key (PSK) handshake modes of TLS 1.3 allow for the performant, low-latency resumption of previous connections and are widely used on the Web and by resource-constrained devices, e.g., in the Internet of Things. Taking advantage of these performance benefits with optimal and theoretically-sound parameters requires tight security proofs. We give the first tight security proofs for the TLS 1.3 PSK handshake modes. Our main technical contribution is to address a gap in prior...

A large proportion of modern symmetric cryptographic building blocks are designed using the Substitution-Permutation Networks (SPNs), or more generally, Shannon's confusion-diffusion paradigm. To justify its theoretical soundness, Dodis et al. (EUROCRYPT 2016) recently introduced the theoretical model of confusion-diffusion networks, which may be viewed as keyless SPNs using random permutations as S-boxes and combinatorial primitives as permutation layers, and established provable security...

MDPH is a double-block-length hash function proposed by Naito at Latincrypt 2019.This is a combination of Hirose's compression function and the domain extender called Merkle-Damg\r{a}rd with permutation (MDP). When instantiated with an $n$-bit block cipher, Naito proved that this achieves the (nearly) optimal indifferentiable security bound of $O(n-\log n)$-bit security. In this paper, we first point out that the proof of the claim contains a gap, which is related to the definition of the...

We prove classical and quantum indifferentiability of a rate-1/3 compression function introduced by Shrimpton and Stam (ICALP '08). This construction was one of the first constructions based on three random functions that achieved optimal collision-resistance. We also prove that our result is tight, we define a classical and a quantum attackers that match the indifferentiability security level. Our tight indifferentiability results provide a negative result on the optimality of security of...

Let $\mathbb{F}_{\!q}$ be a finite field and $E\!: y^2 = x^3 ax b$ be an elliptic $\mathbb{F}_{\!q^2}$-curve of $j(E) \not\in \mathbb{F}_{\!q}$. This article provides a new constant-time hash function $\mathcal{H}\!: \{0,1\}^* \to E(\mathbb{F}_{\!q^2})$ indifferentiable from a random oracle. Furthermore, $\mathcal{H}$ can be computed with the cost of $3$ exponentiations in $\mathbb{F}_{\!q}$. In comparison, the actively used (indifferentiable constant-time) simplified SWU hash function...

Digital signatures have been widely used as building blocks for constructing complex cryptosystems. To facilitate the security analysis of a complex system, we expect the underlying building blocks to achieve desirable composability. Notably, Canetti (FOCS 2001) and then Maurer et al (TCC 2004) propose analysis frameworks, the Universal Composability framework for cryptographic protocols, and the indifferentiability framework for cryptographic objects. In this paper, we develop a “lifting...

We revisit the classical problem of designing optimally efficient cryptographically secure hash functions. Hash functions are traditionally designed via applying modes of operation on primitives with smaller domains. The results of Shrimpton and Stam (ICALP 2008), Rogaway and Steinberger (CRYPTO 2008), and Mennink and Preneel (CRYPTO 2012) show how to achieve optimally efficient designs of $2n$-to-$n$-bit compression functions from non-compressing primitives with asymptotically optimal...

We investigate the digital signature schemes in the indifferentiability framework. We show that the well-known Lamport one-time signature scheme and the tree-based signature scheme can be ``lifted'' to realize ideal one-time signature, and ideal signature, respectively, without using computational assumptions. We for the first time show that the ideal signatures, ideal one-time signatures, and random oracles are equivalent in the framework of indifferentiability.

Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 b$ be an ordinary (i.e., non-supersingular) elliptic curve (of $j$-invariant $0$) such that $\sqrt{b} \in \mathbb{F}_{\!q}$ and $q \not\equiv 1 \: (\mathrm{mod} \ 27)$. For example, these conditions are fulfilled for the curve BLS12-381 ($b=4$). It is a de facto standard in the real world pairing-based cryptography at the moment. This article provides a new constant-time hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$...

Indifferentiability is used to analyze the security of constructions of idealized objects, such as random oracles or ideal ciphers. Reset indifferentiability is a strengthening of plain indifferentiability which is applicable in far more scenarios, but is often considered too strong due to significant impossibility results. Our main results are: - Under weak reset indifferentiability, ideal ciphers imply (fixed size) random oracles and random oracle domain shrinkage is possible. We thus...

The random oracle, generic group, and generic bilinear map models (ROM, GGM, GBM, respectively) are fundamental heuristics used to justify new computational assumptions and prove the security of efficient cryptosystems. While known to be invalid in some contrived settings, the heuristics generally seem reasonable for real-world applications. In this work, we ask: \emph{which heuristics are closer to reality?} Or conversely, which heuristics are a larger leap? We answer this question through...

In this paper we prove quantum indifferentiability of the sponge construction instantiated with random (invertible) permutations. With this result we bring the post-quantum security of the standardized SHA-3 hash function to the level matching its security against classical adversaries. To achieve our result, we generalize the compressed-oracle technique of Zhandry (Crypto'19) by defining and proving correctness of a compressed permutation oracle. We believe our technique will find...

Bernstein et al. recently introduced a system ``Elligator'' for steganographic key distribution. At the heart of their construction are invertible maps between a finite field $\mathbb{F}$ and an elliptic curve $\mathcal{E}$ over $\mathbb{F}$. There are two such maps, called $\phi$ in the ``Elligator 1'' system, and $\psi$ in the ``Elligator 2'' system. Here we show two ways to construct hash functions from $\psi$ which are indifferentiable from a random oracle. Because $\psi$ is relatively...

We provide a formal proof for the indifferentiability of SKINNY-HASH internal function from a random oracle. SKINNY-HASH is a family of function-based sponge hash functions, and it was selected as one of the second round candidates of the NIST lightweight cryptography competition. Its internal function is constructed from the tweakable block cipher SKINNY. The construction of the internal function is very simple and the designers claim $n$-bit security, where $n$ is the block length of...

In the backdoored random-oracle (BRO) model, besides access to a random function $H$, adversaries are provided with a backdoor oracle that can compute arbitrary leakage functions $f$ of the function table of $H$. Thus, an adversary would be able to invert points, find collisions, test for membership in certain sets, and more. This model was introduced in the work of Bauer, Farshim, and Mazaheri (Crypto 2018) and extends the auxiliary-input idealized models of Unruh (Crypto 2007), Dodis, Guo,...

Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 b$ be an ordinary elliptic $\mathbb{F}_{\!q}$-curve of $j$-invariant $0$ such that $\sqrt{b} \in \mathbb{F}_{\!q}$. In particular, this condition is fulfilled for the curve BLS12-381 and for one of sextic twists of the curve BW6-761 (in both cases $b=4$). These curves are very popular in pairing-based cryptography. The article provides an efficient constant-time encoding $h\!: \mathbb{F}_{\!q} \to E_b(\mathbb{F}_{\!q})$ of an...

We give a framework for relating the concrete security of a “reference” protocol (say, one appearing in an academic paper) to that of some derived, “real” protocol (say, appearing in a cryptographic standard). It is based on the indifferentiability framework of Maurer, Renner, and Holenstein (MRH), whose application has been exclusively focused upon non-interactive cryptographic primitives, e.g., hash functions and Feistel networks. Our extension of MRH is supported by a clearly defined...

In CRYPTO 2018, Russell et al. introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the $n$-bit to $n$-bit function implemented using enveloped XOR construction ($\mathsf{EXor}$) with $3n 1$ many $n$-bit functions and $3n^2$- bit random initial vectors (iv) can be proven secure asymptotically in the crooked indifferentiability setting. -We identify several major issues and gaps in the...

It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task (we call it oracle cloning) of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle...

We present a high-assurance and high-speed implementation of the SHA-3 hash function. Our implementation is written in the Jasmin programming language, and is formally verified for functional correctness, provable security and timing attack resistance in the EasyCrypt proof assistant. Our implementation is the first to achieve simultaneously the four desirable properties (efficiency, correctness, provable security, and side-channel protection) for a non-trivial cryptographic...

In this paper, we first give, to the best of our knowledge, the first exponential separation between the ROM and QROM. Technically, we will first present a simple and efficient quantum distinguisher $\cD_q$ which can recognize the QROM by making at most two quantum RO queries, and can only be cheated by an adversary making (sub-)exponential classical RO queries. This (sub-)exponential query gap allows us to remove the ``unit time'' and ``zero time'' assumptions that are crucially needed for...

Game-playing proofs constitute a powerful framework for non-quantum cryptographic security arguments, most notably applied in the context of indifferentiability. An essential ingredient in such proofs is lazy sampling of random primitives. We develop a quantum game-playing proof framework by generalizing two recently developed proof techniques. First, we describe how Zhandry's compressed quantum oracles~(Crypto'19) can be used to do quantum lazy sampling of a class of non-uniform function...

We initiate the study of indifferentiability for public key encryption and other public key primitives. Our main results are definitions and constructions of public key cryptosystems that are indifferentiable from ideal cryptosystems, in the random oracle model. Cryptosystems include Public key encryption, Digital signatures, Non-interactive key agreement. Our schemes are based on standard public key assumptions. By being indifferentiable from an ideal object, our schemes satisfy any...

We study Authenticated Encryption with Associated Data (AEAD) from the viewpoint of composition in arbitrary (single-stage) environments. We use the indifferentiability framework to formalize the intuition that a good AEAD scheme should have random ciphertexts subject to decryptability. Within this framework, we can then apply the indifferentiability composition theorem to show that such schemes offer extra safeguards wherever the relevant security properties are not known, or cannot be...

The quantum random oracle model (QROM) has become the standard model in which to prove the post-quantum security of random-oracle-based constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary's queries, a crucial feature of many classical ROM proofs, including all proofs of indifferentiability for hash function domain extension. In this work, we give a new QROM proof technique that overcomes this ``recording barrier''. ...

We study the indifferentiability of classical constructions in the quantum setting, such as the Sponge construction or Feistel networks. (But the approach easily generalizes to other constructions, too.) We give evidence that, while those constructions are known to be indifferentiable in the classical setting, they are not indifferentiable in the quantum setting. Our approach is based on an quantum-information-theoreoretical conjecture.

We study instantiating the random permutation of the block-cipher mode of operation IAPM (Integrity-Aware Parallelizable Mode) with the public random permutation of Keccak, on which the draft standard SHA-3 is built. IAPM and the related mode OCB are single-pass highly parallelizable authenticated-encryption modes, and while they were originally proven secure in the private random permutation model, Kurosawa has shown that they are also secure in the public random permutation model assuming...

Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the...

A number of cryptographic schemes are built from (keyless) permutations, which are either designed in an ad-hoc fashion or are obtained by fixing the key in a block cipher. Security proofs for these schemes, however, idealize this permutation, i.e., making it random and accessible, as an oracle, to all parties. Finding plausible concrete assumptions on such permutations that guarantee security of the resulting schemes has remained an elusive open question. This paper initiates the study of...

The iterated Even--Mansour (EM) ciphers form the basis of many block cipher designs. Several results have established their security in the CPA/CCA models, under related-key attacks, and in the indifferentiability framework. In this work, we study the Even--Mansour ciphers under key-dependent message (KDM) attacks. KDM security is particularly relevant for block ciphers since non-expanding mechanisms are convenient in setting such as full disk encryption (where various forms of...

Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression...

We prove that the 5-round iterated Even-Mansour (IEM) construction (which captures the high-level structure of the class of key-alternating ciphers) with a non-idealized key-schedule (such as the trivial key-schedule, where all round keys are equal) is indifferentiable from an ideal cipher. In a separate result, we also prove that five rounds are necessary by describing an attack against the corresponding 4-round construction. This closes the gap regarding the exact number of rounds for...

The concept of indifferentiability of systems, a generalized form of indistinguishability, was proposed in 2004 to provide a simplified and generalized explanation of impossibility results like the non-instantiability of random oracles by hash functions due to Canetti, Goldreich, and Halevi (STOC 1998). But indifferentiability is actually a constructive notion, leading to possibility results. For example, Coron {\em et al.} (Crypto 2005) argued that the soundness of the construction $C(f)$...

We revisit the Even-Mansour (EM) scheme with random oracle key derivation previously considered by Andreeva et al. (CRYPTO 2013). For this scheme, Andreeva et al. provided an indifferentiability (from an ideal $(k,n)$-cipher) proof for 5 rounds while they exhibited an attack for 2 rounds. Left open is the (in)differentiability of 3 and 4 rounds. We present a proof for the indifferentiability of 3 rounds and thus closing the aforementioned gap. This also separates EM ciphers with...

Ever since Keccak won the SHA3 competition, sponge-based constructions are being suggested for many different applications, including pseudo-random number generators (PRNGs). Sponges are very desirable, being well studied, increasingly efficient to implement and simplistic in their design. The initial construction of a sponge-based PRNG (Bertoni et al. CHES 2010) based its security on the well known sponge indifferentiability proof in the random permutation model and provided no forward...

BLAKE2 is a hash function introduced at ACNS 2013, which has been adopted in many constructions and applications. It is a successor to the SHA-3 finalist BLAKE, which received a significant amount of security analysis. Nevertheless, BLAKE2 introduces sufficient changes so that not all results from BLAKE carry over, meaning new analysis is necessary. To date, all known cryptanalysis done on BLAKE2 has focused on its underlying building blocks, with little focus placed on understanding...

Shannon defined an ideal $(\kappa,n)$-blockcipher as a secrecy system consisting of $2^{\kappa}$ independent $n$-bit random permutations. In this paper, we revisit the following question: in the ideal cipher model, can a cascade of several ideal $(\kappa,n)$-blockciphers realize an ideal $(2\kappa,n)$-blockcipher? The motivation goes back to Shannon's theory on product secrecy systems, and similar question was considered by Even and Goldreich (CRYPTO '83) in different settings. We give the...

A robust combiner for hash functions takes two candidate implementations and constructs a hash function which is secure as long as at least one of the candidates is secure. So far, hash function combiners only aim at preserving a single property such as collision-resistance or pseudorandomness. However, when hash functions are used in protocols like TLS they are often required to provide several properties simultaneously. We therefore put forward the notion of robust multi-property...

In recent work, Bellare, Hoang, and Keelveedhi (CRYPTO 2013) introduced a new abstraction called Universal Computational Extractors (UCEs), and showed how they can replace random oracles (ROs) across a wide range of cryptosystems. We formulate a new framework, called Interactive Computational Extractors (ICEs), that extends UCEs by viewing them as models of ROs under unpredictable (aka. high-entropy) queries. We overcome a number of limitations of UCEs in the new framework, and in particular...

We reconsider the formalization of known-key attacks against ideal primitive-based block ciphers. This was previously tackled by Andreeva, Bogdanov, and Mennink (FSE 2013), who introduced the notion of known-key indifferentiability. Our starting point is the observation, previously made by Cogliati and Seurin (EUROCRYPT 2015), that this notion, which considers only a single known key available to the attacker, is too weak in some settings to fully capture what one might expect from a block...

We prove that a balanced 8-round Feistel network is indifferentiable from a random permutation. This result comes on the heels of (and is part of the same body of work as) a 10-round indifferentiability result for Feistel network recently announced by the same team of authors. The current 8-round simulator achieves similar security, query complexity and runtime as the 10-round simulator and is not significantly more involved. The security of our simulator is also slightly better than the...

Holenstein et al. (STOC 2011) have shown that the Feistel construction with fourteen rounds and public random round functions is indifferentiable from a random permutation. In the same paper, they pointed out that a previous proof for the 10-round Feistel construction by Seurin (PhD thesis) was flawed. However, they left open the question of whether the proof could be patched (leaving hope that the simulator described by Seurin could still be used to prove indifferentiability of the 10-round...

We prove that a (balanced) 10-round Feistel network is indifferentiable from a random permutation. In a previous seminal result, Holenstein et al. had established indifferentiability of Feistel at 14 rounds. Our simulator achieves security $O(q^8/2^n)$ and query complexity $O(q^4)$, where $n$ is half the block length, similarly to the 14-round simulator of Holenstein et al., so that our result is a strict (and also the first) improvement of that work. Our simulator is very similar to a...

Iterated Even-Mansour scheme (IEM) is a generalization of the basic 1-round proposal (ASIACRYPT '91). The scheme can use one key, two keys, or completely independent keys. Most of the published security proofs for IEM against relate-key and chosen-key attacks focus on the case where all the round-keys are derived from a single master key. Whereas results beyond this barrier are relevant to the cryptographic problem whether a secure blockcipher with key-size twice the block-size can be built...

We show the first positive results for the indifferentiability security of the confusion-diffusion networks (which are extensively used in the design of block ciphers and hash functions). In particular, our result shows that a constant number of confusion-diffusion rounds is sufficient to extend the domain of a public random permutation.

Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it $c$~times, for some...

Known-key distinguishers for block ciphers were proposed by Knudsen and Rijmen at ASIACRYPT 2007 and have been a major research topic in cryptanalysis since then. A formalization of known-key attacks in general is known to be difficult. In this paper, we tackle this problem for the case of block ciphers based on ideal components such as random permutations and random functions as well as propose new generic known-key attacks on generalized Feistel ciphers. We introduce the notion of...

We define ideal functionalities that are weaker than ideal functionalities traditionally used in realizing variable input length (VIL) random oracles (RO) in the indifferentiability or universal-Composability (UC) model. We also show realization of VIL-RO using these weaker ideal functionalities, with applications to proving Fugue and CubeHash hash functions to be VIL-RO. We argue that components of Fugue realize this weaker ideal functionality using techniques employed in proving...

The iterated Even-Mansour cipher is a construction of a block cipher from $r$ public permutations $P_1,\ldots,P_r$ which abstracts in a generic way the structure of key-alternating ciphers. The indistinguishability of this construction from a truly random permutation by an adversary with oracle access to the inner permutations $P_1,\ldots,P_r$ has been investigated in a series of recent papers. This construction has also been shown to be (fully) indifferentiable from an ideal cipher for a...

The simplicity and widespread use of blockciphers based on the iterated Even--Mansour (EM) construction has sparked recent interest in the theoretical study of their security. Previous work has established their strong pseudorandom permutation and indifferentiability properties, with some matching lower bounds presented to demonstrate tightness. In this work we initiate the study of the EM ciphers under related-key attacks which, despite extensive prior work, has received little attention....

Feistel constructions have been shown to be indifferentiable from random permutations at STOC 2011. Whereas how to properly mix the keys into an un-keyed Feistel construction without appealing to domain separation technique to obtain a block cipher which is provably secure against known-key and chosen-key attacks (or to obtain an ideal cipher) remains an open problem. We study this, particularly the basic structure of NSA's SIMON family of block ciphers. SIMON family takes a construction...

The notion of indifferentiability, which is a stronger version of the classic notion of indistinguishability, was introduced by Maurer, Renner, and Holenstein in 2003. Indifferentiability, among other things, gives us a way of ``securely replacing" a random oracle of one type by a random oracle of a different type. Most indifferentiability proofs in the literature are very complicated, which makes them difficult to verify and in some cases, has even resulted in them being erroneous. In this...

This paper suggests and explores the use of UCE security for the task of turning VIL-ROM schemes into FIL-ROM ones. The benefits we offer over indifferentiability, the current leading method for this task, are the ability to handle multi-stage games and greater efficiency. The paradigm consists of (1) Showing that a VIL UCE function can instantiate the VIL RO in the scheme, and (2) Constructing the VIL UCE function given a FIL random oracle. The main technical contributions of the paper are...

The equivalence of the random-oracle model and the ideal-cipher model has been studied in a long series of results. Holenstein, Künzler, and Tessaro (STOC, 2011) have recently completed the picture positively, assuming that, roughly speaking, equivalence is indifferentiability from each other. However, under the stronger notion of reset indifferentiability this picture changes significantly, as Demay et al. (EUROCRYPT, 2013) and Luykx et al. (ePrint, 2012) demonstrate. We complement these...

We show that the second iterate H^2(M) = H(H(M)) of a random oracle H cannot achieve strong security in the sense of indifferentiability from a random oracle. We do so by proving that indifferentiability for H 2 holds only with poor concrete security by providing a lower bound (via an attack) and a matching upper bound (via a proof requiring new techniques) on the complexity of any successful simulator. We then investigate HMAC when it is used as a general-purpose hash function with...

We present the hash function BLAKE2, an improved version of the SHA-3 finalist BLAKE optimized for speed in software. Target applications include cloud storage, intrusion detection, or version control systems. BLAKE2 comes in two main flavors: BLAKE2b is optimized for 64-bit platforms, and BLAKE2s for smaller architectures. On 64-bit platforms, BLAKE2 is often faster than MD5, yet provides security similar to that of SHA-3: up to 256-bit collision resistance, immunity to length extension,...

The indifferentiability framework by Maurer, Renner and Holenstein (MRH; TCC 2004) formalizes a sufficient condition to safely replace a random oracle by a construction based on a (hopefully) weaker assumption such as an ideal cipher. Indeed, many indifferentiable hash functions have been constructed and could since be used in place of random oracles. Unfortunately, Ristenpart, Shacham, and Shrimpton (RSS; Eurocrypt 2011) discovered that for a large class of security notions, the MRH...

We show how to construct an ideal cipher with $n$-bit blocks and $n$-bit keys (\emph{i.e.} a set of $2^n$ public $n$-bit permutations) from a small constant number of $n$-bit random public permutations. The construction that we consider is the \emph{single-key iterated Even-Mansour cipher}, which encrypts a plaintext $x\in\{0,1\}^n$ under a key $k\in\{0,1\}^n$ by alternatively xoring the key $k$ and applying independent random public $n$-bit permutations $P_1,\ldots, P_r$ (this construction...

A combiner for collision-resistant hash functions takes two functions as input and implements a hash function with the guarantee that it is collision-resistant if one of the functions is. It has been shown that such a combiner cannot have short output (Pietrzak, Crypto 2008); that is, its output length is lower bounded by roughly $2n$ if the ingoing functions output $n$-bit hash values. In this paper, we present two novel definitions for hash function combiners that allow to bypass the...

We present an efficient key wrapping scheme that uses a single wide permutation and does not rely on block ciphers. The scheme is capable of wrapping keys up to 1400 bits long and processing arbitrarily long headers. Our scheme easily delivers the security level of 128 bits or higher with the master key of the same length. The permutation can be taken from the sponge hash functions such as SHA-3 (Keccak), Quark, Photon, Spongent. We also present a simple proof of security within the...

The Advanced Encryption Standard (AES) is the most widely used block cipher. The high level structure of AES can be viewed as a (10-round) key-alternating cipher, where a t-round key-alternating cipher KA_t consists of a small number $t$ of fixed permutations P_i on n bits, separated by key addition: KA_t(K,m)= k_t P_t(... k_2 P_2(k_1 P_1(k_0 m))...), where (k_0,...,k_t) are obtained from the master key K using some key derivation function. For t=1, KA_1 collapses to the...

In a digital signature scheme with message recovery, rather than transmitting the message $m$ and its signature $\sigma$, a single enhanced signature $\tau$ is transmitted. The verifier is able to recover $m$ from $\tau$ and at the same time verify its authenticity. The two most important parameters of such a scheme are its security and overhead $|\tau|-|m|$. A simple argument shows that for any scheme with ``$n$ bits security" $|\tau|-|m|\ge n$, i.e., the overhead is lower bounded by the...

In this work we present a modification of a well-established measure of dependence appropriate for the analysis of stopping times for adversarial processes on cryptographic primitives. We apply this measure to construct generic criteria for the ideal behavior of fixed functions in both the random oracle and ideal permutation setting. More significantly, we provide a nontrivial extension of the notion of hash function indifferentiability, transporting the theory from the status of providing...

The indifferentiability framework of Maurer, Renner, and Holenstein (MRH) has gained immense popularity in recent years and has proved to be a powerful way to argue security of cryptosystems that enjoy proofs in the random oracle model. Recently, however, Ristenpart, Shacham, and Shrimpton (RSS) showed that the composition theorem of MRH has a more limited scope than originally thought, and that extending its scope required the introduction of reset-indifferentiability, a notion which no...

A major general paradigm in cryptography is the following argument: Whatever an adversary could do in the real world, it could just as well do in the ideal world. The standard interpretation of ``just as well'' is that the translation from the real to the ideal world, usually called a simulator, is achieved by a probabilistic polynomial-time algorithm. This means that a polynomial blow-up of the adversary's time and memory requirements is considered acceptable. In certain contexts this...

The contribution of the paper is two-fold. First, we design a novel permutation-based hash mode of operation FP, and analyze its security. The FP mode is derived by replacing the hard-to-invert primitive of the FWP mode -- designed by Nandi and Paul, Indocrypt 2010 -- with an easy-to-invert permutation; since easy-to-invert permutations with good cryptographic properties are normally easier to design, and are more efficient than the hard-to-invert functions, the FP mode is more suitable in...

In the recent years, several hash constructions have been introduced that aim at achieving enhanced security margins by strengthening the Merkle-Damgård mode. However, their security analysis have been conducted independently and using a variety of proof methodologies. This paper unifies these results by proposing a unique indifferentiability proof that considers a broadened form of the general compression function introduced by Stam at FSE09. This general definition enables us to capture in...

Indifferentiability security of a hash mode of operation guarantees the mode's resistance against all (meaningful) generic attacks. It is also useful to establish the security of protocols that use hash functions as random functions. The JH hash function is one of the five finalists in the ongoing NIST SHA-3 hash function competition. Despite several years of analysis, the indifferentiability security of the JH mode (with n-bit digest and 2n-bit permutation) has remained remarkably low, only...

In the last few years, the need to design new cryptographic hash functions has led to the intense study of when desired hash multi-properties are preserved or assured under compositions and domain extensions. In this area, it is important to identify the exact notions and provide often complex proofs of the resulting properties. Getting this analysis right (as part of provable security studies) is, in fact, analogous to cryptanalysis. We note that it is important and quite subtle to get...

This paper develops a theory of multi-instance (mi) security and applies it to provide the first proof-based support for the classical practice of salting in password-based cryptography. Mi-security comes into play in settings (like password-based cryptography) where it is computationally feasible to compromise a single instance, and provides a second line of defense, aiming to ensure (in the case of passwords, via salting) that the effort to compromise all of some large number $m$ of...

Ristenpart et al. showed that the limitation of the indifferentiability theorem of Maurer et al. which does not cover all multi stage security notions but covers only single stage security notions, defined a new concept (reset indifferentiability), and proved the reset indifferentiability theorem, which is an analogy of the indifferentiability theorem covers all security notions S: if H^U is reset indifferentiable from RO, for any security notion, a cryptosystem C is at least as secure in...

Most of today's popular hash functions are keyless such that they accept variable-length messages and return fixed-length fingerprints. However, recent separation results reported on several serious inherent weaknesses in these functions, motivating the design of hash functions in the keyed setting. The challenge in this case, however, is that on one hand, it is economically undesirable to abundant the already adopted (keyless) functions in favour of new (keyed) ones, and on the other hand,...

A hash function secure in the indifferentiability framework (TCC 2004) is able to resist all meaningful generic attacks. Such hash functions also play a crucial role in establishing the security of protocols that use them as random functions. To eliminate multi-collision type attacks on the MD mode (Crypto 1989), Lucks proposed widening the size of the internal state of hash functions. More specifically, he suggested that hash functions h:{0,1}*->{0,1}^n use underlying primitives of the...

The hash algorithm BLAKE, one of the SHA-3 finalists, was designed by Aumasson, Henzen, Meier, and Phan. Unlike other SHA-3 finalists, there is no known indifferentiable security proof on BLAKE. In this paper, we provide the indifferentiable security proof on BLAKE with the bound O(\delta^2/2^{n-3}), where \delta is the total number of blocks of queries, and n is the hash output size.

We analyze the security of the SHA-3 finalist BLAKE. The BLAKE hash function follows the HAIFA design methodology, and as such it achieves optimal preimage, second preimage and collision resistance, and is indifferentiable from a random oracle up to approximately 2^{n/2} assuming the underlying compression function is ideal. In our work we show, however, that the compression function employed by BLAKE exhibits a non-random behavior and is in fact differentiable in only 2^{n/4} queries. Our ...

We show that the Feistel construction with six rounds and random round functions is publicly indifferentiable from a random invertible permutation (a result that is not known to hold for full indifferentiability). Public indifferentiability (pub-indifferentiability for short) is a variant of indifferentiability introduced by Yoneyama et al. \cite{YoneyamaMO09} and Dodis et al. \cite{DodisRS09} where the simulator knows all queries made by the distinguisher to the primitive it tries to...

In this paper we give a generic security proof for hashing modes that make use of an underlying fixed-length permutation. We formulate a set of five simple conditions, which are easy to implement and to verify, for such a hashing mode to be sound. These hashing modes include tree hashing modes and sequential hashing modes. We provide a proof that for any hashing mode satisfying the five conditions, the advantage in differentiating it from an ideal monolithic hash function is upper bounded by...

We exhibit a hash-based storage auditing scheme which is provably secure in the random-oracle model (ROM), but easily broken when one instead uses typical indifferentiable hash constructions. This contradicts the widely accepted belief that the indifferentiability composition theorem applies to any cryptosystem. We characterize the uncovered limitation of the indifferentiability framework by show- ing that the formalizations used thus far implicitly exclude security notions captured by...

Sponge functions were introduced by Bertoni et al. as an alternative to the classical Merkle-Damgaard design. Many hash function submissions to the SHA-3 competition launched by NIST in 2007, such as CubeHash, Fugue, Hamsi, JH, Keccak and Luffa, derive from the original sponge design, and security guarantees from some of these constructions are typically based on indifferentiability results. Although indifferentiability proofs for these designs often bear significant similarities, these have...