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 {\varvec{s}}$ with small coefficients satisfying $\varvec{A}\vec {\varvec{s}}=\vec {\varvec{t}}$. For typical parameters, the proof sizes have gone down from several megabytes to a bit under 50KB (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.

1 Introduction

Zero-knowledge proofs and commit-and-prove protocols form the foundations of virtually all privacy-based protocols. In preparing for the (eventual) coming of quantum computing, there has been a lot of focus in recent years on building such protocols based on quantum-safe assumptions. Quantum-safe PCP/IOP schemes whose security is just based on the collision-resistance of cryptographic hash functions have existed for decades, and there has been a lot of recent work around them. The main feature of these constructions is that their outputs are sublinear in the statement size. The main downside is that they can be very slow and memory intensive. Furthermore, there is a lower bound of around 100KB for proofs of statements that have small size. So it’s quite likely that they are not the best solution for all scenarios.

In the last few years, new techniques emerged in lattice cryptography that made it a promising foundation for quantum-safe privacy-based protocols. These techniques have been used for blockchain applications [EZS+19], verifiable random functions [EKS+20], and for proofs of arithmetic statements [LNS20a]. In all of these scenarios, lattice schemes appear to be the best solutions available. For example, a commit-and-prove protocol for integer products is significantly smaller and several orders of magnitude faster than other quantum-safe solutions. These results show that lattices might eventually be very reasonable substitutes for the classical cryptography that is currently embedded in those protocols.

At the core of many of the recent privacy-based protocols is the BDLOP commitment scheme [BDL+18] which is able to commit to an arbitrary message vector $\vec {\varvec{m}}$ modulo q. In [BDL+18], it was also shown how one can prove knowledge of $\vec {\varvec{m}}$ by only proving knowledge of the commitment randomness $\vec {\varvec{r}}$. The proof technique was essentially using the “Fiat-Shamir with Aborts” [Lyu09] framework to keep the proofs small and avoid leaking any information about $\vec {\varvec{r}}$. If one uses the Gaussian rejection sampling procedure [Lyu12], then the magnitude of each coefficient of the $\vec {\varvec{r}}'$ output in the proof is around $12\cdot \kappa \Vert \vec {\varvec{r}}\Vert$; where the $\kappa$ is some constant that comes from the challenge and the 12 comes from a Gaussian tail bound needed for (statistical) zero-knowledge.

The increased coefficient size means that the proof is noticeably larger than the randomness itself (and gives rise to a vicious cycle of having to increase the modulus and dimension of the underlying lattice). It nevertheless seems necessary because leaking some information about the randomness can be dangerous. For example, if one were to repeatedly perform proofs of knowledge for the same commitment and leaking something about the same randomness each time, eventually the entire randomness could be recovered by even a passive observer.

1.1 One-Time Commitments

If one looks closer at how the BDLOP commitment is being used in many of the privacy-based protocols, one would notice that the scheme is used to commit to some intermediate value, give a proof-of-knowledge of the value (i.e. proof of knowledge of the commitment randomness), and then discards the commitment. So only one proof of knowledge is performed. In this case, it’s not immediately clear whether some leakage of the randomness vector is problematic. Still, it seems somewhat risky to only perform a minimal perturbation on the randomness and hope that this is good enough for LWE to remain secure. Instead of relying completely on heuristic security, it would be good to have a technique which lowers the proof size, and at the same time concretely allows one to understand exactly how the LWE problem is affected by the leakage.

For efficiency purposes, the BDLOP commitment instantiation is only computationally hiding (i.e. based on LWE), so one cannot use prior techniques to prove that enough entropy remains in the randomness after the leakage. While there are techniques that show that LWE-based encryption schemes can tolerate some leakage, the results are asymptotic and it’s unclear what the actual practical implication of the leakage is [DGK+10, GKPV10, BD20]. There has also been some work examining the practical aspects of leakage in the Ring-LWE setting [DDGR20], and the security of the scheme is barely affected when the leakage is small.

We show that a particular rejection sampling strategy information-theoretically leaks just one bit of randomness, and allows us to exactly quantify what this leakage is. More specifically, in addition to the public LWE samples, there is also a short public vector $\vec {\varvec{z}}$, and we require that the whoe LWE secret (i.e. the secret concatenated with the error vector) has a non-negative inner product with it. Because the LWE secret is uniformly distributed around 0, the probability that the inner product will be non-negative is greater than 1/2, and so this extra restriction loses (less than) one bit of entropy.

We observe that the leakage essentially transforms the LWE problem instance into (a much less leaky version of) an extended-LWE one, which was shown to be equivalent to LWE in [AP12]. The decisional extended-LWE problem asks to distinguish between the distributions $(\varvec{B},\varvec{B}\vec {\varvec{r}},\vec {\varvec{z}},\langle \vec {\varvec{r}},\vec {\varvec{z}}\rangle )$ and $(\varvec{B},\vec {\varvec{u}},\vec {\varvec{z}},\langle \vec {\varvec{r}},\vec {\varvec{z}}\rangle )$, where $\vec {\varvec{r}}$ is sampled from the secret/noise domain of the LWE problem, $\vec {\varvec{u}}$ is uniformly random, and $\vec {\varvec{z}}$ is sampled from some efficiently sampleable distribution. One caveat is that for efficiency, we use a structured matrix $\varvec{B}$, and the proof in [AP12] does not carry over to our setting.¹

Furthermore, it’s clear that there is an equivalence between the search versions of extended Ring-LWE and Ring-LWE – and so a separation between the decisional versions would be quite interesting because all the best current lattice algorithms work by trying to solve the search problem. In short, we do not believe that this one bit of leakage has any practical consequences on the hardness of the Ring-LWE problem. It would actually be interesting if this assumption found even more applications, beside the original ones (e.g. [OPW11]) that inspired the Extended-LWE assumption, for improving the efficiency of lattice schemes.²

1.2 Technical Overview

The last prover move of a Schnorr-type $\varSigma$-protocol is a value $\vec {\varvec{z}} = \vec {\varvec{y}}+\vec {\varvec{v}}$, where $\vec {\varvec{y}}$ is a “masking” vector that the prover created during the first move and $\vec {\varvec{v}}$ is the combination of the secret and the challenge (usually their product, but this is unimportant for our purposes and we can consider the whole $\vec {\varvec{v}}$ to be secret). If we would like $\vec {\varvec{z}}$ to have small norm, then we cannot choose the coefficients of $\vec {\varvec{y}}$ to be so large that the sum $\vec {\varvec{y}}+\vec {\varvec{v}}$ statistically hides $\vec {\varvec{v}}$. Instead we use rejection sampling to force the distribution of $\vec {\varvec{z}}$ to be independent of $\vec {\varvec{v}}$. In particular, if we would like the distribution of the output to be f, while the distribution of $\vec {\varvec{z}}$ is g, then one should output $\vec {\varvec{z}}$ with probability $f(\vec {\varvec{z}})/(M\cdot g(\vec {\varvec{z}}))$, where M is some positive integer set so that this ratio is never larger than 1. Since 1/M is the probability that something will be output, we also want to have M as small as possible. Combining these two requirements, it’s easy to see that M should be set to $\max _{\vec {\varvec{z}}}(g(\vec {\varvec{z}})/f(\vec {\varvec{z}}))$.

If we follow [Lyu12] where the target distribution f is a discrete Gaussian with standard deviation $\mathfrak {s}$ and the distribution g is a shifted Gaussian (by $\vec {\varvec{v}}$) with the same standard deviation, then via [Lyu12, Lemma 4.5], the value for M is derived as

$$\exp \left( \frac{-2\langle \vec {\varvec{z}},\vec {\varvec{v}}\rangle + \Vert \vec {\varvec{v}}\Vert ^2}{2\mathfrak {s}^2}\right) \le \exp \left( \frac{24\mathfrak {s}\Vert \vec {\varvec{v}}\Vert + \Vert \vec {\varvec{v}}\Vert ^2}{2\mathfrak {s}^2}\right) = M.$$

To obtain the inequality, one uses a standard 1-dimensional tail bound for the inner product of a discrete Gaussian with arbitrary vector (c.f. [Lyu12, Lemma 4.3]). And in fact, it is this tail bound that contributes the most to M. For example, if we would like to have $M=\exp (1)$, then we would need to set $\mathfrak {s}\approx 12\Vert \vec {\varvec{v}}\Vert$. On the other hand, if we knew that $\langle \vec {\varvec{z}},\vec {\varvec{v}}\rangle \ge 0$, then we could set $\mathfrak {s}\approx \Vert \vec {\varvec{v}}\Vert /\sqrt{2}$, a decrease of around a factor of 17. So the intuition is for the prover to throw away the potential outputs $\vec {\varvec{z}}$ that have the aforementioned inner product be negative-valued. The effect of this is that it leaks information about $\vec {\varvec{z}}$ – in particular, the fact that its inner product with the secret is positive.

Interestingly, the new value of $\mathfrak {s}$ is identical to what one would get by using bimodal rejection sampling, as in the BLISS signature scheme [DDLL13]. We cannot directly apply the technique from that paper because it required that the public value $\varvec{B}_0$ be set up such that $\varvec{B}_0\vec {\varvec{r}} = q\pmod {2q}$. Intuitively, with this setup, leaking the sign of the secret $\vec {\varvec{r}}$ doesn’t matter because both $\vec {\varvec{r}}$ and $-\vec {\varvec{r}}$ satisfy the equality. Since we do not have this setup, the bimodal technique from BLISS would leak some information. At this point, we do not see a way to quantify the leakage stemming from the bimodal distribution, unlike the fairly simple leakage that we proposed instead. We should also mention that a recent work [TWZ20] showed how to apply the bimodal technique to the BDLOP commitment scheme without any leakage. Their transformation is not for free, though – it increases the length of the output, and also has a technical subtlety that makes it difficult to apply to our current result. The issue is that a part of our security proof requires that the challenge space has a particular distribution over $\{-1,0,1\}$ (it’s necessary for Lemma 2.1, which is crucial for the product proof over fully-splitting rings). In the proof in [TWZ20], on the other hand, the challenges are masked by the prover and so their distribution is possibly determined in an adversarial fashion.

1.3 Applications and Paper Overview

A good benchmark for the progress of the development of lattice-based proof techniques is the simple proof of knowledge of a trinary secret vector $\vec {\varvec{s}}$ satisfying $\varvec{B}\vec {\varvec{s}}=\vec {\varvec{t}}$. Up until a few years ago, for a particular real-world parametrization of the problem ($\varvec{B}$ being a $1024 \times 2048$ dimensional matrix over $\mathbb {Z}_q$ for $q\approx 2^{32}$), the smallest proof used “Stern proofs” [Ste93] ported to lattices [LNSW13], and had proof sizes of several megabytes. Switching the proof strategy to showing that a coefficient $s_i$ is trinary by using a commit-and-prove strategy by proving the algebraic equation $(s_i-1)\cdot s_i\cdot (s_i+1)=0$ lowered the proof sizes to around 300KB [YAZ+19, BLS19]. Then even more recently, by utilizing more efficient product proofs [EZS+19, ALS20], it was shown in [ENS20] how to obtain proofs of size under 50KB.

In Sect. 3, we apply our new technique to the aforementioned benchmark, as well as to the recent framework in [LNS20a] for proving integer relations. [LNS20b, Appendix B] shows how this framework can be further optimised using commitment compression from [DKL+18]. In total, we obtain a size reduction of around $30\%$ for these proofs (see Fig. 1). As a side note, the proofs in [ENS20, LNS20a] used the uniform distribution instead of discrete Gaussians. The reason was that Gaussians did not provide much of a size reduction (a few kilobytes) and are a bit more cumbersome to work with. But in light of our modified rejection sampling, which only appears to apply to the Gaussian technique, we believe that it is now worthwhile to switch in order to take advantage of the additional size reduction.

Fig. 1.

Proof size comparisons for secure commit-and prove protocols for proving knowledge of a (Module)-LWE sample of total dimension (secret and error vector) 2048, and 128-bit integer addition and multiplication. In the last column we list the proof sizes when only masking the secret vector $\varvec{c}\vec {\varvec{r}}$ with a uniformly random masking vector that has the same infinity norm bound than the secret vector and not performing any rejection sampling. This is possibly still secure, but lacks a security proof at this point.

To see how far our new rejection sampling procedure is from the (almost) best possible, we also compute the proof size for the case in which we don’t do any rejection sampling when giving a proof of knowledge of the commitment randomness. In particular, we heuristically mask the secret by adding a random masking vector whose coefficients are as big as those of the vector. This undoubtedly leaks something about the randomness, but it may still be reasonable to hope that the message in the commitment remains hidden because there is still enough entropy in the LWE secret (i.e. the randomness of the commitment).³ This strategy leads to proof sizes that are around $20\%$ smaller. We do not see how one can get any sort of security reduction for this approach, but we don’t see an attack either. It is therefore an interesting open problem whether this approach can lead to something with a security proof. This would lead to essentially optimal parameters for this approach of creating zero-knowledge proofs.

Since our basic proofs are fairly close to optimal (as far as this line of research goes), we find it worthwhile to give further applications of them. Combined with a few extra tricks we develop along the way, we believe this leads to the shortest current constructions for certain primitives. Section 4 describes how one constructs a verifiable decryption scheme for Kyber [BDK+18], which is a finalist of the NIST PQC competition. This approach can be easily extended to other lattice-based KEM finalists, such as Saber [DKRV18] or NTRU [HPS98]. Complementing the previous section, which requires range proofs in the infinity norm, in [LNS20b, Appendix E] we further consider range proofs with respect to the Euclidean norm. Concretely, we show how to prove that a vector $\vec {v}$ has $\Vert \vec {v}\Vert < a$ for some integer a. In [LNS20b, Appendix F], we describe an alternative approach for creating an important ingredient in some proofs – namely, approximate range proofs [BL17, BN20, LNS20a] – by using bimodal Gaussians [DDLL13] which further increases the efficiency of the aforementioned protocol. We also remark that the latter two sections make use of the improved framework from [LNS20a] defined in Sect. 3.

2 Preliminaries

2.1 Notation

Denote $\mathbb {Z}_p$ to be the ring of integers modulo p. Let q be an odd prime. We write $\vec {v} \in R^m$ to denote vectors over a ring R and matrices over R will be written as regular capital letters M. Define $I_n$ to be the $n\times n$ identity matrix over $\mathbb {Z}_q$. For an integer a, we define a vector $\vec {a} = (a,\ldots ,a)$ unless stated otherwise. By default, all vectors are column vectors. We write $\vec {v}||\vec {w}$ for a usual concatenation of $\vec {v}$ and $\vec {w}$ (which is still a column vector). For $\vec {v},\vec {w} \in \mathbb {Z}_q^k$, $\vec {v} \circ \vec {w}$ is the usual component-wise multiplication. For simplicity, we denote $\vec {u}^2 = \vec {u} \circ \vec {u}$. We write $x \leftarrow S$ when $x \in S$ is sampled uniformly at random from the finite set S and similarly $x \leftarrow D$ when x is sampled according to the distribution D. We write [n] to denote the set $\{1,\ldots ,n\}$. Given two functions $f,g: \mathbb {N} \rightarrow [0,1]$, we write $f(\mu ) \approx g(\mu )$ if $|f(\mu )-g(\mu )| < \mu ^{-\omega (1)}$. A function f is negligible if $f \approx 0$. We write $\mathsf {negl}(n)$ to denote an unspecified negligible function in n.

For a power of two d, denote $\mathcal {R}$ and $\mathcal {R}_q$ respectively to be the rings $\mathbb {Z}[X]/(X^{d}+1)$ and $\mathbb {Z}_q[X]/(X^{d}+1)$. Bold lower-case letters denote elements in $\mathcal {R}$ or $\mathcal {R}_q$ and bold lower-case letters with arrows represent column vectors with coefficients in $\mathcal {R}$ or $\mathcal {R}_q$. We also write bold upper-case letters for matrices in $\mathcal {R}$ or $\mathcal {R}_q$. By default, for a polynomial denoted as a bold letter, we write its i-th coefficient as its corresponding regular font letter subscript i, e.g. $f_0 \in \mathbb {Z}_q$ is a constant coefficient of $\varvec{f} \in \mathcal {R}_q$.

Modular Reductions. We define $r'=r\text { mod}^\pm \,q$ to be the unique element $r'$ in the range $-\frac{q-1}{2}\le r'\le \frac{q-1}{2}$ such that $r'\equiv r \pmod q$. We also denote $r'=r\text { mod}^+ q$ to be the unique element $r'$ in the range $0\le r'<q$ such that $r'\equiv r\pmod q$. When the exact representation is not important, we simply write $r\bmod q$.

Sizes of Elements. For an element $w\in \mathbb {Z}_q$, we write $\Vert w\Vert _\infty$ to mean $|w\text { mod}^\pm \, q|$. Define the $\ell _\infty$ and $\ell _p$ norms for $\varvec{w}=w_0+w_1X+\ldots +w_{d-1}X^{d-1}\in \mathcal {R}$ as follows:

$$\Vert \varvec{w}\Vert _\infty =\max _{j}{\Vert w_j\Vert _\infty },\,\,\,\, \Vert \varvec{w}\Vert _p=\root p \of {\Vert w_0\Vert _\infty ^p+\ldots +\Vert w_{d-1}\Vert _\infty ^p}.$$

If $\vec {\varvec{w}}=(\varvec{w}_1,\ldots ,\varvec{w}_m)\in \mathcal {R}^m$, then

$$\Vert \vec {\varvec{w}}\Vert _\infty =\max _{j}{\Vert \varvec{w}_j\Vert _\infty },\,\,\,\, \Vert \vec {\varvec{w}}\Vert _p=\root p \of {\Vert \varvec{w}_1\Vert ^p+\ldots +\Vert \varvec{w}_k\Vert ^p}.$$

By default, we denote $\Vert \vec {\varvec{w}}\Vert := \Vert \vec {\varvec{w}}\Vert _2$.

2.2 Cyclotomic Rings

Suppose (q) splits into l prime ideals of degree d/l in $\mathcal {R}$. This means $X^d + 1 \equiv \varvec{\varphi }_1 \dots \varvec{\varphi }_l \pmod {q}$ with irreducible polynomials $\varvec{\varphi }_j$ of degree d/l modulo q. We assume that $\mathbb {Z}_q$ contains a primitive 2l-th root of unity $\zeta \in \mathbb {Z}_q$ but no elements whose order is a higher power of two, i.e. $q - 1 \equiv 2l \pmod {4l}$. Therefore, we have

$$\begin{aligned} X^d + 1 \equiv \prod _{j \in \mathbb {Z}_{2l}^\times } \left( X^{\frac{d}{l}} - \zeta ^j\right) \pmod {q} \end{aligned}$$

(1)

where $\zeta ^j\ (j \in \mathbb {Z}_{2l}^\times )$ ranges over all the l primitive 2l-th roots of unity.

Let $\mathcal {M}_q := \{\varvec{p} \in \mathbb {Z}_q[X] : \deg (\varvec{p}) < d/l\}$. We define the Number Theoretic Transform (NTT) of a polynomial $\varvec{p} \in \mathcal {R}_q$ as follows:

$$\mathsf {NTT}\left( {\varvec{p}}\right) := \begin{bmatrix} \hat{\varvec{p}}_0 \\ \vdots \\ \hat{\varvec{p}}_{l-1} \end{bmatrix} \in \mathcal {M}_q^l \text { where } \hat{\varvec{p}}_j = \varvec{p} \bmod (X^{\frac{d}{l}} - \zeta ^{2j+1}).$$

We also define the inverse NTT operation. Namely, for a vector $\vec {v} \in \mathcal {M}_q^l$, $\mathsf {NTT}^{-1}\left( {\vec {v}}\right)$ is the polynomial $\varvec{p} \in \mathcal {R}_q$ such that $\mathsf {NTT}\left( {\varvec{p}}\right) = \vec {v}$.

2.3 Automorphisms

The ring $\mathcal {R}_q$ has a group of automorphisms ${\text {Aut}}(\mathcal {R}_q)$ that is isomorphic to $\mathbb {Z}_{2d}^\times \cong \mathbb {Z}_2 \times \mathbb {Z}_{d/2}$,

$$\begin{aligned} i \mapsto \sigma _i :\mathbb {Z}_{2d}^\times \rightarrow {\text {Aut}}(\mathcal {R}_q), \end{aligned}$$

where $\sigma _i$ is defined by $\sigma _i(X) = X^i$. Note that for $i \in \mathbb {Z}^\times _{2d}$ and odd j it holds that $(\sigma _i(X - \zeta ^j)) = (X - \zeta ^{ji^{-1}})$ in $\mathcal {R}_q$ (as ideals), and for $\varvec{f} \in \mathcal {R}_q$,

$$\begin{aligned} \sigma _i\left( \varvec{f} \bmod (X - \zeta ^j)\right) = \sigma _i\left( \varvec{f}\right) \bmod \left( X - \zeta ^{ji^{-1}}\right) . \end{aligned}$$

Let k be a divisor of l and $\sigma := \sigma _{2l/k +1}\in \mathsf {Aut}(\mathcal {R}_q)$. Then, we can write

$$\begin{aligned} \left( X^d + 1\right) = \prod _{j \in \mathbb {Z}_{2l/k}^\times } \prod _{i = 0}^{k-1} \sigma ^i\left( X^{\frac{d}{l}} - \zeta ^j\right) . \end{aligned}$$

2.4 Challenge Space

Let $\mathcal {C}:= \{-1,0,1\}^d \subset \mathcal {R}_q$ be the challenge set of ternary polynomials with coefficients $-1,0,1$. We define the following probability distribution $C: \mathcal {C}\rightarrow [0,1]$. The coefficients of a challenge $\varvec{c} \leftarrow C$ are independently identically distributed with $P(0)=1/2$ and $\Pr (1)=\Pr (-1) = 1/4$.

Consider the coefficients of the polynomial $\varvec{c} \bmod (X^{d/l} - \zeta ^j)$ for $\varvec{c}\leftarrow C$. Then, all coefficients follow the same distribution over $\mathbb {Z}_q$. Let us write Y for the random variable over $\mathbb {Z}_q$ that follows this distribution. Attema et al. [ALS20] give an upper bound on the maximum probability of Y.

Lemma 2.1

Let the random variable Y over $\mathbb {Z}_q$ be defined as above. Then for all $x\in \mathbb {Z}_q$,

$$\begin{aligned} \Pr ( Y=x ) \le \frac{1}{q} + \frac{2l}{q}\sum _{j\in \mathbb {Z}_q^{\times }/\langle \zeta \rangle } \prod _{i=0}^{l-1} \left|\frac{1}{2}+ \frac{1}{2}\cos (2\pi j y \zeta ^i/q)\right|. \end{aligned}$$

(2)

In particular, [ALS20, ENS20] computed that for $q \approx 2^{32}$, the maximum probability for each coefficient of $c \bmod X^{d/l}-\zeta ^j$ is around $2^{-31.4}$. In general, we will call this probability $\mathsf {p}$.

An immediate consequence of Lemma 2.1 is that polynomial $\varvec{c} \leftarrow C$ is invertible in $\mathcal {R}_q$ with overwhelming probability as long as parameters q, d, l are selected so that $q^{-d/l}$ is negligible.

Let k be a divisor of d such that $q^{-kd/l}$ is negligible and set $\sigma = \sigma _{2l/k+1}$. Let us define a probability distribution $\tilde{C}$ over $\mathcal {R}^k$ which first samples $\varvec{c}= \varvec{c}_0 + \varvec{c}_1 X + \ldots + \varvec{c}_{k-1}X^{k-1} \leftarrow C$ and outputs $(\varvec{c}_0,\ldots ,\varvec{c}_{k-1})$ where each $\varvec{c}_i$ is defined as $\varvec{c}_i = \sum _{j=0}^{d/k-1} c_{jk + i} X^{jk}.$ Clearly, we have

$$\varvec{c} = \sum ^{k-1}_{i=0} \varvec{c}_i X^i.$$

2.5 Module-SIS and Module-LWE Problems

Security of the [BDL+18] commitment scheme used in our protocols relies on the well-known computational lattice problems, namely Module-LWE (M-LWE) and Module-SIS (M-SIS) [LS15]. Both problems are defined over $\mathcal {R}_q$.

Definition 2.2

(M-SIS$_{\kappa ,m,B}$). Given $\varvec{A}\leftarrow \mathcal {R}_q^{\kappa \times m}$, the Module-SIS problem with parameters $\kappa ,m>0$ and $0<B<q$ asks to find $\vec {\varvec{z}}\in \mathcal {R}_q^m$ such that $\varvec{A}\vec {\varvec{z}} = \vec {\varvec{0}}$ over $\mathcal {R}_q$ and $0< \Vert \vec {\varvec{z}}\Vert \le B$. An algorithm $\mathcal {A}$ is said to have advantage $\epsilon$ in solving M-SIS$_{\kappa ,m,B}$ if

Definition 2.3

(M-LWE$_{m,\lambda ,\chi }$). The Module-LWE problem with parameters $m,\lambda >0$ and an error distribution $\chi$ over $\mathcal {R}$ asks the adversary $\mathcal {A}$ to distinguish between the following two cases: 1) $(\varvec{A},\varvec{A}\vec {\varvec{s}}+\vec {\varvec{e}})$ for $\varvec{A}\leftarrow \mathcal {R}_q^{m\times \lambda }$, a secret vector $\vec {\varvec{s}}\leftarrow \chi ^\lambda$ and error vector $\vec {\varvec{e}}\leftarrow \chi ^m$, and 2) $(\varvec{A},\vec {\varvec{b}})\leftarrow \mathcal {R}_q^{m\times \lambda }\times \mathcal {R}_q^m$. Then, $\mathcal {A}$ is said to have advantage $\epsilon$ in solving M-LWE$_{m,\lambda ,\chi }$ if

(3)

For our constructions in this work, the practical hardness of either of the problems against known attacks is not affected by the parameter m. Therefore, we sometimes simply write M-SIS$_{\kappa ,B}$ or M-LWE$_{\lambda ,\chi }$. The parameters $\kappa$ and $\lambda$ denote the module ranks for M-SIS and M-LWE, respectively.

2.6 Probability Distributions

For sampling randomness in the commitment scheme that we use, and to define a variant of the Ring Learning with Errors problem, we need to define an error distribution $\chi ^d$ on $\mathcal {R}$. In this paper we sample the coefficients of the random polynomials in the commitment scheme using the distribution $\chi$ on $\{-1,0,1\}$ where $\pm 1$ both have probability 5/16 and 0 has probability 6/16. This distribution is chosen (rather than the more “natural” uniform one) because it is easy to sample given a random bitstring by computing $a_1 + a_2 - b_1 - b_2 \bmod 3$ with uniformly random bits $a_i, b_i$.

Discrete Gaussian Distribution. We now define the discrete Gaussian distribution used for the rejection sampling.

Definition 2.4

The discrete Gaussian distribution on $\mathcal {R}^\ell$ centered around $\vec {\varvec{v}} \in \mathcal {R}^\ell$ with standard deviation $\mathfrak {s}> 0$ is given by

$$\begin{aligned} D^{\ell d}_{\varvec{v}, \mathfrak {s}}(\vec {\varvec{z}}) = \frac{e^{-\Vert \vec {\varvec{z}} - \vec {\varvec{v}}\Vert ^2/2\mathfrak {s}^2}}{\sum _{\vec {\varvec{z}}' \in \mathcal {R}^\ell } e^{-\Vert \vec {\varvec{z}}'\Vert ^2/2\mathfrak {s}^2}}. \end{aligned}$$

When it is centered around $\vec {\varvec{0}} \in \mathcal {R}^\ell$ we write $D^{\ell d}_\mathfrak {s}= D^{\ell d}_{\vec {\varvec{0}}, \mathfrak {s}}$.

2.7 Approximate Range Proofs

Baum and Lyubashevsky [BL17] showed that if $B\vec {s}$ has small coefficients, for a vector $\vec {s}$ over $\mathbb {Z}_q$ and uniformly random binary matrix B, then with high probability $\vec {s}$ must have small coefficients as well. More recently, Lyubashevsky et al. [LNS20a] generalise their result for $B\vec {s} + \vec {e}$ where $\vec {e}$ is an arbitrary vector over $\mathbb {Z}_q$. We extend the lemma for the case when B is sampled from a distribution centered at 0. The main advantage of this approach is that the infinity norm of $B\vec {s}$ decreases significantly, which is essential for the rejection sampling.

Concretely, we define the probability distribution $\mathsf {C}:\{-1,0,1\}\rightarrow [0,1]$ such that $\Pr _{c \leftarrow \mathsf {C}}[c =0] = p$ and $\Pr _{c \leftarrow \mathsf {C}}[c = 1] = \Pr _{c \leftarrow \mathsf {C}}[c = -1] = (1-p)/2$ for some $p\in [0,1]$. Then, we have the following lemma.

Lemma 2.5

Let $\vec {s} \in \mathbb {Z}_q^m$ and $\vec {y} \in \mathbb {Z}_q^n$ . Then

$$\Pr \left[ \Vert B\vec {s} + \vec {y} \Vert _\infty < \frac{1}{2}\Vert \vec {s}\Vert _\infty : B \leftarrow \mathsf {C}^{n \times m} \right] \le \max \{p,1-p\}^{n}.$$

We provide the proof of Lemma 2.5 in [LNS20b, Appendix A].

2.8 Commit-and-Prove

Let $R_L$ be a polynomial-time verifiable relation containing (ck, x, w). We will call ck the commitment key, x the statement and w the witness. Also, we define a language $L_{ck}$ as the set of statements x for which there exists a witness w such that $(ck,x,w) \in R_L$.

We define the commit-and-prove functionality similarly as in [EG14, CLOS02] for a relation $R_L$. Roughly speaking, we want to commit to messages $m_1,\ldots ,m_n$ and prove certain statements about them. Therefore, $w = (m_1,\ldots ,m_n)$ constitutes a witness for $x\in L_{ck}$.

Formally, a commit-and-prove functionality (CP) consists of four algorithms $CP = (\mathsf {Gen},\mathsf {Com}, \mathsf {Prove},\mathsf {Verify})$. We require $\mathsf {Com},\mathsf {Verify}$ to be deterministic whereas $\mathsf {Gen}, \mathsf {Prove}$ are probabilistic.

• $\mathsf {Gen}(1^\mu )$: Given a security parameter $\mu$, generates a commitment key ck. The commitment key specifies a message space $\mathcal {M}_{ck}$ a randomness space $\mathcal {R}_{ck}$ and commitment space $\mathcal {C}_{ck}$.

• $\mathsf {Com}_{ck}(m;r)$: Given a commitment key ck, a message $m \in \mathcal {M}_{ck}$ and randomness $r \in \mathcal {R}_{ck}$ returns a commitment $c \in \mathcal {C}_{ck}$.

• $\mathsf {Prove}_{ck}\left( x,\left( (m_1,r_1),\ldots ,(m_n,r_n)\right) \right)$: Given a commitment key ck, statement x and commitment openings $m_i \in \mathcal {M}_{ck}, r_i\in \mathcal {R}_{ck}$ and (ck, x,  $\left( m_1,\ldots ,m_n\right) ) \in R_L$ returns a proof $\pi$.

• $\mathsf {Verify}_{ck}\left( x,c_1,\ldots ,c_n,\pi \right)$: Given a commitment key ck, a statement x, a proof $\pi$ and commitments $c_i \in \mathcal {C}_{ck}$, outputs 1 (accept) or 0 (reject).

Definition 2.6

(Correctness). The commit-and-prove functionality CP has statistical correctness with correctness error $\rho : \mathbb {N} \rightarrow [0,1]$ if for all adversaries $\mathcal {A}$:

(4)

where $\mathcal {A}$ outputs $m_i \in \mathcal {M}_{ck}, r_i \in \mathcal {R}_{ck}$ so that $\left( ck,x,(m_1,\ldots ,m_n)\right) \in R_L$.

Definition 2.7

(Knowledge Soundness). The commit-and-prove functionality CP is knowledge sound with knowledge error $\epsilon :\mathbb {N} \rightarrow [0,1]$ if for all PPT $\mathcal {A}$ there exists an expected polynomial time extractor $\mathcal {E}$ so that :

(5)

is less or equal to $\epsilon (\mu )$, where $\mathcal {E}$ outputs $m^*_i \in \mathcal {M}_{ck}$ and $r^*_i \in \mathcal {R}_{ck}$.

In lattice-based zero-knowledge proofs, it is sometimes useful to relax the definition of knowledge soundness by only requiring $r^*_1,\ldots ,r^*_n \in \bar{\mathcal {R}}_{ck}$ where $\mathcal {R}_{ck} \subseteq \bar{\mathcal {R}}_{ck}$. However, the definition still makes sense if one can argue that the extracted commitments are still binding. This is what we do by additionally defining notions of weak opening (Definition 2.9).

The next property is a new notion called simulatability. Informally, it means that there exists an efficient simulator $\mathcal {S}$ which can simulate both the commitment generation and the proof at the same time.

Definition 2.8

(Simulatability). The commit-and-prove functionality CP is simulatable if there exist PPT simulators $\mathsf {SimCom}$ and $\mathsf {SimProve}$ such that for all PPT adversaries $\mathcal {A}$:

(6)

where $\xi$ is a probability distribution on $\mathcal {R}_{ck}$.

The difference between simulatability and zero-knowledge is that randomness $r_1,\ldots ,r_n$ is directly generated from $\xi$ as it would in the real-world protocol rather than chosen from adversary. This property becomes crucial when using the BDLOP commitments [BDL+18].

2.9 Commitment Scheme

We recall the BDLOP commitment scheme from [BDL+18] used in our constructions as well as previous works [ALS20, ENS20, LNS20a]. Suppose that we want to commit to a message vector $\vec {\varvec{m}}=(\varvec{m}_1,\ldots ,\varvec{m}_n)\in \mathcal {R}_q^n$ for $n\ge 1$ and that module ranks of $\kappa$ and $\lambda$ are required for M-SIS and M-LWE security, respectively. Then, in the key generation, a matrix $\varvec{B}_0\leftarrow \mathcal {R}_q^{\kappa \times (\kappa +\lambda +n)}$ and vectors $\vec {\varvec{b}}_1,\ldots ,\vec {\varvec{b}}_n\leftarrow \mathcal {R}_q^{\kappa +\lambda +n}$ are generated and output as public parameters. Note that one could choose to generate $\varvec{B}_0,\vec {\varvec{b}}_1, \ldots , \vec {\varvec{b}}_n$ in a more structured way as in [BDL+18] since it saves some computation. However, for readability, we write the commitment matrices in the “Knapsack” form as above. In our case, the hiding property of the commitment scheme is established via the duality between the Knapsack and $\mathsf {MLWE}$ problems. We refer to [EZS+19, Appendix C] for a more detailed discussion.

To commit to the message $\vec {\varvec{m}}$, we first sample $\vec {\varvec{r}}\leftarrow \chi ^{d\cdot (\kappa +\lambda +n)}$. Now, there are two parts of the commitment scheme: the binding part and the message encoding part. In particular, we compute

$$\begin{aligned} \vec {\varvec{t}}_0&= \varvec{B}_0\vec {\varvec{r}} \bmod {q}, \\ \varvec{t}_i&= \langle {\vec {\varvec{b}}_i,\vec {\varvec{r}}}\rangle + \varvec{m}_i \bmod {q},\quad \end{aligned}$$

for $i\in [n]$, where $\vec {\varvec{t}}_0$ forms the binding part and each $\varvec{t}_i$ encodes a message polynomial $\varvec{m}_i$.

We recall the notion of a weak opening [ALS20].

Definition 2.9

A weak opening for the commitment $\vec {\varvec{t}} = \vec {\varvec{t}}_0 \parallel \varvec{t}_1 \parallel \cdots \parallel \varvec{t}_n$ consists of d polynomials $\bar{\varvec{c}}_i \in \mathcal {R}_q$, a randomness vector $\vec {\varvec{r}}^*$ over $\mathcal {R}_q$ and messages $\varvec{m}^*_1,\ldots ,\varvec{m}^*_n \in \mathcal {R}_q$ such that

$$\begin{aligned}&\left\Vert {\bar{\varvec{c}}_i}\right\Vert _1 \le 2\mathsf {k} \text { and } \bar{\varvec{c}}_i \bmod X-\zeta ^{2i+1} \ne 0 \text { for all } 0 \le i< d, \\&\left\Vert {\bar{\varvec{c}}_i\vec {\varvec{r}}^*}\right\Vert _2 \le 2\beta \text { for all } 0 \le i < d, \\&\varvec{B}_0\vec {\varvec{r}}^* = \vec {\varvec{t}}_0, \\&\langle {\vec {\varvec{b}}_i,\vec {\varvec{r}}^*}\rangle + \varvec{m}^*_i = \varvec{t}_i \text { for } i \in [n] \end{aligned}$$

Attema et al. show that the commitment scheme is still binding with respect to weak openings.

2.10 Framework by Lyubashevsky et al. [LNS20a]

Recently, Lyubashevsky et al. [LNS20a] proposed a general framework for proving linear and multiplicative relations between committed messages. Concretely, suppose that the prover $\mathcal {P}$ has a vector of n messages $\vec {m} = (\vec {m}_1,\ldots , \vec {m}_{n}) \in \mathbb {Z}_q^{nl}$. Let $\mathsf {pp}$ be a public set of polynomials $P : \left( \mathbb {Z}_q^l\right) ^{n} \rightarrow \mathbb {Z}_q^l$ of n variables over $\mathbb {Z}_q^l$ with standard component-wise addition and multiplication and define $\alpha = \max _{P \in \mathsf {pp}} \deg (P)$⁴. For readability, we will often “concatenate” polynomials in $\mathsf {pp}$, i.e. we will write $\mathsf {pp}= \{P_1,\ldots ,P_t\}$ where each $P_i : \left( \mathbb {Z}_q^l\right) ^{n} \rightarrow \mathbb {Z}_q^{u_i l}$ and $u_1,\ldots ,u_t >0$.

For the linear relations, let us set $\mathsf {ulp}= (A,\vec {u}) \in \mathbb {Z}_q^{vl \times nl} \times \mathbb {Z}_q^{vl}$. In practice, A can have arbitrary number of rows but then we would have to pad rows with zeroes in order to get a multiple of l.

Overall, [LNS20a] provides a protocol $\varvec{\pi } = (\mathsf {Com}_{n,\alpha },\varPi ^\alpha _n\left( \mathsf {pp},\mathsf {ulp}\right) )$ where the prover $\mathcal {P}$ first generates the BDLOP commitments to $\vec {m}$ (sub-protocol $\mathsf {Com}_{n,\alpha }$) and then wants to prove that $\vec {m} \in \mathcal {L}_{n}\left( \mathsf {pp},\mathsf {ulp}\right)$ (sub-protocol $\varPi ^\alpha _n\left( \mathsf {pp},\mathsf {ulp}\right)$) where

$$\begin{aligned} \mathcal {L}_{n}\left( \mathsf {pp},\mathsf {ulp}\right) := \{ \vec {m} \in \mathbb {Z}_q^{nl} : \forall P \in \mathsf {pp}, P(\vec {m}) = \vec {0} \text { and } A\vec {m} = \vec {u}\}. \end{aligned}$$

(7)

In this paper we are only interested in applying the LNS framework only for the case $l=d$, i.e. $X^d+1$ splits completely into linear factors modulo q, unless stated otherwise.

Let us formulate the protocol $\pi$ in terms of the commit-and-prove functionality from Sect. 2.8. First, the relation $R_{LNS}$ we are interested in here is

$$\left( ck,(\mathsf {pp},\mathsf {ulp}),\vec {m}\right) \in R_{LNS} \iff \vec {m} \in \mathcal {L}_{n}\left( \mathsf {pp},\mathsf {ulp}\right) .$$

We define a CP functionality $LNS = (\mathsf {LNSGen},\mathsf {LNSCom}, \mathsf {LNSProve}^U,$$\mathsf {LNSVerify}^U)$ for the relation $R_{LNS}$ as follows:

• $\mathsf {LNSGen}(1^\mu ):$ It outputs a commitment key ck specifies the message space $\mathcal {M}_{ck} = \mathbb {Z}_q^{nd}$, randomness space $\mathcal {R}_{ck} = \{-1,0,1\}^{d\cdot (\kappa +\lambda +n+\alpha )}$⁵ and the commitment space $\mathcal {C}_{ck} = \mathcal {R}_q^{\kappa +n}$. It also generates the matrix $\varvec{B}_0 \leftarrow \mathcal {R}_q^{\kappa \times (\kappa +\lambda +n+\alpha )}$ and vectors $\vec {\varvec{b}}_1,\ldots ,\vec {\varvec{b}}_{n+\alpha } \leftarrow \mathcal {R}_q^{\kappa +\lambda +n+\alpha }$.

• $\mathsf {LNSCom}_{ck}\left( (\vec {m}_1,\ldots ,\vec {m}_n);\vec {\varvec{r}}\right)$ outputs $(\vec {\varvec{t}}_0,\varvec{t}_1,\ldots ,\varvec{t}_n)$ where

  $$\begin{aligned} \vec {\varvec{t}}_0&= \varvec{B}_0\vec {\varvec{r}} \bmod {q}, \\ \varvec{t}_i&= \langle {\vec {\varvec{b}}_i,\vec {\varvec{r}}}\rangle + \mathsf {NTT}^{-1}\left( {\vec {m}_i}\right) \bmod {q} \text { for } i\in [n]. \end{aligned}$$

• $\mathsf {LNSProve}^U_{ck}\left( (\mathsf {pp},\mathsf {ulp}),\vec {m}_1,\ldots ,\vec {m}_n,\vec {\varvec{r}}\right)$: It runs the non-interactive version of the protocol $\varPi ^\alpha _n\left( \mathsf {pp},\mathsf {ulp}\right)$ (e.g. [LNS20a, Fig. 8]), using the Fiat-Shamir transform, and outputs the proof $\pi$. Letter U denotes that the algorithm uses uniform rejection sampling.

• $\mathsf {LNSVerify}^U_{ck}\left( (\mathsf {pp},\mathsf {ulp}),\vec {\varvec{t}}_0,\varvec{t}_1,\ldots ,\varvec{t}_n,\pi \right)$: Check the verification equations of $\varPi ^\alpha _n\left( \mathsf {pp},\mathsf {ulp}\right)$ (e.g. [LNS20a, Fig. 9]).

Eventually, Lyubashevsky et al. show that the commit-and-prove functionality LNS defined above for the relation $R_{LNS}$ is both knowledge sound with negligible knowledge error under the Module-SIS assumption and simulatable under the Module-LWE assumption where the randomness $\vec {\varvec{r}}$ distribution is defined over $\xi = \chi ^{d\cdot (\kappa +\lambda +n+\alpha )}$ .

3 Opening Proof with Improved Rejection Sampling

In lattice-based zero-knowledge proofs, e.g.[BLS19, ALS20], the prover will want to output a vector $\vec {\varvec{z}}$ whose distribution should be independent of a secret randomness vector $\vec {\varvec{r}}$, so that $\vec {\varvec{z}}$ cannot be used to gain any information on the prover’s secret. During the protocol, the prover computes $\vec {\varvec{z}} = \vec {\varvec{y}} + \varvec{c}\vec {\varvec{r}}$ where $\vec {\varvec{r}}$ is the randomness used to commit to the prover’s secret, $\varvec{c} \leftarrow C$ is a challenge polynomial, and $\vec {\varvec{y}}$ is a “masking” vector. In order to remove the dependency of $\vec {\varvec{z}}$ on $\vec {\varvec{r}}$, one applies the rejection sampling technique.

Lemma 3.1

([BLS19]). Let $V \subseteq \mathcal {R}^\ell$ be a set of polynomials with norm at most T and $\rho :V \rightarrow [{0,1}]$ be a probability distribution. Also, write $\mathfrak {s}= 11T$ and $M = 3$. Now, sample $\vec {\varvec{v}} \leftarrow \rho$ and $\vec {\varvec{y}} \leftarrow D^{\ell d}_\mathfrak {s}$, set $\vec {\varvec{z}} = \vec {\varvec{y}} + \vec {\varvec{v}}$, and run $b \leftarrow \mathsf {Rej}_0(\vec {\varvec{z}}, \vec {\varvec{v}}, \mathfrak {s})$ as defined in Fig. 2. Then, the probability that $b = 0$ is at least $(1- 2^{-100})/M$ and the distribution of $(\vec {\varvec{v}}, \vec {\varvec{z}})$, conditioned on $b = 0$, is within statistical distance of $2^{-100}/M$ of the product distribution $\rho \times D^{\ell d}_\mathfrak {s}$.

Fig. 2.

Two rejection sampling algorithms: the one used in previous works (left) and the one proposed in this section (right).

Let us recall how parameters $\mathfrak {s}$ and M are usually selected. Namely, the repetition rate M is chosen to be an upper-bound on:

$$\begin{aligned} \frac{D^{\ell d}_\mathfrak {s}(\vec {\varvec{z}})}{D^{\ell d}_{\vec {\varvec{v}},\mathfrak {s}}(\vec {\varvec{z}})}=\exp \left( \frac{-2\langle \vec {\varvec{z}},\vec {\varvec{v}}\rangle + \Vert \vec {\varvec{v}}\Vert ^2}{2\mathfrak {s}^2}\right) \le \exp \left( \frac{24\mathfrak {s}\Vert \vec {\varvec{v}}\Vert + \Vert \vec {\varvec{v}}\Vert ^2}{2\mathfrak {s}^2}\right) = M. \end{aligned}$$

(8)

For the inequality we used the tail bound which says that with probability at least $1- 2^{100}$ we have $|\langle \vec {\varvec{z}}, \vec {\varvec{v}} \rangle | < 12\mathfrak {s}\Vert \vec {\varvec{v}}\Vert$ for $\vec {\varvec{z}} \leftarrow D^{\ell d}_\mathfrak {s}$ [Ban93, Lyu12]. Hence, by setting $\mathfrak {s}= 11\Vert \vec {\varvec{v}}\Vert$ we obtain $M \approx 3$.

In this section we propose a new way to apply rejection sampling. Namely, we force $\vec {\varvec{z}}$ to satisfy $\langle \vec {\varvec{z}}, \vec {\varvec{v}} \rangle \ge 0$, otherwise we abort. With this additional assumption, we can set M in the following way:

$$\begin{aligned} \exp \left( \frac{-2\langle \vec {\varvec{z}},\vec {\varvec{v}}\rangle + \Vert \vec {\varvec{v}}\Vert ^2}{2\mathfrak {s}^2}\right) \le \exp \left( \frac{\Vert \vec {\varvec{v}}\Vert ^2}{2\mathfrak {s}^2}\right) = M. \end{aligned}$$

(9)

Hence, for $M\approx 3$ one would select $\mathfrak {s}= 0.675\cdot \Vert \vec {\varvec{v}}\Vert$. Note that the probability for $\vec {\varvec{z}} \leftarrow D^{\ell d}_\sigma$ that $\langle \vec {\varvec{z}}, \vec {\varvec{v}} \rangle \ge 0$ is at least 1/2. Hence, the expected number of rejections would be at most $2M=6$. On the other hand, if one aims for $M = 6$ repetitions using (8), then $\mathfrak {s}= 6.74 \cdot \Vert \vec {\varvec{v}}\Vert$. Thus, we manage to reduce the standard deviation by around a factor of 10.

Subset Rejection Sampling. In order to prove security of our new rejection sampling algorithm, we need the following modification of the rejection sampling lemma by Lyubashevsky [Lyu12].

Lemma 3.2

(Subset Rejection Sampling). Let V be an arbitrary set and $h : V \rightarrow \mathbb {R} , f :\mathbb {Z}^m\rightarrow \mathbb {R}$ be probability distributions. Also define a family of set $S_v \subseteq \mathbb {Z}^m$ for $v \in V$ and $S = \{(z,v) \subseteq V \times \mathbb {Z}^m : z \in S_v\}$. Suppose $g_v:\mathbb {Z}^m\rightarrow \mathbb {R}$ is a family distributions indexed by all $v \in V$ and there exist $M, \gamma \ge 0$ which satisfy:

$$\begin{aligned} \begin{aligned}&\forall v \in V, z \in S_v : Mg_v(z) \ge f(z) \\&\forall v \in V: \sum _{z\in S_v} f(z) \ge \gamma . \end{aligned} \end{aligned}$$

(10)

Then the distributions of the output of $\mathcal {A}$ and $\mathcal {F}$, defined in Fig. 3, are identical. Moreover, the probability that $\mathcal {A}$ and $\mathcal {F}$ output something is at least $\frac{\gamma }{M}$.

Fig. 3.

Algorithms $\mathcal {A}$ and $\mathcal {F}$ for Lemma 3.2.

Proof

Let $v \in V$. If $z \in S_v$, the probability that $\mathcal {A}$ outputs z is equal to $g_v(z)\cdot \frac{f(z)}{Mg_v(z)} = \frac{f(z)}{M}$. Otherwise, the probability that $\mathcal {A}$ outputs $z\not \in S_v$ is exactly 0. Hence

$$\Pr [\mathcal {A}\text { outputs something}] = \sum _{v\in V}h(v)\sum _{z \in S_v} \frac{f(z)}{M}\ge \frac{\gamma }{M}.$$

Moreover, the probability that $\mathcal {F}$ outputs something is also $\frac{\sum _{(z,v)\in S} h(v)f(z)}{M}$. Hence:

$$\begin{aligned} \varDelta (\mathcal {A},\mathcal {F})&= \frac{1}{2} \left( \sum _{(z,v) \in S}|\mathcal {A}(z,v) - \mathcal {F}(z,v)|\right) \\&=\frac{1}{2} \sum _{v \in V} h(v)\left( \sum _{z \in S_v}\left| g_v(z)\cdot \frac{f(z)}{Mg_v(z)} - \frac{f(z)}{M}\right| \right) \\&=\frac{1}{2} \sum _{v \in V} h(v)\left( \sum _{z \in S_v}\left| \frac{f(z)}{M} - \frac{f(z)}{M}\right| \right) = 0. \end{aligned}$$

   $\square$

Later on, we will consider the special case when $f := D^m_{\mathfrak {s}}, g_{\vec {v}} := D^m_{\vec {v},\mathfrak {s}}$ for $\vec {v} \in V \subseteq \mathbb {Z}^m$ and

$$S_v := \{ \vec {z} \in \mathbb {Z}^m : \langle \vec {v},\vec {z} \rangle \ge 0\}.$$

Then, the probability that $\mathcal {A}$ outputs something is at least:

$$\frac{1}{M}\sum _{\vec {v} \in V}h(\vec {v})\Pr _{\vec {z} \leftarrow D^m_{\mathfrak {s}}}[\langle \vec {v},\vec {z} \rangle \ge 0] \ge \frac{1}{2M}.$$

Therefore, we can set $\gamma = 1/2$. Here, we used the fact that $\Pr _{\vec {z} \leftarrow D^m_{\mathfrak {s}}}[\langle \vec {v},\vec {z} \rangle > 0] = \Pr _{\vec {z} \leftarrow D^m_{\mathfrak {s}}}[\langle \vec {v},\vec {z} \rangle < 0]$. We also highlight that the value M we chose in (9) indeed satisfies Eq. 10.

Extended M-LWE. One observes that with the new approach, the verifier learns some new information about the secret. Indeed, if a prover $\mathcal {P}$ returns $\vec {\varvec{z}}$ then the verifier $\mathcal {V}$ knows that $\langle \vec {\varvec{z}}, \vec {\varvec{v}} \rangle \ge 0$. However, later on we will show that the opening proof from [ALS20] using the new rejection sampling is still simulatable assuming that a new problem, which we call Extended M-LWE, is computationally hard. For readability, we will describe it in a “knapsack” form.

Definition 3.3

(Extended M-LWE$_{m,k,\lambda ,\chi ,\xi _1,\xi _2}$). The Extended Module-LWE problem with parameters $m,\lambda >0$ and error distributions $\chi ,\xi _1$ and $\xi _2$ over $\mathcal {R}$ and $\mathcal {R}^k$ respectively, asks the adversary $\mathcal {A}$ to distinguish between the following two cases:

• 1. $\left( \varvec{B},\varvec{B}\vec {\varvec{r}},\varvec{c}_1,\ldots ,\varvec{c}_k,\vec {\varvec{z}},\mathsf {sign}\left( \left\langle \vec {\varvec{z}}, \begin{pmatrix}\varvec{c}_1\vec {\varvec{r}} \\ \vdots \\ \varvec{c}_k \vec {\varvec{r}} \end{pmatrix} \right\rangle \right) \right)$ for $\varvec{B}\leftarrow \mathcal {R}_q^{m\times (m+\lambda )}$, a secret vector $\vec {\varvec{r}}\leftarrow \chi ^{m+\lambda }$ and $(\vec {\varvec{z}},\varvec{c}_1,\ldots ,\varvec{c}_k) \leftarrow \xi ^{k(m+\lambda )}_1 \times \xi _2$

• 2. $\left( \varvec{B},\vec {\varvec{u}},\varvec{c}_1,\ldots ,\varvec{c}_k,\vec {\varvec{z}},\mathsf {sign}\left( \left\langle \vec {\varvec{z}}, \begin{pmatrix}\varvec{c}_1\vec {\varvec{r}} \\ \vdots \\ \varvec{c}_k \vec {\varvec{r}} \end{pmatrix} \right\rangle \right) \right)$ for $\varvec{B}\leftarrow \mathcal {R}_q^{m\times (m+\lambda )}, \vec {\varvec{u}} \leftarrow \mathcal {R}_q^m$ and $(\vec {\varvec{z}},\varvec{c}_1,\ldots ,\varvec{c}_k) \leftarrow \xi ^{k(m+\lambda )}_1 \times \xi _2$

where $\mathsf {sign}(a) = 1$ if $a \ge 0$ and 0 otherwise. Then, $\mathcal {A}$ is said to have advantage $\epsilon$ in solving Extended M-LWE$_{m,k,\lambda ,\chi ,\xi _1,\xi _2}$ if

where

$$s = \mathsf {sign}\left( \left\langle \vec {\varvec{z}}, \begin{pmatrix}\varvec{c}_1\vec {\varvec{r}} \\ \vdots \\ \varvec{c}_k \vec {\varvec{r}} \end{pmatrix} \right\rangle \right) \text { and }\vec {\varvec{c}} = (\varvec{c}_1,\ldots ,\varvec{c}_k).$$

To simplify notation, we will write Extended M-LWE$_{m,\lambda }$ to denote Extended M-LWE$_{m,1,\lambda ,\chi ^d,D^d_\mathfrak {s},C}$ where $\chi$ is defined in Sect. 2.6.

We note that the LWE problem with various side information has already been discussed in e.g. [DGK+10, AP12, DDGR20]. As far as we are aware, our new variant of M-LWE is the closest to the Extended LWE problem defined by Alperin-Sheriff and Peikert [AP12]⁶. Indeed, in [LNS20b, Appendix D] we show that hardness of the non-algebraic version of our Extended M-LWE (i.e. without any polynomial ring structure) can be reduced to plain LWE using similar techniques as in [AP12].

Hardness of Ring/Module-LWE is often analysed as an LWE problem since, so far, the best known attacks do not make use of the algebraic structure of the polynomial ring [ADPS15]. Then, the only two attacks which would be relevant to our Module-LWE problem are be the primal and dual attacks [Alb17, AGVW17, APS15]. Interestingly, the concrete analysis suggests that solving search-LWE (using the primal attack) is more efficient than solving the decisional version of LWE (using the dual attack). Thus, we believe that the search Extended-MLWE problem should still be hard with one bit, i.e. s, leaked since the vector $\vec {\varvec{r}}$ has high enough entropy.

3.1 Concrete Instantiation

We describe how to apply our rejection sampling in the opening proof by Attema et al. [ALS20]. For readability, we consider the simple version of the protocol without any commitment compression [DKL+18] or Galois automorphisms [LNS20a, Appendix A.3] for boosting soundness. We discuss how to apply all those improvements in Sect. 3.2 and [LNS20b, Appendix B].

One observes that the protocol presented in Fig. 4 is not very meaningful since it only shows that prover $\mathcal {P}$ has a polynomial $\varvec{m} \in \mathcal {R}_q$. However, it is a key ingredient to prove linear [ENS20] and multiplicative [ALS20] relations between committed messages.

Formally, let us define the following the commit-and-prove functionality $CP = (\mathsf {Gen},\mathsf {Com}, \mathsf {Prove},\mathsf {Verify})$:

• $\mathsf {Gen}(1^\mu )$: Given a security parameter $\mu$, generates a commitment key ck which specifies a message space $\mathcal {M}_{ck} = R_q$, a randomness space $\mathcal {R}_{ck} = \{-1,0,1\}^{(\lambda +\kappa +1)d}$ and commitment space $\mathcal {C}_{ck}=\mathcal {R}_q^{\kappa +1}$. It also generates the matrix $\varvec{B}_0 \leftarrow \mathcal {R}_q^{\kappa \times (\kappa +\lambda +1)}$ and the vector $\vec {\varvec{b}}_1 \leftarrow \mathcal {R}_q^{\kappa +\lambda +1}$.

• $\mathsf {Com}_{ck}(\varvec{m};\vec {\varvec{r}})$: Given a commitment key ck, a message $\varvec{m} \in \mathcal {M}_{ck}$ and randomness $\vec {\varvec{r}} \in \mathcal {R}_{ck}$ returns a commitment $(\vec {\varvec{t}}_0,\varvec{t}_1)=(\varvec{B}_0\vec {\varvec{r}},\langle {\vec {\varvec{b}}_1,\vec {\varvec{r}}}\rangle + \varvec{m})\in \mathcal {C}_{ck}$.

• $\mathsf {Prove}_{ck}\left( x,\varvec{m},\vec {\varvec{r}}\right)$: It first generates $\vec {\varvec{y}} \leftarrow D^{\kappa +\lambda +1}_\mathfrak {s}$ and computes $\varvec{c} = H(\varvec{B}_0\vec {\varvec{y}})$. Then, it computes $\vec {\varvec{z}} = \vec {\varvec{y}} + \varvec{c}\vec {\varvec{r}}$ and gets $b \leftarrow \mathsf {Rej}_1(\vec {\varvec{z}},\varvec{c}\vec {\varvec{r}},\mathfrak {s})$. If $b=0$, it outputs $\pi = (\varvec{c},\vec {\varvec{z}})$.

• $\mathsf {Verify}_{ck}\left( x,\vec {\varvec{t}}_0,\varvec{t}_1,\pi \right)$: Parse $\pi = (\varvec{c},\vec {\varvec{z}})$. If $\Vert \vec {\varvec{z}}\Vert \le \mathfrak {s}\sqrt{2(\lambda + \kappa + 1)d}$ and $\varvec{c} = H(\vec {\varvec{B}}_0\vec {\varvec{z}} - \varvec{c}\vec {\varvec{t}}_0)$, return 1. Otherwise, return 0.

Here, $H: \{0,1\}^* \rightarrow \{-1,0,1\}^{d} \subset \mathcal {R}_q$ is a random oracle which generates output from the distribution C (see Sect. 2.4). The language $R_L$, for which CP is defined, is trivial: $(ck,x,\varvec{m}) \in R_L \iff \varvec{m} \in \mathcal {R}_q$.

Fig. 4.

Opening proof for the commitment scheme. If $b=0$ then the protocol is identical to the one described in [ALS20] and uses $\mathsf {Rej}_0$ defined in Fig. 2. On the other hand, if $b=1$ then we apply the new rejection sampling algorithm $\mathsf {Rej}_1$ in Fig. 2.

Correctness and knowledge soundness of CP can be proven almost identically as in [ALS20, Theorem 4.4]. Hence, we will only focus on simulatability.

Theorem 3.4

Suppose Extended M-LWE$_{\kappa +1,\lambda }$ is computationally hard. Then, the commit-and-prove functionality $CP = (\mathsf {Gen},\mathsf {Com}, \mathsf {Prove},\mathsf {Verify})$ defined above for the language $R_L$ is simulatable in the random oracle model H.

Proof

Let us consider the following hybrid algorithms.

• $\mathsf {Prove}^1_{ck}\left( x,\varvec{m},\vec {\varvec{r}}\right)$: It first generates $\vec {\varvec{y}} \leftarrow D^{\kappa +\lambda +1}_\mathfrak {s}, \varvec{c} \leftarrow C$. Then, it computes $\vec {\varvec{z}} = \vec {\varvec{y}} + \varvec{c}\vec {\varvec{r}}$ and gets $b \leftarrow \mathsf {Rej}_1(\vec {\varvec{z}},\varvec{c}\vec {\varvec{r}},\mathfrak {s})$. If $b=1$, it outputs $\pi = (\varvec{c},\vec {\varvec{z}})$ and programs $\varvec{c} = H(\varvec{B}_0\vec {\varvec{z}} - \varvec{c}\vec {\varvec{t}}_0)$.

• $\mathsf {Prove}^2_{ck}\left( x,\varvec{m},\vec {\varvec{r}}\right)$: It first generates $\vec {\varvec{z}} \leftarrow D^{\kappa +\lambda +1}_\mathfrak {s}, \varvec{c} \leftarrow C$. If $\langle \vec {\varvec{z}},\varvec{c}\vec {\varvec{r}}\rangle \ge 0$ then with probability 1/M it outputs $\pi = (\varvec{c},\vec {\varvec{z}})$ and programs $\varvec{c} = H(\varvec{B}_0\vec {\varvec{z}} - \varvec{c}\vec {\varvec{t}}_0)$.

It is easy to see that the difference between $\mathsf {Prove}$ and $\mathsf {Prove}^1$ is that the algorithm programs the random oracle at one particular value $\varvec{B}\vec {\varvec{y}}$ (without checking whether it was already set). Hence, by arguing similarly as for zero-knowledge in [KLS18, DKL+18] we have that for all PPT adversaries $\mathcal {A}$:

(11)

For the next hybrid, we apply Lemma 3.2. Namely, let $m = (\lambda +\kappa +1)d$ and $V = \{\varvec{c}\vec {\varvec{r}} : \varvec{c}\in \{-1,0,1\}^d, \vec {\varvec{r}} \in \{-1,0,1\}^{m}\}$. Set the probability distribution $h:V \rightarrow \mathbb {R}$ as

$$h(\vec {\varvec{v}}) = \Pr [\varvec{c}\vec {\varvec{r}} = \vec {\varvec{v}} : \varvec{c} \leftarrow C, \vec {\varvec{r}} \leftarrow \chi ^m].$$

Next, we set $f := D^{m}_{\mathfrak {s}}, g_{\vec {\varvec{v}}} := D^m_{\vec {\varvec{v}},\mathfrak {s}}$ for $\vec {\varvec{v}} \in V$ and

$$S_{\vec {\varvec{v}}} := \{ \vec {\varvec{z}} \in \mathcal {R}_q^{\lambda +\kappa +1} : \langle \vec {\varvec{v}},\vec {\varvec{z}} \rangle \ge 0\}.$$

Then, by Lemma 3.2 we have:

(12)

for all adversaries $\mathcal {A}$. Now we define two algorithms $\mathsf {SimCom}$ and $\mathsf {SimProve}$ responsible for the simulation.

• $\mathsf {SimCom}_{ck}\left( x\right)$: It samples $\vec {\varvec{t}}_0$ and $\varvec{t}_1$ uniformly at random from $\mathcal {R}_q^{\kappa }$ and $\mathcal {R}_q$ respectively and returns $(\vec {\varvec{t}}_0,\varvec{t}_1)$.

• $\mathsf {SimProve}_{ck}\left( x,\vec {\varvec{t}}_0,\varvec{t}_1\right)$: It first generates $\vec {\varvec{z}} \leftarrow D^{\kappa +\lambda +1}_\mathfrak {s}, \vec {\varvec{r}}^* \leftarrow \chi ^{\lambda +\kappa +1}$ and $\varvec{c} \leftarrow C$. Then, if $\langle \vec {\varvec{z}},\varvec{c}\vec {\varvec{r}}^*\rangle \ge 0$ then with probability 1/M it outputs $\pi = (\varvec{c},\vec {\varvec{z}})$ and programs $\varvec{c} = H(\varvec{B}_0\vec {\varvec{z}} - \varvec{c}\vec {\varvec{t}}_0)$.

For the sake of contradiction suppose there exists a PPT adversary $\mathcal {A}$ such that

(13)

Let us construct an adversary $\mathcal {B}$ which solves the Extended M-LWE$_{\kappa +1,\lambda }$ also with probability $\epsilon$ using the algorithm $\mathcal {A}$. Concretely, suppose that $\mathcal {B}$ is given a tuple $\left( (\varvec{B}_0||\vec {\varvec{b}}_1),(\vec {\varvec{t}}_0||\varvec{u}_1),\vec {\varvec{z}},\varvec{c},\mathsf {sign}(\langle \vec {\varvec{z}},\varvec{c}\vec {\varvec{r}}\rangle ) \right)$ for $\vec {\varvec{z}} \leftarrow D^{(\lambda +\kappa +1)d}_\mathfrak {s}, \varvec{c} \leftarrow C$ and $\vec {\varvec{r}} \leftarrow \chi ^{(\lambda +\kappa +1)d}$. Firstly, $\mathcal {A}$ outputs a pair $(x,\varvec{m})$. Then, $\mathcal {B}$ sets $\varvec{t}_1 = \varvec{u}_1 + \varvec{m}$. Finally, if $\mathsf {sign}(\langle \vec {\varvec{z}},\varvec{c}\vec {\varvec{r}}\rangle ) \ge 0$ then $\mathcal {B}$ sets $\pi = (\varvec{c},\vec {\varvec{z}})$ and with probability 1/M sends $(\vec {\varvec{t}}_0,\varvec{t}_1,\pi )$. Otherwise, it aborts. At the end, $\mathcal {B}$ outputs the bit sent from $\mathcal {A}$.

First, suppose that $\vec {\varvec{t}}_0 = \varvec{B}\vec {\varvec{r}}$ and $\varvec{u}_1 = \langle \vec {\varvec{b}}_1, \vec {\varvec{r}}\rangle$. Then, $(\varvec{t}_0,\varvec{t}_1)$ constructed by $\mathcal {B}$ is indeed equal to $\mathsf {Com}_{ck}(\varvec{m};\vec {\varvec{r}})$. Then, the way $\pi$ is built is identical as in $\mathsf {Prove}^2$. In this case, the probability that $\mathcal {B}$ outputs bit 1 is equal to

On the other hand, assume that $\vec {\varvec{t}}_0$ and $\varvec{u}_1$ are chosen uniformly at random and also independently of $\vec {\varvec{r}}$. Then, $\varvec{t}_1$ is random as well. Hence, the probability that $\mathcal {B}$ outputs 1 is indeed equal to

$$ \Pr \left[ \begin{array}{l}ck \leftarrow \mathsf {Gen}(1^\mu ); (x,\varvec{m}) \leftarrow \mathcal {A}(ck); (\vec {\varvec{t}}_0,\varvec{t}_1) \leftarrow \mathsf {SimCom}_{ck}(x);\\ \pi \leftarrow \mathsf {SimProve}_{ck}(x,\vec {\varvec{t}}_0,\varvec{t}_1) ;\left( ck,x,\varvec{m}\right) \in R_L \wedge \mathcal {A}(\vec {\varvec{t}}_0,\varvec{t}_1,\pi ) = 1 \end{array} \right] .$$

Thus, $\mathcal {B}$ can efficiently distinguish between the two Extended M-LWE cases with probability $\epsilon$. Since, we assumed that the problem is computationally hard, this implies that $\epsilon$ is negligible. Then, the statement holds by the hybrid argument.

   $\square$

3.2 Boosting Soundness and Decreasing Standard Deviation

The protocol in Fig. 4 has soundness error around $q^{-d/l}$ which is not necessarily negligible. In order to boost soundness, Attema et al. [ALS20] apply Galois automorphisms. We recall the extended opening proof protocol below.

Prover $\mathcal {P}$ first generates $\vec {\varvec{y}}_0,\ldots ,\vec {\varvec{y}}_{k-1} \leftarrow D^{(\lambda +\kappa +1)d}_{\mathfrak {s}}$ and $\vec {\varvec{r}},\vec {\varvec{t}}_0,\varvec{t}_1$ as before. Next, it outputs $(\vec {\varvec{t}}_0,\varvec{t}_1,\vec {\varvec{w}}_0,\ldots ,\vec {\varvec{w}}_{k-1})$ where $\vec {\varvec{w}}_i = \varvec{B}_0\vec {\varvec{y}}_i$. After receiving a challenge $\varvec{c} \leftarrow C$ from the verifier, $\mathcal {P}$ computes

$$\vec {\varvec{z}}_i = \vec {\varvec{y}}_i + \sigma ^i(\varvec{c})\vec {\varvec{r}} \text { for } i=0,\ldots ,k-1 $$

where $\sigma := \sigma _{2d/k+1}$ where k is a divisor of d. Then, the prover applies rejection sampling $\mathsf {Rej}_1(\vec {\varvec{z}},\vec {\varvec{v}},\mathfrak {s})$ where $\vec {\varvec{z}} = \vec {\varvec{z}}_0 \parallel \cdots \parallel \vec {\varvec{z}}_{k-1}$ and $\vec {\varvec{v}} = \sigma ^0(\varvec{c})\vec {\varvec{r}} \parallel \cdots \parallel \sigma ^{k-1}(\varvec{c})\vec {\varvec{r}}$. If it does not abort, then $\mathcal {P}$ outputs $\vec {\varvec{z}}$. Finally, the verifier checks that $\vec {\varvec{z}}$ is small and

$$\varvec{B}_0 \vec {\varvec{z}}_i = \vec {\varvec{w}}_i + \sigma ^i(\varvec{c})\vec {\varvec{t}}_0 $$

for $i=0,\ldots ,k-1$. As argued by Attema et al., this protocol has soundness around $q^{-dk/l}$.

More recently, Lyubashevsky et al. [LNS20a, Appendix A.6] (also mentioned in [ENS20]) improved this opening proof by applying a simple modification. Suppose $X^n +1$ splits completely modulo q, i.e. $l=d$. Let us write the challenge $\varvec{c} = \varvec{c}_0 + \varvec{c}_1 X + \ldots + \varvec{c}_{k-1}X^{k-1} \leftarrow C$ where

$$\varvec{c}_i = \sum _{j=0}^{d/k-1} c_{jk + i} X^{jk}.$$

By definition of $\sigma = \sigma _{2d/k+1}$, we have that $\sigma (\varvec{c}_i) = \varvec{c}_i$ for each i. Therefore, we have:

$$\sigma ^i(\varvec{c}) = \sum ^{k-1}_{j=0}\sigma ^i(X^j)\varvec{c}_j.$$

The modified opening proof protocol is presented as follows. Prover $\mathcal {P}$ samples $\vec {\varvec{y}}'_0,\ldots ,\vec {\varvec{y}}'_{k-1}$ from $D^{(\lambda +\kappa +1)d}_\mathfrak {s}$ as before. Then, the prover sends $\vec {\varvec{w}}'_i = \varvec{B}_0\vec {\varvec{y}}'_i$. After getting a challenge $\varvec{c} \leftarrow C$, it computes $\varvec{c}_0,\ldots ,\varvec{c}_{k-1}$ as above and calculates $\vec {\varvec{z}}'_i$ as:

$$ \begin{pmatrix} \vec {\varvec{z}}'_0 \\ \vec {\varvec{z}}'_1 \\ \vdots \\ \vec {\varvec{z}}'_{k-1} \end{pmatrix} = \begin{pmatrix} \vec {\varvec{y}}'_0 \\ \vec {\varvec{y}}'_1 \\ \vdots \\ \vec {\varvec{y}}'_{k-1} \end{pmatrix} + \begin{pmatrix} \varvec{c}_0 \vec {\varvec{r}}\\ \varvec{c}_1 \vec {\varvec{r}}\\ \vdots \\ \varvec{c}_{k-1}\vec {\varvec{r}} \end{pmatrix} . $$

Since each $\varvec{c}_i$ has only at most d/k non-zero coefficients, we manage to decrease the standard deviation possibly by a factor of k (in practice the improvement is smaller if one upper-bounds $\Vert \sigma ^i(\varvec{c})\vec {\varvec{r}}\Vert$ more cleverly).

Eventually, the prover applies rejection sampling $\mathsf {Rej}_1(\vec {\varvec{z}},\vec {\varvec{v}},\mathfrak {s})$ where $\vec {\varvec{z}} = \vec {\varvec{z}}'_0 \parallel \cdots \parallel \vec {\varvec{z}}'_{k-1}$ and $\vec {\varvec{v}} = \varvec{c}_0\vec {\varvec{r}} \parallel \cdots \parallel \varvec{c}_{k-1}\vec {\varvec{r}}$. After receiving vectors $\vec {\varvec{z}}'_j$, $\mathcal {V}$ first checks whether

$$\begin{aligned} \varvec{B}_0\vec {\varvec{z}}'_i \overset{?}{=}\vec {\varvec{w}}'_i + \varvec{c}_i\vec {\varvec{t}}_0. \end{aligned}$$

for $i=0,\ldots ,k-1$ and that each $\vec {\varvec{z}}_i$ is small.

Note that by computing

$$\vec {\varvec{y}}_i = \sum ^{k-1}_{j=0}\sigma ^i(X^j)\vec {\varvec{y}}'_j, \text { } \vec {\varvec{z}}_i = \sum ^{k-1}_{j=0}\sigma ^i(X^j)\vec {\varvec{z}}'_j$$

and $\vec {\varvec{w}}_i = \varvec{B}_0\vec {\varvec{y}}_i$ for $i=0,\ldots ,k-1$, we have:

$$\begin{aligned} \varvec{B}_0\vec {\varvec{z}}_i = \vec {\varvec{w}}_i + \sigma ^i(\varvec{c})\vec {\varvec{t}}_0 \end{aligned}$$

which is the exact verification equation as in [ALS20]. This observation is crucial in [LNS20a] in order to still be able to prove linear and multiplicative relations using techniques from [ALS20, ENS20].

Lyubashevsky et al. bound $\Vert \vec {\varvec{v}}\Vert$ by first finding $\alpha$ so that

$$\Pr \left[ \exists i, \Vert \varvec{c}_i\vec {\varvec{r}} \Vert _\infty > \alpha : \varvec{c} \leftarrow C, \vec {\varvec{r}} \leftarrow \chi ^{(\lambda +\kappa +1)d}\right] < 2^{-128}$$

and then setting the bound $\Vert \vec {\varvec{v}}\Vert \le \alpha \sqrt{\lambda +\kappa +1}$. In [LNS20b, Appendix C] we describe a more optimal way to compute an upper-bound on $\Vert \vec {\varvec{v}}\Vert$ using almost identical methods as in [DDLL13].

3.3 Applications

We apply the new rejection sampling technique in the protocol by Esgin et al. [ENS20, Appendix B] to prove knowledge of secrets in LWE samples. Concretely, for $n=2048$, we want to prove knowledge of a ternary vector $\vec {s}\in \{-1,0,1\}^{n}$ such that

$$\begin{aligned} \vec {u} = \left( A' \, \Vert \, I_{m} \right) \cdot \vec {s} \pmod {q}, \end{aligned}$$

where $I_m$ is the m-dimensional identity matrix, $A'\in \mathbb {Z}_q^{m\times (n-m)}$ is a public matrix chosen uniformly at random and q is a modulus of about 32 bits (i.e., $\log q \approx 32$). Note that $\vec {s}$ here corresponds to the concatenation of a secret vector and an error vector of 1024 dimension each in the usual LWE setting. For fair comparison, we will use the protocol described in [ENS20, Fig. 3] with the following two modifications (i) we do the Gaussian rejection sampling according to $\mathsf {Rej}_1$ instead of the uniform one and (ii) we apply the commitment compression techniques as in [LNS20b, Appendix B].

We set parameters $(q,d,l,k) = (\approx 2^{32},128,128,4)$ similarly as in [ENS20]. Esgin et al. choose the expected number of repetitions to be 18.87. Since sampling from a discrete Gaussians is much less efficient than from a uniform distribution, for fairness we set $\mathfrak {s}= T$ and $M \approx 3.3$ where T is the upper-bound on $\Vert \vec {\varvec{v}}\Vert$ where $\vec {\varvec{v}} = \varvec{c}_0\vec {\varvec{r}} \parallel \cdots \parallel \varvec{c}_{k-1} \vec {\varvec{r}}$. Esgin et al. use the fact that $\Vert \vec {\varvec{v}}\Vert _\infty \le d/k=32$ and thus they set $T = 32 \sqrt{(\lambda +\kappa +3+16)d}$. We, however, apply the bound described in [LNS20b, Appendix C] and observe that for $(\kappa ,\lambda )$ selected in the next paragraph, our bound on $\Vert \vec {\varvec{v}}\Vert$ is around five times smaller than in [ENS20].

Now we set $\lambda$ and $\kappa$ such that M-LWE and M-SIS are hard against known attacks. We measure the hardness with the root Hermite factor $\delta$ and aim for $\delta \approx 1.0043$ [ENS20, EZS+19, BLS19]. By assuming that the Extended M-LWE is almost equally hard as M-LWE, we set $\lambda = 10$ as in [ENS20]. On the other hand, for the M-SIS hardness we manage to set $\kappa = 8$ due to having smaller standard deviation $\mathfrak {s}$. Hence, without using the compression techniques, we obtain the proof of size 41.35KB compared to 47KB by [ENS20]. After applying the additional improvements described in [LNS20b, Appendix B] we reduce the proof size to 33.6KB.

Similarly, we can consider the LNS functionality defined in Sect. 2.10 where $\mathsf {LNSProve}^U$ use our new Gaussian rejection sampling in Fig. 2 instead of a uniform one. We will denote this variant of the protocol as $\mathsf {LNSProve}^D$ and the corresponding CP functionality for the language $R_L$ as

$$LNS^{D} = (\mathsf {LNSGen},\mathsf {LNSCom}, \mathsf {LNSProve}^D,\mathsf {LNSVerify}^D).$$

The total proof size (when using Discrete Gaussians and without any Dilithium compression techniques) is about

$$\begin{aligned} (n+\kappa + \alpha + 1) d\log q \,\, + \,\, k (\lambda +\kappa +n+ \alpha )d \cdot \log \left( 12\mathfrak {s}\right) \quad \text{ bits }. \end{aligned}$$

(14)

Here, $n,\alpha$ are defined in Sect. 2.10, k is a divisor of d such that $q^{-k}$ is negligible and $\mathfrak {s}$ is the standard deviation used for the rejection sampling. For efficiency, we also apply Dilithium compression methods described in [LNS20b, Appendix B].

We present the proof sizes for proving n-bit integer addition and multiplication using $LNS^D$ in Fig. 1.

4 Verifiable Decryption

In this section we apply the improved LNS framework with the rejection sampling from Sect. 3 to the problem of constructing a verifiable decryption scheme. We restrict our attention the Kyber key encapsulation scheme [BDK+18] and its NIST level 1 parameter set Kyber512. Kyber is a finalist in the NIST PQC standardization effort. Our techniques work equally well for any of the other lattice-based KEMs in round 3 of the NIST process, i.e. Saber [DKRV18] and NTRU [HPS98]. Kyber512 uses module rank 2 over the ring $\mathcal {R}_q= \mathbb {Z}_{q}[X]/(X^{256} + 1)$ with modulus $q = 3329$. The public key is given by an MLWE vector $\vec {\varvec{t}} = \varvec{A}\vec {\varvec{s}} + \vec {\varvec{e}}$ where $\varvec{A} \in \mathcal {R}_q^{2\times 2}$ is a uniform public matrix and $\vec {\varvec{s}}$ and $\vec {\varvec{e}}$ are short secret vectors with coefficients in the interval $[-2,2]$. The encryption of a binary polynomial $\varvec{m} \in \{0,1\}^{256}$ encoding a 256-bit key consists of the rounded vector and polynomial

$$\begin{aligned} \vec {\varvec{u}}&= \mathsf {Compress}_{10}\left( \varvec{A}^T\vec {\varvec{s}}' + \vec {\varvec{e}}_u\right) = \varvec{A}^T\vec {\varvec{s}}' + \vec {\varvec{e}}'_u \\ \varvec{v}&= \mathsf {Compress}_{4}\left( \langle {\vec {\varvec{t}},\vec {\varvec{s}}'}\rangle + \varvec{e}_v + \left\lceil {\frac{q}{2}}\right\rfloor \varvec{m}\right) = \langle {\vec {\varvec{t}},\vec {\varvec{s}}'}\rangle + \varvec{e}'_v + \left\lceil {\frac{q}{2}}\right\rfloor \varvec{m} \end{aligned}$$

where $\vec {\varvec{s}}'$, $\vec {\varvec{e}}_u$ and $\varvec{e}_v$ are again short, the functions $\mathsf {Compress}_{10}$ and $\mathsf {Compress}_4$ compress to 10 and 4 bits per coefficient, and $\vec {\varvec{e}}'_u$, $\varvec{e}'_v$ include the errors coming from the compression. Finally, decryption uses the observation

$$\begin{aligned} \varvec{v} - \langle {\vec {\varvec{s}},\vec {\varvec{u}}}\rangle = \langle {\vec {\varvec{e}},\vec {\varvec{s}}'}\rangle - \langle {\vec {\varvec{s}},\vec {\varvec{e}}'_u}\rangle + \varvec{e}'_v + \left\lceil {\frac{q}{2}}\right\rfloor \varvec{m}, \end{aligned}$$

which implies

$$\begin{aligned} \left\Vert {\varvec{v} - \langle {\vec {\varvec{s}},\vec {\varvec{u}}}\rangle - \left\lceil {\frac{q}{2}}\right\rfloor \varvec{m}}\right\Vert _\infty < \frac{q}{4} \end{aligned}$$

with overwhelming probability. In fact, the decryption algorithm will recover $\varvec{m}$ precisely if this norm bound is true. In the scheme there is no guarantee for this bound and encrypted keys can fail to be decryptable with probability around $2^{-139}$.

Now, for a verifiable decryption scheme we need to be able to prove knowledge of a vector $\vec {\varvec{s}}$ and polynomials $\varvec{m}$, $\varvec{x}$ such that

$$\begin{aligned}&\varvec{v} - \langle {\vec {\varvec{s}},\vec {\varvec{u}}}\rangle - \left\lceil {\frac{q}{2}}\right\rfloor \varvec{m} = \varvec{x} \end{aligned}$$

(15)

$$\begin{aligned}&\vec {\varvec{s}} \in \{-2,-1,0,1,2\}^{512} \end{aligned}$$

(16)

$$\begin{aligned}&\varvec{m} \in \{0,1\}^{256} \end{aligned}$$

(17)

$$\begin{aligned}&\left\Vert {\varvec{x}}\right\Vert _\infty < \frac{q}{4} \end{aligned}$$

(18)

The first three properties (15), (16), (17) can in principle directly be proven with the LNS framework. For the fourth one we can use a small-base decomposition approach for doing range proofs. A small problem is posed by the magnitude of the Kyber modulus $q = 3329$. While it is possible to instantiate the LNS framework in a way that allows to directly prove linear equations modulo such small primes, this results in quite large soundness error and many repetitions in the opening proof. To circumvent this problem and arrive at a more efficient protocol, we use the framework with a much larger modulus $q'$ and lift Eq. (15) to the integers. This means that we instead prove

$$\begin{aligned} \varvec{v} - \langle {\vec {\varvec{s}},\vec {\varvec{u}}}\rangle - \left\lceil {\frac{q}{2}}\right\rfloor \varvec{m} + \varvec{d}q \equiv \varvec{x} \pmod {q'} \end{aligned}$$

(19)

for another secret polynomial $\varvec{d} \in \mathbb {Z}[X]/(X^{256} + 1)$ whose range $\left\Vert {\varvec{d}}\right\Vert _\infty \le 2^{10}$ we also need to prove. Note that Eq. (19) for $q' > 2^{23}$ together with the range proofs implies Eq. (15) since from the ranges of the individual terms we know that the equation must hold over the integers, which in turn implies (15) since the additional term, which is a multiple of q, vanishes modulo q.

4.1 Range Proofs

In the protocol sketched above there are the two range proofs $\left\Vert {\varvec{d}}\right\Vert _\infty \le 2^{10}$ and $\left\Vert {\varvec{x}}\right\Vert _\infty < q/4$. For the first range proof it is actually enough to prove that $q\left\Vert {\varvec{d}}\right\Vert _\infty < q'/4$. We use a 64-bit prime $q'$ for the LNS framework protocol. Then, there is enough head-room between the actual range $2^{10}$ of $\varvec{d}$ and $q'/(4q) > 2^{50}$ so that we can use the approximate shortness proof. On the other hand, for proving the range of $\varvec{x}$ it is important to not have any slack in the proof. So here we decompose $\varvec{x}$ in base 5. We choose base 5, since for proving the coefficients of $\vec {\varvec{s}}$ to lie in the interval $[-2,2]$ we already have degree-5 product relations and hence can prove the base-5 decomposition without any additional garbage commitments. The interval of the coefficients of $\varvec{x}$ has length $q/2 = 1664$ and hence we need 5 base-5 digits for each coefficient. Now, since 1664 is not a power of 5 we write each coefficient of $\varvec{x}$ in the form

$$\begin{aligned} a_0 + a_15 + a_25^2 + a_35^3 + a_4260 \end{aligned}$$

with $a_4 \in {0,\dots ,4}$. This decomposition is not unique but precisely maps to the integers in the interval [0, 1664].

4.2 Proof Size

We compute the size of the verifiable decryption scheme for Kyber512 from above. As commitment messages we have the vector $\varvec{s}$ of $\mathbb {Z}$-dimension 512, the polynomial $\varvec{m}$ of dimension 256, the masking polynomial for the approximate range proof for $\varvec{d}$, and the expansion of $\varvec{x}$ in base-5, which has $\mathbb {Z}$-dimension $5\cdot 256 = 1280$. This amounts to a total message dimension of $n = 2176$. We then computed that the full LNS protocol with 64-bit modulus, $\mathsf {MLWE}$ rank 20 and $\mathsf {MSIS}$ rank 5 has a proof size of 43.6KB.