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