Paper 2016/1107

Magic Adversaries Versus Individual Reduction: Science Wins Either Way

Yi Deng

Abstract

We prove that, assuming there exists an injective one-way function $f$, \emph{at least} one of the following statements is true: \begin{itemize} \item (Infinitely-often) Non-uniform public-key encryption and key agreement exist; \item The Feige-Shamir protocol instantiated with $f$ is distributional concurrent zero knowledge for a large class of distributions over any OR NP-relations with small distinguishability gap. \end{itemize} The questions of whether we can achieve these goals are known to be subject to black-box limitations. Our win-win result also establishes an unexpected connection between the complexity of public-key encryption and the round-complexity of concurrent zero knowledge. As the main technical contribution, we introduce a dissection procedure for concurrent adversaries, which enables us to transform a magic concurrent adversary that breaks the distributional concurrent zero knowledge of the Feige-Shamir protocol into non-black-box constructions of (infinitely-often) public-key encryption and key agreement. This dissection of complex algorithms gives insight into the fundamental gap between the known \emph{universal} security reductions/simulations, in which a single reduction algorithm or simulator works for \emph{all} adversaries, and the natural security definitions (that are sufficient for almost all cryptographic primitives/protocols), which switch the order of qualifiers and only require that for every adversary there \emph{exists} an \emph{individual} reduction or simulator.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
universal reductionindividual reductionblack-box separationsconcurrent zero knowledge
Contact author(s)
deng @ iie ac cn
History
2017-02-15: revised
2016-11-25: received
See all versions
Short URL
https://ia.cr/2016/1107
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1107,
      author = {Yi Deng},
      title = {Magic Adversaries Versus Individual Reduction: Science Wins Either Way},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1107},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1107}},
      url = {https://eprint.iacr.org/2016/1107}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.