Bay Area Crypto Day
Sep 22, 2023
Sep 22, 2023
9:30am: Breakfast
10:00am: Welcome
10:10am: James Bartusek (UCB)
Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)
10:40am: Binyi Chen (Espresso Systems)
ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols
11:10am: Coffee Break
11:40am: Stefano Tessaro (UW)
Concurrently Secure Blind Signatures in Pairing-Free Groups
12:40pm: Lunch
2:10pm: Arka Rai Choudhuri (NTT Research)
SublonK: Sublinear Prover PlonK
2:40pm: Lior Rotem Benvenisty (Stanford)
Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-randomizable Commitments
3:10pm: Coffee Break
3:40pm: Peter Rindal (Visa)
Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN
4:10pm: Sruthi Sekar (UCB)
zkSaaS: Zero-Knowledge SNARKs as a Service
Speaker: James Bartusek (UCB)
Title: Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)
Abstract:
In this talk, we will consider a model for secure computation in which parties are initialized with shared entanglement in the form of EPR pairs. First, we will show that this setup allows for the possibility of one-shot cryptographic protocols. In particular, we construct a one-message string oblivious transfer protocol with random receiver bit, assuming the sub-exponential hardness of LWE. Such an OT protocol can then be used to obtain one-message secure computation of general unidirectional classical and quantum functionalities. Next, we will consider the multiparty setting, and show how to construct a two-round (round-optimal) MPC in this model from the black-box use of hash functions.
Based on joint work with Dakshita Khurana and Akshayaram Srinivasan
Speaker: Binyi Chen (Espresso Systems)
Title: ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols
Abstract:
Accumulation is a simple yet powerful primitive that enables incrementally verifiable computation (IVC) without the need for recursive SNARKs. We provide a generic, efficient accumulation (or folding) scheme for any (2k-1)-move special-sound protocol with a verifier that checks l degree-d equations. The accumulation verifier only performs k+2 elliptic curve multiplications and k+d+O(1) field/hash operations. This enables building efficient IVC schemes where the recursive circuit only depends on the number of rounds and the verifier degree of the underlying special-sound protocol but not the proof size or the verifier time. We use our generic accumulation compiler to build ProtoStar. ProtoStar is a non-uniform IVC scheme that supports high-degree gates and (vector) lookups. The recursive circuit is dominated by 3 group scalar multiplications and a hash of d* field elements, where d* is the degree of the highest gate. The scheme does not require a trusted setup or pairings, and the prover does not need to compute any FFTs. The prover in each accumulation/IVC step is also only logarithmic in the number of supported circuits and independent of the table size in the lookup.
Speaker: Stefano Tessaro (UWash)
Title: Concurrently Secure Blind Signatures in Pairing-Free Groups
Abstract:
Blind signatures are at the center of renewed attention due to their use in a number of real-world systems. Several solutions exist, based on a variety of assumptions, but coming up with efficient schemes that solely rely on groups without pairings has remained a challenging open question. Benhamouda et al. (EUROCRYPT ‘21) showed in particular that several well-known schemes (such as blind variants of Schnorr signatures) are completely insecure in a natural setting where the adversary can engage in multiple concurrent interactions with the signer.
This talk will cover our recent progress on building concurrently secure blind signatures in pairing-free groups. I will also highlight several open questions and barriers.
This talk is based on joint works with Champ Chairattana-Apirom, Elizabeth Crites, Chelsea Komlo, Mary Maller, Michele Orrù, Greg Zaverucha, and Chenzhi Zhu
Speaker: Arka Rai Choudhuri (NTT Research)
Title: SublonK: Sublinear Prover PlonK
Abstract: We propose SublonK - a new zero-knowledge succinct non-interactive argument of knowledge (zkSNARK). SublonK builds on PlonK [EPRINT'19], a popular state-of-the-art practical zkSNARK. Our new construction preserves all the great features of PlonK, i.e., it supports constant size proofs, constant time proof verification, a circuit-independent universal setup, as well as support for custom gates and lookup gates. Moreover, SublonK achieves improved prover running time over PlonK. In PlonK, the prover runtime grows with circuit size. Instead, in Sublonk, the prover runtime grows with the size of the "active part" of the circuit. For instance, consider circuits encoding conditional execution, where only a fraction of the circuit is exercised by the input. For such circuits, the prover runtime in SublonK grows only with the exercised execution path.
As an example, consider the zkRollup circuit. This circuit involves executing one of n code segments k times. For this case, using PlonK involves proving a circuit of size n.k code segments. In SublonK, the prover costs are close to proving a PlonK proof for a circuit of size roughly k code segments. Concretely, based on our implementation, for parameter choices derived from rollup contracts on Ethereum, n = 8, k = {2^{10},...,2^{16}}, the SublonK prover is approximately 4.6 times faster than the PlonK prover. Proofs in SublonK are 2.4KB, and can be verified in under 50ms.
Speaker: Lior Rotem Benvenisty (Stanfrod)
Title: Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-randomizable Commitments
Abstract:
A Single Secret Leader Election (SSLE) enables a group of parties to randomly select exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to prove that she is the elected leader. Such protocols are used to strengthen the security of proof-of-stake consensus protocols.
The most efficient construction of SSLE -- due to Boneh, Eskandarian, Hanzlik, and Greco -- is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group, which is not post-quantum secure.
In this talk, I will present the first constructions of efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure.
Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC), which may be of independent interest.
The talk is based on a joint work with Dan Boneh and Aditi Partap.
Speaker: Peter Rindal (Visa)
Title: Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN
Abstract:
The recent development of pseudorandom correlation generators (PCG) holds tremendous promise for highly efficient MPC protocols. Among other correlations, PCGs allow for the efficient generation of oblivious transfer (OT) and vector oblivious linear evaluations (VOLE) with sublinear communication and concretely good computational overhead. This type of PCG makes use of a so-called LPN-friendly error-correcting code. That is, for large dimensions the code should have very efficient encoding and have high minimum distance.
We investigate existing LPN-friendly codes and find that several candidates are less secure than was believed. Beginning with the recent expand-accumulate codes, we find that for their aggressive parameters, aimed at good concrete efficiency, they achieve a smaller [pseudo] minimum distance than conjectured. This decreases the resulting security parameter of the PCG but it remains unclear by how much. We additionally show that the recently proposed and extremely efficient silver codes achieve only very small minimum distance and result in concretely efficient attacks on the resulting PCG protocol. As such, silver codes should not be used.
We introduce a new LPN-friendly code which we call expand-convolute. These codes have provably high minimum distance and faster encoding time than suitable alternatives, e.g. expand-accumulate. The main contribution of these codes is the introduction of a convolution step that dramatically increases the minimum distance. This in turn allows for a more efficient parameter selection which results in improved concrete performance. In particular, we observe a 3 times improvement in running time for a comparable security level.
Speaker: Sruthi Sekar (UCB)
Title: zkSaaS: : Zero-Knowledge SNARKs as a Service
Abstract:
A decade of active research has led to practical constructions of zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) that are now being used in a wide variety of applications. Despite this astonishing progress, overheads in proof generation time remain significant.
In this work, we envision a world where consumers with low computational resources can outsource the task of proof generation to a group of untrusted servers in a privacy-preserving manner. The main requirement is that these servers should be able to collectively generate proofs at a faster speed (than the consumer). Towards this goal, we introduce a framework called zk-SNARKs-as-a-service (zkSaaS) for faster computation of zk-SNARKs. Our framework allows for distributing proof computation across multiple servers such that each server is expected to run for a shorter duration than a single prover. Moreover, the privacy of the prover’s witness is ensured against any minority of colluding servers.
We design custom protocols in this framework that can be used to obtain faster runtimes for widely used zk-SNARKs, such as Groth16 [EUROCRYPT 2016], Marlin [EUROCRYPT 2020], and Plonk [EPRINT 2019]. We implement proof of concept zkSaaS for the Groth16 and Plonk provers. In comparison to generating these proofs on commodity hardware, we show that not only can we generate proofs for a larger number of constraints (without memory exhaustion), but we can also get ~22x speed-up when run with 128 parties for $2^{25}$ constraints with Groth16 and $2^{21}$ constraints with Plonk.
The talk is based on joint work with Sanjam Garg, Aarushi Goel, Abhishek Jain, and Guru Vamsi Policharla.