Paper 2016/812
Towards NonBlackBox Separations of Public Key Encryption and One Way Function
Dana DachmanSoled
Abstract
Separating public key encryption from one way functions is one of the fundamental goals of complexitybased 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 agreementto one way function. Unfortunately, known resultsso called blackbox separationsdo 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, nonblackbox 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 blackbox 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 runtime/circuit size of the underlying primitive. We prove that there is no nonadaptive, $\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 ArthurMerlin 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 polynomialsized, nonuniform advice. This assumption is related to the averagecase analogue of the widely believed assumption $\textbf{coNP} \not\subseteq \textbf{NP}/\textbf{poly}$.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in TCC 2016
 Keywords
 blackbox separationpublic key encryptiononeway function
 Contact author(s)
 danadach @ ece umd edu
 History
 20160825: received
 Short URL
 https://ia.cr/2016/812
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/812, author = {Dana DachmanSoled}, title = {Towards NonBlackBox Separations of Public Key Encryption and One Way Function}, howpublished = {Cryptology ePrint Archive, Paper 2016/812}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/812}}, url = {https://eprint.iacr.org/2016/812} }