Welcome to the resource topic for 2016/812
Title:
Towards Non-Black-Box Separations of Public Key Encryption and One Way Function
Authors: 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}.
ePrint: https://eprint.iacr.org/2016/812
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .