## CryptoDB

### Peter Scholl

#### Publications

**Year**

**Venue**

**Title**

2022

PKC

On the Bottleneck Complexity of MPC with Correlated Randomness
Abstract

At ICALP 2018, Boyle et al. introduced the notion of the \emph{bottleneck complexity} of a secure multi-party computation (MPC) protocol. This measures the maximum communication complexity of any one party in the protocol, aiming to improve load-balancing among the parties.
In this work, we study the bottleneck complexity of MPC in the preprocessing model, where parties are given correlated randomness ahead of time.
We present two constructions of \emph{bottleneck-efficient} MPC protocols, whose bottleneck complexity is independent of the number of parties:
1. A protocol for computing abelian programs, based only on one-way functions.
2. A protocol for selection functions, based on any linearly homomorphic encryption scheme.
Compared with previous bottleneck-efficient constructions, our protocols can be based on a wider range of assumptions, and avoid the use of fully homomorphic encryption.

2022

PKC

Low-Communication Multiparty Triple Generation for SPDZ from Ring-LPN
Abstract

The SPDZ protocol for multi-party computation relies on a correlated randomness setup consisting of authenticated, multiplication triples. A recent line of work by Boyle et al. (Crypto 2019, Crypto 2020) has investigated the possibility of producing this correlated randomness in a \emph{silent preprocessing} phase, which involves a ``small'' setup protocol with less communication than the total size of the triples being produced. These works do this using a tool called a \emph{pseudorandom correlation generator} (PCG), which allows a large batch of correlated randomness to be compressed into a set of smaller, correlated seeds. However, existing methods for compressing SPDZ triples only apply to the 2-party setting.
In this work, we construct a PCG for producing SPDZ triples over large prime fields in the multi-party setting. The security of our PCG is based on the ring-LPN assumption over fields, similar to the work of Boyle et al. (Crypto 2020) in the 2-party setting. We also present a corresponding, actively secure setup protocol, which can be used to generate the PCG seeds and instantiate SPDZ with a silent preprocessing phase. As a building block, which may be of independent interest, we construct a new type of 3-party distributed point function supporting outputs over arbitrary groups (including large prime order), as well as an efficient protocol for setting up our DPF keys with active security.

2021

JOFC

High-Performance Multi-party Computation for Binary Circuits Based on Oblivious Transfer
Abstract

We present a unified view of the two-party and multi-party computation protocols based on oblivious transfer first outlined in Nielsen et al. (CRYPTO 2012) and Larraia et al. (CRYPTO 2014). We present a number of modifications and improvements to these earlier presentations, as well as full proofs of the entire protocol. Improvements include a unified pre-processing and online MAC methodology, mechanisms to pass between different MAC variants and fixing a minor bug in the protocol of Larraia et al. in relation to a selective failure attack. It also fixes a minor bug in Nielsen et al. resulting from using Jensen’s inequality in the wrong direction in an analysis.

2021

EUROCRYPT

The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT
📺
Abstract

We describe a simple method for solving the distributed discrete logarithm problem in Paillier groups, allowing two parties to locally convert multiplicative shares of a secret (in the exponent) into additive shares. Our algorithm is perfectly correct, unlike previous methods with an inverse polynomial error probability. We obtain the following applications and further results.
– Homomorphic secret sharing:
We construct homomorphic secret sharing for branching programs with negligible correctness error and supporting exponentially large plaintexts, with security based on the decisional composite residuosity (DCR) assumption.
– Correlated pseudorandomness:
Pseudorandom correlation functions (PCFs), recently introduced by Boyle et al. (FOCS 2020), allow two parties to obtain a practically unbounded quantity of correlated randomness, given a pair of short, correlated keys. We construct PCFs for the oblivious transfer (OT) and vector oblivious linear evaluation (VOLE) correlations, based on the quadratic residuosity (QR) or DCR assumptions, respectively. We also construct a pseudorandom correlation generator (for producing a bounded number of samples, all at once) for OLE, based on a combination of the DCR and learning parity with noise assumptions.
– Public-keysilentOT/VOLE:
We upgrade our PCF constructions to have a public-key setup, where after independently posting a public key, each party can locally derive its PCF key. This allows completely silent generation of an arbitrary amount of OTs or VOLEs, without any interaction beyond a PKI, based on QR and DCR. The public-key setup is based on a novel non-interactive vector OLE protocol which can be seen as a variant of the Bellare-Micali oblivious transfer protocol.

2021

PKC

Banquet: Short and Fast Signatures from AES
📺
Abstract

In this work we introduce Banquet, a digital signature scheme with post-quantum security, constructed using only symmetric-key primitives. The design is based on the MPC-in-head paradigm also used by Picnic (CCS 2017) and BBQ (SAC 2019). Like BBQ, Banquet uses only standardized primitives, namely AES and SHA-3, but signatures are more than 50\% shorter, making them competitive with Picnic (which uses a non-standard block cipher to improve performance). The MPC protocol in Banquet uses a new technique to verify correctness of the AES S-box computations, which is efficient because the cost is amortized with a batch verification strategy.
Our implementation and benchmarks also show that both signing and verification can be done in under 10ms on a current x64 CPU. We also explore the parameter space to show the range of trade-offs that are possible with the Banquet design, and show that Banquet can nearly match the signature sizes possible with Picnic (albeit with slower, but still practical run times) or have speed within a factor of two of Picnic (at the cost of larger signatures).

2021

CRYPTO

Low-Complexity Weak Pseudorandom Functions in AC0[MOD2]
📺
Abstract

A *weak pseudorandom function* (WPRF) is a keyed function $f_k:\{0,1\}^n\to\{0,1\}$ such that, for a random key $k$, a collection of samples $(x, f_k(x))$, for {\em uniformly random} inputs $x$, cannot be efficiently distinguished from totally random input-output pairs $(x,y)$. We study WPRFs in AC0[MOD2], the class of functions computable by AC0 circuits with parity gates, making the following contributions.
- *Between Lapland and Cryptomania.* We show that WPRFs in AC0[MOD2] imply a variant of the Learning Parity with Noise (LPN) assumption. This gives an unconditional version of an earlier conditional result of Akavia et al. (ITCS 2014). We further show that WPRFs in a subclass of AC0[mod 2] that includes a recent WPRF candidate by Boyle et al. (FOCS 2020) imply, under a seemingly weak additional conjecture, public-key encryption.
- *WPRF by sparse polynomials.* We propose the first WPRF candidate that can be computed by sparse multivariate polynomials over $\F_2$. We prove that it has subexponential security against linear and algebraic attacks.
- *WPRF in AC0 ◦ MOD2.* We study the existence of WPRFs computed by AC0 circuits \emph{over} parity gates. We propose a modified version of a previous WPRF candidate of Akavia et al., and prove that it resists the algebraic attacks that were used by Bogdanov and Rosen (ECCC 2017) to break the original candidate in quasipolynomial time. We give evidence against the possibility of using {\em public} parity gates and relate this question to other conjectures.

2021

CRYPTO

Mac'n'Cheese: Zero-Knowledge Proofs for Boolean and Arithmetic Circuits with Nested Disjunctions
📺
Abstract

Zero knowledge proofs are an important building block in many cryptographic applications.
Unfortunately, when the proof statements become very large, existing
zero-knowledge proof systems easily reach their limits: either the computational
overhead, the memory footprint, or the required bandwidth exceed levels that
would be tolerable in practice.
We present an interactive zero-knowledge proof system for boolean and
arithmetic circuits, called Mac'n'Cheese, with a focus on supporting large
circuits. Our work follows the commit-and-prove paradigm instantiated using
information-theoretic MACs based on vector oblivious linear evaluation to
achieve high efficiency. We additionally show how to optimize disjunctions,
with a general OR transformation for proving the disjunction of $m$
statements that has communication complexity proportional to the longest
statement (plus an additive term logarithmic in $m$). These disjunctions can
further be \emph{nested}, allowing efficient proofs about complex statements
with many levels of disjunctions. We also show how to make Mac'n'Cheese
non-interactive (after a preprocessing phase) using the Fiat-Shamir
transform, and with only a small degradation in soundness.
We have implemented the online phase of Mac'n'Cheese and achieve a runtime of 144~ns per AND
gate and 1.5~$\mu$s per multiplication gate in $\mathbb{F}_{2^{61}-1}$ when run over a network
with a 95~ms latency and a bandwidth of 31.5~Mbps. In addition, we show that
the disjunction optimization improves communication as expected: when
proving a boolean circuit with eight branches and each branch containing
roughly 1 billion multiplications, Mac'n'Cheese requires only 75 more bytes to
communicate than in the single branch case.

2020

CRYPTO

Efficient Constant-Round MPC with Identifiable Abort and Public Verifiability
📺
Abstract

Recent years have seen a tremendous growth in the interest in se-
cure multiparty computation (MPC) and its applications. While much progress
has been made concerning its efficiency, many current, state-of-the-art protocols
are vulnerable to Denial of Service attacks, where a cheating party may prevent
the honest parties from learning the output of the computation, whilst remaining
anonymous. The security model of identifiable abort aims to prevent these at-
tacks, by allowing honest parties to agree upon the identity of a cheating party,
who can then be excluded in the future. Several existing MPC protocols offer
security with identifiable abort against a dishonest majority of corrupted parties.
However, all of these protocols have a round complexity that scales linearly with
the depth of the circuit (and are therefore unsuitable for use in high latency net-
works) or use cryptographic primitives or techniques that have a high computa-
tional overhead.
In this work, we present the first efficient MPC protocols with identifiable abort
in the dishonest majority setting, which run in a constant number of rounds and
make only black-box use of cryptographic primitives. Our main construction is
built from highly efficient primitives in a careful way to achieve identifiability
at a low cost. In particular, we avoid the use of public-key operations outside of
a setup phase, incurring a relatively low overhead on top of the fastest currently
known constant-round MPC protocols based on garbled circuits. Our construction
also avoids the use of adaptively secure primitives and heavy zero-knowledge
machinery, which was inherent in previous works. In addition, we show how to
upgrade our protocol to achieve public verifiability using a public bulletin board,
allowing any external party to verify correctness of the computation or identify a
cheating party.

2020

CRYPTO

Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits
📺
Abstract

This work introduces novel techniques to improve the translation between arithmetic and binary data types in multi-party computation.
To this end, we introduce a new approach to performing these conversions, using what we call \emph{extended doubly-authenticated bits} (edaBits), which correspond to shared integers in the arithmetic domain whose bit decomposition is shared in the binary domain.
These can be used to considerably increase the efficiency of non-linear operations such as truncation, secure comparison and bit-decomposition.
Our eDaBits are similar to the \emph{daBits} technique introduced by Rotaru et al.~(Indocrypt 2019).
However, our main observations are that (1) applications that benefit from daBits can also benefit from edaBits in the same way, and (2) we can generate edaBits directly in a much more efficeint way than computing them directly from a set of DaBits.
Technically, the second contribution is much more challenging, and involves a novel cut and choose technique that may be of independent interest, and requires taking advantage of natural tamper-resilient properties of binary circuits that occur in our construction to obtain the best level of efficiency.
Finally, we show how our eDaBits can be applied to efficiently implement various non-linear protocols of interest, and we thoroughly analyze their correctness for both signed and unsigned integers.
The results of this work can be applied to any corruption threshold, although they seem best suited to dishonest majority protocols such as SPDZ.
We implement and benchmark our constructions, and experimentally verify that our technique yield a substantial increase in effiency.
Our eDaBits save in communication by a factor that lies between $2$ and $170$ for
secure comparisons with respect to a purely arithmetic approach, and between $2$ and $60$ with respect to using daBits.
Improvements in throughput per second are more subdued but still as high as a factor of $47$.
We also apply our novel machinery to the tasks of biometric matching and convolutional neural networks, obtaining a noticeable improvement as well.

2020

CRYPTO

Efficient Pseudorandom Correlation Generators from Ring-LPN
📺
Abstract

Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated using a cheap, one-time interaction, followed by only ``silent'' local computation. This is achieved via a \emph{pseudorandom correlation generator} (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation. Previous works constructed concretely efficient PCGs for simple but useful correlations, including random oblivious transfer and vector-OLE, together with efficient protocols to distribute the PCG seed generation. Most of these constructions were based on variants of the Learning Parity with Noise (LPN) assumption. PCGs for other useful correlations had poor asymptotic and concrete efficiency.
In this work, we design a new class of efficient PCGs based on different flavors of the {\em ring-LPN} assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.

2020

JOFC

Low Cost Constant Round MPC Combining BMR and Oblivious Transfer
Abstract

In this work, we present two new actively secure, constant-round multi-party computation (MPC) protocols with security against all-but-one corruptions. Our protocols both start with an actively secure MPC protocol, which may have linear round complexity in the depth of the circuit, and compile it into a constant-round protocol based on garbled circuits, with very low overhead. 1. Our first protocol takes a generic approach using any secret-sharing-based MPC protocol for binary circuits, and a correlated oblivious transfer functionality. 2. Our second protocol builds on secret-sharing-based MPC with information-theoretic MACs. This approach is less flexible, being based on a specific form of MPC, but requires no additional oblivious transfers to compute the garbled circuit. In both approaches, the underlying secret-sharing-based protocol is only used for one actively secure $$\mathbb {F}_2$$ F 2 multiplication per AND gate . An interesting consequence of this is that, with current techniques, constant-round MPC for binary circuits is not much more expensive than practical, non-constant-round protocols. We demonstrate the practicality of our second protocol with an implementation and perform experiments with up to 9 parties securely computing the AES and SHA-256 circuits. Our running times improve upon the best possible performance with previous protocols in this setting by 60 times.

2019

EUROCRYPT

Homomorphic Secret Sharing from Lattices Without FHE
📺
Abstract

Homomorphic secret sharing (HSS) is an analog of somewhat- or fully homomorphic encryption (S/FHE) to the setting of secret sharing, with applications including succinct secure computation, private manipulation of remote databases, and more. While HSS can be viewed as a relaxation of S/FHE, the only constructions from lattice-based assumptions to date build atop specific forms of threshold or multi-key S/FHE. In this work, we present new techniques directly yielding efficient 2-party HSS for polynomial-size branching programs from a range of lattice-based encryption schemes, without S/FHE. More concretely, we avoid the costly key-switching and modulus-reduction steps used in S/FHE ciphertext multiplication, replacing them with a new distributed decryption procedure for performing “restricted” multiplications of an input with a partial computation value. Doing so requires new methods for handling the blowup of “noise” in ciphertexts in a distributed setting, and leverages several properties of lattice-based encryption schemes together with new tricks in share conversion.The resulting schemes support a superpolynomial-size plaintext space and negligible correctness error, with share sizes comparable to SHE ciphertexts, but cost of homomorphic multiplication roughly one order of magnitude faster. Over certain rings, our HSS can further support some level of packed SIMD homomorphic operations. We demonstrate the practical efficiency of our schemes within two application settings, where we compare favorably with current best approaches: 2-server private database pattern-match queries, and secure 2-party computation of low-degree polynomials.

2019

CRYPTO

Efficient Pseudorandom Correlation Generators: Silent OT Extension and More
📺
Abstract

Secure multiparty computation (MPC) often relies on correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight “non-cryptographic” online phase once the inputs are known. However, since the amount of randomness typically scales with the circuit size of the function being computed, securely generating correlated randomness forms an efficiency bottleneck, involving a large amount of communication and storage.A natural tool for addressing the above limitations is a pseudorandom correlation generator (PCG). A PCG allows two or more parties to securely generate long sources of useful correlated randomness via a local expansion of correlated short seeds and no interaction. PCGs enable MPC with silent preprocessing, where a small amount of interaction used for securely sampling the seeds is followed by silent local generation of correlated pseudorandomness.A concretely efficient PCG for Vector-OLE correlations was recently obtained by Boyle et al. (CCS 2018) based on variants of the learning parity with noise (LPN) assumption over large fields. In this work, we initiate a systematic study of PCGs and present concretely efficient constructions for several types of useful MPC correlations. We obtain the following main contributions:PCG foundations. We give a general security definition for PCGs. Our definition suffices for any MPC protocol satisfying a stronger security requirement that is met by existing protocols. We prove that a stronger security requirement is indeed necessary, and justify our PCG definition by ruling out a stronger and more natural definition.Silent OT extension. We present the first concretely efficient PCG for oblivious transfer correlations. Its security is based on a variant of the binary LPN assumption and any correlation-robust hash function. We expect it to provide a faster alternative to the IKNP OT extension protocol (Crypto 2003) when communication is the bottleneck. We present several applications, including protocols for non-interactive zero-knowledge with bounded-reusable preprocessing from binary LPN, and concretely efficient related-key oblivious pseudorandom functions.PCGs for simple 2-party correlations. We obtain PCGs for several other types of useful 2-party correlations, including (authenticated) one-time truth-tables and Beaver triples. While the latter PCGs are slower than our PCG for OT, they are still practically feasible. These PCGs are based on a host of assumptions and techniques, including specialized homomorphic secret sharing schemes and pseudorandom generators tailored to their structure.Multiparty correlations. We obtain PCGs for multiparty correlations that can be used to make the (input-dependent) online communication of MPC protocols scale linearly with the number of parties, instead of quadratically.

2018

CRYPTO

TinyKeys: A New Approach to Efficient Multi-Party Computation
📺
Abstract

We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols does not depend on the number of honest parties, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for
$$n-1$$
n-1 corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties’ keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption.We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys, to improve the efficiency of standard GMW with fewer corruptions. We also obtain more efficient constant-round MPC, using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around
$$n=20$$
n=20 parties with
$$h=6$$
h=6 honest parties, and as these increase we obtain up to a 13 times reduction (for
$$n=400, h=120$$
n=400,h=120) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.

2018

CRYPTO

SPD$\mathbb {Z}_{2^k}$: Efficient MPC mod $2^k$ for Dishonest Majority
📺
Abstract

Most multi-party computation protocols allow secure computation of arithmetic circuits over a finite field, such as the integers modulo a prime. In the more natural setting of integer computations modulo $$2^{k}$$, which are useful for simplifying implementations and applications, no solutions with active security are known unless the majority of the participants are honest.We present a new scheme for information-theoretic MACs that are homomorphic modulo $$2^k$$, and are as efficient as the well-known standard solutions that are homomorphic over fields. We apply this to construct an MPC protocol for dishonest majority in the preprocessing model that has efficiency comparable to the well-known SPDZ protocol (Damgård et al., CRYPTO 2012), with operations modulo $$2^k$$ instead of over a field. We also construct a matching preprocessing protocol based on oblivious transfer, which is in the style of the MASCOT protocol (Keller et al., CCS 2016) and almost as efficient.

2018

PKC

Extending Oblivious Transfer with Low Communication via Key-Homomorphic PRFs
Abstract

We present a new approach to extending oblivious transfer with communication complexity that is logarithmic in the security parameter. Our method only makes black-box use of the underlying cryptographic primitives, and can achieve security against an active adversary with almost no overhead on top of passive security. This results in the first oblivious transfer protocol with sublinear communication and active security, which does not require any non-black-box use of cryptographic primitives.Our main technique is a novel twist on the classic OT extension of Ishai et al. (Crypto 2003), using an additively key-homomorphic PRF to reduce interaction. We first use this to construct a protocol for a large batch of 1-out-of-n OTs on random inputs, with amortized o(1) communication. Converting these to 1-out-of-2 OTs on chosen strings requires logarithmic communication. The key-homomorphic PRF used in the protocol can be instantiated under the learning with errors assumption with exponential modulus-to-noise ratio.

2018

PKC

Compact Zero-Knowledge Proofs of Small Hamming Weight
Abstract

We introduce a new technique that allows to give a zero-knowledge proof that a committed vector has Hamming weight bounded by a given constant. The proof has unconditional soundness and is very compact: It has size independent of the length of the committed string, and for large fields, it has size corresponding to a constant number of commitments. We show five applications of the technique that play on a common theme, namely that our proof allows us to get malicious security at small overhead compared to semi-honest security: (1) actively secure k-out-of-n OT from black-box use of 1-out-of-2 OT, (2) separable accountable ring signatures, (3) more efficient preprocessing for the TinyTable secure two-party computation protocol, (4) mixing with public verifiability, and (5) PIR with security against a malicious client.

2018

ASIACRYPT

Concretely Efficient Large-Scale MPC with Active Security (or, TinyKeys for TinyOT)
Abstract

In this work we develop a new theory for concretely efficient, large-scale MPC with active security. Current practical techniques are mostly in the strong setting of all-but-one corruptions, which leads to protocols that scale badly with the number of parties. To work around this issue, we consider a large-scale scenario where a small minority out of many parties is honest and design scalable, more efficient MPC protocols for this setting. Our results are achieved by introducing new techniques for information-theoretic MACs with short keys and extending the work of Hazay et al. (CRYPTO 2018), which developed new passively secure MPC protocols in the same context. We further demonstrate the usefulness of this theory in practice by analyzing the concrete communication overhead of our protocols, which improve upon the most efficient previous works.

#### Program Committees

- Crypto 2019

#### Coauthors

- Damiano Abram (1)
- Carsten Baum (4)
- Elette Boyle (4)
- Sai Sheshank Burra (1)
- Geoffroy Couteau (3)
- Ronald Cramer (1)
- Ivan Damgård (2)
- Cyprien Delpech de Saint Guilhem (1)
- Daniel Escudero (2)
- Tore Kasper Frederiksen (1)
- Satrajit Ghosh (1)
- Niv Gilboa (3)
- Carmit Hazay (4)
- Yuval Ishai (3)
- Daniel Kales (1)
- Marcel Keller (4)
- Lisa Kohl (4)
- Enrique Larraia (1)
- Ji Luo (1)
- Alex J. Malozemoff (1)
- Jesper Buus Nielsen (1)
- Peter Sebastian Nordholt (1)
- Sabine Oechsner (1)
- Claudio Orlandi (3)
- Emmanuela Orsini (8)
- Rahul Rachuri (1)
- Divya Ravi (1)
- Marc B. Rosen (1)
- Mark Simkin (1)
- Nigel P. Smart (1)
- Eduardo Soria-Vazquez (5)
- Chaoping Xing (1)
- Sophia Yakoubov (1)
- Greg Zaverucha (1)