Welcome to the resource topic for 2023/1049
Title:
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method
Authors: Andrej Bogdanov, Pravesh Kothari, Alon Rosen
Abstract:The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.
We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new public-key encryption scheme whose security is based on Goldreich’s pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.
ePrint: https://eprint.iacr.org/2023/1049
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 .