Cryptology ePrint Archive: Report 2020/911

Lossy Correlation Intractability and PPAD Hardness from Sub-exponential LWE

Ruta Jawale and 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.

Category / Keywords: foundations / correlation intractability, lossy functions, sumcheck, delegation, PPAD

Date: received 20 Jul 2020, last revised 28 Jul 2020

Contact author: jawale2 at illinois edu,dakshita@illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20200728:183423 (All versions of this report)

Short URL: ia.cr/2020/911


[ Cryptology ePrint archive ]