Paper 2015/374

On the Impossibility of Tight Cryptographic Reductions

Christoph Bader, Tibor Jager, Yong Li, and Sven Schäge

Abstract

The existence of tight reductions in cryptographic security proofs is an important question, motivated by the theoretical search for cryptosystems whose security guarantees are truly independent of adversarial behavior and the practical necessity of concrete security bounds for the theoretically-sound selection of cryptographic parameters. At Eurocrypt 2002, Coron described a meta-reduction technique that allows to prove the impossibility of tight reductions for certain digital signature schemes. This seminal result has found many further interesting applications. However, due to a technical subtlety in the argument, the applicability of this technique beyond digital signatures in the single-user setting has turned out to be rather limited. We describe a new meta-reduction technique for proving such impossibility results, which improves on known ones in several ways. First, it enables interesting novel applications. This includes a formal proof that for certain cryptographic primitives (including public-key encryption/key encapsulation mechanisms and digital signatures), the security loss incurred when the primitive is transferred from an idealized single-user setting to the more realistic multi-user setting is impossible to avoid, and a lower tightness bound for non-interactive key exchange protocols. Second, the technique allows to rule out tight reductions from a very general class of non-interactive complexity assumptions. Third, the provided bounds are quantitatively and qualitatively better, yet simpler, than the bounds derived from Coron's technique and its extensions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Keywords
tight securityimpossibilitymeta-reduction
Contact author(s)
sven schaege @ rub de
History
2016-03-07: last of 4 revisions
2015-04-24: received
See all versions
Short URL
https://ia.cr/2015/374
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/374,
      author = {Christoph Bader and Tibor Jager and Yong Li and Sven Schäge},
      title = {On the Impossibility of Tight Cryptographic Reductions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/374},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/374}},
      url = {https://eprint.iacr.org/2015/374}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.