Welcome to the resource topic for 2020/911
Title:
Lossy Correlation Intractability and PPAD Hardness from Sub-exponential LWE
Authors: Ruta Jawale, Dakshita Khurana
Abstract:We introduce a new cryptographic primitive, a lossy correlation-intractable hash function, and use it to soundly instantiate the Fiat-Shamir transform for the general interactive sumcheck protocol, assuming sub-exponential hardness of the Learning with Errors (LWE) problem. By combining this with the result of Choudhuri et al. (STOC 2019), we show that \#\mathsf{SAT} reduces to end-of-line, which is a \mathsf{PPAD}-complete problem, assuming the sub-exponential hardness of LWE.
ePrint: https://eprint.iacr.org/2020/911
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 .