2026-09-22T14:02:58Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/116136 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Khurana, Dakshita 2022-08 application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms The student, Ruta Jawale, accepted the attached license on 2022-04-21 at 18:40. The student, Ruta Jawale, submitted this Thesis for approval on 2022-04-21 at 19:00. This Thesis was approved for publication on 2022-04-25 at 14:43. DSpace SAF Submission Ingestion Package generated from Vireo submission #17902 on 2022-11-15 at 17:37:23 Succinct non-interactive arguments for bounded depth computations Jawale, Ruta S 2022-04-25 cryptography cryptographic protocols delegation schemes non-interactive Fiat-Shamir sum-check GKR PPAD lossy correlation intractability 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. Thesis eng https://hdl.handle.net/2142/116136 Copyright 2022 Ruta Jawale M.S. Thesis Computer Science University of Illinois at Urbana-Champaign Computer Science