Lattice-Based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications

Abstract

We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree $k\ge 2$, where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree $k\ge 2$ have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P ’18) and arithmetic circuit arguments (EUROCRYPT ’16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case ($k=1$) and a very specific quadratic case ($k=2$), which are obtained as a special case of our technique.

Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting “inter-slot” operations, and “NTT-friendly” tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.

To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.

Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.

1 Introduction

Zero-knowledge proofs (ZKP) are fundamental building blocks used in many privacy-preserving applications such as anonymous cryptocurrencies and anonymous credentials [10], and the underlying advanced cryptographic primitives such as ring signatures [26]. They enable a prover to convince a verifier that a certain statement regarding a secret is true with minimal secret information leakage. A core property of ZKPs is soundness, that is, a cheating prover should not be able to create a convincing “proof”. In the context of proofs of knowledge (PoK), this means successful provers know a relevant secret (i.e., a witness), and this is usually proven by using an extractor that efficiently recovers the witness given two accepting protocol transcripts with the same initial message. We call this procedure “basic” witness extraction (also known as “2-special soundness”, see Definition 3). A natural behaviour that is trivially observed in discrete logarithm (DL) based ZKPs is that they achieve a convincing soundness level (i.e., a negligible soundness error) in a single protocol run (i.e., they are one-shot). However, this natural behaviour turns out to be unexpectedly hard to achieve in lattice-based proofs. There are some works [3, 6, 22,23,24] that address this problem in lattice-based cryptography and provide one-shot proofs in the context of protocols that work with “basic” witness extraction. On the other hand, recent research in the DL setting [7,8,9, 16] has shown that it is possible to construct more efficient proofs that require a “complex” witness extraction involving more than two accepting protocol transcripts (and thus more than two challenges) for recovering prover’s secret (i.e., the protocols are many-special sound). Such proofs rely on higher degree relations to obtain compact results, unlike the 2-special sound proofs that can only check linear (first degree) relations (we refer to the aforementioned works for the motivation behind proving high-degree relations). Again, in the DL setting, these proofs work smoothly and are easily one-shot. However, in the lattice setting, the situation is much more complicated, and, to the best of our knowledge, there is no one-shot witness extraction technique for non-linear relations.

1.1 Related Work – Lattice-Based Zero-Knowledge Proofs

In being one-shot proofs, the most relevant works for our zero-knowledge proofs are [6] and [3], where the protocols explicitly make use of lattice-based commitments. In fact, the ideas date back to the works by Lyubashevsky [22, 23] introducing the “Fiat-Shamir with Aborts” technique in lattice-based cryptography. The advantage of these works is that the (underlying) protocols achieve a negligible soundness error in a single run, which makes them very efficient in practice. However, all these approaches are limited to working with “basic” witness extraction except for a specific multiplicative (second degree) relation in [6]. The multiplicative argument in [6] is to prove that the coefficient of a quadratic term is zero and no explicit witness extraction from this non-linear relation is provided (and, indeed, no witness extraction from this second degree relation is needed as witnesses are extracted from the linear relations). All these one-shot proofs introduce new complications (more precisely, relaxations in the relation being proved) as we discuss in detail in Sect. 3. One can get asymptotically efficient lattice-based proofs for arithmetic circuits when the circuit size is large compared to the security parameter $\lambda$ using the amortization techniques from [2]. However, these techniques do not seem to be helpful in our case as the proved relations do not necessarily require a large circuit.

Another line of research makes use of multi-shot proofs that require multiple protocol repetitions to get a negligible soundness error. Stern-like combinatorial protocols [29] and proofs using binary challenges fall into this category, where one needs at least $\lambda$ protocol repetitions for $\lambda$-bit security. Therefore, even though these approaches have a wide range of applications (e.g. logarithmic-sized group and ring signatures as in [20]), they currently seem to fall far behind practical expectations (see Table 1 for the concrete results of [20]).

In the ring $R=\mathbb {Z}[X]/(X^d+1)$, it is possible to achieve a soundness error of $1\text {/}(2d)$ using the monomial challenges from [5]. Here the challenges are of the form $X^i$ for some $0\le i< 2d$ (i.e., there are 2d possible challenges in total), and it is shown in [5] that doubled inverses of challenge differences are short (more precisely, $\left\| 2(X^i-X^j)^{-1}\right\| \le \sqrt{d}$ for $i\ne j$). Still proofs using monomial challenges require at least 10 repetitions for a typical ring dimension $d\le 2048$. To summarize, for a soundness goal of $2^{-\lambda }$, all the above multi-shot approaches produce proofs of length $\widetilde{O}(\lambda ^2)$, as a function of the security parameter $\lambda$.

1.2 Asymptotic Costs of Existing Lattice-Based ZKP Techniques

First, let us assume that one relies on computational hardness assumptions, particularly, Module-SIS (M-SIS) and Module-LWE (M-LWE) for the security of a commitment scheme and let $d_{\text {SIS}},d_{\text {LWE}}$ be the dimension parameters required for M-SIS and M-LWE security, respectively. It is known that one needs $d_{\text {SIS}}= O(\lambda \frac{\log ^2\beta _{\text {SIS}}}{\log q})$ for $\lambda$-bit security based on M-SIS where $\beta _{\text {SIS}}$ is the norm of a valid M-SIS solution (see Appendix F.4 in the full version [13] for more). Letting $\beta _{\text {SIS}}= q^\varepsilon$ for $0<\varepsilon \le 1$, we get $\log \beta _{\text {SIS}}= \varepsilon \log q$ and, for a balanced security,

$$\begin{aligned} d_{\text {LWE}}\approx d_{\text {SIS}}= O(\lambda \varepsilon ^2\log q). \end{aligned}$$

(1)

In lattice-based cryptography, the most commonly used commitment schemes for algebraic proofs are Unbounded-Message Commitment (UMC) and Hashed-Message Commitment (HMC) (see Sect. 2.4). These commitment schemes have different tradeoffs as discussed in the full version. Let n, m, d, v be the module rank for M-SIS, the randomness vector dimension in a commitment, the polynomial ring dimension and the message vector dimension in a commitment, respectively. The commitment vector is of dimension $n+v$ for UMC and n for HMC, which means the space costs of a commitment are $(n+v)d\log q$ and $nd\log q$ for UMC and HMC, respectively. Letting $\kappa$ be the number of protocol repetitions, we get the formulae for space costs in Table 2.

The commitment matrix dimensions are $(n+v)\times m$ for UMC and $n\times (m+v)$ for HMC, and both of the commitments are computed as a matrix-vector multiplication.¹ Therefore, we also get the formulae for the time costs as given in Table 2 assuming a degree-d polynomial multiplication can be performed in time $\widetilde{O}(d)$ (more precisely, $O(d\log d)$) using, e.g., FFT-like methods.

Further, we have $d_{\text {LWE}}=(m-n-v)d$ and thus $md>d_{\text {LWE}}$ for UMC, and $d_{\text {SIS}}=nd$ for both HMC and UMC. As a result, using (1), we get

$$\begin{aligned} md = O(\lambda \varepsilon ^2\log q) \text { for UMC, and} \quad nd=O(\lambda \varepsilon ^2\log q) \text { for UMC/HMC.} \end{aligned}$$

(2)

Now, suppose that we want to prove a relation that involves commitment to $k=O(\log q)$ messages (for example, to prove knowledge of $m_1,\ldots m_k$ such that $\sum _{i=1}^{k}\alpha _i m_i = 0$ for public values $\alpha _1,\ldots ,\alpha _k$). Clearly, if we commit to these messages independently, then the overall cost of both time and space increase by a factor of k. Alternatively, we can pack multiple messages in a commitment by setting $v=k$ and hope that this gives a better performance. If an existing multi-shot technique such as Stern-based proofs, or those using binary or monomial challenges, is used, the number of protocol repetitions $\kappa$ will be $\widetilde{O}(\lambda )$, and thus we get the asymptotic costs in the “multi-shot” column of Table 2 (using (2)). On the other hand, if one can make the proof one-shot, then we get the complexities in the “one-shot” column of Table 2, where there is a clear saving of $\widetilde{O}(\lambda )$.

1.3 Our Contributions

One-shot proof techniques for non-linear polynomial relations via adjugate matrices. We introduce new techniques that provide the first solution to the problem of building efficient one-shot lattice-based ZKPs that require a “complex” witness extraction. In particular, we introduce witness extraction from non-linear polynomial relations of degree $k\ge 2$ (i.e., “$(k+1)$-special sound protocols”, see Definition 3) while still having a one-shot proof. Our proofs reach a negligible soundness error in a single run of the protocol. In comparison to relevant multi-shot prior works such as [14, 20], we improve the asymptotic computation and communication costs by a factor of $\widetilde{O}(\lambda )$ for the security parameter $\lambda$ (see Table 2), and also achieve a dramatic practical efficiency improvement in both costs (see Table 1). The previous one-shot ideas [3, 6, 22, 23] are obtained as a special case of our technique (see Sect. 3.2).

Speedup Technique 1: CRT-packing supporting inter-slot operations. Drawing inspiration from the CRT-packing techniques [15, 27] used in fully homomorphic encryption, we introduce the first CRT-packing technique in lattice-based ZKPs that supports “inter-slot” and a complete set of operations. That is, our technique supports operations between messages stored in separate CRT “slots”, and gives the ability to commit to/encode multiple messages at once and then “extract” all the messages in a way that permits interoperability among extracted values. In its full potential, it provides an asymptotic improvement of $O(\log q)$ in computation costs of proofs involving $O(\log q)$ messages at no additional cost to the proof length (see Table 2).

Table 1. Size comparison of ring signatures for “post-quantum” 128-bit security with N ring participants (the challenge space size is $2^{256}$). Signature lengths are in KB. See Appendix A in the full version [13] for more details.

Speedup Technique 2: “NTT-friendly” tools for fully-splitting rings. An important obstacle to computational efficiency of lattice-based ZKPs is that one often requires invertibility of short elements in a ring. A common solution to meeting this criterion is to choose a modulus q of a special form (such as $q\equiv 5\bmod 8$) at the cost of disabling the ring $R_q=\mathbb {Z}_q[X]/(X^d+1)$ to fully-split, and thus preventing the (full) use of fast computational algorithms such as Number Theoretic Transform (NTT). We introduce a new result (Lemma 7) that can be used as an alternative to enforcing invertibility, and show how it can be made used of while still supporting the use of NTT-like algorithms. The only requirement of our lemma is for the modulus q to be sufficiently large, without putting any assumptions on its “shape”. One can see from, e.g., [25, Table 2] that full NTT provides a speedup of a factor between 6–8 in comparison to plain Karatsuba multiplication (with no FFT).

Design of shorter and faster lattice-based protocols. Our techniques enable the construction of communication and computation efficient lattice-based analogues of DL-based protocols for important applications, where there was previously no efficient lattice-based solutions known. To illustrate this utility of our techniques, we design an efficient range proof that uses speedup technique 1, and an efficient one-out-of-many proof that uses speedup technique 2, where our one-shot proof technique is also applied in both of the proofs.

Application to advanced cryptographic tools. Despite their relaxed nature, we show that our ZKPs are sufficient for important practical applications. Our one-out-of-many proof is used as a building block for lattice-based ring signatures, and our relaxed aggregated range proof is shown to be sufficient for an application in a form of privacy-preserving linkable anonymous credentials.

In Table 1, we compare our ring signature size results to the other potential post-quantum proposals.² Most of these schemes, including ours, are only analyzed in the classical random oracle model (ROM), and all the results provided in Table 1 are those in ROM. [12, 18] are recent proposals from symmetric-key primitives using LowMC cipher [1] and all the rest are lattice-based proposals. As can be seen from the table, we achieve a dramatic improvement in comparison to all these post-quantum solutions. Our scheme even reaches the same performance of the linear-sized proposals (bottom two rows), which are tailored to be efficient for small ring sizes, for the smallest possible ring size $N=2$.³

As detailed in the full version [13], our ring signature achieves a signature length quasi-linear in the security parameter $\lambda$, and poly-logarithmic in the ring size N. In practice, its length is proportional to $\lambda \log ^2\lambda \log ^cN$ for some constant $c\approx 1.67$. This improves on the quadratic dependence on $\lambda$ in [12, 14, 18, 20].⁴ In terms of the dependence on $\log N$, our scheme grows slightly faster, however, it still outperforms all these works for N as big as billions and beyond.

We further analyze the computational efficiency of our ring signature in Appendix F.5 of the full version [13]. The analysis based on reasonable assumptions shows that our construction also greatly improves practical signing/verification times over the existing ring signature proposals with concrete computational efficiency results. For $N=1024$, we estimate the signing/verification times of our scheme to be below 30 ms whereas [18] reports 2.8 s for both of the running times. Our ring signature as well as its underlying protocols, namely binary proof and one-out-of-many proof, do not require any assumption on the “shape” of the modulus q, and thus permit the use of NTT-like algorithms.

1.4 Our Techniques

One-shot witness extraction for non-linear polynomial relations. The main challenge in designing efficient lattice-based ZKPs is that the extracted witness is required to be short as mandated by computational lattice problems (in particular, Short Integer Solution – SIS problem). Traditional witness extraction techniques involve the inverse of challenge differences as a multiplicative factor in extracted witnesses, and such an approach is problematic in lattice-based protocols as these inverse terms need not be short in general. This causes one to either resort to more inefficient techniques such as aforementioned multi-shot proofs or introduce relaxations in the proofs. Our solution falls into the latter.

The target problem reduces to the question of extracting useful information from a system of equations of the form $\varvec{V}\cdot \varvec{c} = \varvec{b}$ where $\varvec{V}$ is a matrix (a Vandermonde matrix in our case) constructed by challenges, $\varvec{c}$ is a vector of commitments with unknown openings and $\varvec{b}$ is a vector of commitments with known openings. Our idea is to introduce the use of adjugate matrices instead of inverse matrices in the “complex” witness extraction of lattice-based ZKPs. This technique, in one hand, enables us to extract useful information about the openings of the commitments in $\varvec{c}$ without the involvement of inverse terms, and on the other hand, is the main cause of relaxations. Here, it is crucial that the relaxed proof proves a useful relation, is sound, and also efficient. These piece together nicely when the use of adjugate matrices is accompanied by a good choice of challenge space, and we provide an analysis of our technique with a family of commonly used challenge spaces. We emphasize that straightforward soundness proofs do not work, and one needs special tools such as those introduced in this work to overcome the complications. Our one-shot proof approach is detailed in Sect. 3 after introducing necessary preliminaries.

Table 2. The (minimal) asymptotic time and space complexities of lattice-based protocols involving commitment to $k=O(\log q)$ messages. $\beta _{\text {SIS}}$: M-SIS solution norm, q: modulus, $\kappa$: the number of protocol repetitions, n: module rank for M-SIS, v: message vector dimension in a commitment, d: polynomial ring dimension, m: randomness vector dimension in a commitment. Assume: $\log q < \log ^2\beta _{\text {SIS}}/2$ and degree-d polynomial multiplication costs $\widetilde{O}(d)$. To optimize both costs, one would set $n=v$ in all cases.

CRT-packing supporting inter-slot operations. Let $R=\mathbb {Z}[X]/(X^d+1)$ and $R_q=\mathbb {Z}_q[X]/(X^d+1)$ for a usual choice of power-of-two d. It is known that $X^d+1$ factors linearly (and thus $R_q$ fully splits) for certain choices of q (e.g., a prime $q \equiv 1 \bmod 2d$) and, in that case, one can use NTT for polynomial multiplication in $R_q$ in time $O(d\log d)$. Assume that we choose such an “NTT-friendly” q. For $1 \le s \le d$ where s is a power of two, let $R_q^{(0)},\ldots ,R_q^{(s-1)}$ be the polynomial rings of dimension ${\textit{d}/s}$ such that $R_q = R_q^{(0)}\times \cdots \times R_q^{(s-1)}$ and $R_q^{(i)}=\mathbb {Z}_q[X]/(P^{(i)}(X))$ for some polynomial $P^{(i)}(X)$ of degree ${\textit{d}/s}$ for all $0\le i< s$ (which is obtained by the Chinese Remainder Theorem – CRT). We use these CRT “slots” to store s messages in a single ring element. Thus, if we have k messages in total, we can set the message vector dimension in a commitment as $v=k/s$ (instead of $v=k$ in previous approaches).

This initial part of the CRT-packing idea seems easy, and indeed a possible application of CRT in lattice-based ZKPs is mentioned in [25] to perform parallel proofs where there is no interaction between the messages in different slots. We are, on the other hand, interested in applications such as range proofs requiring “inter-slot” operations between messages in separate CRT slots, and get a complete set of operations (see [15] for a discussion in the context of FHE).

First thing to note about the CRT-packing technique is that even if the messages to be stored in CRT slots are short, the resulting element in $R_q$ representing s messages need not be so. This makes the technique inapplicable to HMC, which require short message inputs (at least in the general case). More importantly, there are two crucial hurdles we need to overcome: (1) it is not clear how to enable inter-slot operations and make the ZKP work in this setting, and (2) we need to make the proof one-shot in order not to lose the factor $\lambda$ gained.

Let us write $m=\langle m_0,\ldots ,m_{s-1} \rangle$ where $m\in R_q$ and $m_i\in R_q^{(i)}$ for $0\le i< s$ if m maps to $(m_0,\ldots ,m_{s-1})$ under the CRT-mapping. In general, to prove knowledge of a message b, the prover in the protocol needs to send some “encoding” of the message as $f = \text {Enc}_x(b) = x\cdot b + \rho$ where x is a challenge and $\rho$ is a random masking value. Clearly, we do not want to send k encodings in $R_q$ as it does not result in any savings. Instead, our idea is to send $k\text {/}s$ elements in $R_q$, each encoding s messages, in a way that enables the verifier to “extract” all k messages out of them. When the prover sends $f=x\cdot m + \rho$ (there may be multiple such f’s), for each $0\le i < s$, the verifier can compute $f_i = f \bmod (q,P^{(i)}(X)) = x_i\cdot m_i + \rho _i$ as the extracted encodings where $x=\langle x_0,\ldots ,x_{s-1} \rangle$ and $\rho =\langle \rho _0,\ldots ,\rho _{s-1} \rangle$. The main problem here is now that $f_i$’s are encodings of $m_i$’s, but under possibly different $x_i$’s, which circumvents interoperability of distinct $f_i$’s. For example, the sum $f_i + f_j$ for $i\ne j$ does not result in an encoding of the sum of messages under a common challenge x if $x_i\ne x_j$.

To overcome this problem, our idea is to choose the challenge $x=\langle x,\ldots ,x \rangle$ for $x\in \bigcap _{i=0}^{s-1} R_q^{(i)}$ such that all extracted encodings are under the same challenge x. This means x must be of degree smaller than ${\textit{d}/s}$ and thus the challenge space size is possibly greatly decreased.⁵ To make the proof one-shot, we choose the challenges to be polynomials of degree at most ${\textit{d}/s}-1$ with coefficients in $\mathbb {Z}_p$ such that $p^{d/s}= 2^{2\lambda }$ (i.e., there are $2^{2\lambda }$ challenges in total).⁶ Therefore, we need $d/s \cdot \log p =2\lambda$, which is satisfied by choosing $d/s = \lambda \varepsilon ^2$ and $\log p = 2/\varepsilon ^2$. We should also ensure $\log q > \log p = 2/\varepsilon ^2 = 2\log ^2q/\log ^2\beta _{\text {SIS}}$. This holds assuming $\log q < \log ^2\beta _{\text {SIS}}/2$, which is easily satisfied in most of the practical applications.

To have fast computation, we also set $d=d_{\text {SIS}}=O(\lambda \varepsilon ^2\log q)$, and hence get $s=O(\log q)$. Recall that we have k messages in total and s slots in a single ring element. As a result, for $k=O(\log q)$, it is enough to have $v=k/s=O(1)$. Overall, we end up with the asymptotic costs in the last column of Table 2, where our technique has a factor $\log q$ saving in asymptotic computational time in comparison to previous approaches without any compromise in communication.

An attractive example in practice where one would need a commitment to $k=O(\log q)$ messages is a range proof on $[0,2^k-1]$. Let us take a range proof on $\ell \in [0,2^{64}-1]$ as a running example. In this case, our proof proceeds as follows. We allow $R_q$ to split into at least 64 factors, and thus use a single $R_q$ element to commit to all the bits of $\ell$ (so committing to all the bits of $\ell$ only cost a single commitment with message vector dimension $v=1$). In its initial move, the prover sends some commitments and gets a challenge from the verifier. Then, the prover responds with a single encoding in $R_q$ (or 64 small encodings that costs as much as a single element in $R_q$). From here, the verifier extracts the encodings of all the bits, reconstructs the masked integer value $\ell$ and checks whether it matches the input commitment to $\ell$. In this setting, it is clear that we require operability between different slots, and thus set the encodings of all the bits to be under the same challenge x. For a ring dimension $d=512$, the infinity norm of a challenge can be as large as $2^{31}$, which seems quite large.

Table 3. Comparison of non-interactive range proof sizes (in KB). “Ideal w/o CRT” is a hypothetical scheme optimized for proof length. FFT denotes the maximum number of FFT levels supported. Our proof sizes can be slightly reduced at the cost of reducing the FFT levels. The full parameter setting details are given in the full version [13].

An alternative to this approach is to use “norm-optimal” challenges from [25] (named “optimal” in [25]) such that the infinity norm of a challenge is set to 1, and thus the overall Euclidean norm of a challenge is minimized. In this case, one needs to set the ring dimension $d\ge 256$ to get a challenge space size of at least $2^{256}$. However, this results in significantly longer proofs as shown in Table 3. The reason behind this phenomenon is that one needs to encode 64 values and with the “norm-optimal” challenges the cost of these encodings and the commitments grow too much. The use of challenges with larger (even much larger) norm does not seem to cause significant increase in the proof length, which can be explained as follows. To do a range proof on 64-bit range, the modulus q must be at least $2^{64}$. Using UMC, where the message part does not affect the hardness of finding binding collisions (in particular, M-SIS hardness), such a large q already makes M-SIS very hard and M-LWE very easy. Therefore, having a challenge with a large norm only brings the hardness level of M-SIS to that of M-LWE, and results in a very compact proof.

We also add for comparison a hypothetical idealized range proof scheme optimized for proof length in Table 3, where for this scheme we only check two conditions: (1) $q\ge N$ and (2) M-SIS and M-LWE root Hermite factors are less than or equal to 1.0045. More specifically, we go over all the values of the ring dimension $d\in \{8,16,\ldots ,1024\}$, $\log q\in \{\log N,\ldots ,100\}$ and initial noise distribution $\mathcal {U}(\{-\mathcal {B},\ldots ,\mathcal {B}\})$ for $\mathcal {B}\in \{1,2,3\}$, and set the remaining parameters so that the above security condition (2) is satisfied. Therefore, for the “ideal w/o CRT” scheme we do not check whether the soundness proof of the protocol works with the parameters set. Even with this advantage given, we see from Table 3 that our range proof, as expected, has approximately the same proof length as “ideal w/o CRT”, and also achieves a significant speedup as the ring dimension as well as the number of FFT levels supported is higher. One can see from [25, Table 2] that going from 2 levels of FFT to 6 levels of FFT alone results in a speedup of a factor more than 3.

When we allow the ring $R_q$ to split into more than 64 factors, then the 64 subrings in which the message bits are encoded will not be fields and the structure of $R_q$ in these subring is lost. We are currently unable to make the soundness proof of the binary proof go through in these subrings, whose structure is unclear. On the other hand, we can make the binary proof work both in $R_q$ using our new result (Lemma 7) and in any field. Thus, we allow $R_q$ to split into exactly $\log N$ fields for a range proof of width N, which also gives the invertibility of challenges and challenge differences at no cost. The reason why the scheme with “norm-optimal” challenges cannot split into more than $2^2 = 4$ factors is because the invertibility of polynomials with coefficients as large as $2^{16}$ is required when one relies solely on the results of [25].

“NTT-friendly” tools for fully-splitting rings. [25] studies in detail how cyclotomic rings split and the required invertibility conditions for short ring elements. A main motivation in [25] for the invertibility of short elements can be sketched as follows. In the hope of proving knowledge of a secret s (which is usually a message-randomness pair (m, r)) that satisfies a certain relation $g(s)=t$ for public homomorphic function g and public t, one-shot proofs can only convince the verifier of knowledge of $\bar{s}$ such that $g(\bar{s}) = \bar{x}t,$ where $\bar{x}=x-x'$ for some (distinct) challenges $x,x'$. If g is a commitment scheme and one later opens t to a valid $s'$ such that $g(s')=t$, then one can show that $s'=\bar{s}/\bar{x}$ using the binding property of the commitment scheme provided that $\bar{x}$ is invertible. In our protocols, however, the relaxed relation proves knowledge of a secret message m such that

$$\begin{aligned} g'(\bar{x} m) = \bar{x} t' \end{aligned}$$

where $g'$ and $t'$ are the parts dependent on the message (see Definitions 4 and 6). When one gets two relaxed openings $(\bar{x}_0,m_0)$ and $(\bar{x}_1,m_1)$, we have

$$\begin{aligned} \begin{aligned} g'(\bar{x}_0 m_0) = \bar{x}_0 t' \\ g'(\bar{x}_0 m_1) = \bar{x}_1 t' \end{aligned}&\implies&\begin{aligned} g'(\bar{x}_1\bar{x}_0 m_0) = \bar{x}_1\bar{x}_0 t' \\ g'(\bar{x}_0\bar{x}_1 m_1) = \bar{x}_0\bar{x}_1 t' \end{aligned}&\implies&\bar{x}_1\bar{x}_0 m_0 = \bar{x}_0\bar{x}_1 m_1, \end{aligned}$$

(3)

due to the binding property of the commitment scheme. On contrary to the invertibility requirement, if the norm of each term is small relative to q, which is often the case, we use our new result Lemma 7 to show that,

$$\begin{aligned} \bar{x}_0 \bar{x}_1 (m_0 - m_1) = 0 \text { in }\mathbb {Z}_q[X]/(X^d+1)&\implies&m_0 = m_1. \end{aligned}$$

(4)

That is, we can conclude the equality of two message openings even for non-invertible challenge differences. The lemma only requires q to be sufficiently large without putting any condition on its “shape”, and thus enables the use of an “NTT-friendly” modulus q.

Open Problems. Our CRT technique only allows us to gain an improvement in terms of computation. A very interesting result would be to also have an asymptotic/practical advantage in communication costs, which remains as an open problem. Another interesting question is whether one can make the binary proof work while having a fully-splitting $R_q$. This would allow us to exploit the full potential of our CRT technique in its application to range proofs.

Roadmap. Section 3 is devoted to the introduction of the one-shot proof technique for non-linear polynomial relations. Our CRT-packing technique and other new tools that enable faster proofs are detailed in Sect. 4, followed by an application to range proofs. We apply our one-shot proof techniques to build efficient ZKPs of useful relations such as one-out-of-many proofs in Sect. 5. Further applications to advanced cryptographic tools such as ring signatures and anonymous credentials are discussed under Sect. 6. Some formal definitions, further discussions and proofs of lemmas/theorems are given in the full version [13].

2 Preliminaries

In addition to the standard notations, for a vector of polynomials $\varvec{p}$, $\textsf {HW}(\varvec{p})$ denotes the Hamming weight of the coefficient vector of $\varvec{p}$, and $D_\sigma ^r$ denotes the discrete normal distribution with center zero and standard deviation $\sigma$ over $\mathbb {Z}^r$. The formal definition and the norm bounds of normal distribution, and relations between different norms are recalled in the full version. We summarize the rejection sampling [23], used to make prover’s responses independent of secret information, in Algorithm 1 and its full statement is given in the full version.

2.1 Vandermonde Matrices and Some Basics of Linear Algebra

We recall some basics about Vandermonde matrices and from Linear Algebra relevant to our discussions (see e.g. [17] for more details). We denote the n-dimensional identity matrix by $\varvec{I}_n$, and assume that the matrices are defined over a ring $\mathfrak {R}$. Let $\varvec{A}$ be a $n\times n$ square matrix and $\det (\varvec{A})$ denote its determinant. The adjugate $\text {adj}(\varvec{A})$ of $\varvec{A}$, defined as the transpose of the cofactor matrix of $\varvec{A}$, satisfies the following property

$$\begin{aligned} \text {adj}(\varvec{A}) \cdot \varvec{A} = \varvec{A}\cdot \text {adj}(\varvec{A}) = \det (\varvec{A})\cdot \varvec{I}_n. \end{aligned}$$

(5)

Therefore, if $\varvec{A}$ is non-singular, $\text {adj}(\varvec{A}) = \det (\varvec{A})\cdot \varvec{A}^{-1}$. A $(k+1)$-dimensional Vandermonde matrix $\varvec{V}$ is defined as below for some $x_0,\ldots ,x_k\in \mathfrak {R}$, with its determinant satisfying the following property

$$\begin{aligned} \varvec{V} = \left( \begin{array}{ccccc} 1 &{} x_{0} &{} x_{0}^2 &{} \cdots &{} x_{0}^k \\ 1 &{} x_{1} &{} x_{1}^2 &{} \cdots &{} x_{1}^k \\ : &{} : &{} : &{} : &{} : \\ 1 &{} x_{k} &{} x_{k}^2 &{} \cdots &{} x_{k}^k \end{array}\right) ,&\text {and}&\det (\varvec{V}) = \prod _{0\le i < j \le k} (x_j-x_i). \end{aligned}$$

(6)

The following is an easy consequence of (6).

Fact 1

The Vandermonde determinant $\det (\varvec{V})$ has $\left( {\begin{array}{c}k+1\\ 2\end{array}}\right)$ multiplicands of the form $x_j-x_i$ with $j\ne i$.

As given in [14], the Vandermonde matrix inverse $\varvec{V}^{-1}$, when it exists, has the following structure

$$\begin{aligned} \left( \begin{array}{cccc} \frac{*}{(x_0-x_1)(x_0-x_2)\cdots (x_0-x_k)} &{} \frac{*}{(x_0-x_1)(x_1-x_2)\cdots (x_1-x_k)} &{} \cdots &{} \frac{*}{(x_0-x_k)(x_1-x_k)\cdots (x_{k-1}-x_k)} \\ \frac{*}{(x_0-x_1)(x_0-x_2)\cdots (x_0-x_k)} &{} \frac{*}{(x_0-x_1)(x_1-x_2)\cdots (x_1-x_k)} &{} \cdots &{} \frac{*}{(x_0-x_k)(x_1-x_k)\cdots (x_{k-1}-x_k)} \\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ \frac{1}{(x_0-x_1)(x_0-x_2)\cdots (x_0-x_k)} &{} \frac{-1}{(x_0-x_1)(x_1-x_2)\cdots (x_1-x_k)} &{} \cdots &{} \frac{(-1)^k}{(x_0-x_k)(x_1-x_k)\cdots (x_{k-1}-x_k)} \end{array}\right) \!\!, \end{aligned}$$

(7)

where $*$ denotes some element in the ring $\mathfrak {R}$, computed as a function of $x_i$’s. It is clear from this structure that $\varvec{V}^{-1}$ exists over $\mathfrak {R}$ if and only if the differences $x_i-x_j$ for $0\le i<j\le k$ are invertible over $\mathfrak {R}$. The structure in (7) helps us to visualize the structure of $\text {adj}(\varvec{V})$ using the fact that $\text {adj}(\varvec{V}) = \det (\varvec{V})\cdot \varvec{V}^{-1}$ if $\varvec{V}$ is non-singular. In particular, we have the following fact.

Fact 2

Let $(\varGamma _0,\ldots ,\varGamma _k)$ be the last row of $\text {adj}(\varvec{V})$. Then,

$$ \varGamma _i = (-1)^{i+k}\prod _{0\le l < j \le k \, \wedge \, j,l\ne i} (x_j-x_l), $$

and $\varGamma _i$ has $\left[ \left( {\begin{array}{c}k+1\\ 2\end{array}}\right) -k\right] =\frac{k(k-1)}{2}$ multiplicands for all $0\le i\le k$.

Fact 2 follows by observing that k multiplicands in $\det (\varvec{V})$ are cancelled out by the corresponding denominator in $\varvec{V}^{-1}$.

2.2 Module-SIS and Module-LWE Problems

Our schemes’ security relies on the hardness of Module-SIS (M-SIS) (defined in “Hermite normal form” as in [3]) and Module-LWE (M-LWE) problems [19].

Definition 1

(M-SIS$_{n,m,q,\beta _{\text {SIS}}}$). Given $\varvec{A}{\,=\,}[\, \varvec{I}_n \, \Vert \, \varvec{A}' \, ]$ with $\varvec{A}'{\,\leftarrow \,} \mathcal {U}(R_q^{n\times (m-n)})$, the goal is to find $\varvec{z}\in R_q^m$ such that $\varvec{A}\varvec{z}=\varvec{0}\bmod q$ and $0<\left\| \varvec{z}\right\| \le \beta _{\text {SIS}}$.

Definition 2

(M-LWE$_{n,m,q,\chi }$). Let $\chi$ be a distribution over $R_q$ and $\varvec{s}\leftarrow \chi ^n$ be a secret key. Define $\mathtt {LWE}_{q,\varvec{s}}$ as the distribution obtained by sampling $\varvec{a}\leftarrow R_q^n$, $e\leftarrow \chi$ and outputting $(\varvec{a},\langle \varvec{a} , \varvec{s} \rangle +e)$. The goal is to distinguish between m given samples from either $\mathtt {LWE}_{q,\varvec{s}}$ or $\mathcal {U}(R_q^n,R_q)$.

The above definition is a standard variant of decision M-LWE problem where the secret is sampled from the error distribution. More discussion about the security aspects is given in the full version [13].

2.3 $\varSigma$-protocols

$\varSigma$-protocols are a type of interactive proof systems between a prover $\mathcal {P}$ and a verifier $\mathcal {V}$. It is 3-move as in Protocol 1. A protocol transcript is accepting if it is accepted by the verifier. $\varSigma$-protocols are defined for a relation , and for a $(v,w)\in \mathcal {R}$, the quantity w is said to be a witness for v. We use the generalized definition of $\varSigma$-protocols from [14] that extends the one in [5].

Definition 3

([14, Definition 4]). For relations with , $(\mathcal {P},\mathcal {V})$ is called a $\varSigma$-protocol for with completeness error $\alpha$, a challenge space $\mathcal {C}$, public-private inputs (v, w), if the following properties are satisfied.

• Completeness: An interaction between an honest prover and an honest verifier is accepted with probability at least $1-\alpha$ whenever .

• $(k+1)$-special soundness: There exists an efficient PPT extractor $\mathcal {E}$ that computes $w'$ satisfying given $(k+1)$ accepting protocol transcripts $(a,x_0,z_0),\ldots ,(a,x_k,z_k)$ with distinct $x_i$’s for $0\le i\le k$. We refer to this process as witness extraction.

• Special honest-verifier zero-knowledge (SHVZK): There exists an efficient PPT simulator $\mathcal {S}$ that outputs (a, z) given v in the language of and $x\in \mathcal {C}$ such that (a, x, z) is indistinguishable from an accepting transcript produced by a real run of the protocol.

As seen from above, the special soundness is relaxed in the sense the verifier is only convinced of the proof of knowledge of a witness for the relation $\mathcal {R}'$. This is usually referred to as the soundness gap. This relaxation is necessary for efficient algebraic proofs and such relaxed proofs are sufficient for our applications.

2.4 Commitment Schemes

We define the commitment schemes UMC (Unbounded-Message Commitment) [3, 6] and HMC (Hashed-Message Commitment) (see, e.g., [3, 14]). Both hiding and binding properties are computational (see the full version [13] for formal definitions of commitments, their properties and more discussion). Let $n,m,\mathcal {B},q$ be positive integers, and assume that we commit to v-dimensional vectors over $R_q$ for $v\ge 1$. As in [3, 6], the opening algorithm Open is relaxed in the sense that there is an additional input $y\in R_q$, called relaxation factor, to Open algorithm along with a message-randomness pair $(\varvec{m}',\varvec{r}')$ such that Open checks if $y\cdot C={\mathrm {Com}}_{ck}(\varvec{m}';\,\varvec{r}')$. The instantiation of HMC with $m>n$ is as follows.

• CKeygen$(1^\lambda )$: Pick $\varvec{G}'_r\leftarrow R_q^{n\times (m-n)}$ and $\varvec{G}_m\leftarrow R_q^{n\times v}$. Output $ck = \varvec{G} = [\, \varvec{G}_r \, \Vert \, \varvec{G}_m \, ]\in R_q^{n\times (m+v)}$ where $\varvec{G}_r = [\, \varvec{I}_n \, \Vert \, \varvec{G}'_r \, ]$. We assume that Commit and Open takes ck as an input implicitly.

• Commit$(\varvec{m})$: Pick $\varvec{r}\leftarrow \{-\mathcal {B},\ldots ,\mathcal {B}\}^{md}$. Output

  $$\begin{aligned} {\mathrm {Com}}_{ck}(\varvec{m};\,\varvec{r}) = \varvec{G}\cdot (\varvec{r},\varvec{m}) = \varvec{G}_r\cdot \varvec{r} + \varvec{G}_m\cdot \varvec{m}. \end{aligned}$$

• Open$(C,(y,\varvec{m}',\varvec{r}'))$: If ${\mathrm {Com}}_{ck}(\varvec{m}';\,\varvec{r}') = y C$ and $\left\| (\varvec{r}',\varvec{m}')\right\| \le \gamma _{\text {com}}$, return 1. Otherwise, return 0.

Lemma 1

If M-LWE$_{m-n,n,q,\mathcal {U}(\{-\mathcal {B},\ldots ,\mathcal {B}\}^d)}$ problem is hard, then HMC is computationally hiding. If M-SIS$_{n,m+v,q,2\gamma _{\text {com}}}$ is hard, then HMC is computationally strong $\gamma _{\text {com}}$-binding with respect to the same relaxation factor y.

The instantiation of UMC is also similar and defined as below for $m>n+v$.

• CKeygen$(1^\lambda )$: Pick $\varvec{G}'_1\leftarrow R_q^{n\times (m-n)}$ and $\varvec{G}'_2\leftarrow R_q^{v\times (m-n-v)}$. Set $\varvec{G}_1=[\, \varvec{I}_n \, \Vert \, \varvec{G}_1' \, ]$ and $\varvec{G}_2=[\, \varvec{0}^{v\times n} || \varvec{I}_v \, \Vert \, \varvec{G}_2' \, ]$. Output $ck = \varvec{G} = \left[ \begin{array}{c} \varvec{G}_1 \\ \varvec{G}_2 \\ \end{array}\right] \in R_q^{(n+v)\times m}$. We assume that Commit and Open takes ck as an input implicitly.

• Commit$(\varvec{m})$: Pick $\varvec{r}\leftarrow \{-\mathcal {B},\ldots ,\mathcal {B}\}^{md}$. Output

  $$\begin{aligned} {\mathrm {Com}}_{ck}(\varvec{m};\,\varvec{r}) = \varvec{G}\cdot \varvec{r} + (\varvec{0}^n,\varvec{m}). \end{aligned}$$

• Open$(C,(y,\varvec{m}',\varvec{r}'))$: If ${\mathrm {Com}}_{ck}(\varvec{m}';\,\varvec{r}') = y C$ and $\left\| \varvec{r}'\right\| \le \gamma _{\text {com}}$, return 1. Otherwise, return 0.

Observe from the above definition that only the norm of $\varvec{r}'$ is checked in the Open algorithm of UMC whereas that of $(\varvec{m}',\varvec{r}')$ is checked in HMC. Also, our definition of Open for UMC is slightly different than that in [3] because we do not multiply the relaxation factor with the message as the invertibility of the relaxation factor is not guaranteed in our case.

Lemma 2

([3]). If M-LWE$_{m-n-v,n+v,q,\mathcal {U}(\{-\mathcal {B},\ldots ,\mathcal {B}\}^d)}$ problem is hard, then UMC is computationally hiding. If M-SIS$_{n,m,q,2\gamma _{\text {com}}}$ is hard, then UMC is computationally $\gamma _{\text {com}}$-binding with respect to the same relaxation factor y.

We use the same notation for both of the commitment schemes and will clarify in the relevant sections which specific instantiation is used. We say that $(y,\varvec{m}',\varvec{r}')$ is a valid opening of C if Open$(C,(y,\varvec{m}',\varvec{r}'))=1$. A valid opening $(y,\varvec{m}',\varvec{r}')$ with $y=1$ is called an exact valid opening. We call the message part $\varvec{m}'$ of an opening as message opening, and if $(y,\varvec{m}',\varvec{r}')$ is a valid opening such that $yC = {\mathrm {Com}}_{ck}(y\varvec{m}';\,\varvec{r}')$, then we call $\varvec{m}'$ a relaxed message opening with relaxation factor y. It is also straightforward that both UMC and HMC satisfy the following homomorphic properties: ${\mathrm {Com}}_{ck}(\varvec{m}_0;\,\varvec{r}_0)+{\mathrm {Com}}_{ck}(\varvec{m}_1;\,\varvec{r}_1) = {\mathrm {Com}}_{ck}(\varvec{m}_0+\varvec{m}_1;\,\varvec{r}_0+\varvec{r}_1)$ and $c\cdot {\mathrm {Com}}_{ck}(\varvec{m};\,\varvec{r})={\mathrm {Com}}_{ck}(c\cdot \varvec{m};\,c\cdot \varvec{r})$ for $c\in R_q$.

3 One-Shot Proofs for Non-Linear Polynomial Relations

In this section, we focus on lattice-based zero-knowledge proofs in a general framework using homomorphic commitments, and introduce our techniques to get efficient proofs. Even though such a setting is also mostly shared with DL-based $\varSigma$-protocols using homomorphic commitments, the main challenges described here are not encountered in those cases. Since our main concern is about the soundness of the protocol, in this section, we omit the discussion about the zero-knowledge property, which is later obtained using a standard rejection sampling technique. We always consider homomorphic commitments when referring to “commitment” and assume that all the elements are in a ring $\mathfrak {R}$.

3.1 The Case for Linear Relations (2-Special Soundness)

If we investigate the (underlying) one-shot $\varSigma$-protocols from [3, 6, 22, 23], we see the following. The common input of the protocol is a commitment $C_1$ to the prover’s witness and the prover sends an initial commitment $C_0$.⁷ Then, the verifier sends a random challenge $x\leftarrow \mathcal {C}$, which is responded by the prover as $(\varvec{f},\varvec{z})$, and $(\varvec{f},\varvec{z})$ is used by the verifier as a message-randomness pair for a commitment computation.⁸ More precisely, the verification checks if $C_0 + xC_1 = {\mathrm {Com}}_{ck}(\varvec{f};\,\varvec{z})$ holds and $\varvec{f},\varvec{z}$ have small norm. This is equivalent to the structure represented in Protocol 1 for $k=1$. From here, when the extractor gets two valid protocol transcripts $(C_0,x_0,\varvec{f}_0,\varvec{z}_0),(C_0,x_1,\varvec{f}_1,\varvec{z}_1)$ using the same initial message $C_0$, and different challenges $x_0$ and $x_1$, the extractor obtains

$$\begin{aligned} \begin{aligned} C_0 + x_0C_1 = {\mathrm {Com}}_{ck}(\varvec{f}_0;\,\varvec{z}_0) \\ C_0 + x_1C_1 = {\mathrm {Com}}_{ck}(\varvec{f}_1;\,\varvec{z}_1) \end{aligned} \implies \!(x_1-x_0)C_1 = {\mathrm {Com}}_{ck}(\varvec{f}_1\!-\!\varvec{f}_0;\,\varvec{z}_1\!-\!\varvec{z}_0). \end{aligned}$$

(8)

At this stage, it is not possible to obtain a valid exact opening of $C_1$ unless $(x_1-x_0)^{-1}$ is guaranteed to be short due to the shortness requirements of valid openings for lattice-based commitment schemes.⁹ Unless ensured by design, there is no particular reason why the inverse term $(x_1-x_0)^{-1}$ would be short. In the current state of affairs, the largest set of challenges with short challenge difference inverses is monomial challenges [5] used with ring variants of lattice assumptions. Here, only $2(x_1-x_0)^{-1}$ is guaranteed to be short and thus the extractor can only get the openings of $2C_1$. As discussed previously, for a ring dimension of d, the cardinality of the monomial challenge space is only 2d, which is typically smaller than $2^{12}$ in practice. This small challenge space problem causes major efficiency drawbacks in terms of both computation and communication as the protocol is required to be repeated many times to get a negligible soundness error (that is, the same computation and communication steps are repeated multiple times, resulting in a multi-fold increase in both computation and communication). The situation is even worse in terms of the number of repetitions when binary challenges or Stern’s framework [29] is used where the protocol is required to be repeated at least $\lambda$ times for $\lambda$-bit security.

The idea for a one-shot proof is to make use of (8) without any inverse computation by observing that $(\varvec{f}_1-\varvec{f}_0,\varvec{z}_1-\varvec{z}_0)$ is a valid opening of $(x_1-x_0)C_1$ as long as $\varvec{f}_1-\varvec{f}_0$ and $\varvec{z}_1-\varvec{z}_0$ are short, which is ensured by norm checks on $\varvec{f},\varvec{z}$ in each verification. If one can prove that having this relaxed case is sufficient and also violates the binding property of the commitment (i.e., that it allows one to solve a computationally hard problem), then the soundness of the protocol is achieved (with a relaxed relation as in Definition 3) with no challenge difference inverses involved. This eliminates the need for challenge differences to have short inverses and enables one to use exponentially large challenge spaces, resulting in one-shot proofs. The main technical difficulty here is handling soundness gap, where the extractor only obtains an exact opening of $(x_1-x_0)C_1$ (rather than $C_1$, which is the commitment to the prover’s witness).

3.2 Generalization to Degree $k>1$ ($(k+1)$-Special Soundness)

As can be seen from (8), the 2-special sound case is quite restrictive as it only allows witness extraction from linear (first degree) relations. On the other hand, the ability to work with non-linear relations is a must in recent efficient proofs [7,8,9, 16], which renders the existing lattice-based one-shot techniques inapplicable. Therefore, we generalize our setting, and suppose that we have a degree-k polynomial relation ($(k+1)$-special sound $\varSigma$-protocol), $k\ge 1$, with the structure given in Protocol 1. Note that since the extractor only knows that verification steps hold, unaware of how any component is generated, other steps but those in the verification is not important. Therefore, we write all the $C_i$’s as a common input whereas in the actual protocol a subset of them can be generated during a protocol run. The commitment to the prover’s witness $(\varvec{m}_k,\varvec{r}_k)$ is $C_k$.

The witness extraction, in this case, works by the extractor obtaining $k+1$ accepting protocol transcripts for distinct challenges $x_0,\ldots ,x_k$ with the same input $(C_0,\ldots ,C_k)$, and responses $(\varvec{f}_0,\varvec{z}_0),\ldots ,(\varvec{f}_k,\varvec{z}_k)$, represented as below.

$$\begin{aligned} \left( \begin{array}{ccccc} 1 &{} x_{0} &{} x_{0}^2 &{} \cdots &{} x_{0}^k \\ 1 &{} x_{1} &{} x_{1}^2 &{} \cdots &{} x_{1}^k \\ : &{} : &{} : &{} : &{} : \\ 1 &{} x_{k} &{} x_{k}^2 &{} \cdots &{} x_{k}^k \end{array}\right) \cdot \left( \begin{array}{c} C_0 \\ C_1 \\ : \\ C_k \end{array}\right) = \left( \begin{array}{c} {\mathrm {Com}}_{ck}(\varvec{f}_0;\,\varvec{z}_0) \\ {\mathrm {Com}}_{ck}(\varvec{f}_1;\,\varvec{z}_1) \\ : \\ {\mathrm {Com}}_{ck}(\varvec{f}_k;\,\varvec{z}_k) \end{array}\right) . \end{aligned}$$

(9)

We have seen that using the aforementioned relaxed opening approach, one can extract a witness from a linear relation (8) in one shot. Now a natural generalization is to ask “Can we extract a witness from a non-linear relation (9) as in Protocol 1 in one shot?”

Naive approach and previous multi-shot approach. Denoting (9) as $\varvec{V}\cdot \varvec{c} = \varvec{b}$, the matrix $\varvec{V}$ is a Vandermonde matrix. A straightforward idea to obtain the openings of $C_i$’s is to multiply both sides of (9) by $\varvec{V}^{-1}$, which gives $\varvec{c}=\varvec{V}^{-1}\cdot \varvec{b}$. From here, using the homomorphic properties of the commitment scheme, we can get potential “openings” of $C_i$’s. However, one needs to make sure that $\varvec{V}^{-1}$ exists over $\mathfrak {R}$ and that it has short entries so that these “openings” are valid. The way [14] deals with this issue is by making use of monomial challenges from [5]. Using the structure of $\varvec{V}^{-1}$ in (7), it is argued in [14] that the entries in $2^k\varvec{V}^{-1}$ are short by the fact that doubled inverse of challenge differences (i.e., $2(x_j-x_i)^{-1}$) are short when monomial challenges are used. Thus, this approach still maintains the drawback of requiring multiple protocol repetitions to achieve a negligible soundness error, and does not address our question.

Our one-shot solution. Now, let us see how we develop a one-shot proof technique for non-linear relations. Using (5), we multiply both sides of (9) by $\text {adj}(\varvec{V})$, and obtain

$$\begin{aligned} \text {adj}(\varvec{V})\cdot \varvec{V}\cdot \varvec{c} = \text {adj}(\varvec{V})\cdot \varvec{b} \quad \implies \quad \det (\varvec{V})\cdot \varvec{c} = \text {adj}(\varvec{V})\cdot \varvec{b}. \end{aligned}$$

(10)

Note that $\det (\varvec{V})$ is just some scalar in $\mathfrak {R}$, and we obtain potential relaxed “openings” of $C_i$’s as a result of the multiplication $\text {adj}(\varvec{V})\cdot \varvec{b}$. In particular, for the commitment $C_k$ of the witness, we have

$$\begin{aligned} \det (\varvec{V}) \cdot C_k = \sum _{i=0}^{k} \varGamma _i\cdot {\mathrm {Com}}_{ck}(\varvec{f}_i;\,\varvec{z}_i) = {\mathrm {Com}}_{ck}(\sum _{i=0}^{k}\varGamma _i\cdot \varvec{f}_i;\,\sum _{i=0}^{k}\varGamma _i\cdot \varvec{z}_i), \end{aligned}$$

(11)

where $\varGamma _i = (-1)^{i+k}\prod _{0\le l < j \le k \wedge j,l\ne i} (x_j-x_l)$ by Fact 2. As a result, we get a relaxed opening of $C_k$, or more precisely, an exact opening of $\det (\varvec{V}) \cdot C_k$ as $(\varvec{\hat{m}}_k,\varvec{\hat{r}}_k)=\left( \sum _{i=0}^{k} \varGamma _i\varvec{f}_i, \sum _{i=0}^{k} \varGamma _i\varvec{z}_i\right)$. Provided that the norms of $\varvec{\hat{m}}_k$ and $\varvec{\hat{r}}_k$ are small, this gives a valid opening and thus can be related to a hard lattice problem (M-SIS, in particular). It is important to observe here that $\varvec{\hat{m}}_k$ and $\varvec{\hat{r}}_k$ do not involve any inverse term and can be guaranteed to be short by ensuring that $\varGamma _i$’s are short. The opening of other $C_i$’s can also be recovered in a similar fashion, but the case for $C_k$ is sufficient for our applications.

When $k=1$, i.e., when the protocol is 2-special sound, $\det (\varvec{V})=(x_1-x_0)$ and $(\varGamma _0,\varGamma _1)=(-1,1)$. Therefore, we exactly obtain (8) as a special case of (11) with $k=1$. That is, we get the results of the previous approaches from [3, 6, 22, 23] as a special case of ours.

3.3 New Tools for Compact Proofs

Let us analyze our generalized solution and introduce our new tools to get compact proofs. The results can be easily used in other protocols that use a challenge space of the form defined in (12) as they are independent of the low-level details of a protocol. Since the most commonly used challenge spaces (e.g., in [3, 4, 11, 24, 25]) for one-shot proofs are special cases of (12), our results are widely applicable. Let $\mathfrak {R}=R=\mathbb {Z}[X]/(X^d+1)$ and $R_q = \mathbb {Z}_q[X]/(X^d+1)$ for $q\in \mathbb {Z}^+$. For $w\le d$ and $p\le q/2$, let $\mathcal {C}_{w,p}^{d}$ be the challenge space defined as

$$\begin{aligned} \mathcal {C}_{w,p}^d = \{ \, x \in \mathbb {Z}[X] \, : \, \deg (x) \le d-1 \, \wedge \, \textsf {HW}(x) = w \, \wedge \, \Vert x\Vert _{_\infty }=p \, \}. \end{aligned}$$

(12)

It is easy to observe that $\Vert x\Vert _{_1}\le pw$ for any $x\in \mathcal {C}_{w,p}^d$ and $|\mathcal {C}_{w,p}^d|= \left( {\begin{array}{c}d\\ w\end{array}}\right) \cdot (2p)^w$, which is, for example, larger than $2^{256}$ for $(d,w,p)=(256,60,1)$. We define $\varDelta \mathcal {C}_{w,p}^{d}$ to be the set of challenge differences excluding zero.

Bound on the product of challenge differences.

Lemma 3

For any $y_1,\ldots ,y_n\in \varDelta \mathcal {C}_{w,p}^d$, the following holds

$$\begin{aligned} \Vert \prod _{i=1}^{n} y_i\Vert _{_\infty } \le (2p)^n\cdot w^{n-1}, \quad \text {and} \quad \Vert \prod _{i=1}^{n} y_i\Vert \le \sqrt{d}\cdot (2p)^n\cdot w^{n-1}. \end{aligned}$$

Bound on the relaxation factor: $\det (\varvec{V})$.

Lemma 4

Let $\kappa = \left( {\begin{array}{c}k+1\\ 2\end{array}}\right) = \frac{k(k+1)}{2}$. For the $(k+1)$-dimensional Vandermonde matrix $\varvec{V}$ defined in (9) using the challenge space $\mathcal {C}_{w,p}^d$ in (12),

$$\Vert \det (\varvec{V})\Vert _{_\infty }\le (2p)^\kappa \cdot w^{\kappa -1}.$$

Proof

By Fact 1, $\det (\varvec{V})$ has $\kappa = \left( {\begin{array}{c}k+1\\ 2\end{array}}\right)$ multiplicands where each multiplicand is in $\varDelta \mathcal {C}_{w,p}^d$. The result follows from Lemma 3.    $\square$

Bound on the extracted witness norm: $\text {adj}(\varvec{V})\times ($openings of $\varvec{b})$.

Lemma 5

For $k\ge 1$ and $(\varvec{\hat{m}}_k,\varvec{\hat{r}}_k)=\left( \sum _{i=0}^{k} \varGamma _i\varvec{f}_i, \sum _{i=0}^{k} \varGamma _i\varvec{z}_i\right)$ where $\varGamma _i = \prod _{0\le l < j \le k \wedge j,l\ne i} (x_j-x_l)$, the following holds, for $\kappa '={k(k-1)}/{2}$,

• $\left\| \varvec{\hat{m}}_k\right\| \le (k+1)\cdot d\cdot (2p)^{\kappa '}\cdot w^{\kappa '-1}\cdot \max _i\left\| \varvec{f}_i\right\|$, and

• $\left\| \varvec{\hat{r}}_k\right\| \le (k+1)\cdot d\cdot (2p)^{\kappa '}\cdot w^{\kappa '-1}\cdot \max _i\left\| \varvec{z}_i\right\|$.

The proofs of Lemmas 3 and 5 are provided in the full version [13].

Reducing extracted witness norm in proofs with non-linear relations. In some proofs with non-linear polynomial relations such as our one-out-of-many proof, the extractor obtains an opening with a relaxation factor y of some component that is witness of a sub-protocol. Since the invertibility of y is not ensured, when this opening is used in the non-linear polynomial relation, the relaxation factor also gets exponentiated by the degree $k>1$. In the end, instead of getting $\det (\varvec{V})$ as the overall relaxation factor, we end up with relaxation factor $y^k\cdot \det (\varvec{V})$. We use the lemma below to show that even though we cannot completely eliminate the extra term $y^k$, we can eliminate its exponent k. This results in obtaining an extracted witness with a smaller norm, and in turn, helps in getting shorter proofs. The proof of Lemma 6 is given in the full version.

Lemma 6

Let $f,g\in R = \mathbb {Z}[X]/(X^d+1)$. If $f\cdot g^k = 0$ in $R_q=\mathbb {Z}_q[X]/(X^d+1)$ for some $k\in \mathbb {Z}^+$, then $f\cdot g = 0$ in $R_q$.

4 New Techniques for Faster Lattice-Based Proofs

In this section, we go into the details of our new techniques to get computation-efficient proofs. We first show a lemma that enables one to prove that if a product of polynomials is equal to zero in $R_q$ and the norm of each factor is sufficiently small, then there must be a factor which is exactly equal to zero. This result works for any sufficiently large q, enabling the use of a modulus suitable for fast computation such as an “NTT-friendly” modulus.

Lemma 7

Let $f_1,\ldots ,f_n\in R$ for some $n\ge 1$. If $\prod _{i=1}^{n}f_i = 0$ in $R_q$ and $q/2 > \Vert f_1\Vert _{_\infty }\cdot \prod _{i=2}^{n}\Vert f_i\Vert _{_1}$, then there exists $1\le j \le n$ such that $f_j = 0$.

Proof

(Lemma 7). Using standard norm relations in R and the assumption on q, we have

$$\begin{aligned} \Vert \prod _{i=1}^{s}f_i\Vert _{_\infty } \le \Vert f_1\Vert _{_\infty }\cdot \prod _{i=2}^{n}\Vert f_i\Vert _{_1} < q/2. \end{aligned}$$

Therefore, $\prod _{i=1}^{n}f_i = 0$ holds over R. Since $X^d+1$ is irreducible over $\mathbb {Q}$, (at least) one of the multiplicand $f_i$’s must be zero.    $\square$

Note that Lemma 7 requires all the multiplicands to have bounded norm whereas there is no such requirement in Lemma 6. Therefore, we are unable to use Lemma 7 for the purpose of the use of Lemma 6 described previously as there is no norm-bound on a multiplicand in the place Lemma 6 is used (see how these lemmas are used in the soundness proofs for more details). Lemma 7 is used in the binary proof to argue that $y_0y_1y_2\hat{b}(y-\hat{b}) =0$ in $R_q$ for some (non-zero) challenge differences $y,y_0,y_1,y_2$ implies $\hat{b}=yb$ for a bit $b\in \{0,1\}$ without requiring invertibility of any challenge difference (see Sect. 5.1).

4.1 Supporting Inter-slot Operations on CRT-packed Messages

Now, we can go into the details of our CRT packing technique. Define $f=\text {Enc}_x(m) = x\cdot m + \rho \in R_q$ as an encoding of a message m under a challenge x. This encoding is widely used in proofs of knowledge as a “masked” response to a challenge x. An important advantage of this encoding over a commitment is that the storage cost of an encoding is at most $d\log q$ whereas that of a commitment is $nd\log q$ for HMC and $(n+v)d\log q$ for UMC. Therefore, for a typical module rank of, say, 4, a commitment is $4\times$ more costly than an encoding.

There are known methods to choose a modulus q such that $X^d+1$ splits into s factors, in which case, $R_q$ splits into s fields and we get $R_q = R_q^{(0)}\times \cdots \times R_q^{(s-1)}$. In the case that $X^d+1$ splits into more than s factors, but we only want to use s slots, we still have $R_q = R_q^{(0)}\times \cdots \times R_q^{(s-1)}$ where $R_q^{(i)}=\mathbb {Z}_q[X]/(P^{(i)}(X))$ for some polynomial $P^{(i)}(X)$ of degree ${\textit{d}/s}$. However, $R_q^{(i)}$’s are not a field in that case as $P^{(i)}(X)$’s are not irreducible over $\mathbb {Z}_q$.

As discussed previously, when we use these s slots to pack s messages in a single ring element, we have

$$\begin{aligned} f=\text {Enc}_x(m) = x\cdot m + \rho = \langle x_0m_0 + \rho _0, \ldots , x_{s-1}m_{s-1} + \rho _{s-1} \rangle , \end{aligned}$$

(13)

where $x=\langle x_0,\ldots ,x_{s-1} \rangle$, $m=\langle m_0,\ldots ,m_{s-1} \rangle$ and $\rho =\langle \rho _0,\ldots ,\rho _{s-1} \rangle$ in the CRT-packed representation. In this case, parallel additions are easy as

$$ \text {Enc}_x(\langle m_0,\ldots ,m_{s-1} \rangle ) + \text {Enc}_x(\langle m'_0,\ldots ,m'_{s-1} \rangle ) = \text {Enc}_x(\langle m_0+m'_0,\ldots ,m_{s-1}+m'_{s-1} \rangle ).$$

Parallel multiplication is also possible as $\text {Enc}_x(m)\cdot \text {Enc}_x(m') = m\cdot m'\cdot x^2 + c_1 x + c_0$ for $c_0,c_1$ only dependent on $m,m',\rho ,\rho '$, all of which are known to the prover in advance of his first move. Therefore, the prover can prove that the coefficient of $x^2$ is the product of m and $m'$, and thus proving the relation in parallel for all CRT slots.¹⁰ Addition and multiplication alone, however, do not provide a complete set of operations (see [15] for a discussion in the context of FHE). Given an encoding of m, our main requirement is to have the ability to extract all encodings in the CRT slots of m in a way that allows further operations among extracted encodings. That is, all extracted encodings must be under the same challenge x, which translates to requiring $x=\langle x,\ldots ,x \rangle$ for $x\in \bigcap _{i=0}^{s-1} R_q^{(i)}$. As a result, when we use s slots, the degree of a challenge can be at most ${\textit{d}/s}-1$. With this, from an encoding $f=\text {Enc}_x(\langle m_0,\ldots ,m_{s-1} \rangle )$, anyone can extract encodings by computing

$$\begin{aligned} f_i=\text {Enc}_x(m_i)= f\bmod (q,P^{(i)}(X))=x\cdot m_i + \rho _i = \text {Enc}_{x}(m_i) \end{aligned}$$

for all $0\le i \le s-1$. Conversely, given encoding $\text {Enc}_x(m_i)$’s for all $0\le i \le s-1$, anyone can compute an encoding $\text {Enc}_x(\langle m_0,\ldots ,m_{s-1} \rangle )$.

Even more, with this choice of the challenge $x=\langle x,\ldots ,x \rangle$ for $x\in \bigcap _{i=0}^{s-1} R_q^{(i)}$, we get invariance of the challenge under any permutation $\sigma$ on CRT slots. That is, for any permutation $\sigma$, we have $\sigma (\text {Enc}_x(m)) = \text {Enc}_{x}(\sigma (m)).$ From here, one can perform any inter-slot operation, and may even not require packing/unpacking of the messages in some applications. In our application to the range proof, extraction of the slots is sufficient and we refer to [15] for more on permutations. In our approach, an encoding and a commitment per message slot costs, respectively, at most $d\log q/s$ bits and $(n+v)\log q/s$ bits, which are much cheaper than a commitment to a single message.

4.2 Using CRT-packed Inter-slot Operations in Relaxed Range Proof

In this section, we introduce the first application of our ideas to $\varSigma$-protocols where the proof is relaxed as described in Sect. 2.3. In all of our protocols, the prover aborts if any rejection sampling step (Algorithm 1) returns 0, and our protocols are honest-verifier zero-knowledge for non-aborting interactions. For most of the practical applications, the protocol is made non-interactive, and thus having only non-aborting protocols with the zero-knowledge property does not cause an issue. Nevertheless, the protocols can be easily adapted to be zero-knowledge for the aborting cases using a standard technique from [5].

Our first application is a range proof that allows an efficient aggregation in the sense that the prover can prove that a set of committed values packed in a single commitment falls within a set of certain ranges. Let $\psi \in \mathbb {Z}^+$, $\ell ^{(i)}\in [0,N_i)$ be prover’s values for $1\le i \le \psi$ and $N_i = 2^{k_i}$ with $k=k_1+\cdots +k_\psi$, and s be the smallest power of two such that $s\ge \max \{k_1,\ldots ,k_{\psi }\}$. For simplicity, we use base $\beta =2$, but the result can be generalized to other base values $\beta$. Binary case gives the the most compact proofs in practice. Assume that $R_q = \mathbb {Z}_q[X]/(X^d+1)$ splits into exactly s fields such that $R_q = R_q^{(0)}\times \cdots \times R_q^{(s-1)}$ and $R_q^{(i)}=\mathbb {Z}_q[X]/(P^{(i)}(X))$ for some irreducible polynomial $P^{(i)}(X)$ of degree ${\textit{d}/s}$ for all $0\le i< s$. Write $\ell ^{(i)} = (b_{0}^{(i)},\ldots ,b_{k_i-1}^{(i)})$ in the binary representation and define $\ell _{\text {crti}}^{(i)} = \langle b_{0}^{(i)},\ldots ,b_{k_i-1}^{(i)} \rangle$. The exact relations proved by our “simultaneous” range proof is given in Definition 4. We show in the full version of the manuscript [13] that the relaxed range proof is sufficient for an application in anonymous credentials. Such a “simultaneous” range proof is useful when showing a credential that a set of attributes such as age, expiry date, residential postcode etc. fall into some respective ranges, and this can be achieved with a single commitment and a single proof using our techniques.

Definition 4

The following defines the relations for Protocol 2 for $\mathcal {T},\mathcal {\hat{T}}\in \mathbb {R}^+$.

$$\begin{aligned} \mathcal {R}_\text {range}(\mathcal {T})&= \left\{ \begin{array}{c} ((ck,V),(\ell ^{(1)},\ldots ,\ell ^{(\psi )},\varvec{r})) \;:\; \left\| \varvec{r}\right\| \le \mathcal {T} \; \wedge \; \\ V={\mathrm {Com}}_{ck}(\ell ^{(1)},\ldots ,\ell ^{(\psi )};\,\varvec{r}) \; \wedge \; \ell ^{(i)}\in [0,N_i) \; \forall 1\le i\le \psi \end{array}\right\} , \\ \mathcal {R}_\text {range}'(\mathcal {\hat{T}})&= \left\{ \begin{array}{c} ((ck,V),(\bar{x},{\ell }^{(1)},\ldots ,{\ell }^{(\psi )},\varvec{\hat{r}})) \;:\; \left\| \varvec{\hat{r}}\right\| \le \mathcal {\hat{T}} \; \wedge \; \bar{x}\in \varDelta \mathcal {C}_{w,p}^{d/s} \;\wedge \\ \!\!\bar{x} V\!=\!{\mathrm {Com}}_{ck}(\bar{x}{\ell }^{(1)}\!,\ldots ,\bar{x}{\ell }^{(\psi )};\,\varvec{\hat{r}}) \wedge \ell ^{(i)}\in [0,N_i) \; \forall 1\le i\le \psi \end{array}\right\} \!. \end{aligned}$$

The full description of the range proof is given in Protocol 2 where the commitment scheme is instantiated with UMC and $\phi _1,\phi _2$ are parameters determining the rejection sampling rate. The first part of the proof (Steps 4 and 5 in the verification, and its relevant components) uses the binary proof idea from [7, 14] to show that $f_j^{(i)}$’s are encodings of bits, but the proof is done in parallel CRT slots. Observe in Protocol 2 that $f^{(i)} = x\cdot \langle b_{0}^{(i)},\ldots ,b_{k_i-1}^{(i)},\varvec{0}^{s-k_i} \rangle + \langle a_{0}^{(i)},\ldots ,a_{k_i-1}^{(i)},\varvec{0}^{s-k_i} \rangle = x\cdot \ell _{\text {crti}}^{(i)} + a_{\text {crti}}^{(i)}$ where $\varvec{0}^{s-k_i}$ denotes a zero vector of dimension $s-k_i$. Therefore, we have, for each $1\le i \le \psi$,

$$\begin{aligned} f^{(i)}(x-f^{(i)}) = x^2\cdot \ell _{\text {crti}}^{(i)}(1-\ell _{\text {crti}}^{(i)}) + x\cdot a_{\text {crti}}^{(i)}(1-2\ell _{\text {crti}}^{(i)}) - (a_{\text {crti}}^{(i)})^2 \end{aligned}$$

Since there is no $x^2$ term (i.e., the coefficient of $x^2$ is zero) on the left hand side of Step 5 in the verification, we get $\ell _{\text {crti}}^{(i)}(1-\ell _{\text {crti}}^{(i)}) = 0$ when Step 5 is satisfied for 3 distinct challenges x. This gives us

$$\begin{aligned} \langle b_{0}^{(i)}(1-b_{0}^{(i)}),\ldots ,b_{k_i-1}^{(i)}(1-b_{k_i-1}^{(i)}),\varvec{0}^{s-k_i} \rangle = 0 \implies b_{j}^{(i)}(1-b_{j}^{(i)}) = 0 \text { in }R_q^{(j)} \end{aligned}$$

(14)

for each $0\le j < s-k_i$. This fact is then used to prove that $b_{j}^{(i)}$’s are binary. However, since the proof is relaxed, we need to deal with more complicated issues and give the full details in the proofs of Theorem 1.

The second part of the proof is a standard argument to show that the bits $b_{0}^{(i)},\ldots ,b_{k_i-1}^{(i)}$ construct a value $\ell ^{(i)}$ for each $1\le i\le \psi$. We assumed $N_i$’s are of the form $N_i=2^{k_i}$ for $k_i\ge 1$. This can be extended to work for any range as described in the full version [13], where we also discuss about the practical aspects of the range proof. The following states the properties of Protocol 2.

Theorem 1

Let $\gamma _{\text {range}} = 4\sqrt{3}\phi _2 pw\mathcal {B}md$. Assume $q> \max \{N_1,\ldots ,N_\psi \}$, $d\ge 128$,¹¹ $R_q$ splits into exactly s fields and UMC is hiding and $\gamma _{\text {range}}$-binding. Then, Protocol 2 is a 3-special sound $\varSigma$-protocol (as in Definition 3) for the relations $\mathcal {R}_\text {range}(\mathcal {B}\sqrt{md})$ and $\mathcal {R}_\text {range}'(\gamma _{\text {range}})$ with a completeness error $1-1/(\mu (\phi _1)\mu (\phi _2))$ for $\mu (\phi _i)=e^{12/\phi _i+1/(2\phi _i^2)}$, $i=1,2$.

Proof

(Theorem 1). Completeness and SHVZK proofs are in the full version.

3-special soundness: Given 3 accepting protocol transcripts, we have $(A,B,C,D,E,x,\varvec{f}_{\text {crt}},\varvec{z}_b,\varvec{z}_c,\varvec{z}),$ $(A,B,C,D,E,x',\varvec{f}_{\text {crt}}',\varvec{z}_b',\varvec{z}_c',\varvec{z}'),$ $(A,B,C,D,E,x'',\varvec{f}_{\text {crt}}'',\varvec{z}_b'',\varvec{z}_c'',\varvec{z}''),$ with $\varvec{f}=(f^{(1)},\ldots ,f^{(\psi )})$, $\varvec{f}'=(f'^{(1)},\ldots ,f'^{(\psi )})$ and $\varvec{f}''=(f''^{(1)},\ldots ,f''^{(\psi )})$ computed as in the verification. We split the proof into two parts: binary proof and range proof.

Binary proof. By Step 4 in the verification, we have

$$\begin{aligned} xB + A&= {\mathrm {Com}}_{ck}(\varvec{f};\,\varvec{z}_b) , \end{aligned}$$

(15)

$$\begin{aligned} x'B + A&= {\mathrm {Com}}_{ck}(\varvec{f}';\,\varvec{z}_b') , \end{aligned}$$

(16)

$$\begin{aligned} x''B + A&= {\mathrm {Com}}_{ck}(\varvec{f}'';\,\varvec{z}_b'') . \end{aligned}$$

(17)

Subtracting (16) from (15), we get $(x-x')\cdot B = {\mathrm {Com}}_{ck}(\varvec{f}-\varvec{f}';\,\varvec{z}_b-\varvec{z}_b')$. Thus, for $y:=x-x'$, we get exact valid openings of yB such that

$$\begin{aligned} yB = {\mathrm {Com}}_{ck}(\varvec{f}-\varvec{f}';\,\varvec{z}_b-\varvec{z}_b') = : {\mathrm {Com}}_{ck}(\varvec{\hat{b}};\,\varvec{\hat{r}}_b). \end{aligned}$$

(18)

Note that $\left\| \varvec{\hat{r}}_b\right\| = \left\| \varvec{z}_b-\varvec{z}_b'\right\| \le 4\sqrt{3}\phi _2pw\mathcal {B}md = \gamma _{\text {range}}$, proving the claimed bound for $\mathcal {R}_\text {range}'$. Multiplying (15) by y and using (18) gives

$$\begin{aligned} \begin{aligned} yA&= {\mathrm {Com}}_{ck}(y\varvec{f};\,y\varvec{z}_b) - xyB = {\mathrm {Com}}_{ck}(y\varvec{f}-x\varvec{\hat{b}};\,y\varvec{z}_b-x\varvec{\hat{r}}_b) \\&= {\mathrm {Com}}_{ck}(x\varvec{f}'-x'\varvec{f};\,x\varvec{z}_b'-x'\varvec{z}_b) =: {\mathrm {Com}}_{ck}(\varvec{\hat{a}};\,\varvec{\hat{r}}_a). \end{aligned} \end{aligned}$$

(19)

Observe that $y\varvec{f}=x\varvec{\hat{b}}+\varvec{\hat{a}}$ by the definition of $\varvec{\hat{a}}$. By the Chinese Remainder Theorem, the equality holds in each CRT slot. Using Step 5 of the verification in a similar manner, we get exact message openings $\varvec{\hat{c}}$ and $\varvec{\hat{d}}$ of yC and yD such that $y\varvec{g} = x\varvec{\hat{c}}+\varvec{\hat{d}}$. Writing these equations coordinate-wise in each CRT slot, we have the following for all $1\le i\le \psi$ and $0\le j \le s-1$

$$\begin{aligned} yf_{j}^{(i)}&= x\hat{b}_{j}^{(i)} + \hat{a}_{j}^{(i)} \quad \text {in }R_q^{(j)}, \text { and} \end{aligned}$$

(20)

$$\begin{aligned} yg_{j}^{(i)}&= yf_{j}^{(i)}(x-f_{j}^{(i)}) = x\hat{c}_{j}^{(i)} + \hat{d}_{j}^{(i)} \quad \text {in }R_q^{(j)}, \end{aligned}$$

(21)

since all the challenges and their differences are the same in each CRT slot. Now, by the $\gamma _{\text {range}}$-binding property of UMC, except with negligible probability, the PPT prover cannot output a new valid exact opening of yA, yB, yC or yD in any of its rewinds. Thus, except with negligible probability, responses with respect to $x'$ and $x''$ will have the same form. That is, the following holds

$$\begin{aligned} \begin{aligned} yf_{j}'^{(i)}&= x'\hat{b}_{j}^{(i)} + \hat{a}_{j}^{(i)}, \\ yf_{j}''^{(i)}&= x''\hat{b}_{j}^{(i)} + \hat{a}_{j}^{(i)}, \end{aligned}&\begin{aligned} yf_{j}'^{(i)}(x'-f_{j}'^{(i)})&= x'\hat{c}_{j}^{(i)} + \hat{d}_{j}^{(i)}, \\ yf_{j}''^{(i)}(x''-f_{j}''^{(i)})&= x''\hat{c}_{j}^{(i)} + \hat{d}_{j}^{(i)}, \end{aligned} \quad \text {in }R_q^{(j)}. \end{aligned}$$

(22)

Now, multiplying (21) by y and using (20), we get

$$\begin{aligned} \begin{aligned} y\cdot&\left( x\cdot \hat{c}_{j}^{(i)} + \hat{d}_{j}^{(i)}\right) = y\cdot \left( yf_{j}^{(i)}(x-f_{j}^{(i)})\right) = yf_{j}^{(i)}(yx-yf_{j}^{(i)}) \\&= (x\hat{b}_{j}^{(i)} + \hat{a}_{j}^{(i)})(yx-x\hat{b}_{j}^{(i)} - \hat{a}_{j}^{(i)}) = (x\hat{b}_{j}^{(i)} + \hat{a}_{j}^{(i)})(x(y-\hat{b}_{j}^{(i)}) - \hat{a}_{j}^{(i)}) \\&= x^2\left[ \hat{b}_{j}^{(i)}(y-\hat{b}_{j}^{(i)}) \right] + x \left[ \hat{a}_{j}^{(i)}(y-2\hat{b}_{j}^{(i)})\right] - (\hat{a}_{j}^{(i)})^2, \end{aligned} \end{aligned}$$

(23)

and thus

$$\begin{aligned} x^2\left[ \hat{b}_{j}^{(i)}(y-\hat{b}_{j}^{(i)}) \right] + x \left[ \hat{a}_{j}^{(i)}(y-2\hat{b}_{j}^{(i)}) - y\hat{c}_{j}^{(i)}\right] - (\hat{a}_{j}^{(i)})^2 - y\hat{d}_{j}^{(i)} = 0 \quad \text {in }R_q^{(j)}. \end{aligned}$$

(24)

Repeating the same steps of (23) with the equations in (22), we get two copies of (24) where x is replaced with $x'$ in one and with $x''$ in the other. That is, we have the following system

$$\begin{aligned} \left( \begin{array}{ccc} 1 &{} x &{} x^{2} \\ 1 &{} x' &{} x'^{2} \\ 1 &{} x'' &{} x''^{2} \end{array}\right) \cdot \left( \begin{array}{c} - (\hat{a}_{j}^{(i)})^2 - y\hat{d}_{j}^{(i)} \\ \hat{a}_{j}^{(i)}(y-2\hat{b}_{j}^{(i)}) - y\hat{c}_{j}^{(i)} \\ \hat{b}_{j}^{(i)}(y-\hat{b}_{j}^{(i)}) \end{array}\right)= & {} \varvec{0} \qquad \text {in } R_q^{(j)}. \end{aligned}$$

(25)

Since $R_q^{(j)}$ is a field, Vandermonde matrix on the left is invertible for distinct challenges, and we get $\hat{b}_{j}^{(i)}(y-\hat{b}_{j}^{(i)})=0$, which implies $\hat{b}_{j}^{(i)}\in \{0,y\}$ in a field, i.e.

$$\begin{aligned} \hat{b}_{j}^{(i)} = y{b}_{j}^{(i)} \quad \text {for }b_j^{(i)}\in \{0,1\}. \end{aligned}$$

(26)

The range proof part is rather easier and is given in the full version [13].    $\square$

Remark 1

The first rejection sampling at Step 14 of Protocol 2 is not necessary as UMC allows unbounded-length messages. However, when rejection sampling is done, the bitsize of $f_j^{(i)}$’s are smaller (about a factor 3) than $d\log q/s$, which is the bitsize of a random element in $R_q^{(j)}$. Further, there is no mod q reduction in the prover’s response, and also no mod $P^{(j)}(X)$ at Step 13 of Protocol 2 since $b_j^{(i)}$’s are binary.

5 Efficient One-Shot Proofs for Useful Relations

5.1 Relaxed Proof of Commitment to Sequences of Bits

Using our new techniques, we extend the multi-shot proof of commitment to bits from [14] to a one-shot proof. Our protocol, called Protocol Bin, proves a weaker relation but, the relaxation is tailored in a way that the soundness proof of higher level proofs (Protocol 3) still work. It proves that a commitment B opens to sequences of binary values such that there is a single 1 in each sequence, i.e., Hamming weight of each sequence is exactly 1. The relations of Protocol Bin are defined in Definition 5 where $\varvec{b}=(b_{0,0},\ldots ,b_{k-1,\beta -1})$ for $k\ge 1,\beta \ge 2$.

Definition 5

The following defines the relations for Protocol Bin $\mathcal {T},\mathcal {\hat{T}}\in \mathbb {R}^+$.

$$\begin{aligned} \mathcal {R}_\text {bin}(\mathcal {T})&= \left\{ \begin{array}{c} \!((ck,B),(\varvec{b},\varvec{r})) \;:\; \left\| \varvec{r}\right\| \le \mathcal {T} \;\wedge \; (b_{j,i}\in \{0,1\}\; \forall j,i ) \\ \;\wedge \; B={\mathrm {Com}}_{ck}(\varvec{b};\,\varvec{r}) \; \wedge \; (\sum _{i=0}^{\beta -1}b_{j,i}=1 \;\forall j) \end{array}\right\} \!. \\ \mathcal {R}_\text {bin}'(\mathcal {\hat{T}})&= \left\{ \begin{array}{c} \!((ck,B),(y,\varvec{b},\varvec{\hat{r}})) : \left\| \varvec{\hat{r}}\right\| \le \mathcal {\hat{T}} \;\wedge \; (b_{j,i}\in \{0,1\}\; \forall j,i) \; \wedge \\ y\in \varDelta \mathcal {C}_{w,p}^d \;\wedge \;yB={\mathrm {Com}}_{ck}(y\varvec{b};\,\varvec{\hat{r}}) \; \wedge \; (\sum _{i=0}^{\beta -1}b_{j,i}=1 \;\forall j) \end{array}\right\} \!. \end{aligned}$$

The idea of the binary proof (combined with the CRT-packing technique) is already used in Protocol 2. The condition on the Hamming weight is the difference to Protocol 2 and is handled with a small modification. We defer the full description of Protocol Bin to the full version of the manuscript and show below the crucial part in making the binary proof work in a fully-splitting ring $R_q$.

Handling binary proof for NTT-friendly modulus q . As in (25) in the soundness proof of Theorem 1, we get the same system of equations below in the soundness proof of Protocol Bin

$$\begin{aligned} \left( \begin{array}{ccc} 1 &{} x &{} x^{2} \\ 1 &{} x' &{} x'^{2} \\ 1 &{} x'' &{} x''^{2} \end{array}\right) \cdot \left( \begin{array}{c} - (\hat{a}_{j,i})^2 - y\hat{d}_{j,i} \\ \hat{a}_{j,i}(y-2\hat{b}_{j,i}) - y\hat{c}_{j,i} \\ \hat{b}_{j,i}(y-\hat{b}_{j,i}) \end{array}\right) = \varvec{0} \qquad \text {in } R_q, \end{aligned}$$

where $\hat{b}_{j,i}$ are the values we want to prove to be of the form $\hat{b}_{j,i}=yb_{j,i}$ for $b_{j,i}\in \{0,1\}$. The difference now is that all equations now hold in $R_q$, and we cannot use any invertibility argument. Multiplying both sides of the above system by $\text {adj}(\varvec{V})$ where $\varvec{V}$ is the Vandermonde matrix on the left, we get

$$\begin{aligned} \det (\varvec{V})\hat{b}_{j,i}(y-\hat{b}_{j,i}) = (x''-x')(x'-x)(x''-x)\hat{b}_{j,i}(y-\hat{b}_{j,i}) = 0 \quad \text {in } R_q. \end{aligned}$$

(27)

We show in the proof of Theorem 2 that $\Vert (x''-x')(x'-x) (x''-x)\hat{b}_{j,i}(y-\hat{b}_{j,i})\Vert _{_\infty } \le 2^7\phi _1^2p^5w^3d^2k\beta$. Therefore assuming $q/2> 2^7\phi _1^2p^5w^3d^2k\beta$, one of the factors in (27) must be zero by Lemma 7. As challenge differences are non-zero, this gives either $\hat{b}_{j,i}$ or $y-\hat{b}_{j,i}$ is zero. Thus, we get $\hat{b}_{j,i}\in \{0,y\}$. That is, $\hat{b}_{j,i} = y{b}_{j,i}$ for ${b}_{j,i}\in \{0,1\}$ as needed for $\mathcal {R}_\text {bin}'$. We state the results in the theorem below, and defer its full proof to the full version of the manuscript [13].

Theorem 2

Let $\gamma _{\text {bin}}{\,=\,}2p\sqrt{dw} \left( 16\phi _1^4p^4d^3k^3w^2\beta (\beta +1)+ 12\phi _2^2p^2w^2\mathcal {B}^2m^2d^2 \right) ^{1/2}$. Assume that $d\ge 128$, $q/2> 2^7\phi _1^2p^5w^3d^2k\beta$ and HMC is hiding and $\gamma _{\text {bin}}$-binding. Then, Protocol Bin is a 3-special sound $\varSigma$-protocol (as in Definition 3) for the relations $\mathcal {R}_\text {bin}(\mathcal {B}\sqrt{md})$ and $\mathcal {R}_\text {bin}'(4\sqrt{2}\phi _2 pw\mathcal {B}md )$ with a completeness error $1-1/(\mu (\phi _1)\mu (\phi _2))$ for $\mu (\phi _i)=e^{12/\phi _i+1/(2\phi _i^2)}$, $i=1,2$.

5.2 Relaxed One-out-of-many Proof

Our one-out-of-many proof has the same structure as in [14], which combines ideas from [7, 16]. The main differences of our proof from that in [14] are the use of an exponentially large challenge set, enabling one-shot proofs, the relation the verifier is convinced of and some tweaks to the rejection sampling. The challenging part here is the soundness proof of the protocol. We use our new tools, namely Lemmas 3, 5 and 6, from Sect. 3 for the soundness proof.

Let $\varvec{L}=\{P_0,\ldots ,P_{N-1}\}$ be a set of public commitments for some $N\ge 1$. The prover’s goal is to show that he knows an opening of one of these $P_i$’s. In common with the previous works [7, 14, 16], we assume that $N=\beta ^k$, which can be easily satisfied by adding dummy values to $\varvec{L}$ when needed. Suppose that the prover’s commitment is $P_\ell$ for some $0\le \ell < N$. Observe that $\sum _{i=0}^{N-1}\delta _{\ell ,i}P_i = P_\ell$. The idea for the proof is then to prove knowledge of the index $\ell$ with $\sum _{i=0}^{N-1}\delta _{\ell ,i}P_i$ being a commitment to zero. Writing $\ell =(\ell _0,\ldots ,\ell _{k-1})$ and $i=(i_0,\ldots ,i_{k-1})$ as the representations in base $\beta$, we have $\delta _{\ell ,i}=\prod _{j=0}^{k-1}\delta _{\ell _j,i_j}$. The prover first commits to the sequences $(\delta _{\ell _j,0},\ldots ,\delta _{\ell _j,\beta -1})$ for all $0\le j\le k-1$, and then uses Protocol Bin to show that they are well-formed (i.e., they construct an index in the range [0, N) as in the range proof). Let us define the proved relations next.

Definition 6

The following defines the relations for Protocol 3 for $\mathcal {T},\mathcal {\hat{T}}\in \mathbb {R}^+$.

$$\begin{aligned} \mathcal {R}_\text {1/N}(\mathcal {T})&= \left\{ \begin{array}{c} ((ck,(P_{0},\ldots ,P_{N-1})),(\ell ,\varvec{r})) \;:\; \\ \ell \in [0,N) \; \wedge \; \left\| \varvec{r}\right\| \le \mathcal {T} \; \wedge \; P_\ell ={\mathrm {Com}}_{ck}(\varvec{0};\,\varvec{r}) \end{array}\right\} , \\ \mathcal {R}_\text {1/N}'(\mathcal {\hat{T}})&= \left\{ \begin{array}{c} ((ck,(P_{0},\ldots ,P_{N-1})),(y,\ell ,\varvec{\hat{r}})) \;:\; \ell \in [0,N) \; \wedge \; \left\| \varvec{\hat{r}}\right\| \le \mathcal {\hat{T}} \; \wedge \; \\ yP_\ell ={\mathrm {Com}}_{ck}(\varvec{0};\,\varvec{\hat{r}}) \;\wedge \; y\,\,is\,\,a\,\,product\,\,of\,\,elements\,\,in\,\,\varDelta \mathcal {C}_{w,p}^d \end{array}\right\} . \end{aligned}$$

From Protocol Bin, the prover’s response contains $f_{j,i}=x\delta _{\ell _j,i}+a_{j,i}$ for a challenge x. Considering the product $p_i(x):=\prod _{j=0}^{k-1}f_{j,i_j}$, we see, for all $i\in [0,N-1]$,

$$\begin{aligned} p_i(x) \! = \! \prod _{j=0}^{k-1} \left( x \delta _{\ell _j,i_j} + a_{j,i_j} \right) = \prod _{j=0}^{k-1} x\cdot \delta _{\ell _j,i_j} + \sum _{j=0}^{k-1}p_{i,j}x^j = \delta _{\ell ,i}x^k + \sum _{j=0}^{k-1}p_{i,j}x^j, \end{aligned}$$

(28)

for some ring element $p_{i,j}$’s as a function of $\ell$ and $a_{j,i}$’s (independent of the challenge x). Since $\ell$ and $a_{j,i}$’s are known to the prover before receiving a challenge, he can compute $p_{i,j}$’s prior to sending the initial commitment. Since $p_\ell$ is the only such polynomial of degree k, in his first move, the prover sends some $E_j$’s that are tailored to cancel out the coefficients of the terms $1,x,\ldots ,x^{k-1}$, and the coefficient of $x^k$ is set to the prover’s commitment $P_\ell$ using $\sum _{i=0}^{N-1}\delta _{\ell ,i}P_i$. The full description is given in Protocol 3. In the full version [13], we show how our one-out-of-many proof can be extended to a set membership proof.

Theorem 3

Let $\gamma _{\text {1/N}}=(k+1)2^{\kappa '+2}\sqrt{3}\phi _2 \mathcal {B}m d^2 w^{\kappa } p^{\kappa +1}$ for $\kappa ' = k(k-1)/2$ and $\kappa =k(k+1)/2$. Assume $d\ge 128$, $q> 2^7\phi _1^2p^5w^3d^2k\beta$ and HMC is hiding and $\gamma$-binding for $\gamma =\max \{\gamma _{\text {bin}},\gamma _{\text {1/N}}\}$. For $\mu (\cdot )$ as in Theorem 1, Protocol 3 is a $(k'+1)$-special sound $\varSigma$-protocol (as in Definition 3) for the relations $\mathcal {R}_\text {1/N}(\mathcal {B}\sqrt{md})$ and $\mathcal {R}_\text {1/N}'(\gamma _{\text {1/N}})$ with a completeness error $1-1/(\mu (\phi _1)\mu (\phi _2))$ where $k'=\max \{2,k\}$.

Proof

(Theorem 3). Completeness and SHVZK proofs are in the full version. $(k'+1)$-special soundness: Assume that $k>1$. Given $(k+1)$ distinct challenges $x_0,\ldots ,x_k$, we have $(k+1)$ accepting responses with the same $(A,B,C,D,E_0,\ldots ,$ $E_{k-1})$. Let $(\varvec{f}_1^{(0)},\varvec{z}^{(0)}),\ldots ,(\varvec{f}_1^{(k)},\varvec{z}^{(k)})$ be part of the responses with respect to challenges $x_0,\ldots ,x_k$, respectively. Setting $y=x_1-x_0$, we first use 3-special soundness of Protocol Bin to extract exact valid message openings $\hat{b}_{j,i}$ and $\hat{a}_{j,i}$ of yB and yA, respectively. We know that $\hat{b}_{j,i}=yb_{j,i}$ for $b_{j,i}\in \{0,1\}$ and only a single one of $\{b_{j,0},\ldots ,b_{j,\beta -1}\}$ is 1 for each $j\in \{0,\ldots ,k-1\}$. Now, we construct the representation of $\ell$ in base $\beta$ as follows. For each $0\le j \le k-1$, the j-th digit $\ell _j$ is the integer c such that $b_{j,c}=1$. It is easy to construct the index $\ell$ from here using its digit $\ell _j$’s.

From the soundness proof of Protocol Bin that use $\gamma _{\text {bin}}$-binding property of the commitment scheme, we have, for all $0\le \eta \le k-1$, $y f_{j,i}^{(\eta )} = x_\eta \hat{b}_{j,i} + \hat{a}_{j,i} = x_\eta \cdot y b_{j,i} + \hat{a}_{j,i}.$ Now compute $\hat{p}_i(x_\eta ) = y^k\prod _{j=0}^{k-1}f_{j,i_j}^{(\eta )} = \prod _{j=0}^{k-1}yf_{j,i_j}^{(\eta )} = \prod _{j=0}^{k-1} \left( yx_\eta b_{j,i_j} + \hat{a}_{j,i_j}\right)$ for each $i=0,\ldots ,N-1$. By the construction of $\ell$, $\hat{p}_\ell (x_\eta )$ is the only polynomial of degree k in $x_\eta$ for all $0\le \eta \le k-1$. Then, we can multiply the both sides of the last verification step by $y^k$ and re-write it as below

$$\begin{aligned} \sum _{i=0}^{N-1}\hat{p}_i(x_\eta )P_i - \sum _{j=0}^{k-1} y^kE_jx_\eta ^j = x_\eta ^k\cdot y^k P_\ell + \sum _{j=0}^{k-1}\tilde{E}_jx_\eta ^j = {\mathrm {Com}}_{ck}(\varvec{0};\,y^k\varvec{z}^{(\eta )}), \end{aligned}$$

(29)

where $\tilde{E}_j$’s are the terms multiplied by the monomials $x^j_\eta$’s of degree at most $k-1$ and are independent of $x_\eta$. Equation (29) is exactly the case described in (9) and the verification of Protocol 1 in Sect. 3 with $C_k = y^kP_\ell$. By the discussion in Sect. 3, we obtain exact openings of $\det (\varvec{V})y^kP_\ell$ as $(\varvec{0}, y^k\hat{\varvec{r}})$ where $\hat{\varvec{r}} = \sum _{i=0}^{k}\varGamma _i \varvec{z}^{(i)}$ for $\varGamma _i = (-1)^{i+k}\prod _{0\le l < j \le k \wedge j,l\ne i} (x_j-x_l)$, i.e., we have

$$\begin{aligned} \det (\varvec{V})y^kP_\ell = {\mathrm {Com}}_{ck}(\varvec{0};\,y^k\hat{\varvec{r}})&\implies y^k\cdot \left( \det (\varvec{V})P_\ell - {\mathrm {Com}}_{ck}(\varvec{0};\,\hat{\varvec{r}}) \right) = 0 \nonumber \\ \text {(by Lemma 6)}&\implies y\cdot \left( \det (\varvec{V})P_\ell - {\mathrm {Com}}_{ck}(\varvec{0};\,\hat{\varvec{r}}) \right) = 0 \nonumber \\&\implies \det (\varvec{V})yP_\ell = {\mathrm {Com}}_{ck}(\varvec{0};\,y\hat{\varvec{r}}). \end{aligned}$$

(30)

In the end, we have an exact opening of $\det (\varvec{V})yP_\ell$ as $(\varvec{0},y\hat{\varvec{r}})$. This randomness opening is a factor $y\in \varDelta \mathcal {C}_{w,p}^d$ larger than what we have in Lemma 5. Thus, using Lemma 3 and Lemma 5, we conclude, for $\kappa ' = k(k-1)/2$ and $\kappa = k(k+1)/2$,

$$\begin{aligned} \left\| y\hat{\varvec{r}}\right\|&\le (k+1) d (2p)^{\kappa '+1} w^{\kappa '} \max _i\Vert \varvec{z}^{(i)}\Vert \le (k+1) d (2p)^{\kappa '+1} w^{\kappa '}\cdot 2\sqrt{3} \phi _2 \mathcal {B}md w^kp^k \\&\le (k+1)2^{\kappa '+2}\sqrt{3}\phi _2 \mathcal {B}m d^2 w^{\kappa } p^{\kappa +1} . \end{aligned}$$

Recall that we assumed $k>1$. When $k=1$, Protocol Bin still needs 3 challenges for its soundness property. Hence, Protocol 3 is at least 3-special sound.    $\square$

6 Applications of Relaxed ZKPs to Advanced Tools

The relaxed range proof combined with a relaxed proof of knowledge results in a form of efficient anonymous credentials as detailed in the full version of the manuscript [13]. To prove relations on a set of attributes, a single use of our range proof is sufficient and we show how the relaxation is handled. Our second construction is a ring signature that builds on the relaxed one-out-of-many proof.

Ring Signature. The construction of ring signature from one-out-of-many proof follows the same strategy as in [7, 14, 16]. The users commit to their secret keys and these commitments represent the public keys. A set of public keys is then used as the set of public commitments in one-out-of-many proof. The prover proves knowledge of an opening of one of the commitments (i.e., knowledge of a secret key corresponding to one of the public keys of the ring signature). The main difference from [7, 14, 16] is that we show that our relaxed proof is still sufficient (see the full version [13] for details). In Table 4, we give the concrete instantiation of the parameters.

Table 4. Parameter setting of our ring signature with a root Hermite factor $\le 1.0045$ for both M-LWE and M-SIS. $\mathcal {B}=1,\phi _1=\phi _2=15$ for all cases.