Indifferentiability
A construction that uses an ideal primitive is indifferentiable from an ideal primitive if a simulator with access to can play the role of so that no efficient distinguisher, given both the honest interface ( or ) and the adversarial interface ( or the simulator), can tell the two worlds apart — MRH04.
Definition
Let and be ideal primitives, each a distribution over oracles (for instance a random oracle , or an ideal cipher queried in both directions), and let be an efficient oracle algorithm.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{indiff}}_{C,\Sim,\calA}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$; $G \getsr \calG$; $F \getsr \calF$
\State $\calO^{\mathrm{priv}}_0 := C^{G}$; $\calO^{\mathrm{pub}}_0 := G$
\Comment{real: the construction and its primitive}
\State $\calO^{\mathrm{priv}}_1 := F$; $\calO^{\mathrm{pub}}_1 := \Sim^{F}$
\Comment{ideal: $\Sim$ sees only its own queries to $F$}
\State $b' \gets \calA^{\calO^{\mathrm{priv}}_b, \calO^{\mathrm{pub}}_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
is indifferentiable from if there is an efficient, stateful simulator such that for all efficient ,
is negligible — MRH04; the formulation for hash functions is that of CDMP05. Concrete statements bound the advantage of , and the running time and query count of , in terms of the number of queries of — standard. Indistinguishability of from for an without access to is weaker; indifferentiability is the notion needed when the adversary also queries , as it does in every idealized model — standard.
Composition
If is indifferentiable from , then a scheme that is secure when it and the adversary use remains secure when it uses and the adversary uses : an adversary against the scheme with becomes the adversary against the scheme with — MRH04. The theorem covers single-stage games, where the adversary is one algorithm with one state. It does not extend to multi-stage games in general, whose adversary consists of stages that cannot share state freely: a hash-based proof-of-storage protocol is secure with a random oracle but not with several indifferentiable Merkle–Damgård variants, because the prover can store a chaining value in place of the file; the stronger notion of reset indifferentiability restores composition for multi-stage games, but practical hash constructions are not reset indifferentiable — RSS11.
Constructions
- Merkle–Damgård. Plain Merkle–Damgård over a fixed-input-length random oracle is not indifferentiable from a random oracle, because of length extension: determines for every . Prefix-free Merkle–Damgård, chopped Merkle–Damgård (dropping enough output bits), and NMAC- and HMAC-style constructions are indifferentiable from a random oracle when the compression function is a fixed-input-length random oracle, and also when it is Davies–Meyer over an ideal cipher — CDMP05.
- Sponge. The sponge construction over a random permutation or random transformation of width is indifferentiable from a random oracle, with advantage , where is the total number of calls to the permutation or transformation that the distinguisher’s queries cost, is the rate and the capacity — BDPV08.
- Feistel. A Feistel network whose round functions are independent random oracles (keyed by the cipher key, for an ideal cipher) is indifferentiable from a random permutation, or an ideal cipher, with enough rounds. CPS08 claimed six rounds; HKT11 showed that proof flawed and proved fourteen rounds suffice. Ten rounds suffice for an ideal cipher — DKT16; eight rounds suffice for a random permutation — DS16a.
With the Davies–Meyer result of CDMP05, the Feistel result makes the random-oracle model and the ideal-cipher model equivalent for single-stage games: each primitive is indifferentiably constructible from the other — HKT11.