Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-195 | 28th November 2024 15:32

On White-Box Learning and Public-Key Encryption

RSS-Feed




TR24-195
Authors: Yanyi Liu, Noam Mazor, Rafael Pass
Publication: 29th November 2024 19:15
Downloads: 107
Keywords: 


Abstract:

We consider a generalization of the Learning With Error problem, referred to as the white-box learning problem: You are given the code of a sampler that with high probability produces samples of the form $y, f (y) + \epsilon$ where $\epsilon$ is small, and $f$ is computable in polynomial-size, and the computational task consist of outputting a polynomial-size circuit C that with probability, say, 1/3 over a new sample $y?$ according to the same distributions, approximates $f(y?)$ (i.e., $|C(y?) ? f (y?)|$ is small). This problem can be thought of as a generalizing of the Learning with Error Problem (LWE) from linear functions f to polynomial-size computable functions.

We demonstrate that worst-case hardness of the white-box learning problem, conditioned on the instances satisfying a notion of computational shallowness (a concept from the study of Kolmogorov complexity) not only suffices to get public-key encryption, but is also necessary; as such, this yields the first problem whose worst-case hardness characterizes the existence of public-key encryption. Additionally, our results highlights to what extent LWE “overshoots” the task of public-key encryption.

We complement these results by noting that worst-case hardness of the same problem, but restricting the learner to only get black-box access to the sampler, characterizes one-way functions.



ISSN 1433-8092 | Imprint