To obtain this result, we introduce a new cryptographic primitive: lossy correlation-intractable hash functions. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the $\mathsf{GKR}$ protocol, assuming the sub-exponential hardness of $\mathsf{LWE}$.
By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of $\mathsf{PPAD}$, assuming the sub-exponential hardness of $\mathsf{LWE}$.
Category / Keywords: cryptographic protocols / delegation schemes, non-interactive, Fiat-Shamir, sum-check, GKR, PPAD, lossy, correlation intractability Date: received 13 Aug 2020, last revised 18 Aug 2020 Contact author: jawale2 at illinois edu,yael@microsoft com,dakshita@illinois edu,rachelyz44@gmail com Available format(s): PDF | BibTeX Citation Version: 20200819:035531 (All versions of this report) Short URL: ia.cr/2020/980