## CryptoDB

### Carsten Baum

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

Moz$\mathbb{Z}_{2^k}$zarella: Efficient Vector-OLE and Zero-Knowledge Proofs Over $\mathbb{Z}_{2^k}$
📺
Abstract

Zero-knowledge proof systems are usually designed to support computations for circuits over $\mathbb{F}_2$ or $\mathbb{F}_p$ for large $p$, but not for computations over $\mathbb{Z}_{2^k}$, which all modern CPUs operate on. Although $\mathbb{Z}_{2^k}$-arithmetic can be emulated using prime moduli, this comes with an unavoidable overhead. Recently, Baum et al. (CCS 2021) suggested a candidate construction for a designated-verifier zero-knowledge proof system that natively runs over $\mathbb{Z}_{2^k}$. Unfortunately, their construction requires preprocessed random vector oblivious linear evaluation (VOLE) to be instantiated over $\mathbb{Z}_{2^k}$. Currently, it is not known how to efficiently generate such random VOLE in large quantities.
In this work, we present a maliciously secure, VOLE extension protocol that can turn a short seed-VOLE over $\mathbb{Z}_{2^k}$ into a much longer, pseudorandom VOLE over the same ring. Our construction borrows ideas from recent protocols over finite fields, which we non-trivially adapt to work over $\mathbb{Z}_{2^k}$. Moreover, we show that the approach taken by the QuickSilver zero-knowledge proof system (Yang et al. CCS 2021) can be generalized to support computations over $\mathbb{Z}_{2^k}$. This new VOLE-based proof system, which we call QuarkSilver, yields better efficiency than the previous zero-knowledge protocols suggested by Baum et al. Furthermore, we implement both our VOLE extension and our zero-knowledge proof system, and show that they can generate 13-50 million VOLEs per second for 64 to 256 bit rings, and evaluate 1.3 million 64 bit multiplications per second in zero-knowledge.

2021

EUROCRYPT

TARDIS: A Foundation of Time-Lock Puzzles in UC
📺
Abstract

Time-based primitives like time-lock puzzles (TLP) are finding widespread use in practical protocols, partially due to the surge of interest in the blockchain space where TLPs and related primitives are perceived to solve many problems. Unfortunately, the security claims are often shaky or plainly wrong since these primitives are used under composition. One reason is that TLPs are inherently not UC secure and time is tricky to model and use in the UC model. On the other hand, just specifying standalone notions of the intended task, left alone correctly using standalone notions like non-malleable TLPs only, might be hard or impossible for the given task. And even when possible a standalone secure primitive is harder to apply securely in practice afterwards as its behavior under composition is unclear. The ideal solution would be a model of TLPs in the UC framework to allow simple modular proofs. In this paper we provide a foundation for proving composable security of practical protocols using time-lock puzzles and related timed primitives in the UC model. We construct UC-secure TLPs based on random oracles and show that using random oracles is necessary. In order to prove security, we provide a simple and abstract way to reason about time in UC protocols. Finally, we demonstrate the usefulness of this foundation by constructing applications that are interesting in their own right, such as UC-secure two-party computation with output-independent abort.

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

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

PKC

Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography
📺
Abstract

In this work we present a new interactive Zero-Knowledge Argument of knowledge for general arithmetic circuits. Our protocol is based on the “MPC-in-the-head”-paradigm of Ishai et al. (STOC 2009) and follows the recent “MPC-in-the-head with Preprocessing” as proposed by Katz, Kolesnikov and Wang (ACM CCS 2018). However, in contrast to Katz et al. who used the “cut-and-choose” approach for pre-processing, we show how to incorporate the well-known “sacrificing” paradigm into “MPC-in-the-head”, which reduces the proof size when working over arithmetic circuits. Our argument system uses only lightweight symmetric-key primitives and utilizes a simplified version of the so-called SPDZ-protocol. Based on specific properties of our protocol we then show how it can be used to construct an efficient Zero-Knowledge Argument of Knowledge for instances of the Short Integer Solution (SIS) problem. We present different protocols that are tailored to specific uses of SIS, while utilizing the advantages of our scheme. In particular, we present a variant of our argument system that allows the parties to sample the circuit “on the fly”, which may be of independent interest. We furthermore implemented our Zero-Knowledge argument for SIS and show that using our protocols it is possible to run a complete interactive proof, even for general SIS instances which result in a circuit with $${>}10^6$$ gates, in less than 0.5 s .

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.

2018

CRYPTO

Sub-linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits
📺
Abstract

We propose the first zero-knowledge argument with sub-linear communication complexity for arithmetic circuit satisfiability over a prime
$${p}$$
whose security is based on the hardness of the short integer solution (SIS) problem. For a circuit with
$${N}$$
gates, the communication complexity of our protocol is
$$O\left( \sqrt{{N}{\lambda }\log ^3{{N}}}\right) $$
, where
$${\lambda }$$
is the security parameter. A key component of our construction is a surprisingly simple zero-knowledge proof for pre-images of linear relations whose amortized communication complexity depends only logarithmically on the number of relations being proved. This latter protocol is a substantial improvement, both theoretically and in practice, over the previous results in this line of research of Damgård et al. (CRYPTO 2012), Baum et al. (CRYPTO 2016), Cramer et al. (EUROCRYPT 2017) and del Pino and Lyubashevsky (CRYPTO 2017), and we believe it to be of independent interest.

#### Program Committees

- Crypto 2022
- PKC 2022

#### Coauthors

- Jonathan Bootle (1)
- Lennart Braun (1)
- Andrea Cerulli (1)
- Ivan Damgård (1)
- Bernardo David (1)
- Cyprien Delpech de Saint Guilhem (1)
- Rafael del Pino (1)
- Rafael Dowsley (1)
- Jens Groth (1)
- Daniel Kales (1)
- Kasper Green Larsen (1)
- Vadim Lyubashevsky (1)
- Alex J. Malozemoff (1)
- Alexander Munch-Hansen (1)
- Michael Nielsen (1)
- Jesper Buus Nielsen (1)
- Ariel Nof (1)
- Sabine Oechsner (1)
- Emmanuela Orsini (3)
- Marc B. Rosen (1)
- Peter Scholl (5)
- Eduardo Soria-Vazquez (1)
- Greg Zaverucha (1)