International Association
for Cryptologic Research

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.

In the context of secure multiparty computation (MPC) protocols with guaranteed output delivery (GOD) for the honest majority setting, the state-of-the-art in terms of communication is the work of (Goyal et al. CRYPTO'20), which communicates O(n|C|) field elements, where |C| is the size of the circuit being computed and n is the number of parties. Their round complexity, as usual in secret-sharing based MPC, is proportional to O(depth(C)), but only in the optimistic case where there is no cheating. Under attack, the number of rounds can increase to \Omega(n^2) before honest parties receive output, which is undesired for shallow circuits with depth(C) << n^2. In contrast, other protocols that only require O(depth(C) rounds even in the worst case exist, but the state-of-the-art from (Choudhury and Patra, Transactions on Information Theory, 2017) still requires \Omega(n^4|C|) communication in the offline phase, and \Omega(n^3|C|) in the online (for both point-to-point and broadcast channels). We see there exists a tension between efficient communication and number of rounds. For reference, the recent work of (Abraham et al., EUROCRYPT'23) shows that for perfect security and t<n/3, protocols with both linear communication and O(depth(C)) rounds exist. We address this state of affairs by presenting a novel honest majority GOD protocol that maintains O(depth(C)) rounds, even under attack, while improving over the communication of the most efficient protocol in this setting by Choudhury and Patra. More precisely, our protocol has point-to-point (P2P) online communication of O(n|C|), accompanied by O(n|C|) broadcasted (BC) elements, while the offline has O(n^3|C|) P2P communication with O(n^3|C|) BC. This improves over the previous best result, and reduces the tension between communication and round complexity. Our protocol is achieved via a careful use of packed secret-sharing in order to improve the communication of existing verifiable secret-sharing approaches, although at the expense of weakening their robust guarantees: reconstruction of shared values may fail, but only if the adversary gives away the identities of many corrupt parties. We show that this less powerful notion is still useful for MPC, and we use this as a core building block in our construction. Using this weaker VSS, we adapt the recent secure-with-abort Turbopack protocol (Escudero et al. CCS'22) to the GOD setting without significantly sacrificing in efficiency.

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.

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).

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.

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].