**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.

**Category / Keywords: **foundations / universal reduction; individual reduction;black-box separations; concurrent zero knowledge

**Original Publication**** (with minor differences): **IACR-EUROCRYPT-2017

**Date: **received 23 Nov 2016, last revised 15 Feb 2017

**Contact author: **deng at iie ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20170215:160758 (All versions of this report)

**Short URL: **ia.cr/2016/1107

[ Cryptology ePrint archive ]