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

*Dana Dachman-Soled*

**Abstract: **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}$.

**Category / Keywords: **black-box separation, public key encryption, one-way function

**Original Publication**** (in the same form): **IACR-TCC B--2016

**Date: **received 23 Aug 2016, last revised 25 Aug 2016

**Contact author: **danadach at ece umd edu

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

**Version: **20160825:183514 (All versions of this report)

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

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]