International Association
for Cryptologic Research

We present the first round-optimal and plausibly quantum-safe oblivious transfer (OT) and multi-party computation (MPC) protocols from the computational CSIDH assumption - the weakest and most widely studied assumption in the CSIDH family of isogeny-based assumptions. We obtain the following results: - The first round-optimal maliciously secure OT and MPC protocols in the plain model that achieve (black-box) simulation-based security while relying on the computational CSIDH assumption. - The first round-optimal maliciously secure OT and MPC protocols that achieves Universal Composability (UC) security in the presence of a trusted setup (common reference string plus random oracle) while relying on the computational CSIDH assumption. Prior plausibly quantum-safe isogeny-based OT protocols (with/without setup assumptions) are either not round-optimal, or rely on potentially stronger assumptions. We also build a 3-round maliciously-secure OT extension protocol where each base OT protocol requires only 4 isogeny computations. In comparison, the most efficient isogeny-based OT extension protocol till date due to Lai et al. [Eurocrypt 2021] requires 12 isogeny computations and 4 rounds of communication, while relying on the same assumption as our construction, namely the reciprocal CSIDH assumption.

In the setting of subversion, an adversary tampers with the machines of the honest parties thus leaking the honest parties' secrets through the protocol transcript. The work of Mironov and Stephens-Davidowitz (EUROCRYPT’15) introduced the idea of reverse firewalls (RF) to protect against tampering of honest parties' machines. All known constructions in the RF framework rely on the malleability of the underlying operations in order for the RF to rerandomize/sanitize the transcript. RFs are thus limited to protocols that offer some structure, and hence based on public-key operations. In this work, we initiate the study of efficient Multiparty Computation (MPC) protocols in the presence of tampering. In this regard, - We construct the first Oblivious Transfer (OT) extension protocol in the RF setting. We construct poly(k) maliciously-secure OTs using O(k) public key operations and O(1) inexpensive symmetric key operations, where k is the security parameter. - We construct the first Zero-knowledge protocol in the RF setting where each multiplication gate can be proven using O(1) symmetric key operations. We achieve this using our OT extension protocol and by extending the ZK protocol of Quicksilver (Yang, Sarkar, Weng and Wang, CCS'21) to the RF setting. - Along the way, we introduce new ideas for malleable interactive proofs that could be of independent interest. We define a notion of full malleability for Sigma protocols that unlike prior notions allow modifying the instance as well, in addition to the transcript. We construct new protocols that satisfy this notion, construct RFs for such protocols and use them in constructing our OT extension. The key idea of our work is to demonstrate that correlated randomness may be obtained in an RF friendly way without having to rerandomize the entire transcript. This enables us to avoid expensive public-key operations that grow with the circuit-size.

We present a new framework for building round-optimal one-sided statistically secure two party computation (2PC) protocols in the plain model. We demonstrate that a relatively weak notion of oblivious transfer (OT), namely a three round elementary oblivious transfer (EOT) with statistical receiver privacy, along with a non-interactive commitment scheme suffices to build a one-sided statistically secure two party computation protocol with black-box simulation. Our framework enables the first instantiations of round-optimal one-sided statistically secure 2PC protocols from the CDH assumption and certain families of isogeny-based assumptions. As part of our compiler, we introduce the following new one-sided statistically secure primitives in the pre-processing model that might also be of independent interest: 1. Three round statistically sender private random-OT where only the last OT message depends on the receiver's choice bit and the sender receives random outputs generated by the protocol. 2. Four round delayed-input statistically sender private conditional disclosure of secrets where the first two rounds of the protocol are independent of the inputs of the parties. The above primitives are directly constructed from EOT and hence we obtain their instantiations from the same set of assumptions as our 2PC.

Non-interactive zero knowledge (NIZK) enables a prover, to prove that a statement in an NP language is valid, given an accepting witness, without leaking any information about the witness. We study universally composable (UC) NIZKs which are secure against adaptive corruption of parties and provides adaptive soundness, i.e. the statement is adaptively chosen by a malicious prover based on the setup string distribution. The only known adaptively secure NIZK protocols either fail to achieve full adaptive soundness or rely on non-falsifiable knowledge assumptions. We construct the first NIZK protocols which are triply adaptive - secure against adaptive corruptions, guarantees adaptive soundness and satisfies adaptive zero knowledge, from falsifiable assumptions. We do so using the following methodology: - We define a new ideal functionality, denoted as F_NICOM, for non-interactive commitment schemes in the UC framework. - We define and construct Sigma protocols which satisfy triply adaptive security in the F_NICOM model. - By relying on correlation intractable (CI) hash functions, we compile a triply adaptively secure Sigma protocol (in F_NICOM model) into a triply adaptive UC-NIZK argument in the F_NICOM+common reference string (crs) model. In addition to CI hash functions, our compiler requires standard cryptographic primitives - non-interactive equivocal commitments and public key encryption with obliviously samplable ciphertexts, for implementing F_NICOM in the crs model. We instantiate our framework by demonstrating that most statically secure Sigma protocols can be proven to be triply adaptively secure in the F_NICOM model, hence, bridging the gap between static and adaptive security for NIZKs. Our NIZK arguments can be concretely based on assumptions, like LWE, or LPN and DDH.

We study Multi-party computation (MPC) in the setting of subversion, where the adversary tampers with the machines of honest parties. Our goal is to construct actively secure MPC protocols where parties are corrupted adaptively by an adversary (as in the standard adaptive security setting), and in addition, honest parties' machines are compromised. The idea of reverse firewalls (RF) was introduced at EUROCRYPT'15 by Mironov and Stephens-Davidowitz as an approach to protecting protocols against corruption of honest parties' devices. Intuitively, an RF for a party $\mathcal{P}$ is an external entity that sits between $\mathcal{P}$ and the outside world and whose scope is to sanitize $\mathcal{P}$’s incoming and outgoing messages in the face of subversion of their computer. Mironov and Stephens-Davidowitz constructed a protocol for passively-secure two-party computation. At CRYPTO'20, Chakraborty, Dziembowski and Nielsen constructed a protocol for secure computation with firewalls that improved on this result, both by extending it to \textit{multi}-party computation protocol, and considering \textit{active} security in the presence of \textit{static} corruptions. In this paper, we initiate the study of RF for MPC in the \textit{adaptive} setting. We put forward a definition for adaptively secure MPC in the reverse firewall setting, explore relationships among the security notions, and then construct reverse firewalls for MPC in this stronger setting of adaptive security. We also resolve the open question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted setup in constructing RF for MPC. Towards this end, we construct reverse firewalls for adaptively secure augmented coin tossing and adaptively secure zero-knowledge protocols and obtain a constant round adaptively secure MPC protocol in the reverse firewall setting without setup. Along the way, we propose a new multi-party adaptively secure coin tossing protocol in the plain model, that is of independent interest.

We present a new framework for building round-optimal (two-round) adaptively secure MPC. We show that a relatively weak notion of OT that we call indistinguishability OT with receiver oblivious sampleability (r-iOT) is enough to build two-round, adaptively secure MPC against malicious adversaries in the CRS model. We then show how to construct r-iOT from CDH, LPN, or isogeny-based assumptions that can be viewed as group actions (such as CSIDH and CSI-FiSh). This yields the first concrete constructions of two-round adaptively secure MPC against malicious adversaries from CDH, LPN, or isogeny-based assumptions. We further extend our non-isogeny results to the plain model, achieving (to the best of our knowledge) the first construction of two-round adaptively secure MPC against semi-honest adversaries in the plain model from LPN. Our results allow us to build two-round adaptively secure MPC against malicious adversaries from essentially all of the well-studied assumptions in cryptography. In addition, our constructions from isogenies or LPN provide the first post-quantum alternatives to LWE-based constructions for round-optimal adaptively secure MPC. Along the way, we show that r-iOT also implies non-committing encryption (NCE), thereby yielding the first constructions of NCE from isogenies or LPN.

Oblivious Transfer (OT) is an important building block for multi-party computation (MPC). Since OT requires expensive public-key operations, efficiency-conscious MPC protocols use an OT extension (OTE) mechanism [Beaver 96, Ishai et al. 03] to provide the functionality of many independent OT instances with the same sender and receiver, using only symmetric-key operations plus few instances of some base OT protocol. Consequently there is significant interest in constructing OTE friendly protocols, namely protocols that, when used as base-OT for OTE, result in extended OT that are both round-efficient and cost-efficient. We present the most efficient OTE-friendly protocol to date. Specifically: Our base protocol incurs only 3 exponentiations per instance. Our base protocol results in a 3 round extended OT protocol. The extended protocol is UC secure in the Observable Random Oracle Model (ROM) under the CDH assumption. For comparison, the state of the art for base OTs that result in 3-round OTE are proven only in the programmable ROM, and require 4 exponentiations under Interactive DDH or 6 exponentiations under DDH [Masney-Rindal 19]. We also implement our protocol and benchmark it against the Simplest OT protocol [Chou and Orlandi, Latincrypt 2015], which is the most efficient and widely used OT protocol but not known to suffice for OTE. The computation cost is roughly the same in both cases. Interestingly, our base OT is also 3 rounds. However, we slightly modify the extension mechanism (which normally adds a round) so as to preserve the number of rounds in our case.

We construct the most efficient two-round adaptively secure bit-OT in the Common Random String (CRS) model. The scheme is UC secure under the Decisional Diffie-Hellman (DDH) assumption. It incurs O(1) exponentiations and sends O(1) group elements, whereas the state of the art requires O(k^2) exponentiations and communicates poly(k) bits, where k is the computational security parameter. Along the way, we obtain several other efficient UC-secure OT protocols under DDH : - The most efficient yet two-round adaptive string-OT protocol assuming global programmable random oracle. Furthermore, the protocol can be made non-interactive in the simultaneous message setting, assuming random inputs for the sender. - The first two-round string-OT with amortized constant exponentiations and communication overhead which is secure in the global observable random oracle model. - The first two-round receiver equivocal string-OT in the CRS model that incurs constant computation and communication overhead. We also obtain the first non-interactive adaptive string UC-commitment in the CRS model which incurs a sublinear communication overhead in the security parameter. Specically, we commit to polylog(k) bits while communicating O(k) bits. Moreover, it is additively homomorphic. We can also extend our results to the single CRS model where multiple sessions share the same CRS. As a corollary, we obtain a two-round adaptively secure MPC protocol in this model.

Zero-knowledge (ZK) protocols are undoubtedly among the central primitives in cryptography, lending their power to numerous applications such as secure computation, voting, auctions, and anonymous credentials to name a few. The study of efficient ZK protocols for non-algebraic statements has seen rapid progress in recent times, relying on secure computation techniques. The primary contribution of this work lies in constructing efficient UC-secure constant round ZK protocols from garbled circuits that are secure against adaptive corruptions, with communication linear in the size of the statement. We begin by showing that the practically efficient ZK protocol of Jawurek et al. (CCS 2013) is adaptively secure when the underlying oblivious transfer (OT) satisfies a mild adaptive security guarantee. We gain adaptive security with little to no overhead over the static case. A conditional verification technique is then used to obtain a three-round adaptively secure zero-knowledge argument in the non-programmable random oracle model (NPROM). Our three-round protocol yields a proof size that is shorter than the known UC-secure practically-efficient schemes in the short-CRS model with the right choice of security parameters.We draw motivation from state-of-the-art non-interactive secure computation protocols and leveraging specifics of ZK functionality show a two-round protocol that achieves static security. It is a proof, while most known efficient ZK protocols and our three round protocol are only arguments.