2026-07-23T03:27:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22701 2026-04-17T05:32:30Z ddc:004 open_access

On White-Box Learning and Public-Key Encryption Liu, Yanyi Mazor, Noam Pass, Rafael Public-Key Encryption White-Box Learning 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) + ε where ε 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yanyi Liu and Noam Mazor and Rafael Pass 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.73 urn:nbn:de:0030-drops-227012 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.73 eng https://creativecommons.org/licenses/by/4.0/legalcode