Crypto Seminar
— 5:30pm
Location:
In Person and Virtual - ET
-
Blelloch-Skees Conference Room, Gates Hillman 8115 and Zoom
Speaker:
ABHIRAM KOTHAPALLI
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://abhiramkothapalli.github.io/
HyperNova: Recursive arguments for customizable constraint
We introduce HyperNova, a recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023), a customizable constraint system that simultaneously generalizes Plonkish, R1CS, and AIR without overheads. A distinguishing aspect of HyperNova is that the prover’s cost at each step is dominated by a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme.
To construct HyperNova, we generalize folding schemes (CRYPTO 22), to allow instances from two (potentially) different NP relations, that share the same structure, to be folded; we refer to this generalization as multi-folding schemes. Furthermore, we devise a public-coin, multi-folding scheme for instances in CCS and linearized CCS (a variant of CCS that we introduce). This construction can be viewed as an “early stopping” version of Spartan (CRYPTO 20), applied to a carefully-crafted polynomial that includes claims about prior linearized CCS instances.
The prover’s work in the multi-folding scheme is a linear number of finite field operations and the verifier’s work is a logarithmic number of finite field operations and a single group scalar multiplication. We then construct incrementally verifiable computation (IVC) from non-interactive multi-folding schemes with the lowest prover costs and the lowest recursion overheads in the literature.
In Person and Zoom Participation. See announcement.
Event Website:
https://sites.google.com/view/crypto-seminar/home