Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR17-003 | 9th January 2017 02:46

#### Magic Adversaries Versus Individual Reduction: Science Wins Either Way

Revision #1
Authors: Yi Deng
Accepted on: 9th January 2017 02:46
Keywords:

Abstract:

We prove that, assuming there exists an injective one-way function $f$, \emph{at least} one of the following statements is true:

--(Infinitely-often) Public-key encryption and key agreement exist;
-- For any inverse polynomial $\epsilon$, the 4-round classic Feige-Shamir protocol based on $f$ is distributional concurrent zero knowledge for any efficiently samplable distribution over any OR NP-relations with distinguishability gap bounded by $\epsilon$.
\end{itemize}

Both these statements have been shown to be unprovable [Impagliazzo and Rudich, STOC 89; Canetti et. al., STOC 01] via black-box reduction. 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 $\epsilon$-distributional concurrent zero knowledge of the Feige-Shamir protocol into an (infinitely-often) public-key encryption and key agreement.

This dissection of adversary algorithms gives insight into the fundamental gap between the known \emph{universal} security reduction that works for \emph{any} adversaries, and the security definition (of almost all cryptographic primitives/protocols), which switches the order of qualifiers and only requires that for every adversary there \emph{exists} an \emph{individual} reduction. If it could be proved that the reduction from injective one-way functions to public-key encryption does not exist, then our dissection reveals that all possible concurrent verifiers for the Feige-Shamir protocol share a common \emph{structure} in their computation, that would permit us to show the existence of individual simulation and prove the above second statement.

Changes to previous version:

Main changes:
1. Fixed some typos;
2. For the sake of clarity, we revised section 3 using the term "circuit family" (rather than "non-uniform algorithm").
3. Abstract and introduction were also revised slightly.

### Paper:

TR17-003 | 24th November 2016 03:08

#### Magic Adversaries Versus Individual Reduction: Science Wins Either Way

TR17-003
Authors: Yi Deng
Publication: 8th January 2017 16:41
Keywords:

Abstract:

We prove that \emph{at least} one of the following statements is true:

-- (Infinitely-often) Public-key encryption and key agreement can be based on injective one-way functions;
-- For every inverse polynomial $\epsilon$, the 4-round protocol from [Feige and Shamir, STOC 90] is distributional concurrent zero knowledge for any efficiently samplable distribution over any OR NP-relations with distinguishability gap bounded by $\epsilon$.

Both these statements have been shown to be unprovable [Impagliazzo and Rudich, STOC 89; Canetti et. al., STOC 01] via black-box reduction. 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 show that, if there is a magic concurrent adversary that breaks the $\epsilon$-distributional concurrent zero knowledge of the Feige-Shamir protocol for some OR NP-relations, then we transform it to an (infinitely-often) public-key encryption and key agreement based on injective one-way functions. If it could be proved that the reduction from injective one-way functions to public-key encryption does not exist, then our dissection reveals that all possible concurrent verifiers for the Feige-Shamir protocol share a common structure in their computation.

This dissection of adversary algorithms also gives insight into the fundamental gap between the known \emph{universal} security reduction that works for \emph{any} adversaries, and the security definition (of almost all cryptographic primitives/protocols), which switches the order of qualifiers and only requires that for every adversary there \emph{exists} an \emph{individual} reduction.

ISSN 1433-8092 | Imprint