Paper 2016/812

Towards Non-Black-Box Separations of Public Key Encryption and One Way Function

Dana Dachman-Soled


Separating public key encryption from one way functions is one of the fundamental goals of complexity-based cryptography. Beginning with the seminal work of Impagliazzo and Rudich (STOC, 1989), a sequence of works have ruled out certain classes of reductions from public key encryption (PKE)---or even key agreement---to one way function. Unfortunately, known results---so called black-box separations---do not apply to settings where the construction and/or reduction are allowed to directly access the code, or circuit, of the one way function. In this work, we present a meaningful, non-black-box separation between public key encryption (PKE) and one way function. Specifically, we introduce the notion of $\textsf{BBN}^-$ reductions (similar to the $\textsf{BBN}\text{p}$ reductions of Baecher et al. (ASIACRYPT, 2013)), in which the construction $E$ accesses the underlying primitive in a black-box way, but wherein the universal reduction $R$ receives the efficient code/circuit of the underlying primitive as input and is allowed oracle access to the adversary $\textsf{Adv}$. We additionally require that the number of oracle queries made to $\textsf{Adv}$, and the success probability of $R$ are independent of the run-time/circuit size of the underlying primitive. We prove that there is no non-adaptive, $\textsf{BBN}^-$ reduction from PKE to one way function, under the assumption that certain types of strong one way functions exist. Specifically, we assume that there exists a regular one way function $f$ such that there is no Arthur-Merlin protocol proving that ``$z \not\in \textsf{Range}(f)$'', where soundness holds with high probability over ``no instances,'' $y \sim f(U_n)$, and Arthur may receive polynomial-sized, non-uniform advice. This assumption is related to the average-case analogue of the widely believed assumption $\textbf{coNP} \not\subseteq \textbf{NP}/\textbf{poly}$.

Available format(s)
Publication info
Published by the IACR in TCC 2016
black-box separationpublic key encryptionone-way function
Contact author(s)
danadach @ ece umd edu
2016-08-25: received
Short URL
Creative Commons Attribution


      author = {Dana Dachman-Soled},
      title = {Towards Non-Black-Box Separations of Public Key Encryption and One Way Function},
      howpublished = {Cryptology ePrint Archive, Paper 2016/812},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.