Scrutinizing Black-Box Separations in (Quantum) Cryptography
Final Report Abstract
The project investigates the strength and limitations of black-box reductions in cryptography. Reductions are a common construction and proof technique which allow to base the security of complex protocols onto well-established cryptographic primitives, yielding security of the protocol under the usually justified assumption that the primitives are secure. Formally, one shows that any adversary attacking the protocol can be turned via a reduction into a successful attack against the underlying primitive. A common paradigm for cryptographic reductions are so-called black-box reductions which are general-purpose reductions which work with any instances of the adversary and primitives. The term black-box reduction originates from the property that the reduction only considers the adversary and primitives as abstract items with a pre-specified input-output behavior, but neglecting any internal details of these items. While such black-box reductions have proven to be applicable in a vast number of scenarios, there are yet a few examples where the technique fails to yield proofs. This is often interpreted as an indication that the protocol cannot be constructed securely from the primitives. The proposal looks into cases where the limitations of black-box reductions can be -or cannot berelaxed. This can be tackled by looking into “semi-black-box” reductions which, for instance, take advantage of knowledge of the internal randomness of the adversary, or by switching to non-uniform models and using auxiliary input. The goal is to get a better understanding of the reduction technique itself and to apply the new ideas in known protocol cases. As a result of the proposal we show that proving the well-known Fiat-Shamir proofs as well as the signed ElGamal encryption scheme to be secure in the random oracle model cannot be done in general in a black-box way. At the same time, using stronger assumptions about the primitives (and the ability to interfere with the randomness of the adversary) one can show signed ElGamal to be secure.
Publications
- Cryptographic Reductions: Classification and Applications to Ideal Models, Dissertation, TU Darmstadt
Paul Baecher
- Adaptive Proofs of Knowledge in the Random Oracle Model. Public Key Cryptography, LNCS pp. 629-649, Springer-Verlag, 2015
David Bernhard, Marc Fischlin, Bogdan Warinschi
- On the Hardness of Proving CCA-Security of Signed ElGamal. Public Key Cryptography (1), LNCS, pp.47-69, Springer-Verlag, 2016
David Bernhard, Marc Fischlin, Bogdan Warinschi
