## CryptoDB

### Gregor Seiler

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

Practical Sublinear Proofs for R1CS from Lattices
📺
Abstract

We propose a practical sublinear-size zero-knowledge proof system for Rank-1 Constraint Satisfaction (R1CS) based on lattices. The proof size scales asymptotically with the square root of the witness size. Concretely, the size becomes 2-3 times smaller than Ligero (ACM CCS 2017), which also exhibits square root scaling, for large instances of R1CS. At the core lies an interactive variant of the Schwartz-Zippel Lemma that might be of independent interest.

2022

TCHES

Verified NTT Multiplications for NISTPQC KEM Lattice Finalists: Kyber, Saber, and NTRU
Abstract

Postquantum cryptography requires a different set of arithmetic routines
from traditional public-key cryptography such as elliptic curves. In particular, in
each of the lattice-based NISTPQC Key Establishment finalists, every state-of-the-art
optimized implementation for lattice-based schemes still in the NISTPQC round 3
currently uses a different complex multiplication based on the Number Theoretic
Transform. We verify the NTT-based multiplications used in NTRU, Kyber, and Saber
for both the AVX2 implementation for Intel CPUs and for the pqm4 implementation
for the ARM Cortex M4 using the tool CryptoLine. We are able to verify that in
six instances multiplications are correct including range properties.
We demonstrate the feasibility for a programmer to verify his or her high-speed
assembly code for PQC, as well as to verify someone else’s high-speed PQC software
in assembly code, with some cooperation from the programmer.

2022

TCHES

Verified NTT Multiplications for NISTPQC KEM Lattice Finalists: Kyber, SABER, and NTRU
Abstract

Postquantum cryptography requires a different set of arithmetic routines from traditional public-key cryptography such as elliptic curves. In particular, in each of the lattice-based NISTPQC Key Establishment finalists, every state-ofthe-art optimized implementation for lattice-based schemes still in the NISTPQC round 3 currently uses a different complex multiplication based on the Number Theoretic Transform. We verify the NTT-based multiplications used in NTRU, Kyber, and SABER for both the AVX2 implementation for Intel CPUs and for the pqm4 implementation for the ARM Cortex M4 using the tool CryptoLine. e extended CryptoLine and as a result are able to verify that in six instances multiplications are correct including range properties.We demonstrate the feasibility for a programmer to verify his or her high-speed assembly code for PQC, as well as to verify someone else’s high-speed PQC software in assembly code, with some cooperation from the programmer.

2021

ASIACRYPT

Shorter Lattice-Based Group Signatures via ``Almost Free'' Encryption and Other Optimizations
📺
Abstract

We present an improved lattice-based group signature scheme whose parameter sizes and running times are independent of the group size. The signature length in our scheme is around $200$KB, which is approximately a $3$X reduction over the previously most compact such scheme, based on any quantum-safe assumption, of del Pino et al. (CCS 2018). The improvement comes via several optimizations of some basic cryptographic components that make up group signature schemes, and we think that they will find other applications in privacy-based lattice cryptography.

2021

TCHES

NTT Multiplication for NTT-unfriendly Rings: New Speed Records for Saber and NTRU on Cortex-M4 and AVX2
📺
Abstract

In this paper, we show how multiplication for polynomial rings used in the NIST PQC finalists Saber and NTRU can be efficiently implemented using the Number-theoretic transform (NTT). We obtain superior performance compared to the previous state of the art implementations using Toom–Cook multiplication on both NIST’s primary software optimization targets AVX2 and Cortex-M4. Interestingly, these two platforms require different approaches: On the Cortex-M4, we use 32-bit NTT-based polynomial multiplication, while on Intel we use two 16-bit NTT-based polynomial multiplications and combine the products using the Chinese Remainder Theorem (CRT).For Saber, the performance gain is particularly pronounced. On Cortex-M4, the Saber NTT-based matrix-vector multiplication is 61% faster than the Toom–Cook multiplication resulting in 22% fewer cycles for Saber encapsulation. For NTRU, the speed-up is less impressive, but still NTT-based multiplication performs better than Toom–Cook for all parameter sets on Cortex-M4. The NTT-based polynomial multiplication for NTRU-HRSS is 10% faster than Toom–Cook which results in a 6% cost reduction for encapsulation. On AVX2, we obtain speed-ups for three out of four NTRU parameter sets.As a further illustration, we also include code for AVX2 and Cortex-M4 for the Chinese Association for Cryptologic Research competition award winner LAC (also a NIST round 2 candidate) which outperforms existing code.

2021

PKC

Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments
📺
Abstract

There has been a lot of recent progress in constructing efficient zero-knowledge proofs for showing knowledge of an $\vec{\bm{s}}$ with small coefficients satisfying $\bm{A}\vec{\bm{s}}=\vec{\bm{t}}$. For typical parameters, the proof sizes have gone down from several megabytes to a bit under $50$KB (Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of the sizes of lattice-based signatures, which themselves constitute proof systems which demonstrate knowledge of something weaker than the aforementioned equation. One can therefore see that this line of research is approaching optimality. In this paper, we modify a key component of these proofs, as well as apply several other tweaks, to achieve a further reduction of around $30\%$ in the proof output size. We also show that this savings propagates itself when these proofs are used in a general framework to construct more complex protocols.

2021

CRYPTO

SMILE: Set Membership from Ideal Lattices with Applications to Ring Signatures and Confidential Transactions
📺
Abstract

In a set membership proof, the public information consists of a set of elements and a commitment. The prover then produces a zero-knowledge proof showing that the commitment is indeed to some element from the set. This primitive is closely related to concepts like ring signatures and ``one-out-of-many'' proofs that underlie many anonymity and privacy protocols. The main result of this work is a new succinct lattice-based set membership proof whose size is logarithmic in the size of the set.
We also give transformations of our set membership proof to a ring signature scheme and to a confidential transaction payment system. The ring signature size is also logarithmic in the size of the public key set and has size $16$~KB for a set of $2^5$ elements, and $22$~KB for a set of size $2^{25}$. At an approximately $128$-bit security level, these outputs are between 1.5X and 7X smaller than the current state of the art succinct ring signatures of Beullens et al. (Asiacrypt 2020) and Esgin et al. (CCS 2019).
We then show that our ring signature, combined with a few other techniques and optimizations, can be turned into a fairly efficient Monero-like confidential transaction system based on the MatRiCT framework of Esgin et al. (CCS 2019). With our new techniques, we are able to reduce the transaction proof size by factors of about 4X - 10X over the aforementioned work. For example, a transaction with two inputs and two outputs, where each input is hidden among $2^{15}$ other accounts, requires approximately $30$KB in our protocol.

2020

ASIACRYPT

Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings
📺
Abstract

We propose a lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution $\vec{s} \in \{-1,0,1\}^n$ to a linear equation $A\vec{s}=\vec{u}$ over $\mathbb{Z}_q$, which improves upon the protocol by Bootle, Lyubashevsky and Seiler (CRYPTO 2019) by producing proofs that are shorter by a factor of $7.5$.
At the core lies a technique that utilizes the module-homomorphic BDLOP commitment scheme (SCN 2018) over the fully splitting cyclotomic ring $\mathbb{Z}_q[X]/(X^d + 1)$ to prove scalar products with the NTT vector of a secret polynomial.

2020

CRYPTO

A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge
📺
Abstract

Today's most compact zero-knowledge arguments are based on the hardness of the discrete logarithm problem and related classical assumptions. If one is interested in quantum-safe solutions, then all of the known techniques stem from the PCP-based framework of Kilian (STOC 92) which can be instantiated based on the hardness of any collision-resistant hash function. Both approaches produce asymptotically logarithmic sized arguments but, by exploiting extra algebraic structure, the discrete logarithm arguments are a few orders of magnitude more compact in practice than the generic constructions.\\
In this work, we present the first (poly)-logarithmic \emph{post-quantum} zero-knowledge arguments that deviate from the PCP approach. At the core of succinct zero-knowledge proofs are succinct commitment schemes (in which the commitment and the opening proof are sub-linear in the message size), and we propose two such constructions based on the hardness of the (Ring)-Short Integer Solution (Ring-SIS) problem, each having certain trade-offs. For commitments to $N$ secret values, the communication complexity of our first scheme is $\tilde{O}(N^{1/c})$ for any positive integer $c$, and $O(\log^2 N)$ for the second. %Both of our protocols have somewhat large \emph{slack}, which in lattice constructions is the ratio of the norm of the extracted secrets to the norm of the secrets that the honest prover uses in the proof. The lower this factor, the smaller we can choose the practical parameters. For a fixed value of this factor, our $\tilde{O}(N^{1/c})$-argument actually achieves lower communication complexity.
Both of these are a significant theoretical improvement over the previously best lattice construction by Bootle et al. (CRYPTO 2018) which gave $O(\sqrt{N})$-sized proofs.

2020

CRYPTO

Practical Product Proofs for Lattice Commitments
📺
Abstract

We construct a practical lattice-based zero-knowledge argument for proving multiplicative relations between committed values. The underlying commitment scheme that we use is the currently most efficient one of Baum et al. (SCN 2018), and the size of our multiplicative proof is only slightly larger than of the one for just proving knowledge of the committed values. We additionally improve on the results of Lyubashevsky and Seiler (Eurocrypt 2018) to show that the above-mentioned techniques can work over rings $Z_q[X]/(X^d+1)$ where $X^d+1$ splits into low-degree factors, which is a property necessary for many applications. In particular, we use Fourier analysis to show that the NTT coefficients of random small-norm challenges are not concentrated on any particular value.

2019

PKC

Short Discrete Log Proofs for FHE and Ring-LWE Ciphertexts
Abstract

In applications of fully-homomorphic encryption (FHE) that involve computation on encryptions produced by several users, it is important that each user proves that her input is indeed well-formed. This may simply mean that the inputs are valid FHE ciphertexts or, more generally, that the plaintexts m additionally satisfy
$$f(m)=1$$
for some public function f. The most efficient FHE schemes are based on the hardness of the Ring-LWE problem and so a natural solution would be to use lattice-based zero-knowledge proofs for proving properties about the ciphertext. Such methods, however, require larger-than-necessary parameters and result in rather long proofs, especially when proving general relationships.In this paper, we show that one can get much shorter proofs (roughly 1.25 KB) by first creating a Pedersen commitment from the vector corresponding to the randomness and plaintext of the FHE ciphertext. To prove validity of the ciphertext, one can then prove that this commitment is indeed to the message and randomness and these values are in the correct range. Our protocol utilizes a connection between polynomial operations in the lattice scheme and inner product proofs for Pedersen commitments of Bünz et al. (S&P 2018). Furthermore, our proof of equality between the ciphertext and the commitment is very amenable to amortization – proving the equivalence of k ciphertext/commitment pairs only requires an additive factor of
$$O(\log {k})$$
extra space than for one such proof. For proving additional properties of the plaintext(s), one can then directly use the logarithmic-space proofs of Bootle et al. (Eurocrypt 2016) and Bünz et al. (IEEE S&P 2018) for proving arbitrary relations of discrete log commitment.Our technique is not restricted to FHE ciphertexts and can be applied to proving many other relations that arise in lattice-based cryptography. For example, we can create very efficient verifiable encryption/decryption schemes with short proofs in which confidentiality is based on the hardness of Ring-LWE while the soundness is based on the discrete logarithm problem. While such proofs are not fully post-quantum, they are adequate in scenarios where secrecy needs to be future-proofed, but one only needs to be convinced of the validity of the proof in the pre-quantum era. We furthermore show that our zero-knowledge protocol can be easily modified to have the property that breaking soundness implies solving discrete log in a short amount of time. Since building quantum computers capable of solving discrete logarithm in seconds requires overcoming many more fundamental challenges, such proofs may even remain valid in the post-quantum era.

2019

TCHES

NTTRU: Truly Fast NTRU Using NTT
📺
Abstract

We present NTTRU – an IND-CCA2 secure NTRU-based key encapsulation scheme that uses the number theoretic transform (NTT) over the cyclotomic ring Z7681[X]/(X768−X384+1) and produces public keys and ciphertexts of approximately 1.25 KB at the 128-bit security level. The number of cycles on a Skylake CPU of our constant-time AVX2 implementation of the scheme for key generation, encapsulation and decapsulation is approximately 6.4K, 6.1K, and 7.9K, which is more than 30X, 5X, and 8X faster than these respective procedures in the NTRU schemes that were submitted to the NIST post-quantum standardization process. These running times are also, by a large margin, smaller than those for all the other schemes in the NIST process as well as the KEMs based on elliptic curve Diffie-Hellman. We additionally give a simple transformation that allows one to provably deal with small decryption errors in OW-CPA encryption schemes (such as NTRU) when using them to construct an IND-CCA2 key encapsulation.

2019

CRYPTO

Algebraic Techniques for Short(er) Exact Lattice-Based Zero-Knowledge Proofs
📺
Abstract

A key component of many lattice-based protocols is a zero-knowledge proof of knowledge of a vector
$$\vec {s}$$
with small coefficients satisfying
$$A\vec {s}=\vec {u}\bmod \,q$$
. While there exist fairly efficient proofs for a relaxed version of this equation which prove the knowledge of
$$\vec {s}'$$
and c satisfying
$$A\vec {s}'=\vec {u}c$$
where
$$\Vert \vec {s}'\Vert \gg \Vert \vec {s}\Vert $$
and c is some small element in the ring over which the proof is performed, the proofs for the exact version of the equation are considerably less practical. The best such proof technique is an adaptation of Stern’s protocol (Crypto ’93), for proving knowledge of nearby codewords, to larger moduli. The scheme is a
$$\varSigma $$
-protocol, each of whose iterations has soundness error
$$2{/}3$$
, and thus requires over 200 repetitions to obtain soundness error of
$$2^{-128}$$
, which is the main culprit behind the large size of the proofs produced.
In this paper, we propose the first lattice-based proof system that significantly outperforms Stern-type proofs for proving knowledge of a short
$$\vec {s}$$
satisfying
$$A\vec {s}=\vec {u}\bmod \,q$$
. Unlike Stern’s proof, which is combinatorial in nature, our proof is more algebraic and uses various relaxed zero-knowledge proofs as sub-routines. The main savings in our proof system comes from the fact that each round has soundness error of
$$1{/}n$$
, where n is the number of columns of A. For typical applications, n is a few thousand, and therefore our proof needs to be repeated around 10 times to achieve a soundness error of
$$2^{-128}$$
. For concrete parameters, it produces proofs that are around an order of magnitude smaller than those produced using Stern’s approach.

2018

EUROCRYPT

2018

TCHES

CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
Abstract

In this paper, we present the lattice-based signature scheme Dilithium, which is a component of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite that was submitted to NIST’s call for post-quantum cryptographic standards. The design of the scheme avoids all uses of discrete Gaussian sampling and is easily implementable in constant-time. For the same security levels, our scheme has a public key that is 2.5X smaller than the previously most efficient lattice-based schemes that did not use Gaussians, while having essentially the same signature size. In addition to the new design, we significantly improve the running time of the main component of many lattice-based constructions – the number theoretic transform. Our AVX2-based implementation results in a speed-up of roughly a factor of 2 over the previously best algorithms that appear in the literature. The techniques for obtaining this speed-up also have applications to other lattice-based schemes.

#### Coauthors

- Thomas Attema (1)
- Jonathan Bootle (2)
- Chi-Ming Marvin Chung (1)
- Rafael del Pino (1)
- Léo Ducas (1)
- Muhammed F. Esgin (1)
- Vincent Hwang (3)
- Matthias J. Kannwischer (1)
- Eike Kiltz (1)
- Tancrède Lepoint (1)
- Jiaxiang Liu (2)
- Vadim Lyubashevsky (10)
- Ngoc Khanh Nguyen (6)
- Maxime Plançon (1)
- Peter Schwabe (1)
- Xiaomu Shi (2)
- Cheng-Jhih Shih (1)
- Damien Stehlé (1)
- Ming-Hsien Tsai (2)
- Bin Wang (1)
- Bow-Yaw Wang (1)
- Bo-Yin Yang (3)