Charles River Crypto Day: Friday, May 1 @ Northeastern
Daniel Wichs
When: Friday, May 1.
Where: Northeastern University, West Village H (440 Huntington Ave), Room 366
Organizers: Ran Canetti, Yael Kalai, Eran Tromer, Vinod Vaikuntanathan and Daniel Wichs.
Program:
| 9:30–10:00 | Coffee/Welcome |
| 10:00–11:00 | Giulio Malavolta (Bocconi University) How to Authenticate a Non-Deterministic Computation |
| 11:30–12:30 | Yuval Ishai (Technion and AWS) Computing on Encrypted Data via Secret Dual Codes |
| 12:30–2:00 | Lunch (provided) |
| 2:00–3:00 | Alex Lombardi (Princeton) On SNARGs for NP and Nullstellensatz Proofs |
| 3:30–4:30 | Zhengzhong Jin (Northeastern) SNARKs from LWE via Non-black-box Reductions |
Abstracts:
Title: How to Authenticate a Non-Deterministic Computation
Speaker: Giulio Malavolta (Bocconi University)
Abstract: We propose a new method to construct homomorphic authentication codes supporting the evaluation of non-deterministic computations, extending the celebrated homomorphic lattice encodings [Boneh et al., Eurocrypt 2014]. Our approach relies on the hardness of the decomposed learning with errors problem (LWE), a recently introduced modification of Regev’s LWE problem. We survey applications of this method to cryptography and complexity theory.
Based on joint works with Damiano Abram and Lawrence Roy.
Title: Computing on Encrypted Data via Secret Dual Codes
Speaker: Yuval Ishai (Technion and AWS)
Abstract: We revisit the question of computing on encrypted data, in the following secret-key setting. A client uploads an encryption of a large input X to an untrusted server and then wishes to make an unbounded number of queries q(X) while hiding q and X from the server, using only its secret key. How efficiently can this be done and under what assumptions?
We present efficient solutions for useful special cases, including matrix-vector multiplication and private information retrieval (PIR). These solutions rely on either the standard Learning Parity with Noise assumption, in a parameter regime not known to imply public-key encryption, or new assumptions related to the hardness of learning a secret linear subspace from noisy samples. The latter assumptions yield efficiency features that no prior approach meets, including a vanishing computational overhead on the server side.
Our core idea, inspired by prior works on PIR with preprocessing, is to encode the input X and the queries q using a pair of secret dual codes, while avoiding linear algebra attacks by adding noise.
Based on joint works with Fabrice Benhamouda, Caicai Chen, Shai Halevi, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen
Title: On SNARGs for NP and Nullstellensatz Proofs
Speaker: Alex Lombardi (Princeton)
Abstract: We construct the first succinct non-interactive arguments of knowledge (SNARKs) from the polynomial-hardness of Learning with Errors (LWE) for UP languages whose witness uniqueness has a polynomial-size Extended Frege (EF) proof. Our construction achieves an infinitely-often soundness guarantee with a uniformly random CRS whose length depends non-constructively on any fixed sequence of false instances.
We also obtain:
- SNARGs from LWE for any NP language whose false instances have polynomial-size EF proofs of witness uniqueness, with the same style of soundness guarantee.
- SNARKs from LWE for all true instances of UP languages whose instances have polynomial-size EF proofs of witness uniqueness, but without soundness guarantees for false instances.
To obtain our results, we rely on a non-black-box reduction that depends on the adversary circuit. We also introduce Cryptographic Extended Frege (CEF), a new proof system extending EF with rules for formalizing indistinguishability arguments in cryptography. Extending the framework of [Jin–Kalai–Lombardi–Vaikuntanathan, STOC’24], we construct SNARGs for CEF proofs of non-membership. These techniques may be of independent interest.
Based on the joint work with Mingqi Lu and Bo Peng in STOC 2026
Title: SNARKs from LWE via Non-black-box Reductions
Speaker: Zhengzhong Jin (Northeastern)
Abstract: We construct the first succinct non-interactive arguments of knowledge (SNARKs) from the polynomial-hardness of Learning with Errors (LWE) for UP languages whose witness uniqueness has a polynomial-size Extended Frege (EF) proof. Our construction achieves an infinitely-often soundness guarantee with a uniformly random CRS whose length depends non-constructively on any fixed sequence of false instances.
We also obtain:
- SNARGs from LWE for any NP language whose false instances have polynomial-size EF proofs of witness uniqueness, with the same style of soundness guarantee.
- SNARKs from LWE for all true instances of UP languages whose instances have polynomial-size EF proofs of witness uniqueness, but without soundness guarantees for false instances.
To obtain our results, we rely on a non-black-box reduction that depends on the adversary circuit. We also introduce Cryptographic Extended Frege (CEF), a new proof system extending EF with rules for formalizing indistinguishability arguments in cryptography. Extending the framework of [Jin–Kalai–Lombardi–Vaikuntanathan, STOC’24], we construct SNARGs for CEF proofs of non-membership. These techniques may be of independent interest.
Based on the joint work with Mingqi Lu and Bo Peng in STOC 2026.
Daniel Wichs
corrected abstracts below. thanks to everyone who caught the error within seconds :-)
Abstracts:
Title: How to Authenticate a Non-Deterministic Computation
Speaker: Giulio Malavolta (Bocconi University)
Abstract: We propose a new method to construct homomorphic authentication codes supporting the evaluation of non-deterministic computations, extending the celebrated homomorphic lattice encodings [Boneh et al., Eurocrypt 2014]. Our approach relies on the hardness of the decomposed learning with errors problem (LWE), a recently introduced modification of Regev’s LWE problem. We survey applications of this method to cryptography and complexity theory.
Based on joint works with Damiano Abram and Lawrence Roy.
Title: Computing on Encrypted Data via Secret Dual Codes
Speaker: Yuval Ishai (Technion and AWS)
Abstract: We revisit the question of computing on encrypted data, in the following secret-key setting. A client uploads an encryption of a large input X to an untrusted server and then wishes to make an unbounded number of queries q(X) while hiding q and X from the server, using only its secret key. How efficiently can this be done and under what assumptions?
We present efficient solutions for useful special cases, including matrix-vector multiplication and private information retrieval (PIR). These solutions rely on either the standard Learning Parity with Noise assumption, in a parameter regime not known to imply public-key encryption, or new assumptions related to the hardness of learning a secret linear subspace from noisy samples. The latter assumptions yield efficiency features that no prior approach meets, including a vanishing computational overhead on the server side.
Our core idea, inspired by prior works on PIR with preprocessing, is to encode the input X and the queries q using a pair of secret dual codes, while avoiding linear algebra attacks by adding noise.
Based on joint works with Fabrice Benhamouda, Caicai Chen, Shai Halevi, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen
Title: On SNARGs for NP and Nullstellensatz Proofs
Speaker: Alex Lombardi (Princeton)
Abstract: We revisit the question of whether it is possible to build succinct non-interactive arguments (SNARGs) for all of NP under standard cryptographic assumptions. In particular, we give a candidate non-adaptive SNARG for NP and prove its soundness under
– the learning with errors assumption (or other standard assumptions such as bilinear maps), and
– a mathematical conjecture about multivariate polynomials over the reals. In more detail, our conjecture is an upper bound on the minimum total coefficient size of Nullstellensatz proofs (Potechin-Zhang, ICALP 2024) of membership in a concrete polynomial ideal.
In this talk, we will discuss the construction, security analysis, and our current understanding of the conjecture.
Based on joint work with Lali Devadas, Sam Hopkins, Yael Kalai, Pravesh Kothari, and Surya Mathialagan.
Title: SNARKs from LWE via Non-black-box Reductions
Speaker: Zhengzhong Jin (Northeastern)
Abstract: We construct the first succinct non-interactive arguments of knowledge (SNARKs) from the polynomial-hardness of Learning with Errors (LWE) for UP languages whose witness uniqueness has a polynomial-size Extended Frege (EF) proof. Our construction achieves an infinitely-often soundness guarantee with a uniformly random CRS whose length depends non-constructively on any fixed sequence of false instances.
We also obtain:
- SNARGs from LWE for any NP language whose false instances have polynomial-size EF proofs of witness uniqueness, with the same style of soundness guarantee.
- SNARKs from LWE for all true instances of UP languages whose instances have polynomial-size EF proofs of witness uniqueness, but without soundness guarantees for false instances.
To obtain our results, we rely on a non-black-box reduction that depends on the adversary circuit. We also introduce Cryptographic Extended Frege (CEF), a new proof system extending EF with rules for formalizing indistinguishability arguments in cryptography. Extending the framework of [Jin–Kalai–Lombardi–Vaikuntanathan, STOC’24], we construct SNARGs for CEF proofs of non-membership. These techniques may be of independent interest.
Based on the joint work with Mingqi Lu and Bo Peng in STOC 2026.