Crypto Seminar - Yanyi Liu February 20, 2025 4:30pm — 5:30pm Location: In Person and Virtual - ET - Gates Hillman 8215 and Zoom Speaker: YANYI LIU , Ph.D. Student in Computer Science, Cornell Tech, Cornell University https://www.cs.cornell.edu/~yanyiliu/ White-Box Learning and Public-Key Encryption 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 consists 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 generalization 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 highlight 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. In Person and Zoom Participation. See announcement. Event Website: https://sites.google.com/view/crypto-seminar/home Add event to Google Add event to iCal
