## CryptoDB

### James Bartusek

#### Publications

**Year**

**Venue**

**Title**

2022

PKC

Reusable Two-Round MPC from LPN
📺
Abstract

We present a new construction of maliciously-secure, two-round multiparty computation (MPC) in the CRS model, where the first message is reusable an unbounded number of times. The security of the protocol relies on the Learning Parity with Noise (LPN) assumption with inverse polynomial noise rate $1/n^{1-\epsilon}$ for small enough constant $\epsilon$, where $n$ is the LPN dimension. Prior works on reusable two-round MPC required assumptions such as DDH or LWE that imply some flavor of homomorphic computation. We obtain our result in two steps:
- In the first step, we construct a two-round MPC protocol in the {\it silent pre-processing model} (Boyle et al., Crypto 2019). Specifically, the parties engage in a computationally inexpensive setup procedure that generates some correlated random strings. Then, the parties commit to their inputs. Finally, each party sends a message depending on the function to be computed, and these messages can be decoded to obtain the output. Crucially, the complexity of the pre-processing phase and the input commitment phase do not grow with the size of the circuit to be computed. We call this {\it multiparty silent NISC} (msNISC), generalizing the notion of two-party silent NISC of Boyle et al. (CCS 2019). We provide a construction of msNISC from LPN in the random oracle model.
- In the second step, we give a transformation that removes the pre-processing phase and use of random oracle from the previous protocol. This transformation additionally adds (unbounded) reusability of the first round message, giving the first construction of reusable two-round MPC from the LPN assumption. This step makes novel use of randomized encoding of circuits (Applebaum et al., FOCS 2004) and a variant of the ``tree of MPC messages" technique of Ananth et al. and Bartusek et al. (TCC 2020).

2022

CRYPTO

Succinct Classical Verification of Quantum Computation
📺
Abstract

We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in the runtime of the BQP computation (and polynomial in the security parameter). Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning with Errors (LWE). This is the first succinct argument for quantum computation in the plain model; prior work (Chia-Chung-Yamakawa, TCC ’20) requires both a long common reference string and non-black-box use of a hash function modeled as a random oracle.
At a technical level, we revisit the framework for constructing classically verifiable quantum computation (Mahadev, FOCS ’18). We give a self-contained, modular proof of security for Mahadev’s protocol, which we believe is of independent interest. Our proof readily generalizes to a setting in which the verifier’s first message (which consists of many public keys) is compressed. Next, we formalize this notion of compressed public keys; we view the object as a generalization of constrained/programmable PRFs and instantiate it based on indistinguishability obfuscation.
Finally, we compile the above protocol into a fully succinct argument using a (sufficiently composable) succinct argument of knowledge for NP. Using our framework, we achieve several additional results, including
– Succinct arguments for QMA (given multiple copies of the witness),
– Succinct non-interactive arguments for BQP (or QMA) in the quantum random oracle model, and
– Succinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without iO).

2021

CRYPTO

One-Way Functions Imply Secure Computation in a Quantum World
📺
Abstract

We prove that quantum-hard one-way functions imply simulation-secure quantum oblivious transfer (QOT), which is known to suffice for secure computation of arbitrary quantum functionalities. Furthermore, our construction only makes black-box use of the quantum-hard one-way function.
Our primary technical contribution is a construction of extractable and equivocal quantum bit commitments based on the black-box use of quantum-hard one-way functions in the standard model. Instantiating the Crépeau-Kilian (FOCS 1988) framework with these commitments yields simulation-secure quantum oblivious transfer.

2021

EUROCRYPT

Post-Quantum Multi-Party Computation
📺
Abstract

We initiate the study of multi-party computation for classical functionalities in the plain model, with security against malicious quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and quantum polynomial hardness of an LWE-based circular security assumption.
Along the way, we develop the following cryptographic primitives that may be of independent interest:
1.) A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of (a circular variant of) the LWE problem. This immediately yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys.
2.) A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.
To prove the security of our protocol, we develop a new straight-line non-black-box simulation technique against parallel sessions that does not clone the adversary's state. This technique may also be relevant to the classical setting.

2021

CRYPTO

On the Round Complexity of Secure Quantum Computation
📺
Abstract

We construct the first constant-round protocols for secure quantum computation in the two-party (2PQC) and multi-party (MPQC) settings with security against malicious adversaries. Our protocols are in the common random string (CRS) model.
- Assuming two-message oblivious transfer (OT), we obtain (i) three-message 2PQC, and (ii) five-round MPQC with only three rounds of online (input-dependent) communication; such OT is known from quantum-hard Learning with Errors (QLWE). - Assuming sub-exponential hardness of QLWE, we obtain (i) three-round 2PQC with two online rounds and (ii) four-round MPQC with two online rounds. - When only one (out of two) parties receives output, we achieve minimal interaction (two messages) from two-message OT; classically, such protocols are known as non-interactive secure computation (NISC), and our result constitutes the first maliciously-secure quantum NISC. Additionally assuming reusable malicious designated-verifier NIZK arguments for NP (MDV-NIZKs), we give the first MDV-NIZK for QMA that only requires one copy of the quantum witness. Finally, we perform a preliminary investigation into two-round secure quantum computation where each party must obtain output. On the negative side, we identify a broad class of simulation strategies that suffice for classical two-round secure computation that are unlikely to work in the quantum setting. Next, as a proof-of-concept, we show that two-round secure quantum computation exists with respect to a quantum oracle.

2021

TCC

Secure Quantum Computation with Classical Communication
📺
Abstract

The study of secure multi-party computation (MPC) has thus far been limited to the following two settings: every party is fully classical, or every party has quantum capabilities. This paper studies a notion of MPC that allows some classical and some quantum parties to securely compute a quantum functionality over their joint private inputs.
In particular, we construct constant-round \emph{composable} protocols for blind and verifiable classical delegation of quantum computation, and give applications to secure quantum computation with classical communication. Assuming QLWE (the quantum hardness of learning with errors), we obtain the following (maliciously-secure) protocols for computing any BQP (bounded-error quantum polynomial-time) functionality.
- A six-round protocol between one quantum server and multiple classical clients in the CRS (common random string) model.
- A three-round protocol between one quantum server and multiple classical clients in the PKI (public-key infrastructure) + QRO (quantum random oracle) model.
- A two-message protocol between quantum sender and classical receiver (a quantum non-interactive secure computation protocol), in the QRO model.
To enable composability of classical verification of quantum computation, we require the notion of \emph{malicious blindness}, which stipulates that the prover does not learn anything about the verifier's delegated computation, even if it is able to observe whether or not the verifier accepted the proof. To construct a protocol with malicious blindness, we use a classical verification protocol for sampBQP computation (Chung et al., Arxiv 2020), which in general has inverse polynomial soundness error, to prove honest evaluation of QFHE (quantum fully-homomorphic encryption) ciphertexts with negligible soundness error. Obtaining a constant-round protocol requires a strong parallel repetition theorem for classical verification of quantum computation, which we show following the "nearly orthogonal projector" proof strategy (Alagic et al., TCC 2020).

2021

TCC

Two-Round Maliciously Secure Computation with Super-Polynomial Simulation
📺
Abstract

We propose the first maliciously secure multi-party computation (MPC) protocol for general functionalities in two rounds, without any trusted setup. Since polynomial-time simulation is impossible in two rounds, we achieve the relaxed notion of superpolynomial-time simulation security [Pass, EUROCRYPT 2003]. Prior to our work, no such maliciously secure protocols were known even in the two-party setting for functionalities where both parties receive outputs. Our protocol is based on the sub-exponential security of standard assumptions plus a special type of non-interactive non-malleable commitment.
At the heart of our approach is a two-round multi-party conditional disclosure of secrets (MCDS) protocol in the plain model from bilinear maps, which is constructed from techniques introduced in [Benhamouda and Lin, TCC 2020].

2020

TCC

Reusable Two-Round MPC from DDH
📺
Abstract

We present a reusable two-round multi-party computation (MPC) protocol from the Decisional Diffie Hellman assumption (DDH). In particular, we show how to upgrade any secure two-round MPC protocol to allow reusability of its first message across multiple computations, using Homomorphic Secret Sharing (HSS) and pseudorandom functions in NC1 — each of which can be instantiated from DDH.
In our construction, if the underlying two-round MPC protocol is secure against semi-honest adversaries (in the plain model) then so is our reusable two-round MPC protocol. Similarly, if the underlying two-round MPC protocol is secure against malicious adversaries (in the common random/reference string model) then so is our reusable two-round MPC protocol. Previously, such reusable two-round MPC protocols were only known under assumptions on lattices.
At a technical level, we show how to upgrade any two-round MPC protocol to a first message succinct two-round MPC protocol, where the first message of the protocol is generated independently of the computed circuit (though it is not reusable). This step uses homomorphic secret sharing (HSS) and low-depth pseudorandom functions. Next, we show a generic transformation that upgrades any first message succinct two-round MPC to allow for reusability of its first message.

2019

EUROCRYPT

New Techniques for Obfuscating Conjunctions
📺
Abstract

A conjunction is a function $$f(x_1,\dots ,x_n) = \bigwedge _{i \in S} l_i$$ where $$S \subseteq [n]$$ and each $$l_i$$ is $$x_i$$ or $$\lnot x_i$$. Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon codeword and placing the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group model for random conjunctions where $$|S| \ge 0.226n$$. While conjunction obfuscation is known from LWE [31, 47], these constructions rely on substantial technical machinery.In this work, we conduct an extensive study of simple conjunction obfuscation techniques.
We abstract the Bishop et al. scheme to obtain an equivalent yet more efficient “dual” scheme that can handle conjunctions over exponential size alphabets. This scheme admits a straightforward proof of generic group security, which we combine with a novel combinatorial argument to obtain distributional VBB security for |S| of any size.If we replace the Reed-Solomon code with a random binary linear code, we can prove security from standard LPN and avoid encoding in a group. This addresses an open problem posed by Bishop et al. to prove security of this simple approach in the standard model.We give a new construction that achieves information theoretic distributional VBB security and weak functionality preservation for $$|S| \ge n - n^\delta $$ and $$\delta < 1$$. Assuming discrete log and $$\delta < 1/2$$, we satisfy a stronger notion of functionality preservation for computationally bounded adversaries while still achieving information theoretic security.

2019

CRYPTO

The Distinction Between Fixed and Random Generators in Group-Based Assumptions
📺
Abstract

There is surprisingly little consensus on the precise role of the generator g in group-based assumptions such as DDH. Some works consider g to be a fixed part of the group description, while others take it to be random. We study this subtle distinction from a number of angles.
In the generic group model, we demonstrate the plausibility of groups in which random-generator DDH (resp. CDH) is hard but fixed-generator DDH (resp. CDH) is easy. We observe that such groups have interesting cryptographic applications.We find that seemingly tight generic lower bounds for the Discrete-Log and CDH problems with preprocessing (Corrigan-Gibbs and Kogan, Eurocrypt 2018) are not tight in the sub-constant success probability regime if the generator is random. We resolve this by proving tight lower bounds for the random generator variants; our results formalize the intuition that using a random generator will reduce the effectiveness of preprocessing attacks.We observe that DDH-like assumptions in which exponents are drawn from low-entropy distributions are particularly sensitive to the fixed- vs. random-generator distinction. Most notably, we discover that the Strong Power DDH assumption of Komargodski and Yogev (Komargodski and Yogev, Eurocrypt 2018) used for non-malleable point obfuscation is in fact false precisely because it requires a fixed generator. In response, we formulate an alternative fixed-generator assumption that suffices for a new construction of non-malleable point obfuscation, and we prove the assumption holds in the generic group model. We also give a generic group proof for the security of fixed-generator, low-entropy DDH (Canetti, Crypto 1997).

2019

TCC

On the (In)security of Kilian-Based SNARGs
Abstract

The Fiat-Shamir transform is an incredibly powerful technique that uses a suitable hash function to reduce the interaction of general public-coin protocols. Unfortunately, there are known counterexamples showing that this methodology may not be sound (no matter what concrete hash function is used). Still, these counterexamples are somewhat unsatisfying, as the underlying protocols were specifically tailored to make Fiat-Shamir fail. This raises the question of whether this transform is sound when applied to natural protocols.One of the most important protocols for which we would like to reduce interaction is Kilian’s four-message argument system for all of
$$\mathsf {NP}$$
, based on collision resistant hash functions (
$$\mathsf {CRHF}$$
) and probabilistically checkable proofs (
$$\mathsf {PCP}$$
s). Indeed, an application of the Fiat-Shamir transform to Kilian’s protocol is at the heart of both theoretical results (e.g., Micali’s CS proofs) as well as leading practical approaches of highly efficient non-interactive proof-systems (e.g.,
$$\mathsf {SNARK}$$
s and
$$\mathsf {STARK}$$
s).In this work, we show significant obstacles to establishing soundness of (what we refer to as) the “Fiat-Shamir-Kilian-Micali” (
$$\mathsf {FSKM}$$
) protocol. More specifically:We construct a (contrived)
$$\mathsf {CRHF}$$
for which
$$\mathsf {FSKM}$$
is unsound for a very large class of
$$\mathsf {PCP}$$
s and for any Fiat-Shamir hash function. The collision-resistance of our
$$\mathsf {CRHF}$$
relies on very strong but plausible cryptographic assumptions. The statement is “tight” in the following sense: any
$$\mathsf {PCP}$$
outside the scope of our result trivially implies a
$$\mathsf {SNARK}$$
, eliminating the need for
$$\mathsf {FSKM}$$
in the first place.Second, we consider a known extension of Kilian’s protocol to an interactive variant of
$$\mathsf {PCP}$$
s called probabilistically checkable interactive proofs (
$$\mathsf {PCIP})$$
(also known as interactive oracle proofs or
$$\mathsf {IOP}$$
s). We construct a particular (contrived)
$$\mathsf {PCIP}$$
for
$$\mathsf {NP}$$
for which the
$$\mathsf {FSKM}$$
protocol is unsound no matter what
$$\mathsf {CRHF}$$
and Fiat-Shamir hash function is used. This result is unconditional (i.e., does not rely on any cryptographic assumptions).
Put together, our results show that the soundness of
$$\mathsf {FSKM}$$
must rely on some special structure of both the
$$\mathsf {CRHF}$$
and
$$\mathsf {PCP}$$
that underlie Kilian’s protocol. We believe these negative results may cast light on how to securely instantiate the
$$\mathsf {FSKM}$$
protocol by a synergistic choice of the
$$\mathsf {PCP}$$
,
$$\mathsf {CRHF}$$
, and Fiat-Shamir hash function.

2019

ASIACRYPT

Public-Key Function-Private Hidden Vector Encryption (and More)
Abstract

We construct public-key function-private predicate encryption for the “small superset functionality,” recently introduced by Beullens and Wee (PKC 2019). This functionality captures several important classes of predicates:Point functions. For point function predicates, our construction is equivalent to public-key function-private anonymous identity-based encryption.Conjunctions. If the predicate computes a conjunction, our construction is a public-key function-private hidden vector encryption scheme. This addresses an open problem posed by Boneh, Raghunathan, and Segev (ASIACRYPT 2013).d-CNFs and read-once conjunctions of d-disjunctions for constant-size d.
Our construction extends the group-based obfuscation schemes of Bishop et al. (CRYPTO 2018), Beullens and Wee (PKC 2019), and Bartusek et al. (EUROCRYPT 2019) to the setting of public-key function-private predicate encryption. We achieve an average-case notion of function privacy, which guarantees that a decryption key
$$\mathsf {sk} _f$$
reveals nothing about f as long as f is drawn from a distribution with sufficient entropy. We formalize this security notion as a generalization of the (enhanced) real-or-random function privacy definition of Boneh, Raghunathan, and Segev (CRYPTO 2013). Our construction relies on bilinear groups, and we prove security in the generic bilinear group model.

2018

TCC

Return of GGH15: Provable Security Against Zeroizing Attacks
Abstract

The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly broken by so-called “zeroizing attacks,” which exploit leakage from honest zero-test queries. The precise settings in which zeroizing attacks are possible have remained unclear. Most notably, none of the current indistinguishability obfuscation (iO) candidates from GGH15 have any formal security guarantees against zeroizing attacks.In this work, we demonstrate that all known zeroizing attacks on GGH15 implicitly construct algebraic relations between the results of zero-testing and the encoded plaintext elements. We then propose a “GGH15 zeroizing model” as a new general framework which greatly generalizes known attacks.Our second contribution is to describe a new GGH15 variant, which we formally analyze in our GGH15 zeroizing model. We then construct a new iO candidate using our multilinear map, which we prove secure in the GGH15 zeroizing model. This implies resistance to all known zeroizing strategies. The proof relies on the Branching Program Un-Annihilatability (BPUA) Assumption of Garg et al. [TCC 16-B] (which is implied by PRFs in $$\mathsf {NC}^1$$ secure against $$\mathsf {P}/\mathsf {poly}$$) and the complexity-theoretic p-Bounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).

#### Coauthors

- Amit Agarwal (2)
- Liron Bronfman (1)
- Brent Carmer (1)
- Andrea Coladangelo (2)
- Sanjam Garg (2)
- Vipul Goyal (2)
- Jiaxin Guan (1)
- Justin Holmgren (1)
- Abhishek Jain (1)
- Zhengzhong Jin (1)
- Yael Tauman Kalai (1)
- Dakshita Khurana (4)
- Tancrède Lepoint (2)
- Alex Lombardi (1)
- Fermi Ma (8)
- Giulio Malavolta (3)
- Tal Malkin (1)
- Alex J. Malozemoff (1)
- Daniel Masny (1)
- Pratyay Mukherjee (1)
- Mariana Raykova (1)
- Ron D. Rothblum (1)
- Akshayaram Srinivasan (1)
- Vinod Vaikuntanathan (1)
- Thomas Vidick (1)
- Lizhen Yang (1)
- Mark Zhandry (3)
- Yinuo Zhang (1)