Succinct non-interactive arguments for bounded depth computations

We construct a succinct non-interactive publicly-verifiable delegation scheme for any logspace uniform circuit under the sub-exponential Learning With Errors (LWE) assumption. For a circuit C : {0, 1}^N → {0, 1} of size S and depth D, the prover runs in time poly(S), the communication complexity is D · polylog(S), and the verifier runs in time (D + N) · polylog(S). To obtain this result, we introduce a new cryptographic primitive: a lossy correlation-intractable hash function family. 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 Goldwasser-Kalai-Rothblum (GKR) protocol, assuming the subexponential hardness of LWE. Additionally, by relying on the result of Choudhuri et al. (STOC 2019), we establish (sub-exponential) average-case hardness of PPAD, assuming the sub-exponential hardness of LWE.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Jawale, Ruta S

Contributors dc:contributor

• Khurana, Dakshita

• cryptography
• cryptographic protocols
• delegation schemes
• non-interactive
• Fiat-Shamir
• sum-check
• GKR
• PPAD
• lossy
• correlation intractability

Statement dc:rights

• Copyright 2022 Ruta Jawale

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/116136

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F116136