Bay Area Crypto Day
April 7, 2023
Program
9:30am: Breakfast
10:00am: Welcome
10:10am: Aditi Partap (Stanford)
Proactive Refresh for Accountable Threshold Signatures
10:40am: Guru Policharla (UCB)
End-to-End Secure Messaging with Traceability Only for Illegal Content
11:10am: Coffee Break
11:40am: David Wu (UT Austin)
Succinct Vector, Polynomial, and Functional Commitments from Lattices
12:40pm: Lunch
2:10pm: Benedikt Bünz (Stanford)
Multilinear Schwartz-Zippel mod N with Applications to Succinct Arguments
2:40pm: Aarushi Goel (NTT Research)
Stacking Zero-Knowledge Proofs for Disjunctions
3:10pm: Coffee Break
3:40pm: Kevin Lewi (Meta)
WhatsApp End-to-End Encrypted Backups
4:10pm: Mingyuan Wang (UCB)
Cryptography with Weights: MPC, Encryption and Signatures
Abstracts
Speaker: Aditi Partap (Stanford)
Title: Proactive Refresh for Accountable Threshold Signatures
Abstract:
An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without changing the public key or the threshold. We give several definitions for this notion achieving different levels of security. We observe that certain natural constructions for an ATS cannot be proactively refreshed because the secret key generated at setup is needed for accountability. We then construct three types of ATS schemes with proactive refresh. The first is a generic construction that is efficient when the number of signers is small. The second is a hybrid construction that performs well for a large number of signers and satisfies a strong security definition. The third is a collection of very practical constructions derived from ATS versions of the Schnorr and BLS signature schemes; however these practical constructions only satisfy our weaker notion of security
Speaker: Guru Policharla (UCB)
Title: End-to-End Secure Messaging with Traceability Only for Illegal Content
Abstract:
As end-to-end encrypted messaging services become widely adopted, law enforcement agencies have increasingly expressed concern that such services interfere with their ability to maintain public safety. Indeed, there is a direct tension between preserving user privacy and enabling content moderation on these platforms. Recent research has begun to address this tension, proposing systems that purport to strike a balance between the privacy of ‘’honest’' users and traceability of ‘’malicious’' users. Unfortunately, these systems suffer from a lack of protection against malicious or coerced service providers.
In this work, we address the privacy vs. content moderation question through the lens of pre-constrained cryptography [Ananth et al., ITCS 2022]. We introduce the notion of set pre-constrained (SPC) group signatures that guarantees security against malicious key generators. SPC group signatures offer the ability to trace users in messaging systems who originate pre-defined illegal content (such as child sexual abuse material), while providing security against malicious service providers.
We construct concretely efficient protocols for SPC group signatures, and demonstrate the real-world feasibility of our approach via an implementation. The starting point for our solution is the recently introduced Apple PSI system, which we significantly modify to improve security and expand functionality.
Speaker: David Wu (UT Austin)
Title: Succinct Vector, Polynomial, and Functional Commitments from Lattices
Abstract:
In a functional commitment scheme, a user can commit to an input x and later on, open it to an arbitrary function evaluation f(x). We require that both the commitment and the opening be short. Important special cases of functional commitments include vector commitments and polynomial commitments. In this talk, I will introduce a new lattice-based framework for constructing functional commitments that supports functions computable by arbitrary (bounded-depth) Boolean circuits. Our constructions rely on a new falsifiable "basis-augmented SIS" assumption that we introduce, which can be viewed as a new "q-type" variant of the standard SIS assumption.
Based on joint work with Hoeteck Wee
Speaker: Benedikt Bünz (Stanford)
Title: Multilinear Schwartz-Zippel mod N with Applications to Succinct Arguments
Abstract:
We show that for x_1,..,x_k sampled from a grid and any integer N the probability that f(x_1,...,x_k) ≡ 0 mod N for any non-zero multilinear polynomial f ∈ Z[X_1, . . . , X_m], co-prime to N is roughly inversely proportional to N.
We then apply this Multilinear Composite Schwartz-Zippel Lemma (LCSZ) to show that the classical Bulletproofs succinct argument of knowledge for a Pedersen commitment opening generalizes to commitment schemes binding only over short integer vectors, which includes commitments both from lattice hardness assumptions (SIS/R-SIS/M-SIS) and groups of unknown order (GUOs), in which case the verification time also becomes logarithmic. Along the way, we define the notion of Almost Special Soundness, a generalization of Special Soundness, which still implies knowledge-soundness. This unified treatment subsumes prior work in GUO-based SNARKs (DARK Eurocrypt 2020) and lattice-based Bulletproofs (Crypto 2020). Our analysis closes a critical gap in the original security proof of DARK. Prior analysis of lattice-based Bulletproofs showed knowledge soundness with polynomial-size challenge sets and thus had a non-negligible knowledge error that necessitated parallel repetition. Our analysis shows knowledge soundness for the original Bulletproofs protocol over an exponential-size challenge set and achieves a negligible soundness error without repetition. This circumvents a previous impossibility result.
Speaker: Aarushi Goel (NTT Research)
Title: Stacking Zero-Knowledge Proofs for Disjunctions
Abstract:
We propose a new framework for efficiently composing zero-knowledge proofs for disjunctions. First, we demonstrate how to compile a large class of unmodified sigma-protocols, each for an individual statement, into a new sigma-protocol that proves a disjunction of these statements. Our framework can be used both when each clause is proved using the same sigma-protocol as well as when different sigma-protocols are used for different clauses. The resulting sigma-protocol is concretely efficient and has communication complexity proportional to the communication required by the largest clause, with additive terms that are only logarithmic in the number of clauses.
Next, we show how to apply this framework to sublinear-sized proofs. This results in sublinear-sized disjunctive zero-knowledge proof systems with sublinear proving times (without meaningfully increasing proof sizes). Our key observation here is that simulation in sublinear-sized zero-knowledge proof systems can be much faster (both concretely and asymptotically) than the honest prover. We study applying our compiler to two classes of sublinear-sized proof systems, namely interactive oracle proofs (specifically Aurora [Eurocrypt 2019] and Fractal [Eurocrypt 2020]) and proofs based on folding arguments (specifically Compressed sigma-protocols [Crypto 20,21] and Bulletproofs [S&P 18]).
This is based on joint works with Matthew Green, Mathias Hall-Andersen, Gabriel Kaptchuk and Nicholas Spooner.
Speaker: Kevin Lewi (Meta)
Title: WhatsApp End-to-End Encrypted Backups
Abstract:
WhatsApp provides end-to-end encryption (E2EE) by default so that messages can be seen only by the sender and recipient, and no one in between. And now, if people choose to enable E2EE backups, neither WhatsApp nor the backup service provider will be able to access their backup or their backup encryption key. In this presentation, we will describe how our recently-launched E2EE backups work, which includes the use of server-side HSMs that interact with clients using the OPAQUE (Eurocrypt 2018) password authentication protocol.
Speaker: Mingyuan Wang (UCB)
Title: Cryptography with Weights: MPC, Encryption and Signatures
Abstract:
The security of many powerful cryptographic systems such as secure multiparty computation, threshold encryption, and threshold signatures rests on trust assumptions about the parties. The de-facto model treats all parties equally and requires that a certain fraction of the parties are honest. While this paradigm of one-person-one-vote has been very successful over the years, current and emerging practical use cases suggest that it is outdated.
In this work, we consider weighted cryptosystems where every party is assigned a certain weight and the trust assumption is that a certain fraction of the total weight is honest. This setting can be translated to the standard setting (where each party has a unit weight) via virtualization. However, this method is quite expensive, incurring a multiplicative overhead in the weight.
We present new weighted cryptosystems with significantly better efficiency: our proposed schemes incur only an additive overhead in weights.
We first present a weighted ramp secret-sharing scheme (WRSS) where the size of a secret share is O(w) (where w corresponds to the weight). In comparison, Shamir's secret sharing with virtualization requires secret shares of size w*\lambda, where \lambda= log |F| is the security parameter.
Next, we use our WRSS to construct weighted versions of (semi-honest) secure multiparty computation (MPC), threshold encryption, and threshold signatures. All these schemes inherit the efficiency of our WRSS and incur only an additive overhead in weights.
Our WRSS is based on the Chinese remainder theorem-based secret-sharing scheme. Interestingly, this secret-sharing scheme is non-linear and only achieves statistical privacy. These distinct features introduce several technical hurdles in applications to MPC and threshold cryptosystems. We resolve these challenges by developing several new ideas.