The Fiat--Shamir transformation turns public-coin interactive protocols into non-interactive proof systems.  

We study malleability attacks against Fiat-Shamir transformed multi-round protocols. In this talk, we will look at simulation extractability of two classes of protocols:

1. Bulletproofs: We show that Bulletproofs (or any other similar multi-round proof system satisfying some form of weak unique response property) achieve simulation-extractability in the algebraic group model.

2. SRS-based SNARKs: We formally define simulation extractability for protocols in the random oracle model (ROM) which use a structured reference string (SRS). We show sufficient conditions for compiling via the Fiat--Shamir transformation public-coin multi-round interactive protocols with SRS into simulation-extractable NIZK proof systems. We consider the case where the SRS is updatable and define a strong simulation extractability notion that allows for simulated proofs with respect to an SRS to which the adversary can contribute updates.

We show that three popular universal zero knowledge SNARKs --- Plonk, Sonic, and Marlin --- are simulation extractable.

Based on joint works with Claudio Orlandi, Mahak Pancholi, Akira Takahashi, Daniel Tschudi (Eurocrypt’22) and Hamidreza Koshakhlagh, Markulf Kohlweiss, Anca Nitulescu, Michal Zając (SCN’22).

In this talk we will discuss an approach based on cryptographic techniques like zero knowledge proofs to augment prevailing AI/ML practices to adequately address concerns around privacy and provenance. We are particularly interested in setting involving several participants such as data owners, data curators, model builders and finally the consumers of AI models, and how we can adequately address privacy of assets such as data and models, while simultaneously addressing concerns of end consumers regarding provenance of the results. The technical centerpiece of the work is efficient representation of dataset operations inside verifiable computation circuits, and an improved scheme to prove inference from a private decision tree in zero knowledge. 

Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality f to the task of securely computing a simpler functionality g. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as privacy. The special case of a degree-2 encoding g (2MPRE) has recently found several applications to secure multiparty computation (MPC) with either information-theoretic security or making black-box access to cryptographic primitives. Unfortunately, as all known constructions are based on information-theoretic MPC protocols in the plain model, they can only be private with an honest majority.

In this paper, we break the honest-majority barrier and present the first construction of general 2MPRE that remains secure in the presence of a dishonest majority. Our construction encodes every n-party functionality f by a 2MPRE that tolerates at most $t=\lfloor 2n/3\rfloor$ passive corruptions.

We derive several applications including: (1) The first non-interactive client-server MPC protocol with perfect privacy against any coalition of a minority of the servers and up to t of the n clients; (2) Completeness of 3-party functionalities under non-interactive t-private reductions; and (3) A single-round t-private reduction from general-MPC to an ideal oblivious transfer (OT). These positive results partially resolve open questions that were posed in several previous works. We also show that t-private 2MPREs are necessary for solving (2) and (3), thus establishing new equivalence theorems between these three notions. 

Finally, we present a new approach for constructing fully-private 2MPREs based on multi-round protocols in the OT-hybrid model that achieve perfect privacy against active attacks. Moreover, by slightly restricting the power of the active adversary, we derive an equivalence between these notions. This forms a surprising, and quite unique, connection between a non-interactive passively-private primitive to an interactive actively-private primitive.

Based on a joint work with Benny Applebaum, Yuval Ishai and Or Karni, accepted to CRYPTO’22.

Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of n mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC with information-theoretic security (also called unconditional security) provides the strongest security guarantees and remains secure even against computationally unbounded} adversaries. Perfectly-secure MPC protocols is a class of information-theoretically secure MPC protocols, which provides all the security guarantees in an error-free fashion. The focus of this talk is perfectly-secure MPC.

Known protocols are designed assuming either a synchronous or asynchronous communication network. It is well known that perfectly-secure synchronous MPC protocol is possible as long as adversary can corrupt any t_s < n/3 parties. On the other hand, perfectly-secure asynchronous MPC protocol can tolerate up to t_a < n/4 corrupt parties. A natural question is does there exist a single MPC protocol for the setting where the parties are not aware of the exact network type and which can tolerate up to t_s < n/3 corruptions in a synchronous network and up to t_a < n/4 corruptions in an asynchronous network. We design such a best-of-both-worlds perfectly-secure MPC protocol, provided 3t_s + t_a < n holds.

For designing our protocol, we design two important building blocks, which are of independent interest. The first building block is a best-of-both-worlds Byzantine agreement (BA) protocol tolerating t < n/3 corruptions and which remains secure, both in a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worlds verifiable secret-sharing (VSS) protocol, which can tolerate up to t_s and t_a corruptions in a synchronous and in an asynchronous network respectively.

The Oblivious Cross-Tags (OXT) protocol due to Cash et al. (CRYPTO'13) is a highly scalable searchable symmetric encryption (SSE) scheme that allows fast processing of conjunctive and more general Boolean queries over encrypted relational databases. A longstanding open question has been to extend OXT to also support queries over joins of tables without pre-computing the joins. In this paper, we solve this open question without compromising on the nice properties of OXT with respect to both security and efficiency. We propose Join Cross-Tags (JXT) - a purely symmetric-key solution that supports efficient conjunctive queries over (equi) joins of encrypted tables without any pre-computation at setup. JXT is fully compatible with OXT, and can be used in conjunction with OXT to support a wide class of SQL queries directly over encrypted relational databases. JXT incurs a storage cost (over OXT) of a factor equal to the number of potential join-attributes in a table, which is usually compensated by the fact that JXT is a fully symmetric-key solution (as opposed to OXT which relies on discrete-log hard groups). We prove the (adaptive) simulation-based security of JXT with respect to a rigorously defined leakage profile.

Based on joint work with Charanjit Jutla, accepted to ASIACRYPT 2022.

We construct polynomial commitments of constant size with no trusted setup and with evaluation proofs of constant size and logarithmic time verification. They imply transparent zkSNARKs of constant size and logarithmic verification. Our polynomial commitments use hardness assumptions in groups of unknown order – instantiated by, e.g., class groups – and the Generic Group Model (GGM). They also rely on a new result in extremal combinatorics. 

Joint work with Arasu Arun, Chaya Ganesh, Tushar Mopuri, and Sriram Sridhar.