International Association for Cryptologic Research

International Association
for Cryptologic Research


Amit Agarwal


Compressing Unit-Vector Correlations via Sparse Pseudorandom Generators
A unit-vector (UV) correlation is an additive secret-sharing of a vector of length B that contains 1 in a secret random position and 0's elsewhere. UV correlations are a useful resource for many cryptographic applications, including low-communication secure multiparty computation and multi-server private information retrieval. However, current practical methods for securely generating UV correlations involve a significant communication cost per instance, and become even more expensive when requiring security against malicious parties. In this work, we present a new approach for constructing a pseudorandom correlation generator (PCG) for securely generating n independent instances of UV correlations of any polynomial length B. Such a PCG compresses the n UV instances into correlated seeds whose length is sublinear in the description size n log B. Our new PCGs apply in both the honest-majority and dishonest-majority settings, and are based on a variety of assumptions. In particular, in the honest-majority case they only require "unstructured" assumptions. Our PCGs give rise to secure end-to-end protocols for generating n instances of UV correlations with o(n) bits of communication. This applies even to an authenticated variant of UV correlations, which is useful for security against malicious parties. Unlike previous theoretical solutions, some instances of our PCGs offer good concrete efficiency. Our technical approach is based on combining a low-degree sparse pseudorandom generator, mapping a sparse seed to a pseudorandom sparse output, with homomorphic secret sharing for low-degree polynomials. We then reduce such sparse PRGs to local PRGs over large alphabets, and explore old and new approaches for maximizing the stretch of such PRGs while minimizing their locality. Finally, towards further compressing the PCG seeds, we present a new PRG-based construction of a multiparty distributed point function (DPF), whose outputs are degree-1 Shamir-shares of a secret point function. This result is independently motivated by other DPF applications.
A New Framework for Quantum Oblivious Transfer
We present a new template for building oblivious transfer from quantum information that we call the "fixed basis'' framework. Our framework departs from prior work (eg., Crepeau and Kilian, FOCS '88) by fixing the *correct* choice of measurement basis used by each player, except for some hidden *trap* qubits that are intentionally measured in a conjugate basis. We instantiate this template in the quantum random oracle model (QROM) to obtain simple protocols that implement, with security against malicious adversaries: 1. *Non-interactive* random-input bit OT in a model where parties share EPR pairs a priori. 2. Two-round random-input bit OT without setup, obtained by showing that the protocol above remains secure even if the (potentially malicious) OT receiver sets up the EPR pairs. 3. Three-round chosen-input string OT from BB84 states without entanglement or setup. This improves upon natural variations of the CK88 template that require at least five rounds. Along the way, we develop technical tools that may be of independent interest. We prove that natural functions like XOR enable *seedless* randomness extraction from certain quantum sources of entropy. We also use idealized (i.e. extractable and equivocal) bit commitments, which we obtain by proving security of simple and efficient constructions in the QROM.
On Black-Box Verifiable Outsourcing
We study the problem of verifiably outsourcing computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class F. This allows a verifier to efficiently verify the correctness of any f \in F evaluated on a batch of n instances x_1, ...., x_n, while only making \lambda calls to an oracle for f (along with O(n \lambda) calls to low-complexity helper oracles), where \lambda denotes a security parameter. We obtain the following positive and negative results: 1. We build OBVC protocols for the class F of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes. 2. We show that there cannot exist OBVC schemes for the class F of all functions mapping \lambda-bit inputs to \lambda-bit outputs, for any n = \poly(\lambda).
Post-Quantum Multi-Party Computation 📺
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.
Two-Round Maliciously Secure Computation with Super-Polynomial Simulation 📺
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].