Corentin Jeudy
email: corentin.jeudy@orange.com

Adeline Roux-Langlois
email: adeline.roux-langlois@cnrs.fr

Olivier Sanders
email: olivier.sanders@orange.com

Lattice Signature with Efficient Protocols, Application to Anonymous Credentials

Keywords: Lattice-Based Cryptography, Signature, Efficient Protocols, Privacy, Anonymous Credentials

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Electronic authentication massively relies on digital signatures, a cryptographic primitive that can be traced back to the Diffie-Hellman seminal paper [DH76]. The strong point of digital signatures is that they act in the digital world in the same way as handwritten signatures do in the real world: they add a short element S to some data m attesting that m has been validated by the signer and that it has not been modified afterwards. By emulating handwritten signatures, they represent the perfect electronic counterpart and are indeed ubiquitous today.

However, for several decades, cryptographers have questioned this hegemony in some situations as these signatures may give rise to many privacy issues. Typically, presentation of the same certificate4 S each time m needs to be authenticated allows tracing S and hence its owner. Moreover, if m is a set of elements m i , then verification of S requires knowledge of all these elements even if they are irrelevant for the current authentication.

For example, let us consider the classical use-case of age control (e.g., to check that a customer is an adult) where some customer owns a digital certificate (embedded in some ID document) authenticating his attributes (name, birthdate, address, etc). With standard digital signature, this customer has no other choice than providing the full set of attributes to the controller as they are required to run the verification algorithm. This is clearly a significant privacy issue but here one could argue that the situation already occurs in the real world: it is indeed quite common to present an ID document displaying many personal information to a cashier that needs to control your age.

This apparent paradox epitomizes the differences between the real world and the digital one. In the former, it is natural to assume that the cashier will not memorize all the information contained in the document for further commercial exploitation or identity theft. This does not hold true in the digital world where the users definitely lose control of their data as soon as they reveal them and it is very likely that the same customer will be much more reluctant to provide the same information to a website that needs to verify that he is an adult.

Related Works

Since the problems of the two worlds are different it is actually logical that standard digital signatures are not best suited for all use-cases. In particular, the fact that electronic data can no longer be controlled once they are revealed calls for solutions disclosing as few information as possible during authentication. This has given rise to countless advanced cryptographic primitives, tailored to very specific use-cases, such as anonymous credentials [Cha85,CL01,FHS19], group signatures [CvH91,BSZ05], Direct Anonymous Attestations (DAA) [BCC04], EPID [BL07], etc. Far from simply being theoretical constructions, some of them have been included in standards (e.g., [ISO13a,ISO13b]) and even embedded in billions of devices (e.g., [TCG15,Int16]).

Surprisingly, the diversity of use-cases addressed by these privacy-preserving authentication mechanisms contrasts with the very few mathematical settings allowing efficient designs. A closer look at these standards indeed shows that all of them make use of RSA moduli or cyclic groups and thus cannot withstand the power of quantum computing. The emerging success of such systems is thus based on foundations that will crumble as soon as a sufficiently powerful quantum computer appears.

This unsatisfying state of affairs clearly calls for the design of post-quantum alternatives to such systems. However, when we look at the cryptographic literature on this topic, it is striking to see that the existing post-quantum solutions are not only much less efficient than their classical5 counterparts but also extremely rare. Typically, we are not aware of any explicit post-quantum anonymous credentials system. Even when we consider popular primitives such as group signatures, we note that the most efficient solutions [dPLS18,LNPS21] depart from the traditional model [BSZ05] as they do not achieve non-frameability, a property implying that the certificate issuer does not know users' secret keys and that is thus incompatible with their construction. Although this might seem to be a minor restriction for group signatures, this has very important consequences on their industrial variants such as DAA [CKLL19] and EPID [BEF19]. Indeed, for the latter, the knowledge of the users' secret keys allows one to break anonymity, which makes the whole construction totally pointless.

To understand the contrasting situations of classical constructions and postquantum ones in the area of privacy-preserving authentication mechanisms, it is important to recall that all of them require, at some point, to prove knowledge of a signature on some (potentially secret) attributes. For example, in an anonymous credential system, the user generally receives a signature on their attributes and some secret key at the time of issuance. To show their credentials they then reveal the requested attributes and prove knowledge of the signature, the hidden attributes and the secret key so as to remain anonymous. In non-frameable group signatures, DAA or EPID schemes, the user first receives a certificate C on a secret key s and then generates their own signatures by including a zero-knowledge proof that C is valid on s. Of course, the resulting signatures also contains additional elements that define the specificity of each primitive but the point is that the common core is this proof of knowledge which essentially needs two kinds of building blocks: a "signature scheme with efficient protocols" as coined by Camenisch and Lysyanskaya [CL02] and an associated zero-knowledge (ZK) proof system.

The latter notion is well-known and has seen several advances over the past few years, in particular in the lattice setting, e.g., [BLS19,YAZ + 19,LNP22]. The former notion is rather informal but it usually refers to a digital signature scheme with some specific features such as the ability to sign committed (hidden) messages and to prove knowledge of a signature on such messages. This places some restrictions on the design of the signature scheme as it for example proscribes hash functions and hence most popular paradigms such as Hashand-Sign and Fiat-Shamir. Yet, several extremely efficient constructions from number theoretic assumptions exist, in particular in bilinear (pairing) environ-ments [CL04,BB08,PS16]. They constitute a very powerful and simple-to-use building block which explains the countless applications using them.

This situation stands in sharp contrast with the one of post-quantum cryptography where we are aware of only one lattice-based construction [LLM + 16] with such features. Moreover the latter was designed with Stern's proof of knowledge in mind and thus does not leverage the recent advances in the area of latticebased zero-knowledge proofs. The original paper only provides asymptotic estimation but our thorough analysis (deferred in Appendix H) shows that, even with the recent ZK protocol from [YAZ + 19], a proof of knowledge of a signature is still, at best, 670 MB large, which is far too high for practical applications. This leaves designers of privacy-preserving systems with no other solution than constructing the whole system from scratch, as was done for example in the case of EPID [BEF19] and DAA [CKLL19], which requires skills in many different areas and thus limits the number of contributions.

Our Contributions

The goal of our paper is to propose the lattice counterpart of [CL04,BB08,PS16], that is, a signature scheme with efficient protocols that is specifically designed to smoothly and efficiently interact with the most recent lattice-based zeroknowledge proof systems. More precisely, we provide a lattice-based signature scheme for which we can (1) obtain signatures on potentially hidden (in a commitment) messages, and (2) prove in zero-knowledge the possession of a messagesignature pair. Compared to the only such construction [LLM + 16], our scheme is not only much more efficient but also transposes well to an algebraically structured setting which leads to further performance improvements, as summarized in Table 1.1.

Our natural starting point is [LLM + 16] which consists in a Boyen signature [Boy10] on a randomly chosen tag τ ∈ {0, 1} ℓ and for a syndrome shifted by the binary decomposition of the commitment c = D 0 r + D 1 m to a binary message m, the commitment scheme being implicit in [Ajt96]. At first sight, this scheme perfectly fits the recent zero-knowledge proof system proposed by Yang et al. [YAZ + 19] but yet leads to an extremely large proof of knowledge as explained above (a thorough complexity analysis is provided in Appendix F.3 and Table H.1). We then undertake a complete overhaul of this scheme, pointing out at the same time the reasons of such a high complexity.

The main novelty is that we adopt a much more global approach as we look simultaneously at the three components of such systems, namely the commitment scheme (necessary to obtain signature on hidden messages), the signature scheme and the zero-knowledge proof systems, and the possible synergies. We, in particular, emphasize that the design choices we made for each component were not driven by the will to improve the latter individually but rather by their impact on the whole system. Typically, some of the modifications we introduce in the signature scheme itself has almost no impact on its complexity but yet results in very significant gains when it comes to proving knowledge of a sig-nature. More generally, our approach leads to a series of contributions that we regroup in three main parts.

The signature scheme. One of the first consequences of having to sign committed messages is that the signature must now include the randomness added to the commitment by the signer. In [LLM + 16], this randomness has the same dimension as the one of the Boyen signature but a much larger width (see Table H.1) and thus represents the largest part of the signature. This is amplified by the proof of knowledge, which explains in part the high complexity of the latter. One of the reasons of such a large width is that the security proof requires to embed a hidden relation in the matrix D that is applied to the binary decomposition of the Ajtai commitment c. More precisely, it defines D = AU for the matrix A from the Boyen public key and some short matrix U. This (along with other design choices discussed below) deteriorates the quality of the SIS solution extracted during the security proof and thus leads to large parameters.

To address this issue, we depart from [LLM + 16] by generating conjointly the parameters of the signature scheme and the ones of the commitment scheme and in particular by re-using parts of the former in the latter. More specifically, in our construction, a commitment to m is c = Ar + Dm, for a Gaussian randomness r, where A is a matrix from the signer's public key and D is a public random matrix. From the efficiency standpoint, this has two important effects. First, this allows merging the randomness r with the other parts of the signatures, as we explain below, and thus to reduce the number of elements that we have to prove knowledge of. Second, as A is no longer hidden by a matrix U, this significantly reduces the discrepancy between the adversary output and the extracted SIS solution in the security proof, leading to much better parameters.

Obviously, this has important consequences on the construction as the commitment matrix A is now selected by the signer, which is usually embodied by the adversary in privacy security games. To ensure that A is random to make the Ajtai commitment hiding, we need to generate it as a hash output. This solution is then totally incompatible with the [LLM + 16] approach where the signer needs to generate A together with an associated trapdoor.

Instead of Boyen's signature, we then choose to use the trapdoors of [MP12], which interface well with the Ajtai commitment. More precisely, our public key is composed of a random matrix A, a matrix B = AR and a random syndrome u, and the secret key is a random ternary matrix R. In order to sign a binary message m hidden in a commitment c = Ar + Dm, we use pre-image sampling to sample a Gaussian vector v ′ such that [A|τ G -B]v ′ = u + c, where τ is a tag from a tag space T ⊆ Z × q and G is the gadget matrix from [MP12]. As A is involved in both the left hand side of the equation and in c, we can set the signature as (τ, v = v ′ -[r T |0] T ). Verification consists in checking [A|τ G -B]v = u + Dm mod q and ∥v∥ ∞ small.

(1)

One can note that we have removed in the process the binary decomposition of c. We indeed choose a very different approach in the security proof which shows that this step is actually not necessary. Removing this decomposition is also crucial in order to compact the commitment randomness r with the preimage v ′ . It avoids further intermediate steps that deteriorate the SIS solution extracted from the forgery, as explained above, which leads to better parameters overall. Moreover, when it comes to proving knowledge of the signature, each intermediate step makes the whole statement harder to prove and requires to create additional witnesses, i.e., each bit of c, that must be committed, whose membership in {0, 1} must be proven, etc. Our point here is that each seemingly innocent modification is considerably amplified when considering the full protocol and therefore results in major gains.

At this stage, a reader familiar with the construction in [dPLS18] might wonder why we do not try to embed the committed message in the tag τ , instead of having this Dm component in our verification equation. Here, we need to recall that the situation of [dPLS18] is very specific as the signer (the group manager in their application) knows the signed message m, which belongs to some bounded set in their application. In our case, we want to hide this message that may have a very large entropy (this is for example the case in anonymous credentials systems). In all cases, the security reduction must guess, at the setup stage, the value of the tag τ * involved in the forgery. Therefore, if τ is generated from m itself, then the reduction would have to guess this message, which would result in an exponential security loss in most scenarios. A workaround could be to construct τ from H(m) for some appropriate function H (most likely a hash function because of the properties it would have to satisfy) whose image has lower entropy so as to guess H(m) instead of m. Alternatively, H could be modelled as a random oracle. The problem with this solution is that verification would now require to prove that H(m) has been correctly evaluated. For very specific scenarios (e.g., blind signature [dPK22,BLNS23]) where m can be revealed at the verification time, this would work with a security loss depending on the entropy of H(m). For all others (e.g., group signature, anonymous credentials, e-cash, etc), where the message must remain secret, this would not be possible with the zero-knowledge frameworks we target because of the nature of H. As we aim to design a versatile tool, suitable for all applications, we choose to have a tag uncorrelated to the message, hence the Dm component mentioned above. As per the security proof, there are two constraints in the way to choose tags: generate tags without encountering collisions to only emit one signature per tag, and without enduring an exponential loss in the security proof due to guesses. Given that we essentially target privacy-preserving applications such as group signatures or anonymous credentials, we focus, in the body of our paper, on a stateful construction that inherently solves these two problems. For all these applications, it is indeed natural for the signer to keep track of the signatures it has issued. For group signature, this is even a requirement of the security model [BSZ05]: a registration table must be updated after each addition of a group member. However, for completeness, we show in Appendix G that our construction can easily be tweaked to be stateless, at the cost of a very mild increase of the signature size, while complying with the two constraints above. of Section 3 and of Section 3.3 for λ = 128 bits of quantum security, with the size of zeroknowledge proof of possession of a message-signature pair. In the setting column, stand. stands for standard lattices, as opposed to the ring setting of our last construction. The proofs for [LLM + 16] and Section 3 are either exact proofs or approximate ones using the fast mode of Section 4.2 and described in the technical overview. The complete analysis and parameter sets used for these estimates can be found in Appendix H.

So far, we have essentially discussed improvements of both the commitment and the signature schemes. Table 1.1 shows that our resulting signature is between 30 and 40 times smaller than that of [LLM + 16] when considering the same setting (standard lattices). However, this gain is still not sufficient to lead to practical proofs as ZK lattice proofs are still complex, even with the recent framework of [YAZ + 19]. We now focus on the proofs of knowledge necessary for our protocol and explain how we can modify the previous framework for a better efficiency.

Efficient Protocols and Zero-Knowledge Arguments. A "signature scheme with efficient protocols" requires two kinds of protocols, one to get a signature on a committed message and one for proving possession of a message-signature pair. Regarding the former, the problem is rather simple as the message m to sign is already embedded in a commitment c = Ar + Dm. However, we have to slightly modify this construction because both the user requesting the signature and the signer must contribute to the randomness of the commitment. This leads to a commitment c = A(r ′ + r ′′ ) + Dm where r ′ is added by the user to enforce the hiding property of c and r ′′ is added by the signer to be able to handle any query in the security proof. Only the former needs to prove knowledge of r ′ and m so as to rely on the EUF-CMA property of the signature scheme we introduced. In all cases, the user ends up with a signature (τ, v) on a binary m verifying (1) and needs to prove it in a zero-knowledge way.

For that, we employ the recent zero-knowledge framework proposed by Yang et al. [YAZ + 19] which can be used to prove linear relations with quadratic constraints. The latter feature is very useful in our case as our verification equation (1) is quadratic in (m; (τ, v)) because of the term τ Gv 2 (where v 2 is the bottom part of v). Moreover, this allows one to prove that an element is short by first writing its binary decomposition and then proving that each resulting component x is indeed binary through the quadratic equation x(x -1) = 0.

Unfortunately, this nice feature comes at a price as this decomposition procedure entails a (log 2 B)-fold increase of the size of the witness v, where B is a bound on ∥v∥ ∞ . For a high dimensional vector v in Z m , this results in a very large proof which has led the authors of [YAZ + 19] to propose a so-called fast mode for their protocol. In a nutshell, this variant relies on the observation that the norm of Hv, for a random short matrix H of dimension k × m, implies some bound on the norm of v, even when the latter is chosen by the adversary. As Hv must be hidden, one must still use the quadratic relation above to prove shortness but on a witness with a much smaller dimension as k is in practice much smaller than m. The efficiency gains are very significant but we point out several shortcomings with the solution proposed in [YAZ + 19]. First, contrarily to the claim in [YAZ + 19], this fast mode cannot be used to prove that v is positive and we provide a concrete counter-example in Section 4. This is not a problem in our case as we only want to prove results on the ℓ ∞ norm of v but this can be a problem for specific applications such as the e-cash system considered in [YAZ + 19]. Second, the authors in [YAZ + 19] make use of a binary matrix H which significantly deteriorates the overall statement as one must set a bound mβ on the norm of Hv, when ∥v∥ ∞ is bounded by β. Although this soundness gap seems unavoidable with this mode, we show that we can do better with a matrix H ∈ {-1, 0, 1} k×m , which allows selecting better parameters and thus leads to more efficient protocols.

Finally, we also propose in Appendix E a series of optimizations for the protocol of [YAZ + 19] that range from better parameter selection to compression of the commitments, resulting in further efficiency improvements. For a fair comparison, the figures in Table 1.1 take into account these improvements for both our scheme and the one from [LLM + 16]. This table shows that our contributions reduce the size of a proof of knowledge (using the fast mode) to roughly 18 MB, which can be interpreted in two ways. On the one hand, this is an important improvement over [LLM + 16]. On the other hand, this is still large and probably impractical for many applications. The next part of our contributions thus investigates how to instantiate our construction in another setting to further reduce this size.

Extending to Structured Lattices. Our construction extends to the module setting where we replace the integers by polynomials with integer coefficients. More concretely, we consider a power-of-two cyclotomic ring, i.e., R = Z[X]/⟨X n + 1⟩ with n a power-of-two. The additional structure yields more efficient computations, as well as more compact keys. The trapdoors of [MP12] have already been used over such algebraic rings, e.g., [DM14,dPLS18,BEP + 21], which makes our module construction very similar to the one based on standard lattice assumptions. All the tools required to prove the security of our scheme also have a ring counterpart, which therefore leads to almost no differences in the security proofs either. The main difference comes when considering exact zeroknowledge proofs over algebraic rings. Our verification equation in the module setting is

[A|τ G -B]v = u + Dm mod qR and v short.
(2)

Proving knowledge of (2) requires to prove that (1) τ is in the specified tag space, (2) v is short, (3) m is a vector of binary polynomials, and (4) that the quadratic equation is verified. Based on state-of-the-art proof systems, (1) constrains which tag space to choose so that we can efficiently prove membership, while ensuring that a difference of tags is in (R/qR) × as needed per the security proofs. Statement (2) requires to define a notion of shortness over the ring, which is usually defined based on the size of the polynomials' coefficients. Up until recently, exact proofs performing the latter task [BLS19,ENS20] (also used for (3)) used NTT packing, i.e., interpreting the coefficients of v as the NTT (Number Theoretic Transform) of another vector v ′ , which is most efficient when X n + 1 splits into low-degree irreducible factors modulo q. This splitting makes it harder to choose a proper tag space for which differences are always invertible. Finally, (4) requires a proof system able to deal with quadratic equations. Similar relations [dPLS18,LNPS21] were handled by transforming the relation quadratic in the witnesses into a linear relation in the commitment of the witnesses. Since efficient proofs of commitment opening rely on relaxed openings, this solution introduces a soundness gap in the proven statement, which we would like to avoid. Instead, we use the very recent framework of Lyubashevsky et al.

[LNP22] which provides a unified method to prove all our statements. It extends the previous works of [BLS19,ENS20] and enables proving quadratic relations exactly, as well as quadratic evaluations. The latter can be used to prove exact bounds directly in the ℓ 2 norm, which leads to more efficient proofs than proving ℓ ∞ bounds.

In the module setting, we therefore end up with a signature scheme that is efficient on all metrics, as highlighted in Table 1.1. In particular, we manage to keep our proofs of knowledge of a message-signature pair below 650 KB6 . As these proofs are one of the main building blocks of privacy-preserving protocols, these efficiency gains readily translate to the latter and thus should have a significant impact on the area. More generally, our construction is designed to be used as a black box, which should foster many applications, as was the case with the pairing-based signatures with efficient protocols [CL04,BB08,PS16].

Application: Anonymous Credentials. Signature with efficient protocols like the one we propose gives a single signature construction that can be turned into several privacy-preserving primitives such as group signatures, anonymous credentials, e-cash etc. We give an example of one such construction based on our signature to show how it interfaces with the "efficient protocols". More precisely, we propose an anonymous credentials system following the syntax and security model from [FHS19]. At a high-level, the security relies on the zero-knowledge and soundness properties of the proof system and on the EUF-CMA security of our signature. To the best of our knowledge, this provides the first explicit lattice-based anonymous credentials system.

Preliminaries

Throughout this paper, for two integers a ≤ b, we define [a, b] = {k ∈ Z : a ≤ k ≤ b}. When a = 1 and b ≥ 1, we simply use [b] to denote [1, b]. For a positive integer q, we define Z q = Z/qZ. In this work, we consider q to be an odd prime (or product of odd primes), and we sometimes identify Z q with the set of representatives [-(q -1)/2, (q -1)/2]. The vectors are written in bold lowercase letters a, while the matrices are in bold uppercase letters A. The transpose operator is denoted with the superscript T . The identity matrix of size n × n is denoted by I n . For any a ∈ R n , we define its Euclidean (ℓ 2 ) norm as

∥a∥ 2 = ( i∈[n] |a i | 2 ) 1/2 and its infinity (ℓ ∞ ) norm as ∥a∥ ∞ = max i∈[n] |a i |. For a matrix A = [a i ] i∈[m] ∈ R n×m , we define ∥A∥ max = max i∈[m] ∥a i ∥ ∞ ,
and ∥A∥ 2 = max x̸ =0 ∥Ax∥ 2 /∥x∥ 2 . We denote by λ the security parameter.

Lattices

A (full-rank) lattice L of rank n is a discrete additive subgroup of R n . The dual lattice of a lattice L is defined by

L * = {x ∈ Span R (L) : ∀y ∈ L, ⟨x , y⟩ ∈ Z}.
In this work, we consider the following family of q-ary lattices.

Definition 2.1. Let n, m, q be positive integers. Let A ∈ Z n×m q . We define the lattice L ⊥ q (A) = {e ∈ Z m : Ae = 0 mod q}.

Probabilities

For a finite set S, we define |S| to be its cardinality, and U (S) to be the uniform probability distribution over S. The action of sampling x ∈ S from a probability distribution P is denoted by x ← P . We use x ∼ P to say that the random variable x follows the distribution P . The statistical distance between two discrete probability distributions P and Q over a countable set S is defined as

∆(P, Q) = 1 2 x∈S |P (x) -Q(x)|.
We start by recalling the leftover hash lemma from [HILL99] which we write to match our context and notations.

Lemma 2.1 (Adapted from [HILL99,DORS08]). Let n, m, q be positive integers such that q is an odd prime. For A ∼ U (Z n×m q ), x ∼ U ({-1, 0, 1} m ), and u ∼ U (Z n q ), it holds that ∆((A, Ax mod q), (A, u)) ≤ 1 2 q n /3 m . In particular, whenever m log 2 3 ≥ n log 2 q + ω(log 2 λ), the statistical distance is negligible.

For any center vector c ∈ R n , and Gaussian width σ > 0, we define the Gaussian function ρ σ,c : When c = 0, we omit it in the notations. We then use it to define the smoothing parameter of a lattice L [MR07], parameterized by a real ε > 0, by η ε (L) = inf{s > 0 : ρ 1/s (L * ) ≤ 1+ε}. If the standard deviation is wider than the smoothing parameter, the discrete Gaussian distribution benefits from properties that are similar to the ones of the continuous Gaussian distribution. In particular, the sum of two independent discrete Gaussians is a discrete Gaussian.

x ∈ R n → exp(-π∥x -c∥ 2 2 /σ 2 ).
Lemma 2.2 (Adapted from [Reg05,Claim 3.9][MP13,Thm. 3.3]). Let L be lattice of rank n. Let r, s > 0 and t = √ r 2 + s 2 be such that rs/t ≥ η ε (L) for some ε ∈ (0, 1/2]. Then, we have ∆(D L,r + D L,s , D L,t ) ≤ 7ε/4. The condition on r, s is satisfied for example when r, s ≥ √ 2η ε (L).

When centered around 0, the discrete Gaussian distribution benefits from tail bounds similar to the standard Gaussian distribution. In this work, we use tail bounds on the ℓ 2 and ℓ ∞ norms. We also recall the result of [Lyu12] bounding the magnitude of ⟨x , v⟩ for a discrete Gaussian x and an arbitrary vector v. Although the tail bound on the ℓ ∞ norm follows directly from the latter, it was first proven in [Pei08,Cor. 5.3].

Lemma 2.3 ([Ban93,Lem. 1.5][Pei08,Cor. 5.3][Lyu12,Lem 4.3]). Let L be a lattice of rank n. Let σ > 0 and v ∈ R n . Then, for all t > 0, it holds that

1. P x∼D L,σ [∥x∥ 2 > σ √ n] < 2 -2n , 2. P x∼D L,σ [∥x∥ ∞ > σ log 2 n] ≤ 2ne -π log 2 2 n , 3. P x∼D L,σ [|⟨x , v⟩| > σt∥v∥ 2 ] ≤ 2e -πt 2 .
We also use the following bound on the spectral norm of a matrix with independent sub-Gaussian entries. We recall the definition of a sub-Gaussian random vector.

Definition 2.2 (Sub-Gaussian Distribution). Let n be a positive integer, and x a (discrete or continuous) random vector over R n . We say that x is sub-Gaussian with sub-Gaussian moment s if for all unit vector u ∈ R n and all t ∈ R, we have E[exp(t ⟨x , u⟩)] ≤ e s 2 t 2 /2 . Lemma 2.4 ([Ver12]). Let ℓ, m be two positive integers, and P a sub-Gaussian distribution of moment s. There exists a universal constant C > 0 such that for all t > 0,

P U← P ℓ×m [∥U∥ 2 ≥ Cs( √ ℓ + √ m + t)] ≤ 2e -πt 2 .
By noticing that P = U ([-1, 1]) is sub-Gaussian with moment 2/3, we can bound the spectral norm of ternary uniform matrix by C 2/3( √ ℓ + √ m + t) except with probability 2e -πt 2 , for some constant C > 0 that does not depend on the dimensions. We can verify experimentally that in this case C 2/3 ≤ 1, and we thus omit it in the rest of the paper for clarity. The security proof of our signature requires a bound on ∥Um∥ 2 for an arbitrary message m ∈ {0, 1} m and uniform ternary U. When m is small, Lemma 2.4 gives a close to optimal bound by ∥Um∥ 2 ≤ ∥U∥ 2 √ m. However, when m is large, we expect a tighter bound. By using the fact that square sub-Gaussian random variables are sub-exponential and tail bounds on sub-exponential distributions, we get the following lemma. The proof and associated definitions are provided in Appendix A.

Lemma 2.5. Let ℓ, m be two positive integers and x > 0. We assume that ℓ > x• 10/ log 2 e. Let m ∈ {0, 1} m . We have

P U← U ([-1,1]) ℓ×m [∥Um∥ 2 ≥ 2 √ ℓm] ≤ 2 -x .
In our situation, x = Θ(λ) with λ the security parameter, and ℓ = O(n log 2 q + ω(log 2 λ)). The condition ℓ > 10x/ log 2 e is then verified. Note that this condition is necessary only to obtain the simple bound 2 √ ℓm with probability 2 -x , but one could use a different bound or different probability to avoid this condition. Combining both lemmas gives the following

P U← U ([-1,1] ℓ×m ) [∥Um∥ 2 ≥ min(2 √ ℓ, √ ℓ + √ m + t) √ m] ≤ 2 -2λ + 2e -πt 2 , (3)
whenever ℓ ≥ 20λ/ log 2 e which is the case in our context. The spectral bound of Lemma 2.4 is also necessary to set the correct parameters to sample Gaussian vectors v verifying [A|τ G -AR]v = u, where A is a uniform matrix, R a short random matrix and G the gadget matrix of [MP12] used for efficient pre-image sampling. Our signature uses the following pre-image sampling algorithm.

Lemma 2.6 ([MP12]

). There exists an algorithm SampleD that takes as input a trapdoor matrix R ∈ Z m1×n⌈log 2 q⌉ , a partial parity-check matrix A ∈ Z n×m1 q , an invertible tag matrix H ∈ Z n×n q , a syndrome u ∈ Z n q and a standard de-

viation σ ≥ η ε (Z) √ 7 1 + ∥R∥ 2 2
, and that outputs v that is statistically close to

D Z m 1 +n⌈log 2 q⌉ ,σ conditioned on [A|HG -AR]v = u mod q, with G = I n ⊗ g and g = [1 . . . 2 ⌈log 2 q⌉-1 ].

Hardness Assumption

The security of our signature scheme relies on the Short Integer Solution (SIS) problem [Ajt96], which we recall here.

Definition 2.3 (Short Integer Solution). Let n, m, q be positive integers, and

β 2 ≥ β ∞ ≥ 1. The Short Integer Solution problem SIS ∞,2
n,m,q,β∞,β2 asks to find x ∈ L ⊥ q (A)\{0} given A ← U (Z n×m q

) such that ∥x∥ ∞ ≤ β ∞ and ∥x∥ 2 ≤ β 2 .

Note that the original formulation of SIS considers a single bound β on the ℓ 2 norm. There is a trivial reduction from the latter to SIS ∞,2 n,m,q,β∞,β2 by setting β = min(β ∞ √ m, β 2 ). As discussed by Micciancio and Peikert [MP13, Thm. 1.1], using both norm bounds leads to more precise hardness results, and sometimes smaller approximation factors when relating the problem to worst-case problems on lattices. Moreover, it seems to be relevant for the concrete hardness of the problem as well. Indeed, most lattice reduction algorithms aim at finding vectors in the ball of radius β 2 but without constraining the magnitude of the coefficients. Finding a lattice vector in the intersection of the ball of radius β 2 and the hypercube of half side β ∞ is at least as hard as the same task without the β ∞ bound. When β ∞ ≪ β 2 , it may even be substantially harder.

Signature Scheme

A signature scheme is defined by four algorithms. The Setup algorithm is a probabilistic algorithm that, on input a security parameter λ, outputs the public parameters pp that will be common to all users. The key generation algorithm KeyGen is a probabilistic algorithm that, on input pp, outputs a secret signing key sk and a public verification key pk. The signing algorithm Sign is a probabilistic algorithm which, on inputs sk and a message m (and pk, pp), outputs a signature sig. Finally, the verification algorithm Verify is a deterministic algorithm that, on inputs pk, m, sig (and pp), outputs 1 if sig is a valid signature on m under pk, and 0 otherwise. We use the Existential Unforgeability against Chosen Message Attacks (EUF-CMA) security model, which we formally recall in Appendix B along with the security proofs of our signature scheme.

A Lattice-Based Signature Scheme

We present here our signature scheme which interfaces smoothly with privacyenhancing protocols. It provides an alternative to the only such scheme based on lattices due to Libert et al. [LLM + 16].

One of the main differences between their construction and ours is that we aim at optimizing the interactions between the commitment scheme implicitly used by such kind of protocols and the signature scheme itself. In [LLM + 16], the public parameters of these two components were generated independently. We depart completely from this approach by generating these parameters conjointly and even by using a common matrix A for these two parts. Besides the natural gain in the public key size, this strategy allows one to merge different components of the signature itself. In particular, compared to [LLM + 16], our signature no longer has to include the commitment opening, which significantly reduces its size.

Obviously, this has important consequences on the design of the scheme itself. One of them is that it forbids to re-use the approach of [LLM + 16], inherited from Boyen signature [Boy10], where A was generated together with a trapdoor, because it would clearly break the hiding property of the commitment scheme. We instead rely on a G-trapdoor R of size m 1 × m 2 in the sense of [MP12] and then use a matrix [A|τ G -AR] where τ is a tag from Z × q . We can therefore generate A as a random matrix7 of size n × m 1 , where m 1 is the dimension of the commitment randomness. We then use it to construct the commitment c to a message m ∈ {0, 1} m3 as c = Ar + Dm mod q, where D is a random matrix of size n × m 3 and m 3 is the dimension of the message. The randomness r can then be merged with the short vector v generated thanks to the trapdoor, as mentioned above.

In [LLM + 16], the authors had to first compute a binary decomposition c ′ of the commitment c to the message before generating a short pre-image of u + Dc ′ where u (resp. D) was some public vector (resp. matrix). This might look harmless when we only consider the signature because it does not increase its size. However, when plugged in the Yang et al. ZK framework [YAZ + 19] this replaces one secret vector c by log 2 q ones and makes the overall statement to prove more complex 8 . To remove this binary decomposition we revisit the security proof and show how to avoid it by using an argument based on the Rényi Divergence. Additionally, this change seems necessary to extend our construction to polynomial rings, as described in Section 3.3.

More generally, all the modifications we introduce have a second positive effect on complexity. In both our security proof and the one of [LLM + 16], it is necessary to generate the public matrices with hidden relations, usually by multiplying one by some low-norm matrix U to generate the other. This impacts the norm of the extracted solutions, which grows with the number of such matrices and computational steps, and therefore impacts the system parameters. By reusing A for different purposes and by removing some computational steps (e.g., multiplication by D), we significantly reduce the discrepancy between the adversary output and the resulting SIS solution, leading to much better parameters.

Description of the Signature

We now describe the four algorithms that define our signature scheme. The signature is designed to sign a binary message m. We present our scheme for the more general case of a message with variable length m 3 rather than a variable number of blocks of fixed length which may require unnecessary padding. Except for m 3 which is chosen depending on the use case, the other parameters are determined by the correctness and security analysis of the scheme, which are the object of Lemmas 3.1, 3.2, and 3.3.

Algorithm 3.1: Setup Input: Security parameter λ.

1. Select a positive integer n. ▷ SIS dimension driving security 2. Select a prime integer q.

▷ modulus driving security 3. Select a positive integer Q ≤ q ′ ≤ q.

▷ Bound on tags 4. T ← Z q ′ \ {0}.

▷ Tag space 5. Select f (λ) ← ω(log 2 λ).

▷ Leftover Hash Lemma slack 6. m1 ← ⌈(n log 2 q + f (λ))/ log 2 3⌉.

▷ Commitment randomness dimension 7. m2 ← n⌈log 2 q⌉. 8. m ← m1 + m2. ▷ Signature dimension 9. Choose a positive integer m3. ▷ Maximum bit-size of m 10. g ← [2 0 | . . . |2 ⌈log 2 q⌉-1 ] ∈ Z 1×⌈log 2 q⌉ q . ▷ Gadget vector 11. r ← ηε(Z). ▷ r = 5.4 leads to ε ≈ 2 -131 12. Select t > 0. ▷ Spectral norm slack (Equation (3)) 13. σ ← r √ 7 ( √ m1 + √ m2 + t) 2 + 1. ▷ Preimage sampling width 14. σ2 ← max m3 min(2 √ m1, √ m1 + √ m2 + t) 2 -σ 2 , ω( log 2 m1) . 15. σ1 ← σ 2 + σ 2 2 . 16. D ← U (Z n×m 3 q ).
▷ Message commitment key Output: pp = (D; g; λ, n, m1, m2, m3, q, σ, σ2, σ1).

8 Considering a binary tag also leads to similar inefficiencies Algorithm 3.2: KeyGen Input: Public parameters pp as in Algorithm 3.1.

1. A ← U (Z n×m 1 q ). 2. R ← U ([-1, 1] m 1 ×m 2 ). 3. B ← AR mod q ∈ Z n×m 2 q . 4. u ← U (Z n q ). Output: pk = (A, B, u), and sk = R. Algorithm 3.3: Sign Input: Signing key sk, Message m ∈ {0, 1} m 3 , Public key pk, Public Param. pp, State st. 1. r ← D Z m 1 ,σ 2 . 2. c ← Ar + Dm mod q. ▷ Commitment to m 3. τ ← F (st). ▷ τ ∈ T 4. v ← SampleD(R, A, τ In, u + c, σ) -[r T |0m 2 ] T . ▷ Aτ = [A|τ (In ⊗ g) -B] 5. st ← st + 1. Output: sig = (τ, v). Algorithm 3.4: Verify Input: Public key pk, Message m ∈ {0, 1} m 3 , Signature sig, Public Param. pp. 1. Aτ ← [A|τ (In ⊗ g) -B] ∈ Z n×m q . 2. Split v into [v T 1 |v T 2 ] T , with v1 ∈ Z m 1 , v2 ∈ Z m 2 . 3. b ← (Aτ v = u + Dm mod q) ∧ (∥v1∥ ∞ ≤ σ1 log 2 m1) ∧ (∥v2∥ ∞ ≤ σ log 2 m2) ∧ (τ ∈ T ) Output: b. ▷ b = 1 if valid, 0 otherwise
The correctness of the signature scheme simply relies on the sum of discrete Gaussians (Lemma 2.2) and the Gaussian tail bound (Lemma 2.3). The former guarantees that v 1 is statistically close to D Z m 1 ,σ1 , and the latter ensures that for an honest signature it holds that ∥v 1 ∥ ∞ ≤ σ 1 log 2 m 1 , and ∥v 2 ∥ ∞ ≤ σ log 2 m 2 with overwhelming probability.

Lemma 3.1 (Correctness). The signature scheme of Algorithms 3.1, 3.2, 3.3, and 3.4 is correct with negligible correctness error.

Proof. Let pp ← Setup(1 λ ), (pk, sk) = ((A, B, u), R) ← KeyGen(pp). Let m ∈ {0, 1} m3 and (τ, v) ← Sign(sk, m, pk, pp, st). Then, there exists a vector r ∈ Z m1 drawn from D Z m 1 ,σ2 such that v = v ′ -[r T |0] T , where v ′ was obtained from SampleD(R, A, τ I n , u + Ar + Dm mod q, σ). By Lemma 2.6, it holds that [A|τ (I n ⊗ g) -B]v = [A|τ (I n ⊗ g) -B]v ′ -Ar = u + Ar + Dm -Ar mod q = u + Dm mod q.
Then, also by Lemma 2.6, it holds that v ′ is statistically close to

D Z m 1 +m 2 ,σ conditioned on A τ v ′ = u + Ar + Dm mod q. Hence, by Lemma 2.2, v is statistically close to D Z m 1 +m 2 ,S conditioned on A τ v = u + Dm mod q and where S = diag( σ 2 + σ 2 2 I m1 , σI m2 ) = diag(σ 1 I m1 , σI m2 ).
Finally, applying Lemma 2.3 yields the bounds on ∥v 1 ∥ ∞ and ∥v 2 ∥ ∞ . It gives that b = 1 except with negligible probability as claimed.

Note that the randomness r used to commit to the message can be drawn from a Gaussian with any width σ 2 > 0. However, the security proofs require σ 1 to be at least min(2

√ m 1 , √ m 1 + √ m 3 +t)
√ m 3 in order to hide the shifted center of the Gaussian vector, which in turns restricts the value of σ 2 . Additionally, the goal of this signature scheme being to allow signing on committed messages, σ 2 must be chosen so that the commitment scheme is statistically hiding, which is why we take it at least ω( log 2 m 1 ). We present our signature scheme in the most general way, thus explaining the multitude of dimensions m i and Gaussian widths σ i . This also allows fine-tuning of the parameters depending on the specific application. Typically, an application requiring to sign only small messages of constant bit-size m 3 would be able to select a much smaller σ 1 and would then yield smaller signatures.

We also point out the fact that we express the shortness condition on v in the ℓ ∞ norm. This is due to the fact that the zero-knowledge argument framework from [YAZ + 19] that we consider to prove possession of a message-signature pair allows one to prove bounds on the coefficients more naturally. As a result, we can base the security of our signature scheme on SIS ∞,2 which is at least as hard as SIS 2 as explained in Section 2.3.

An example parameter set, also taking into account the requirements of Sections 4 and 5, can be found in Appendix H, Table H.2. The scheme can also be instantiated as a standalone signature, without considering the efficient protocols and zero-knowledge proof systems. This would allow one to reduce the size of q, but at the expense of increasing n to achieve the same security, which in the end leads to similar signature and key sizes.

Remark 3.1. As discussed in Section 1, we choose to describe a stateful version of our construction that better suits our applications, hence the fact that our tags τ are generated as F (st). The only requirements placed on F are that it must be injective, with outputs in the tag space, which should easily be met in practice. For example, in the case of group signatures, one can proceed as in [dPLS18] and set the tags as the group members' identities. Nevertheless, if selecting such a function F proved to be difficult for some use case, we recall that a stateless version of our construction is provided in Appendix G.

Security of the Signature

We distinguish two types of forgeries that an attacker can produce, which we treat separately for the sake of clarity. More precisely we distinguish between the cases depending on whether or not the tag τ * of the forgery has been reused from the signature queries. Combining the corresponding lemmas proves the EUF-CMA security of the signature under the SIS assumption. It consists in the SIS challenger tossing a coin and proceeding as in either Lemma 3.2 or 3.3 and aborting if the forgery does not match the coin toss. The proofs are provided in Appendix B.2 and B.3 for completeness.

Lemma 3.2. An adversary produces a Type I forgery (τ * , v * ) if the tag τ * does not collide with the tags of the signing queries. If an adversary can produce a Type I forgery with advantage δ, then we can construct an adversary B that solves the SIS ∞,2 n,m1+1,q,β∞,β2 problem with advantage Adv

[B] ≳ δ/(|T | -Q), for    β ∞ = σ 1 log 2 m 1 + m 2 σ log 2 m 2 + m 3 β 2 = 1 + ( √ m 1 + √ m 2 + t) 2 • m 1 (σ 1 log 2 m 1 ) 2 + m 2 (σ log 2 m 2 ) 2 + min(2 √ m 1 , √ m 1 + √ m 3 + t) √ m 3 + 1. Lemma 3.3. An adversary produces a Type II forgery (τ * , v * ) if the tag τ * is re-used from some i * -th signing query (τ (i * ) , v (i * ) ), i.e., τ * = τ (i * )
. If an adversary can produce a Type II forgery with advantage δ,

we can construct B solving SIS ∞,2 n,m1,q,β ′ ∞ ,β ′ 2 with advantage Adv[B] ≳ δ α * /(α * -1) e -α * π Q , for      β ′ ∞ = 2σ 1 log 2 m 1 + m 2 • 2σ log 2 m 2 + m 3 β ′ 2 = 1 + ( √ m 1 + √ m 2 + t) 2 • σ 2 1 m 1 (1 + log 2 2 m 1 ) + σ 2 m 2 (1 + log 2 2 m 2 ) + min(2 √ m 1 , √ m 1 + √ m 3 + t) √ m 3 .
and where α * = 1 + log 2 (1/δ)/(π log 2 e).

Our Signature on Modules

The results of Table 1.1 show that the performances of the signature scheme from Section 3.1 and associated protocols are greatly improved over [LLM + 16]. However, the complexity is still rather high and we therefore investigate in this section a way to decrease it. Concretely, we show that the signature scheme from Section 3.1 can be extended over the ring of integers of a number field.

For the zero-knowledge arguments required by the efficient protocols, we employ the recent framework from [LNP22], which we detail in Section 4.3. We use a tag space that corresponds to the identity space of their group signature construction. We also use a message space that is similar to the latter but with no restriction on the number of non-zero coefficients. We present our construction with a single power-of-two cyclotomic ring, but we note that it can be adapted to use subrings for efficiency gains. For more details on the use of subrings, we refer to [LNPS21,LNP22]. In what follows, we take n a power of two and R the 2n-th cyclotomic ring, i.e., R = Z[X]/⟨X n + 1⟩. We also define R q = Z q [X]/⟨X n + 1⟩ for any modulus q ≥ 2. We call θ the coefficient embedding of R, i.e., for all r

= i∈[0,n-1] r i X i ∈ R, θ(r) = [r 0 . . . r n-1 ] T . We then define S bin = θ -1 ({0, 1} n ) and S 1 = θ -1 ({-1, 0, 1} n ).
We also define the usual norms ∥•∥ p over R by ∥r∥ p := ∥θ(r)∥ p . Finally, we define the discrete Gaussian distribution over R by θ -1 (D θ(R),σ ), which we denote by D R,σ .

Remark 3.2. The Gaussian distributions are defined with respect to the coefficient embedding θ. Theoretical works usually define Gaussian distributions with respect to the Minkowski embedding (or canonical embedding) σ H . We refer to [LPR13] for more details. In our specific case of power-of-two cyclotomic rings, it holds that σ H = √ nPθ where P is a unitary matrix. Hence, by denoting

D θ R,σ (resp. D σ H R,σ ) the Gaussian distribution with respect to θ (resp. σ H ), we can show that D σ H R,σ √
n is exactly the same distribution as D θ R,σ .

3.3.1 Description. Our module signature scheme is described by Algorithms 3.5, 3.6, 3.7 and 3.8.

Algorithm 3.5: Setup Input: Security parameter λ.

1. Select a positive integer d. ▷ M-SIS rank driving security 2. Select k ≤ n to be a power of two.

▷ Number of splitting factors 3. Select a prime integer q such that q = 2k + 1 mod 4k and q ≥ (2

√ k) k . 4. Select positive integers w, κ. ▷ w such that n w ≥ Q 5. Tw ← {τ ∈ S bin : ∥τ ∥ 2 = √ w}. ▷ Tag space 6. g ← ⌈q 1/κ ⌋. 7. m1 ← ⌈(d log 2 q + f (λ))/ log 2 3⌉ ▷ f (λ) = ω(log 2 λ) 8. m2 ← dκ 9. m ← m1 + m2. ▷ Signature dimension 10. Choose a positive integer m3. ▷ Maximum bit-size of m is n • m3 11. g = [1 • • • g κ-1 ] ∈ R 1×κ q .
▷ Gadget vector 12. r ← ηε(Z).

▷ r = 5.4 leads to ε ≈ 2 -131 13. Select t > 0.

▷ Spectral norm slack 14. σ ← r g 2 + 1 (

√ nm1 + √ nm2 + t) 2 + 1. ▷ Pre-image sampling width 15. σ2 ← ( √ nm1 + √ nm3 + t) 2 • nm3 -σ 2 . ▷ Commitment randomness width 16. σ1 ← √ σ 2 + σ2 2 . 17. D ← U (R d×m 3 q ).
▷ Message Commitment Key Output: pp = (D; g; λ, n, d, m1, m2, m3, q, w, κ, σ, σ2, σ1).

Algorithm 3.6: KeyGen

Input: Public parameters pp as in Algorithm 3.5.

1. A ← U (R d×m 1 q ). 2. R ← U (S m 1 ×m 2 1 ). 3. B ← AR mod qR ∈ R d×m 2 q . 4. u ← U (R d q ). Output: pk = (A, B, u), and sk = R. Algorithm 3.7: Sign Input: Signing key sk, Message m ∈ S m 3 bin , Public key pk, Public Parameters pp, State st 1. r ← D R m 1 ,σ 2 . 2. c ← Ar + Dm mod qR. ▷ Commitment to m 3. τ ← F (st). ▷ τ ∈ Tw 4. v ← SampleD(R, A, τ I d , u + c, σ) -[r T |0m 2 ] T . ▷ Aτ = [A|τ (I d ⊗ g) -B] 5. st ← st + 1. Output: sig = (τ, v). Algorithm 3.8: Verify Input: Public key pk, Message m ∈ S m 3 bin , Signature sig, Public Parameters pp. 1. Aτ ← [A|τ (I d ⊗ g) -B] ∈ R d×m q . 2. b ← (Aτ v = u + Dm mod qR) ∧ (∥v∥ 2 ≤ σ 2 1 nm1 + σ 2 nm2) ∧ (τ ∈ Tw) Output: b. ▷ b = 1 if valid, 0 otherwise
3.3.2 Security Analysis. The security of the scheme is now based on the problem M-SIS d,m1,q,β . It asks to find w ∈ R m1 such that Aw = 0 mod qR and 0

< ∥w∥ 2 ≤ β given A ← U (R d×m1 q
). The security proofs rigorously follow that of Lemma 3.2 and 3.3. This is due to the fact that all the tools that we use have a ring counterpart. We briefly explain what tools are needed to carry out the proofs in the module case. We stress that the construction can also be used over rings (d = 1).

First, we need to ensure that a difference of distinct tags is invertible in

R q . By [LS18, Cor. 1.2], when q = 2k + 1 mod 4k, a ring element r is invertible in R q if 0 < ∥r∥ ∞ ≤ q 1/k / √ k. We chose q so that a difference of tags τ 1 -τ 2 has ℓ ∞ norm at most 2 ≤ q 1/k / √ k. Hence, a difference of distinct tags is in R × q .
Then, the leftover hash lemma of Lemma 2.1 has been adapted to general rings of integer by Boudgoust et al. and further generalized in [BJRW23]. We state it here for our specific usage in power-of-two cyclotomic rings.

Lemma 3.4 ([BJRW23, Lem. 2.8]). Let R = Z[X]/⟨X n + 1⟩
with n a power of two, and d, m, q be positive integers with q prime. Then, ∆((A, As), (A, u))

≤ 1 2 (1 + q d /3 m ) n -1, where A ∼ U (R d×m q ), s ∼ U (S d 1 ) and u ∼ U (R d q )
. The use of the Rényi divergence in the proof of Lemma 3.3 applies on the discrete Gaussian distributions, which are defined by their embedding to R n . As such, the argument remains unchanged. We also need to argue that for A ←

U (R d×m1+m2 q ) and v ← D R m 1 +m 2 ,Σ with Σ = σ 1 I nm1 0 0 σI nm2 , then u =
Av mod q is close to uniform. For that, we use [LPR13, Thm. 7.4] which states that if σ, σ 1 ≥ 2nq (d+2/n)/(m1+m2) , then the public syndrome u is close to uniform in R d q . We note that this results holds when the Gaussian over R is defined with respect to the Minkowski embedding. As explained in Remark 3.2, in the case of our Gaussian distributions, we only need

σ, σ 1 ≥ 2 √ nq d+2/n m 1 +m 2 . Since m 1 + m 2 ≥ d(log 2 (q)/ log 2 (3) + κ) + f (λ)/ log 2 (3), the result holds when- ever σ, σ 1 ≥ 3 1+2/n • 2
√ n, which is the case in our context. Finally, we need to bound the spectral norm of structured matrices that are of size nm 1 ×nm 2 (or nm 1 ×nm 3 ). In power-of-two cyclotomic rings, the structured matrix considered is a block matrix whose blocks are nega-circulant matrices of size n × n. The entries are thus all distributed according to U ([-1, 1]) but they are not all independent within a block. This means we cannot apply Lemma 2.4 directly. The spectral norm of such a structured matrix of size nm 1 × nm 2 is proven to be the maximal spectral norm of the n complex-embedded matrices of size m 1 × m 2 [BJRW23, Lem. 2.3], which all have i.i.d. entries that are sub-Gaussian of moment 2n/3. Applying Lemma 2.4 to these embedded matrices with the union bound (on half the complex embeddings) gives

P R← S m 1 ×m 2 1 [∥R∥ 2 ≥ C 2n/3( √ m 1 + √ m 2 + t)] ≤ ne -πt 2 ,
for an absolute constant C > 0. Although this bound is proven, we can verify experimentally that it is not tight, and rather that the original bound (when there is no structure) of √ nm 1 + √ nm 2 + t for a small t (typically 6 -7) is satisfied with overwhelming probability. Further, we use the latter bound for setting parameters in the description of the signature.

Lemma 3.5. If an adversary can produce a Type I forgery with advantage δ, then we can construct B that solves M-SIS 2 d,m1+1,q,β with advantage Adv

[B] ≳ δ/(|T w | -Q), for β = 1 + ( √ nm 1 + √ nm 2 + t) 2 σ 2 1 nm 1 + σ 2 nm 2 + ( √ nm 1 + √ nm 3 + t) √ nm 3 + 1.
Lemma 3.6. If an adversary can produce a Type II forgery with advantage δ, we can construct B that solves the M-SIS 2 d,m1,q,β ′ problem with advantage

Adv[B] ≳ δ α * /(α * -1) e -α * π Q , for β ′ = 1 + ( √ nm 1 + √ nm 2 + t) 2 • 2σ 2 1 nm 1 + 2σ 2 nm 2 + ( √ nm 1 + √ nm 3 + t) √ nm 3 ,
and where α * is defined by α * = 1 + log 2 (1/δ)/(π log 2 e).

Zero-Knowledge Arguments of Knowledge

We now detail out the zero-knowledge arguments of knowledge (ZKAoK) that we use to instantiate the protocols from Section 5. Since we propose a construction over Z q and another over structured lattices, we employ the frameworks from [YAZ + 19] and [LNP22] respectively to tackle the relations to be proven. We first discuss some aspects of the former, and later explain in Section 4.3 how to use both frameworks to instantiate the necessary relations.

A Framework for Quadratic Relations over Z q

Our construction requires a proof system that handles exact quadratic relations, over Z q for our first construction and another framework over R q for our structured variant. Let us first focus on the former. To handle such relations, we could have used Stern-like protocols but this would only reach constant soundness error, thus implying a large number of repetitions and hence bad performance. Additionally, the decomposition-extension methods used in the original scheme [LLM + 16] make the relation to be proven much larger.

R * = {((A, y, M); x) ∈(Z k×Lx q × Z k q × ([Lx] 3 ) L M ) × Z Lx q : Ax = y mod q ∧ ∀(h, i, j) ∈ M, x[h] = x[i] • x[j] mod q}.
This relation can be used to prove that the witness vector is short, which we need for our verification equation for example. Concretely, any witness x ∈ Z q that we need to prove smaller than some bound B is decomposed as x 1 , . . . , x ℓ , where ℓ = ⌈log 2 B⌉, which are proved binary using the quadratic relation x 2 i = x i mod q. The downside of this approach is that it adds ℓ witnesses for each short element, which quickly becomes cumbersome. To address this issue, the authors of [YAZ + 19] introduced a so-called fast mode that significantly reduces the size of the witness. We describe such a mode in Section 4.2 but also show that its analysis in [YAZ + 19] is not entirely correct and thus provide a more thorough one. We also propose additional optimizations in Appendix E.

Zero-Knowledge Fast Mode Revisited

As explained above, the decomposition technique entails a (ℓ+1)-fold increase of the witness, which is prohibitive for high-dimensional vectors. This has led the authors of [YAZ + 19] to sketch a so-called fast mode to obtain drastic efficiency gains in this case. The idea is to relax the zero-knowledge argument, thus introducing a soundness gap, and prove knowledge of a solution w ′ of Pw ′ = v mod q such that w ′ is nB-bounded instead of B-bounded, where n is the dimension of w. More precisely, they consider the following relation

R ′ = {((P, v, H, c), (w, u, r)) ∈ (Z m×n q × Z m q × [0, 1] λ×n × C) × (Z n q × [0, nB] λ × R) : Pw = v mod q ∧ Hw -u = 0 mod q ∧ c = Commit(w; r)}
The point is that the prover now only has to prove a bound on the λ elements of u instead of the n elements from w, which is very interesting when λ ≪ n, a condition easily met in practice. The authors argue that, if one knows a witness (w, u, r) satisfying R ′ , it ensures that w is in [0, nB] n , except with negligible probability over the randomness of H. We provide a simple counter-example to the above. For example, assume a prover knows w = [-1, 1, . . . , 1] T such that Pw = v mod q. We now consider H to be a random matrix whose entries are independently distributed according to U ({0, 1}). We denote by

h i the i-th row of H for i ∈ [λ]. For all i ∈ [λ], we have P hi [h T i w ∈ [0, nB]] = 1 -2 -n by simply conditioning on the first coefficient of h i . It yields P H [Hw ∈ [0, nB] λ ] = (1 -2 -n ) λ ≥ 1 -λ2 -n .
Since the fast mode is only relevant when n ≥ λ, it holds that Hw ∈ [0, nB] λ with overwhelming probability. This shows that R ′ cannot be used to prove that w has non-negative coefficients and thus for example invalidates the use of the fast mode in the e-cash use-case in [YAZ + 19].

Fortunately, a more thorough analysis shows that Hw mod q is in [0, B] λ implies that w mod q ∈ [-2B, 2B] n with high probability, which would be sufficient in our case as we only need to prove bounds on the ℓ ∞ norm. However, we have so far only discussed of soundness. When it comes to correctness, we note that the choices made in [YAZ + 19] results in an unwieldy situation.

First, because one has to set an upper bound on Hw that will be satisfied with high probability for any w in [-B, B] n . For a binary matrix H, it seems hard to do much better than [-nB, nB] λ since we will be close to this bound for w = [B, . . . , B] T , hence the factor n in the soudness gap mentioned above.

Second, because one cannot start the argument with w ∈ [-B, B] n as it can lead to having Hw with negative coefficients. One must shift all the coefficients of w before running the protocol, but it results in a skewed statement on w. Indeed, it would prove that w + B1 n is in [-2nB, 2nB] n and therefore that w ∈ [-(2n + 1)B, (2n -1)B] n , where

1 n = [1 . . . 1] T ∈ Z n .
For these reasons, we believe it is much more natural to sample the coefficients of H uniformly from {-1, 0, 1}. We prove below that Hw mod q is in [-B, B] λ still implies that w mod q ∈ [-2B, 2B] n , which avoids to shift the witness and thus the problem mentioned above. Moreover, such distribution of H allows us to derive much better upper bounds on Hw using for example an argument similar to the one of lemma 2.5. However, we do not study more thoroughly this general problem as we are able to derive sharp bounds for our specific use case (see remark 4.1 below). More formally, let H ∈ [-1, 1] k×n , with k = λ/ log 2 (9/5). The following lemma, proven in Appendix D, argues that Hw mod q ∈ [-B, B] k implies w mod q ∈ [-2B, 2B] n with overwhelming probability over the choice of H. Lemma 4.1. Let B ∈ Z be such that 6B < q/2. Let k be a positive integer. Let w ∈ Z n be a vector. Assuming that ∥w mod q∥ ∞ > 2B, it then holds that

P H← U ([-1,1] k×n ) [∥Hw mod q∥ ∞ ≤ B] ≤ (5/9) k .
The fast mode that we consider now corresponds to the following relation, where B is chosen so that ∥Hw mod q∥ ∞ ≤ B with overwhelming probability for an honest witness w.

R ′′ ={((P, v, H, c), (w, u, r)) ∈ (Z m×n q × Z m q × [-1, 1] k×n × C)× (Z n q × [-B, B] k × R) : Pw = v mod q ∧ Hw -u = 0 mod q ∧ c = Commit(w; r)}
Remark 4.1. For our relations, the vectors that we need to prove short are sampled from discrete Gaussian distributions. For example the vector

v 1 fol- lows D Z m 1 ,σ1 . For a fixed H ∈ {-1, 0, 1} k×m1 , the third statement of Lemma 2.3 yields that P v1 [|⟨v 1 , h i ⟩| ≥ σ 1 t √ m 1 ] ≤ P v1 [|⟨v 1 , h i ⟩| ≥ σ 1 t∥h i ∥ 2 ] ≤ 2e -πt 2 ,
where h i is the i-th row of H and the first inequality follows by event inclusion as

∥h i ∥ 2 ≤ √ m 1 . The union bound yields P v1 [∥Hv∥ ∞ ≥ σ 1 t √ m 1 ] ≤ 2ke -πt 2 ,
where k = λ/ log 2 (9/5) as per Lemma 4.1. Hence, taking t = log 2 λ gives that ∥Hv∥ ∞ ≤ σ 1 √ m 1 log 2 λ with overwhelming probability. This improves on the trivial bound σ 1 m 1 log 2 m 1 . By making sure that 2σ 1 √ m 1 log 2 λ < (q -1)/2, which is generally the case, we have no wrap-around modulo q in Hv 1 and therefore

∥Hv 1 mod q∥ ∞ ≤ σ 1 √ m 1 log 2 λ. The conditions of Lemma 4.1 allow one to choose B = σ 1 √ m 1 log 2 λ ≪ q/12. Then, proving that ∥Hv 1 mod q∥ ∞ ≤ σ 1 √ m 1 log 2 λ implies that ∥v 1 mod q∥ ∞ ≤ 2σ 1 √ m 1 log 2 λ.

Zero-Knowledge Arguments and Relations

The zero-knowledge framework from [YAZ + 19] allows to prove quadratic relations over Z q . The protocols accompanying our signature that we present in Section 5 require a proof system to prove knowledge of a commitment opening, and to prove knowledge of a message-signature pair, which are both quadratic relations. At a high level, the commitment opening proof requires to prove a linear relation and that the witness is short. As explained when describing R * , the latter can be dealt with by decomposing each entry in a binary vector, and proving that the latter indeed has binary coefficients. Similarly, proving knowledge of (m, τ, v) such that Verify(pk, m, (τ, v), pp) = 1, requires proving that some elements have small magnitude, and that Av 1 -Bv 2 + τ Gv 2 = u + Dm mod q which is quadratic because of the term τ v 2 . Due to lack of space, we defer to Appendix F the details on how to use the framework of [YAZ + 19] to instantiate them.

We however give more details for our construction over structured lattices. Although the framework of [YAZ + 19] straightforwardly adapts to the ring or module setting, it results in relations of the form Ax = y mod qR and x[h] = x[i]x[j] mod qR. In our case, we aim to prove that the witness is short (or binary for the message part) with respect to the coefficient embedding of R. Taking the example of the message, m[i] = m[i] 2 mod qR does not imply that the coefficients of the polynomial m[i] are binary, but only that the number theoretic transform (NTT) of m[i] is a binary vector. A naive alternative would be to embed the entire relation into Z via the coefficient embedding and applying [YAZ + 19] in a non-structured way. This would indeed prove the desired relation but it would also ignore the underlying structure and all the optimizations that come with it. Instead, we use the very recent framework by Lyubashevsky,Nguyen and Plançon [LNP22], which generalizes the previous work of [BLS19] and [ENS20] used to obtain exact proofs. The advantage of this framework is that it provides a way to prove bounds on the ℓ 2 norm of the witness without resorting to bounds on the ℓ ∞ norm. As explained in [LNP22], this leads to proving tighter bounds on the ℓ 2 norm, and in a more efficient way as a result. We denote by σ -1 to be the automorphism of R q that can be defined as σ -1 (

n-1 i=0 r i X i ) = r 0 - n-1 i=1 r i X n-i .
Their proof system allows one to prove relations of the form

   ∀i ∈ [ρ], f i (s) = 0 mod qR ∀i ∈ [v e ], E (e)
i su

(e) i 2 ≤ β (e) i ∀i ∈ [ρ eval ], F i (s) = 0 ∀i ∈ [v a ], E (a) i s -u (a) i ∞ ≤ β (a) i ,
where the f i , F i are quadratic functions in s = [s T 1 , σ -1 (s 1 ) T ] T (s 1 being the committed vector), and F i (s) denotes the constant coefficient of the polynomial F i (s). The norm conditions with superscript (e) are proven exactly, while those with superscript (a) are proven approximately. We note for completeness that the considered automorphism is not necessarily σ -1 . We present here how our relations can be instantiated in their framework, which consists in describing the functions f i , F i and matrices and vectors for the norm conditions.

Let q 1 < q be a prime integer such that q 1 = 2k + 1 mod 4k, and define q π = q 1 q as the modulus of the proof system, which is different from the modulus of our signature. We take q 1 having the same splitting as q in R to ensure the invertibility of challenge differences in R qπ as discussed in [LNP22, Sec. 2.3].

Proof of Commitment Opening. Consider the relation

q 1 (Ar ′ + Dm) = q 1 c mod q π R ∧ ∥r ′ ∥ 2 ≤ σ 3 √ nm 1 =: α 3 ∧ m ∈ S m3
bin , where the private input is r ′ , m and the public input is A, D, c. We multiply the linear equation by q 1 to work with the proof system modulus. We now instantiate this relation in the framework of [LNP22]. Using the notations of [LNP22], we define

s 1 = [r ′ |m] ∈ R m1+m3 and s = [s 1 |σ -1 (s 1 )] ∈ R 2(m1+m3) . Quadratic Equations: Define f i (s) = (e T i [q 1 A|q 1 D|0 d×m1+m3 ]) • s + (-e T i q 1 c) for all i ∈ [d]
, where e i is the zero vector with a 1 at position i. Then, proving

f i (s) = 0 mod q π R for all i ∈ [d] yields q 1 (Ar ′ + Dm) = q 1 c mod q π R. Quadratic Evaluations: We define r = j∈[0,n-1] X j . For all i ∈ [m 3 ], de- fine F i (s) = s T E 2m1+m3+i,m1+i s + (-re 2m1+m3+i ) T s = σ -1 (m[i])(m[i] -r),
where E k,ℓ denotes the zero matrix with a 1 at position (k, ℓ). Then, proving

F i (s) = 0 for all i ∈ [m 3 ] implies m ∈ S m3
bin . This relies on the fact that for m ∈ R, the constant coefficient of σ -1 (m)(m -r) is ⟨θ(m) , θ(m) -1 n ⟩. Then, proving that this inner product is 0 over Z is equivalent to proving that θ(m) ∈ {0, 1} n , i.e., m ∈ S bin . Norm Conditions: We define E (e) = [I m1 |0 m1×m1+2m3 ], u (e) = 0 m1 , and β (e) = α 3 . Then E (e) su (e) 2 ≤ β (e) is equivalent to ∥r ′ ∥ 2 ≤ α 3 . Remark 4.2. The above aims at proving the relation exactly. However, we note that the commitment scheme employed in [LNP22] already contains a part A 1 s 1 + A 2 s 2 . By setting the public matrices A 1 , A 2 as A, D respectively, s 2 = r ′ which is chosen from a Gaussian distribution, and s 1 = m, we can directly use the protocol of [LNP22, Fig. 8]. We simply have to set ∥s 1 ∥ 2 ≤ √ nm 3 =: α, and the quadratic evaluations as above to prove (exactly) that s 1 = m is indeed in S m3 bin . It then proves the correct statement but with a soundness gap on the norm of r ′ .

Proof of Message-Signature Pair Possession. Consider the relation

q 1 (Av 1 -Bv 2 + τ Gv 2 -Dm) = q 1 u mod q π R with ∥v∥ 2 ≤ σ 2 1 nm 1 + σ 2 nm 2 =: α ∧ m ∈ S m3 bin ∧ τ ∈ T w ,
where the private input is τ

, v = [v T Quadratic Equations: We define A ′ = q 1 [A| -B| -D|0 d×m1+m2+m3+2 ],
and for all i ∈ [d], we define

G i = q 1   0 (m1+m2+m3)×2(m1+m2+m3+1) 0 1×m1 e T i G 0 1×m1+m2+2(m3+1) 0 (m1+m2+m3+1)×2(m1+m2+m3+1)   . Then, for all i ∈ [d], define f i (s) = s T G i s+(e T i A ′ )s+(-q 1 e T i u). Proving f i (s) = 0 mod q π R for all i ∈ [d] yields q 1 (Av 1 -Bv 2 + τ Gv 2 -Dm) = q 1 u mod q π R. Quadratic Evaluations: We define r = j∈[0,n-1] X j . For all i ∈ [m 3 + 1], de- fine F i (s) = s T E 2(m1+m2)+m3+1+i,m1+m2+i s + (-re 2(m1+m2)+m3+1+i ) T s. We also define F m3+2 (s) = s T E 2(m1+m2+m3+1),m1+m2+m3+1 s -w = σ -1 (τ )τ -w. Proving F i (s) = 0 for i ∈ [m 3 ] is equivalent to m ∈ S m3
bin as before. Then, showing F m3+1 (s) = 0 proves τ ∈ S bin , while F m3+2 (s) = 0 proves that ∥τ ∥ 2 2 = ⟨θ(τ ) , θ(τ )⟩ = w, thus giving τ ∈ T w . Norm Conditions: We define E (e) = [I m1+m2 |0 m1+m2×m1+m2+2(m3+1) ], u (e) = 0 m1+m2 , and β (e) = α. Then E (e) su (e) 2 ≤ β (e) proves ∥v∥ 2 ≤ α.

Privacy-Preserving Protocols and Anonymous Credentials

The very purpose of a signature scheme with efficient protocols (SEP) is to be used as a building block for privacy-preserving primitives such as group signature, anonymous credentials or e-cash. For such applications, one usually needs (1) to get a signature on committed (hidden) messages and (2) to prove knowledge of a signature, without revealing it. This has led previous papers, e.g., [CL04,PS16,LLM + 16], providing such types of signatures to describe specific protocols addressing those needs. We here follow the same approach. More specifically, we give a first protocol in Section 5.1 which allows a signer to obliviously sign a message, by only knowing a commitment to the message. The second protocol, presented in Section 5.2, enables a user to prove the possession of a message-signature pair, where the signature has been obtained by the oblivious signing protocol. As in previous works, we do not identify any properties expected from such protocols nor prove any results regarding their security. As this might look unconventional, we need to recall a few facts about SEPs and their use in privacy-preserving applications. The use of signature schemes in the latter applications can be done based on formal generic frameworks, e.g., [BSZ05] for group signature or [BPS19] for e-cash, or on some rather common heuristics, e.g., for anonymous credentials [CL04]. In all cases, the point is that, in theory, no specific property is expected from the signatures beyond EUF-CMA security. Typically, [BSZ05] and [BPS19] consider standard digital signature schemes for their framework.

However, in practice, the use of any digital signature is likely to lead to a totally impractical construction because of the difficult interactions between general-purpose signatures and the other building blocks such as zero-knowledge proofs. This is where SEPs prove handy. They are specifically designed to smoothly interact with the other building blocks so as to optimize the efficiency of the resulting construction.

In this context, defining security notions that such protocols should achieve would be meaningless as no such formal properties are expected by the constructions using them. Worse, this is likely to lead to unnecessary complications as it is difficult to define a relevant security model for SEPs. Typically, an SEP allows one to get a signature on hidden messages and then to prove knowledge of the message-signature pair. How to define a relevant security model in this context? Unforgeability indeed means the inability to produce a signature on new messages but here we do not know the messages requested by the adversary to the signing oracle and we do not know which message-signature pairs it is proving knowledge of. In other words, we cannot decide if the adversary won.

Libert et al [LLM + 16] circumvents this issue by forcing the user to provide an encryption of the messages in the blind issuance process. This does not address the problem of formalizing the properties expected from the protocols (1) and (2) of SEPs (and indeed [LLM + 16] does not define such properties) but this enables to provide some results regarding security as a reduction can recover all the messages it has signed (by decrypting the ciphertexts) and thus decide when a forgery occurs. Besides being unconventional (this led [LLM + 16] to prove "security" of the protocols without defining what "security" means), this approach complicates the protocols by adding this encryption step that is not necessary in most applications using such signatures. Indeed, in concrete applications, this problem is usually solved by other means. For example, in e-cash systems, "forgeries" can be detected by comparing the amount of withdrawn coins with the one of spent coins. In group signatures, there is an opening procedure that allows to trace back a group signature to a group member. This enables to detect forgeries as the latter will be involved in group signatures that cannot be opened to anyone.

To sum up, SEPs constitute an informal subclass of digital signatures designed for privacy-preserving applications. Defining specific security properties for the protocols associated with SEPs is not necessary for such applications and artificially increases complexity. In accordance with previous works, we therefore do not consider such security properties.

However, to demonstrate how an SEP can easily be plugged in a privacypreserving construction and how security is concretely managed in this case, we provide in Section 5.3 the description of an anonymous credentials system based on our SEP scheme.

In this section, we present the protocols for the construction over structured lattices, but they can be naturally adapted for the construction over Z q . We thus use the zero-knowledge arguments presented in Section 4.3 using the framework from [LNP22]. One would instead use the framework of [YAZ + 19] for the relations over Z q , which are detailed in Appendix F.

Oblivious Signing Protocol

We present here our first protocol between a signer S and a user U . The user U is interacting with S in order to obtain a signature (τ, v) on a message m, by only providing S with a commitment c to the message m. We assume that Algorithms 3.5 and 3.6 have been run prior to entering the protocol but with some slight modifications that we detail below. First, instead of choosing σ 2 as in Algorithm 3.5, it chooses σ 3 ≥ √ 2η ε (R m1 ) and then

σ 4 ≥ max (( √ nm 1 + √ nm 3 + t) √ nm 3 + σ 3 √ nm 1 ) 2 -σ 2 , √ 2η ε (R m1 ) .
It then re-defines σ 2 = σ 2 3 + σ 2 4 and σ 1 = σ 2 + σ 2 2 . The new widths σ 3 , σ 4 are also included in pp in addition to σ, σ 1 , σ 2 . We explain this change in Remark 5.1. Second, as we use the public key matrix A as part of the commitment matrices, we must ensure that it cannot be tempered with by the attacker. As such, we generate A as the hash of a public string. In the random oracle model, the matrix can be assumed to follow the prescribed uniform distribution over R d×m1 q .

Algorithm 5.1: OblSign (Oblivious Signing Interactive Protocol) Input: Signer S with sk, pk, pp, st, and a user U with m ∈ S m 3 bin and pk, pp.

User U . 1. r ′ ← D R m 1 ,σ 3 . ▷ σ3 ≥ √ 2ηε(R m 1 ) 2. c ← Ar ′ + Dm mod qR. 3. Send c to S.
User U ←→ Signer S. 4. Interactive zero-knowledge argument between U and S, where U proves that c is commitment to m with randomness r ′ . If S is not convinced, the protocol aborts. Signer S.

5. r ′′ ← D R m 1 ,σ 4 . 6. c ′ ← c + Ar ′′ mod qR. 7. τ ← F (st). ▷ τ ∈ Tw 8. v ′ ← SampleD(R, A, τ I d , u + c ′ , σ) -[r ′′T |0] T . 9. Send (τ, v ′ ) to U . 10. st ← st + 1 User U . 11. v ← v ′ -[r ′T |0] T . 12. if Verify(pk; m; (τ, v); pp) = 1, then return (τ, v).
▷ Algorithm 3.8 13. else return ⊥ Remark 5.1. Notice that Algorithm 5.1 does not exactly rely on the signature scheme of Section 3. This is because the signer S also contributes to the randomness of the commitment to the message m via r ′′ . If the randomness came only from the user U , the signer, who is embodied by the SIS adversary in the security proofs, would have no control over the randomness part of the signing query. In the proof of Lemma 3.5 (and Lemma 3.6 for the i-th query with i ̸ = i + ), the randomness r is legitimately sampled from D R m 1 ,σ2 . As such, it could instead be sampled as r ′ + r ′′ with r ′ ← D R m 1 ,σ3 sampled by the forger A, and r ′′ ← D R m 1 ,σ4 sampled by the SIS adversary, thus matching with Algorithm 5.1. This would restrict

σ 2 = σ 2 3 + σ 2 4 . If σ 3 , σ 4 ≥ √ 2η ε (R m1
), Lemma 2.2 guarantees that r ′ +r ′′ is 7ε/4-close to D R m 1 ,σ2 as required. However, when dealing with the i + -th query in Lemma 3.6, the SIS adversary needs to control part of the randomness. At this step of the proof, r 0 would be distributed according to D R m 1 ,σ4 , and it would construct v ′

1 (i + ) = v 1 -(r 0 -Um (i + ) -r ′ (i + ) )
with r ′ (i + ) sampled from D R m 1 ,σ3 by the forger A. The rest remains the same, but this modification introduces the condition

σ 2 + σ 2 4 ≥ α + σ 3 √ m 1 , where α = ( √ nm 1 + √ nm 3 + t) √ nm 3 . It yields σ 2 ≥ (α + σ 3 √ nm 1 ) 2 + σ 2 3 -σ 2 , leading to σ 1 = σ 2 + σ 2 2 ≥ (α + σ 3 √ nm 1 ) 2 + σ 2 3 instead of just α.
In most applications, m 3 is much larger than σ 3 and it thus only entails a mild increase of σ 1 .

Message-Signature Pair Possession Protocol

The second protocol provides a user, who obtained a certificate sig = (τ, v) on a message m, with the ability to prove possession of this valid message-signature pair. For that, they only have to prove that Verify(pk, m, (τ, v), pp) = 1 without revealing neither m nor (τ, v). The protocol of Algorithm 5.2 thus simply consists in using the ZKAoK presented in Section 4.3 to prove this relation. The proof can be made non-interactive in the random oracle model using the Fiat-Shamir transform.

Algorithm 5.2: Prove (Message-Signature Pair Possession) Input: User U with pk, pp, m, (τ, v), and a verifier V with pk, pp.

User U ←→ Verifier V . 1. Interactive zero-knowledge argument between U and V , where U proves knowledge of (m; (τ, v)) such that Verify(pk, m, (τ, v), pp) = 1.

Application to Anonymous Credentials

Anonymous credentials (AC), a.k.a. attribute-based credentials, is a generic term covering a wide spectrum of privacy-preserving systems considering essentially two main use-cases. One where a user interacts with an organization to get a signature on potentially concealed attributes, and one where this user will prove possession of this signature on his attributes while limiting leakage to some threshold depending on the concrete applications. For example, one may agree to reveal some attributes but wants to retain unlinkability of showings, which implies to hide the signature. We refer to [FHS19] for a discussion on the different features of such systems. In all cases, one can note that our two protocols above readily address those needs. To demonstrate that, we formally describe the anonymous credentials system resulting from our SEP construction and prove that it satisfies the security model introduced in [FHS19]. This model is recalled in Appendix C.1 for completeness but, in a few words, anonymous credentials is defined by two Keygen algorithms, one (OKeyGen) for the organization issuing credentials and one (UKeyGen) for the user, along with two interactive protocols, one (Issue) run by the organization and the user who wants to obtain a certificate and one (Show) run by some user and some verifier to check the validity of the claimed attributes. From the security standpoint, two properties are expected: anonymity and unforgeability. The former informally requires that Show does not leak more information than necessary, i.e., the set of disclosed attributes. The latter requires that no user can claim a credential on some attributes unless it has personally received a certificate from the organization. This in particular implies that nobody can present a credential that they do not own. The OKeyGen and UKeyGen algorithms and the (Issue) and (Show) protocols based on our SEP construction are presented below. It gives, to our knowledge, the first lattice-based anonymous credential system. The algorithm Setup (Alg. 3.5) is modified so that m 3 = m s + m ′ 3 where m s = 2d and m ′ 3 • n is the maximal total bitsize of the attributes. We consider a system with ℓ attributes, where h i • n is the bitsize of the i-th attribute m i which means Algorithm 5.6: Show (Credential Showing Protocol) Input: User U with usk, opk, pp, m, (τ, v), I, and verifier V with opk, pp, (mi)i∈I.

m ′ 3 = i∈[ℓ] h i . The commitment matrix D is decomposed into D = [D s |D 1 | . . . |D k ] where D s ∈ R n×ms q and D i ∈ R n×hi
User U ←→ Verifier V . 1. Interactive zero-knowledge argument between U and V , where U proves knowledge of (s, (mi) i / ∈I ; (τ, v)) such that Verify(pk, m, (τ, v), pp) = 1.

Theorem 5.1. The AC described in Algorithms 5.3, 5.4, 5.5 and 5.6 is correct, anonymous under the zero-knowledge property of the underlying ZKAoKs, and unforgeable under the hardness of Inhomogeneous M-SIS, M-LWE, the soundness of the ZKAoKs and the EUF-CMA security of our SEP.

The proof of Theorem 5.1 is given in Appendix C.2 for lack of space. We also defer the detailed performance analysis in Appendix H. As an example, for 10 128-bit attributes with 4 disclosed ones, the proof size in the Show protocol is less than 730 KB.

Conclusion

In this paper, we have proposed a new signature scheme with efficient protocols which is several orders of magnitude more efficient than the current state-ofthe-art [LLM + 16]. This improvement was obtained by revisiting the latter construction in a systematic way, considering not only the signature scheme itself but also its interactions with the other components such as the commitment scheme and the zero-knowledge proofs. In the process, we have also rectified a problem with the fast mode of the zero-knowledge framework of [YAZ + 19] and introduced some optimizations, which are of independent interest. Our construction was designed to remain as generic as possible in order to be compatible with the broadest possible spectrum of applications. In particular, it can be instantiated in both standard lattices and structured ones so as to suit any lattice-based system. Despite this versatility, the size of a proof of knowledge of a message-signature pair, one of the core component of privacy-preserving systems, can be much lower than 1 MB, which should foster the development of practical post-quantum constructions in this area. We made a step in this direction by giving the first lattice-based anonymous credentials system.

A Proof of Lemma 2.5

We recall here the definition of a sub-exponential random variable. We say that a random variable X is sub-exponential with parameters (ν, α) if for all t ∈ (-1/α, 1/α), E[exp(t(X -E[X])))] ≤ exp(t 2 ν 2 /2). We have that a sum of m independent sub-exponential random variables with the same parameters (ν, α) is sub-exponential with parameters (ν √ m, α). Finally, it holds that for a subexponential random variable with parameter (ν, α)

∀r > 0, P[X -E[X] ≥ r] ≤ e -r 2 /(2ν 2 ) if 0 < r < ν 2 /α e ν 2 /(2α 2 )-r/α if r ≥ ν 2 /α.
Proof (of Lemma 2.5). Let m ∈ {0, 1} m be an arbitrary vector, and we denote by k = ∥m∥ 1 the number of ones in the vector. We consider the random matrix U whose entries are independent and identically distributed according to U ([-1, 1]), and we denote by u ij the random variable representing the (i, j)-th entry of U. For clarity, we also denote by u T i the i-th row of U. We know that each u ij is sub-Gaussian with parameter 2/3, i.e., ∀t ∈ R, E[exp(tu ij )] ≤ exp(t 2 /3).

By independence of the entries, we directly obtain for all

i ∈ [n] ∀t ∈ R, E[exp(tu T i m)] ≤ exp(kt 2 /3).
Hence, each u T i m is sub-Gaussian with parameter s = 2k/3. We define the random variables x i = u T i m, y i = x 2 i and we also define µ i = E[y i ]. Since x i is sub-Gaussian with parameter s, we can prove that

∀p ≥ 1, E[|x i | p ] ≤ p( √ 2s) p Γ (p/2),
where Γ is the Gamma function. In particular, we have µ i ≤ 2( √ 2s) 2 Γ (1) = 4s 2 = 8k/3. We then have

E[e t(yi-µi) ] = 1 + tE[y i -µ i ] + ∞ p=2 t p E[(y i -µ i ) p ]/p! ≤ 1 + ∞ p=2 t p E[x 2p i ]/p! ≤ 1 + ∞ p=2 t p (2p( √ 2s) 2p Γ (p))/p! = 1 + 2 ∞ p=2 (2s 2 t) p = 1 + 8s 4 t 2 /(1 -2s 2 t),
where we used the fact that Γ (p) = (p -1)! and that we restrict |t| < 1/(2s 2 β) for some free variable β ≥ 1. It thus follows that yi-µi) ] ≤ 1 + 8βs 4 t 2 /(β -1) ≤ exp(16βs 4 /(β -1) • t 2 /2).

E[e t(
Hence, y i -µ i is a centered sub-exponential with parameters ν = 4s 2 β/(β -1) and α = 2s 2 β. We then define y = i∈[ℓ] y i and µ = i∈[ℓ] µ i . It thus holds that y -µ is a centered sub-exponential with parameters ν √ ℓ and α. Using the tail bound above for a sub-exponential distribution, we have that for all 0 < r < ν 2 ℓ/α = 16ℓk/(3(β -1)) then

P[y -µ ≥ r] ≤ exp(-r 2 /(2ℓν 2 )).
Since the y i are identically distributed, we have that µ = ℓµ 1 ≤ 8ℓk/3. And we also have y = ∥Um∥ 2 2 . We now set the parameters β and r so that

P[∥Um∥ 2 ≥ 2 √ ℓm] ≤ 2 -x .
In particular, we set β = 1/(1 -8x/(ℓ log 2 e)). Assuming ℓ ≥ 10x/ log 2 e entails β ∈ (1, 5]. Also, we set β this way to have 2β/((β -1) log 2 e) x/ℓ = 1/2. Then, we set r = 8k/3 • 2β/((β -1) log 2 e) √ ℓx = 4ℓk/3. We indeed have r ≤ 16ℓk/(3(β -1)) = ℓν 2 /α. The way we set r, we have exp(-r 2 /(2ℓν 2 )) = 2 -x , and r + µ ≤ 4ℓk/3 + 8ℓk/3 = 4ℓk. Hence

P[∥Um∥ 2 ≥ 2 √ ℓk] ≤ P[ √ y ≥ √ r + µ] ≤ exp(-r 2 /(2ℓν 2 )) = 2 -x ,
In the worst case, we have k = m which yields the claim.

B Security Proofs

B.1 Additional Preliminaries

Probabilities. We denote by Supp(P ) the support of the probability distribution P . In addition to the statistical distance, we use another measure of closeness between two probability distributions, namely the Rényi divergence [R 61] RD. The Rényi divergence was thoroughly studied for its use in cryptography by Bai et al. [BLR + 18] as it shows to be a powerful alternative to the statistical distance.

Definition B.1. Consider two discrete probability distributions P and Q over a countable set S such that Supp(P ) ⊆ Supp(Q). We define the Rényi divergence of order α > 1 as

RD α (P ∥Q) =   x∈Supp(P ) P (x) α Q(x) α-1   1 α-1 .
The two measures enjoy a probability preservation property, which are essential in proving our results.

Lemma B.1. Let P, Q be two probability distributions with Supp(P ) ⊆ Supp(Q), and E ⊆ Supp(Q) be an arbitrary event. Then, P (E) ≤ ∆(P, Q) + Q(E), and P (E)

α α-1 ≤ RD α (P ∥Q) • Q(E).
In the security proofs, we need to compute the Rényi divergence between two shifted discrete Gaussian distributions. We use the following lemma.

Lemma B.2 ([LSS14, Lem. 4.2]). Let L be a lattice of rank n, and c ∈ R n . Let α > 1. Then, for any σ > 0, it holds that

1. RD α (D L,σ ∥D L,σ,c ) ≤ exp(απ∥c∥ 2 2 /σ 2 ), 2. RD α (D L,σ,c ∥D L,σ ) ≤ exp(απ∥c∥ 2 2 /σ 2 ) • 1+ε 1-ε α/(α-1) , if σ ≥ η ε (L).
Finally, to ensure that the syndrome generated by the SIS challenger is correctly distributed, we need to argue that A ′ v ′ is close to uniform for a Gaussian vector v ′ . We thus use the result of [MP12] which argues that the smoothing parameter of L ⊥ q (A ′ ) is small with high probability over the choice of A ′ .

Lemma B.3 (Adapted from [MP12, Lem. 2.4]).

Let n and q be positive integers with q prime, and let m ≥ n log 2 q + log 2 (2 + 2ε -1 ) for some ε > 0.

Let σ ≥ 2η ε (Z m ). Then for any δ > 0, it holds that ∆((A, Ae mod q), (A, u)) ≤ δ + 2ε/δ, where A ∼ U (Z n×m q

), e ∼ D Z m ,σ , and u ∼ U (Z n q ).

In particular, choosing ε = δ 2 /2, m > n log 2 q + 2 -2 log 2 δ, σ ≥ ω( log 2 m) leads to a statistical distance of at most 2δ. In our case, we apply it with m = m 1 +m 2 ≫ n log 2 q+2λ+4, yielding a statistical distance much smaller than 2 -λ .

Signature Security Model. The most widely used notion of security for a signature scheme is the Existential Unforgeability against Chosen Message Attacks (EUF-CMA) security. This captures the fact that an attacker that can obtain signatures on messages of its choosing is incapable of forging a signature on a new message. We formally define it by a game between an adversary A and a challenger C in Figure B.1. The adversary's advantage is defined as Adv[A] = P[A wins], where the probability is over all the random coins. We say that the scheme is EUF-CMA secure if for all probabilistic polynomial time (PPT) adversary A, Adv[A] is negligible.

B.2 Proof of Lemma 3.2

Proof. Consider a PPT adversary A that produces Type I forgeries for the signature scheme with advantage δ. We now construct an adversary B that solves the SIS ∞,2 n,m1,q,β problem. The adversary B is given [A|u] ∈ Z n×m1+1 q as input and is asked to find Setup Stage: B first generates the cryptographic material to give to A. We assume that the parameters g, n, m 1 , m 2 , m 3 , q, σ, σ 2 , σ 1 . are already set. We also define G = I n ⊗ g. The adversary B first generates the tags τ (1) , . . . , τ (Q) that will be used for the signing queries of A by calling F and incrementing the state st. It also makes a guess τ ← U (T \ {τ (i) ; i ∈ [Q]}) on the tag that will be used in the adversary's forgery. In particular, we assume that Q = poly(λ) is the maximum number of signing queries that A is able to make.

w ∈ L ⊥ q ([A|u]) such that 0 < ∥w∥ ∞ ≤ β ∞ and 0 < ∥w∥ 2 ≤ β 2 . Challenger C Adversary A pp ← Setup(1 λ ) (pk, sk) ← KeyGen(pp) pk m (i) Choose m (i) sig i ← Sign(sk, m (i) , pk, pp) sig i Choose m * , sig * m * , sig * A wins if m * / ∈ {m (i) ; i ∈ [Q]} and
Next, B samples U from U ([-1, 1] m1×m3 ). It then randomizes A to define D = AU mod q, and sets pp = (D; g; λ, n, m 1 , m 2 , m 3 , q, σ, σ 2 , σ 1 ). Then, B samples R ← U ([-1, 1] m1×m2 ) and defines B = AR + τ G mod q. The adversary B then forms pk = (A, B, u). From these matrices, we can define A τ for any tag τ ∈ Z q ′ by

A τ = A|τ G -B = A|(τ -τ )G -AR , (4)
Since τ does not collide with the tags τ (1) , . . . , τ (Q) that will be used to answer the signing queries, we have τ (i) -τ ∈ Z × q as q is prime. The matrices A τ (i) thus have the adequate form to sample preimages using the trapdoor-based algorithms from [MP12]. Finally, B sends (pk, pp) to A. Query Stage: At the i-th signature query, A provides B with a message m (i) ∈ {0, 1} m3 . B can then faithfully run Algorithm 3.3 using the carefully crafted key material, and the tag τ (i) . More precisely, it computes A τ (i) using Equation (4), as well as the message commitment c = Ar (i) + Dm (i) mod q for a fresh randomness r (i) ← D Z m 1 ,σ2 . As discussed, we can still use the G-trapdoor R to sample preimages, allowing B to compute

v (i) = SampleD(R, A, (τ (i) -τ )I n , u + c, σ) - r (i) 0 m2 .
Note that v (i) is correctly distributed and passes verification (with overwhelming probability by Lemma 2.2 and 2.3). The signature given to A is sig i = (τ (i) , v (i) ).

Forgery Stage: After at most Q queries, the adversary returns a forgery sig * = (τ * , v * ) on a new message m * that passes verification. If A fails to produce such a forgery, B aborts. We call this event Abort 1 . We now condition on ¬Abort 1 . At this point, B aborts if τ * ̸ = τ . We call this event Abort 2 and further condition on ¬Abort 2 . Then, the guess was correct and therefore the contribution of G in A τ * vanishes. Since the forgery passes verification we have A τ * v * = u + Dm * mod q. Using the definition of the cryptographic material from the setup stage, it can be written as

A| -AR v * = u + AUm * mod q.
This means that

w = [I m1 | -R]v * -Um * -1 ∈ Z m1+1 is in L ⊥ q ([A|u]
). The adversary B thus returns w as a solution for SIS ∞,2 n,m1+1,q,β∞,β2 . Advantage: We now analyze the advantage of B. We first look at the distribution of (pk, pp). Since m 1 log 2 3 ≥ n log 2 q + f (λ), it holds by Lemma 2.1 that

   ∆((A, AR mod q), (A, U (Z n×m2 q ))) ≤ m2 2 q n 3 m 1 ≤ m 2 2 -f (λ)/2-1 , ∆((A, AU mod q), (A, U (Z n×m3 q ))) ≤ m3 2 q n 3 m 1 ≤ m 3 2 -f (λ)/2-1 ,
Additionally, since A, R are independent of τ G, it holds that ∆(B, AR) ≤ m 2 2 -f (λ)/2 (by the triangle inequality). The signatures that are given to A in the query stage are distributed according to the legitimate distribution. This means that P[¬Abort 1 ] ≥ δ -negl(λ).

(5)

As the guess τ is independent of A ′ s view, we directly have

P[¬Abort 2 |¬Abort 1 ] = 1 |T | -Q . ( 6
)
We now analyze the solution provided by B. We have to show it is non-zero and have ℓ ∞ norm at most β. Since the last coefficient of w is -1, we directly get that w ̸ = 0. Then, by decomposing

v * into [v * 1 T |v * 2 T ] T , with v * 1 ∈ Z m1 and v * 2 ∈ Z m2 , we have ∥w∥ ∞ ≤ ∥v * 1 ∥ ∞ + m 2 ∥R∥ max ∥v * 2 ∥ ∞ + m 3 ∥U∥ max ∥m * ∥ ∞ ≤ σ 1 log 2 m 1 + m 2 • σ log 2 m 2 + m 3 = β ∞ . Now, since v * 1 , v *
2 correspond to the forgery that passes verification, we only know their ℓ ∞ norm. In particular, we cannot apply the Gaussian tail bound to determine their ℓ 2 norm. Therefore, we can at best have ∥v *

1 ∥ 2 ≤ σ 1 √ m 1 log 2 m 1 and ∥v * 2 ∥ 2 ≤ σ √ m 2 log 2 m 2 . Also, note that the spectral norm of [I m1 | -R] is exactly 1 + ∥R∥ 2 2 . It follows that ∥w∥ 2 ≤ 1 + (∥[I m1 | -R]∥ 2 ∥v * ∥ 2 + ∥Um * ∥ 2 ) 2 ≤ 1 + 1 + ∥R∥ 2 2 m 1 (σ 1 log 2 m 1 ) 2 + m 2 (σ log 2 m 2 ) 2 + min(2 √ m 1 m 3 , ( √ m 1 + √ m 3 + t) √ m 3 ) ≤ 1 + 1 + ( √ m 1 + √ m 2 + t) 2 m 1 (σ 1 log 2 m 1 ) 2 + m 2 (σ log 2 m 2 ) 2 + min(2 √ m 1 , ( √ m 1 + √ m 3 + t)) √ m 3 = β 2 ,
where the inequalities follow from Equation (3) and Lemma 2.4 except with probability 4e -πt 2 + 2 -2λ . By defining Abort {1,2} = Abort 1 ∨ Abort 2 , we obtain

P[w valid solution|¬Abort {1,2} ] ≥ 1 -4e -πt 2 -2 -2λ = 1 -negl(λ). ( 7
)
Combining Equations ( 5), ( 6) and ( 7) by the probability chain rule, we get

Adv[B] ≥ (δ -negl(λ)) • 1 |T | -Q • (1 -negl(λ)) ≈ δ q ′ -Q , as claimed.

B.3 Proof of Lemma 3.3

Proof. Consider a PPT adversary A that can produce a Type II forgery for the signature scheme with advantage δ. We now construct an adversary B that solves the SIS ∞,2

n,m1,q,β ′ ∞ ,β ′ 2 problem. The adversary B is given A ∈ Z n×m1 q
as input and is asked to find w ∈ L ⊥ q (A) such that 0 < ∥w∥ ∞ ≤ β ′ ∞ and 0 < ∥w∥ 2 ≤ β ′ 2 . Setup Stage: The adversary B first generates the tags τ (1) , . . . , τ (Q) that will be used for the signing queries of A by calling F and incrementing the state st. Note that since F is injective, as mentioned in Remark 3.1, there is no collision among the tags. The adversary B makes a guess i + ← U ([Q]) on the index of the tag that will be re-used by A in the forgery stage. Then,

B samples R ← U ([-1, 1] m1×m2 ), and U from U ([-1, 1] m1×m3 ). It then defines B = AR + τ (i + ) G mod q D = AU mod q
The adversary B samples v from D Z m ,σ , r 0 from D Z m 1 ,σ2 , and defines

u = A τ (i + ) v - r 0 0 m2 mod q.
which is in L ⊥ q (A), and returns it as a solution for SIS. Advantage: We now analyze the advantage of B. We first focus on the distribution of (pk, pp). Since m 1 log 2 3 ≥ n log 2 q + f (λ), Lemma 2.1 yields

   ∆((A, AR mod q), (A, U (Z n×m2 q ))) ≤ m2 2 q n 3 m 1 ≤ m 2 2 -f (λ)/2-1 , ∆((A, AU mod q), (A, U (Z n×m3 q ))) ≤ m3 2 q n 3 m 1 ≤ m 3 2 -f (λ)/2-1 . As A, R are independent of τ (i + ) G, it holds that ∆(B, AR) ≤ m 2 2 -f (λ)/2
(by the triangle inequality). Then, let us analyze the distribution of u. Define A ′ = [A|-AR] mod q. By construction, we have

u = A ′ v ′ mod q, where v ′ 1 is within statistical distance 7ε/4 of D Z m 1 ,σ1 by Lemma 2.2, and v ′ 2 is distributed as D Z m 2 ,σ . Fix f (m) = ω( log 2 m) such that σ, σ 1 ≥ f (m). Lemma B.3 thus yields that u is within negligible statistical distance of U (Z n q ), conditioning on A ′ being uniform. Changing A ′ back to [A| -AR] gives ∆(u, U (Z n q )) ≤ negl(λ) + m 2 2 -f (λ)/2-1 = negl(λ).
As a result, (pk, pp) is correctly distributed up to a negligible statistical distance.

We now analyze the distribution of the signature that are produced by B. For the i-th query with i ̸ = i + , the signature is distributed exactly as in the legitimate algorithm. At the i + -th signing query, the vector v

(i + ) 1
is within statistical distance 7ε/4 of D Z m 1 ,σ1,z + , where z + = Um (i + ) . As before, by Equation (3) obtained by combining Lemma 2.4 and 2.5, we have

z + 2 = Um (i + ) 2 ≤ min(2 √ m 1 , √ m 1 + √ m 3 + t) √ m 3 ,
except with probability 2e -πt 2 + 2 -2λ . We now measure the closeness of v (i + ) to the real distribution by using the Rényi divergence of order α for a free parameter α > 1. By Lemma B.2 it holds that

RD α (D Z m 1 ,σ1 ∥D Z m 1 ,σ1,z + ) ≤ exp απ σ 2 1 z + 2 2 ≤ e απ , as σ 1 ≥ min(2 √ m 1 , √ m 1 + √ m 3 + t) √ m 3 .
Combining the probabilities for the distribution of the keys and the signatures, and by the probability preservation properties of the statistical distance and Rényi divergence of Lemma B.1, we have

P[¬Abort 1 ] ≥ e -απ (δ -negl(λ)) α/(α-1) ≥ e -απ δ α/(α-1) -negl(λ). ( 8
)
We then optimize over α. The maximum value of the right-hand side is attained for α * = 1 + log 2 (1/δ)/(π log 2 e). Further, since the guess i + is independent of A's view it holds that

P[¬Abort 2 |¬Abort 1 ] = 1 Q . ( 9
)
We now analyze the solution constructed by B. We have to show it is non-zero and has norm at most β ′ . We first focus on the former. We essentially show that for A to ensure w = 0, it must predict at least one column u ′ of U as m * ̸ = m (i + ) . So we have

P[w = 0] ≤ P u ′ [u ′ = u * : u * ← A(A, Au ′ mod q, v (i + ) 1
)]

≤ P u ′ [u ′ = u * : u * ← A(A, Au ′ mod q)] • RD 2 (D Z m 1 ,σ1,Um (i + ) ∥D Z m 1 ,σ1 ) + 7ε/4 ≤ 1 + ε 1 -ε e π P U [u ′ = u * : u * ← A(A, Au ′ mod q)] + 7ε/4
where the last inequality stems from Lemma B.2 as

σ 1 ≥ σ ≥ η ε (Z m1 ) 9 .
Then, since m 1 log 2 3 ≥ n log 2 q + f (λ) and that Au ′ mod q can take 2 n log 2 q values, [DORS08, Lem. 2.2] then gives that u ′ given Au ′ mod q contains at least m 1 log 2 3 -n log 2 q ≥ f (λ) = ω(log 2 λ) bits of entropy. Hence, w ̸ = 0 except with negligible probability. Finally, it holds that

∥w∥ ∞ ≤ ∥(v 1 -r 0 ) -v * 1 ∥ ∞ + m 2 ∥R∥ max ∥v 2 -v * 2 ∥ ∞ + m 3 ∥U∥ max ∥m * ∥ ∞ ≤ 2σ 1 log 2 m 1 + m 2 • 2σ log 2 m 2 + m 3 = β ′ ∞ .
The inequality is valid if v 1 -r 0 follows D Z m 1 ,σ1 (Lemma 2.2) and that the Gaussian tail bound of Lemma 2.3 is verified for v 1 -r 0 , v 2 . By the union bound, this happens with probability at least 1 -(2m 1 e -π log 2 2 m1 + 7ε/4) -2m 2 e -π log 2 2 m2 = 1 -negl(λ). As in the proof of Lemma 3.2, we cannot use the Gaussian tail bound in ℓ 2 norm for v * . Hence, we have the following

∥w∥ 2 ≤ 1 + ∥R∥ 2 2 (σ 2 m 1 + σ 2 2 m 1 + m 1 σ 2 1 log 2 2 m 1 ) + (σ 2 m 2 + m 2 σ 2 log 2 2 m 2 ) + ∥Um * ∥ 2 ≤ 1 + ( √ m 1 + √ m 2 + t) 2 σ 2 1 m 1 (1 + log 2 2 m 1 ) + σ 2 m 2 (1 + log 2 2 m 2 ) + min(2 √ m 1 , √ m 1 + √ m 3 + t) √ m 3 = β ′ 2 ,
where the first inequality follows from Lemma 2.3 except with probability 2 • 2 -2m1 + 2 -2m2 , and the second inequality stems from Lemma 2.4 except with probability 4e -πt 2 + 2 -2λ . This yields

P[w valid solution|¬Abort 1 ∧ ¬Abort 2 ] = 1 -negl(λ). ( 10
)
Combining Equations ( 8), ( 9) and ( 10) by the probability chain rule, we get

Adv[B] ≥ (δ α * /(α * -1) e -α * π -negl(λ)) • 1 Q • (1 -negl(λ)),
as desired. Note that the parameters and the behavior of B do not depend on the order α that is used to compute the advantage bound. As such, α * can indeed depend on the forger's advantage δ.

C Anonymous Credentials

C.1 Definitions

In Section 5.3, we use the definition and security model from [FHS19] that we recall below. We note that, in their definition, the attributes are revealed to the signer during issuance (but not the user's secret key). This means that when using the OblSign protocol of our SEP, part of the message to be signed is revealed to the signer. Rather than an artifact specific to the construction from [FHS19], this peculiarity stems from the difficulty of formally defining a notion of unforgeability when the signed message is hidden, as discussed in Section 5. Regardless, this is not problematic in practice as credentials would usually be emitted on known attributes, even though the latter would be hidden when presenting the credential. Although we prove the security of our construction in this setting, our protocol could easily hide the attributes during issuance if necessary.

C.1.1 Syntax. An anonymous credentials is composed of two algorithms and two interactive protocols. The OKeyGen takes as input public parameters (in our case those generated by Setup) and outputs the organization's key pair (opk, osk). Similarly, the UKeyGen takes the public parameters (and possibly the organization's public key) and outputs the user's key pair (upk, usk).

The Issue O,U protocol involves an organization O with (osk, opk, upk, pp, st) and the users' attributes (m i ) i∈ [ℓ] , and a user U with (usk, upk, opk, pp) and its attributes (m i ) i∈ [ℓ] . The user either obtains a credential cred on its attributes or ⊥ if the protocol failed, while the organization just gets notified of whether or not the execution was successful. Finally, the Show U,V protocol involves a user U with (usk, opk, pp, (m i ) i∈[ℓ] , cred, I) and a verifier V with (opk, pp, (m i ) i∈I ). The protocol outputs b = 1 to V if the credential cred is valid for the disclosed attributes (m i ) i∈I and b = 0 otherwise, and U gets no output.

C.1.2 Security Requirements. The model from [FHS19] stipulates that the anonymous credentials system must be correct, anonymous, and unforgeable.

Correctness says that an honest execution of Issue O,U should succeed often 10 , and that an honest execution of Show U,V on honestly obtained credentials should also succeed often. For the anonymity and unforgeability, we stick to the syntax of [FHS19] by first defining the following variables and oracles.

-HU: Set of user indices corresponding to honest users, initially empty.

-CU: Set of user indices corresponding to corrupt users, initially empty.

ctr: Issuance counter, initially set to 0.

-A: Set of triplets (j, j ′ , (m i ) i∈ [ℓ] ) filled when the oracles O ObtIss or O Issue successfully issue a credential for user j on the attributes (m i ) i∈ [ℓ] , and where j ′ is an issuance index.

-O HU (j): Given a user index j, it returns ⊥ if j ∈ HU ∪ CU. Otherwise, it samples (upk j , usk j ) ← UKeyGen(pp) and returns upk j . It then adds j to HU. -O CU (j, upk): Given a user index j and optionally a public key upk, it registers a new user with public key upk if j / ∈ HU. Otherwise, it returns usk j and sets HU ← HU \ {j}. Either way, it adds j to CU. The former case models the ability to register users with malformed keys, i.e., who do not know the associated secret key.

-O ObtIss (j, m): On input j ∈ HU and attributes m = (m i ) i∈[ℓ] , the oracle runs Issue O,U ((osk, opk, upk j , pp, st, m); (usk j , upk j , opk, pp, m)) assuming the roles of both O and user j. If the execution succeeds, it increments the issuance counter ctr, it stores the obtained credential and stores (j, ctr, m) in A. It returns indication of whether the execution succeeded. If j / ∈ HU, it simply returns ⊥.

-O Obtain (j, m): Given a user index j and attributes m, it returns ⊥ if j / ∈ HU. Otherwise, it runs Issue A,U (•, (usk j , upk j , opk, pp, m)) with the adversary A posing as the organization. It thus issues a credential to an honest user.

-O Issue (j, m): Given a user index j and attributes m, it returns ⊥ if j / ∈ CU. Otherwise, it runs Issue O,A ((osk, opk, upk j , pp, st, m), •) with the adversary assuming the role of the user. It thus allows the adversary to obtain credentials from the honest organization. If the execution is successful, it increments the issuance counter ctr, stores the credential and adds (j, ctr, m) in A.

-O Show (j ′ , (m (j ′ ) i ) i∈I ): It takes as input an issuance index j ′ and disclosed attributes (m (j ′ ) i ) i∈I . The issuance index corresponds to a successfully issued credential cred (j ′ ) on (m

(j ′ ) i ) i∈[ℓ]
for a user j during the j ′ -th query to O IssObt or O Obtain . If the corresponding user j is not honest, i.e., j / ∈ HU, the oracle returns ⊥. Else, it runs Show U,A ((usk j , opk, pp, (m

(j ′ ) i ) i∈[ℓ] , cred (j ′ ) , I), •)
with the adversary posing as the verifier.

Anonymity. The anonymity property captures the fact that a user showing its credential cred obtained on attribute vector m remains anonymous among all users who have the same disclosed attributes (m i ) i∈I . It means that during an execution of Show U,V , the verifier V does not learn anything other that U owns a valid credential on the shown attributes (m i ) i∈I . Additionally, different showings of the same credential with the same revealed attributes should be unlinkable. It is formalized by the game presented in Figure C.1. The anonymous credentials system is anonymous if for all PPT adversary A, its advantage |P[b * = b ∧ O CU was not queried on j 0 nor j 1 ] -1/2| in the anonymity game is negligible. To avoid overloading the protocols we assume that (opk, osk) are honestly generated, but this assumption is not necessary if one includes a zeroknowledge proof that they know the secret osk linked to opk.

Challenger C Adversary A (opk, osk) ← OKeyGen(pp) opk, osk Choose issuance indices j ′ 0 , j ′ 1 on same disclosed attributes (mi)i∈I j ′ 0 , j ′ 1 , (mi)i∈I Aborts if (j0, j ′ 0 , m (j ′ 0 ) ) / ∈ A or (j1, j ′ 0 , m (j ′ 1 ) ) / ∈ A b ← U ({0, 1}) ShowC,A((uskj b , opk, pp, m (j ′ b ) , cred (j ′ b ) , I), •) Choose b * ∈ {0, 1} b * Oracle Queries to OHU, OCU, OObtain, OShow
Oracle Queries to OHU, OCU, OObtain, OShow α . The attribute vector m (j ′ α ) is the attribute vector used in the j ′ α issuance, and must satisfy (m

(j ′ α ) i )i∈I = (mi)i∈I.
Unforgeability. The unforgeability property of anonymous credentials ensures that a user cannot show attributes for which it does not own a valid credential. It means that it cannot impersonate an honest user (as it would mean knowing its secret key) which thwarts replay attacks, and that it cannot forge fresh credentials that have not been issued by the Issue protocol. Additionally, malicious users cannot collude and use their legitimate credentials to obtain a new one on a set of attributes that has not been used in a successful issuance. We formalize it as a game in Figure C.2. The adversary wins the game if the challenger does not abort and if the challenger's output of the execution of Show is b = 1. We say that the anonymous credentials system is unforgeable if for all PPT adversary A, its probability of winning is negligible.

C.1.3 Additional Assumptions. In order to prove the unforgeability of our anonymous credentials system, we require the inhomogeneous variant of M-SIS, and M-LWE (in knapsack form) which we now recall. Note that the knapsack form of M-LWE is at least as hard as the standard definition by the duality result of [BJRW23, Lem. 4.1].

(opk, osk) ← OKeyGen(pp) opk

Choose disclosed attributes (mi)i∈I (mi)i∈I Aborts if (j, j ′ , m (j ′ ) ) ∈ A for some j ∈ CU with (m (j ′ ) i )i∈I = (mi)i∈I ShowA,C(•, (opk, pp, (mi)i∈I))
Oracle Queries to OHU, OCU, OObtIss, OIssue, OShow

Definition C.1 (M-ISIS).

Let n be a power of two and R the 2n-th cyclotomic ring. Let d, m, q be positive integers and β > 0. The Module Inhomogeneous Short Integer Solution problem M-ISIS d,m,q,β asks to find s ∈ R m such that Ds = t mod qR and ∥s∥

2 ≤ β, given D ← U (R d×m q ) and t ← U (R d q ).

Definition C.2 (M-LWE).

Let n be a power of two and R the 2n-th cyclotomic ring. Let d, m, q be positive integers and β > 0. The Module Learning With Errors problem M-LWE d,m,q,U (S bin ) asks to distinguish between the following distributions: (1) (D, Ds mod qR), where D ∼ U (R d×m q

) and s ∼ U (S m bin ), and (2) (D, t), where D ∼ U (R d×m q ) and t ∼ U (R d q ).

C.2 Security Analysis

C.2.1 Correctness. We first show correctness of our anonymous credentials, meaning that honest execution of the issuance protocols does not fail, and that honestly obtained credentials can be shown successfully.

Lemma C.1. The anonymous credentials system of Section 5.3 is correct.

Proof. Let pp ← Setup(1 λ ). Let (opk, osk) ← OKeyGen(pp) and (upk, usk) ← UKeyGen(pp). Then, let m ∈ S m ′ 3 bin and I ⊆ [ℓ]. We now consider an honest execution of Issue O,U ((osk, opk, upk, pp, st, m); (usk, upk, opk, pp, m)). By the completeness of the zero-knowledge argument of knowledge, we only have to check the abort condition of step 11. First, note that τ ∈ T w and m ∈ S m3 bin . Then, we

Lemma C.3. The anonymous credentials of Section 5.3 is unforgeable based on the hardness of M-ISIS d,ms,q, √ nms , the zero-knowledge property of the ZKAoK involved in Issue and Show, on the soundness of the ZKAoK involved in Show, and on the EUF-CMA security of the signature scheme of Section 3.

Proof. We consider a PPT adversary A against the unforgeability game. As described, A receives the organization's public key opk and must return a disclosed set of attributes (m * i ) i∈I while proving possession of a credential cred * on said attributes in a successful execution of Show with the honest organization. If (m * i ) i∈I corresponds to an attribute vector m that was queried for issuance by a corrupt user, the forgery is refused. This leaves two scenarios. Either (1) A tried to impersonate an honest user, or (2) it did not. Since A must prove knowledge of a secret s * satisfying D s s * = t, this means that (1) corresponds to the case where there exists j ∈ HU such that s * = usk j , i.e., verifying D s s * = upk j mod qR, and (2) where for every j ∈ HU, s * ̸ = usk j . We tackle these two types of forgeries separately.

(1) Impersonation Forgery. At the outset, the challenger receives an M-ISIS instance (D s , t). It then runs Setup but sets D s = D s instead of sampling it themselves. It then makes a guess on which honest user will be targeted. For that it samples j + ← U ([|T w |]). Indeed, the number of users requesting credentials to one organization is bounded by the number of possible tags as explained in Remark 3.1. It then runs OKeyGen(pp) to obtain (opk, osk) = ((A, B, u), R), and sends opk to A. From there on out the adversary makes queries to different oracles which are answered as follows.

-O HU : On input a user index j, the challenger runs (upk j , usk j ) ← UKeyGen(pp)

and outputs upk j if j ̸ = j + , and outputs t if j = j + . -O CU : On input a user index j, it gives usk j to A if j ̸ = j + . If j = j + , the challenger aborts the reduction altogether as the guess was wrong. -O ObtIss : It takes as input a user index j and attribute vector m ∈ S m ′ 3 bin . If j ∈ CU it sends ⊥ to A. Otherwise, if j ̸ = j + , the challenger can assume the role of the issuer and the user in the Issue protocol as it knows the issuer's key osk and the key usk j of user j. If the execution fails, it sends ⊥ to A, and nothing if it succeeds. However, if j = j + , it instead generates c as Ar ′ + t + i D i m i mod qR, and simulates the zero-knowledge argument when assuming the role of the user in Step 4 of Issue. Again, if this modified execution fails, it sends ⊥ to A, and nothing if it succeeds.

-O Issue : It takes as input a user index j and attribute vector m ∈ S m ′ 3 bin . If j / ∈ CU, it returns ⊥ to A and does not engage in the issuance protocol. Otherwise, since the challenger knows osk, it can run the Issue protocol where the adversary plays the user j with public key upk j , and the challenger plays the signer. In the end, either A gets ⊥ if the execution failed, or obtained a credential (τ, v) on m.

-O Show : It takes an issuance index j ′ , corresponding to the j ′ -th credential issued on (m

(j ′ ) i ) i∈[ℓ]
for some user j, and also disclosed attributes (m

(j ′ ) i ) i∈I .
If user j ∈ CU, the challenger outputs ⊥ to A. Otherwise, if j ̸ = j + , it runs the legitimate protocol Show where A assumes the role of the verifier, which can be done as the challenger knows usk j , the attributes and the credential. If j = j + however, it cannot run Show. Instead, it simulates the zero-knowledge argument with the adversary as the verifier.

If the guess j + is correct, which implies that j + is never queried to O CU , then the game is correctly simulated. Indeed, the differences stem from the public key of user j + and the simulation of the zero-knowledge arguments. Since t is uniform, it is indistinguishable from regular keys D s s under M-LWE d,2d,q,U (S bin ) .

Then, by the zero-knowledge property of the ZKAoK, the simulated proof are correctly distributed. Hence, if A has advantage δ in performing a forgery attack satisfying (1), it can successfully prove knowledge of (s * , (

m * i ) i / ∈I * , τ * , v * ) with disclosed attributes (m * i ) i∈I * such that Verify(opk, m * , (τ * , v * ), pp) = 1 where m * = [s * T |m * 1 T | . . . |m * k T ] T .
The challenger can then extract s * by the soundness of the ZKAoK, and because it is an attack of type (1), there exists j * ∈ HU such that s * = usk j , thus implying D s s * = upk j * . If j * = j + , the challenger's guess is correct and this happens with probability at least 1/|T w | because it means j + was never queried to O CU and was therefore independent of the view of A. In that case, we thus have D s s * = t mod qR, and s * ∈ S ms bin so ∥s * ∥ 2 ≤ √ nm s . The challenger thus solves the M-ISIS instance with advantage at least δ/|T w | -negl(λ).

(2) Fresh Forgery. If the challenger expects this type of forgery, it expects a forgery on the SEP. It therefore flips a coin to guess which type of forgery on the signature will be performed (type I or type II).

If it expects a type I forgery, it proceeds exactly as in Section B.2, without having to extract the commitment randomness in the issuance. This is because signature queries are answered legitimately without having to tamper with the randomness. As a result, once the challenger has changed the setup, it can answer all the oracle queries O HU , O CU , O ObtIss , O Issue , O Show legitimately. When A eventually proves knowledge of (s * , (m * i ) i / ∈I , τ * , v * ) with disclosed attributes (m * i ) i∈I such that Verify(opk, m * , (τ * , v * ), pp) = 1, the challenger can extract (s * , (m * i ) i / ∈I , τ * , v * ) from the proof by the soundness of the ZKAoK. Then, (τ * , v * ) is a valid type I forgery for our SEP as m * is a fresh message. Indeed, by definition of type (2) forgeries of the anonymous credentials, we have that s * ̸ = usk j for all j ∈ HU. This first fact means that m * differs from all the m involved in calls to O ObtIss . Secondly, by the definition of a forgery of the AC, it must hold that for all j ∈ CU, (j, j ′ , (m * i ) i∈[ℓ] ) / ∈ A), which means that m * must differ from all the m involved in calls to O Issue . As a result, we obtain a solution to M-SIS as in Section B.2.

If it expects a type II forgery of the SEP, it proceeds as in Section B.3 with a minor difference due to the fact that it needs to control the commitment randomness for the i + -th signature query, as explained in Remark 5.1. In this context, in the issuance corresponding to the tag τ * = τ (i + ) that will be used in the forgery extracted from the showing of the AC, the challenger proceeds as follows. By the soundness of the ZKAoK, it extracts (r

′ (i + ) , s (i + ) ) such that c (i + ) = Ar ′ (i + ) + D s s (i + ) + i∈[ℓ] D i m (i + ) i mod qR. As opposed to Section B.3 where it computed v ′ (i + ) = v -[(r 0 -U m (i + ) ) T |0] T , with m (i + ) = [s (i + ) T |m (i + ) T ] T , here, it computes v ′ (i + ) = v - r 0 -U m (i + ) -r ′ (i + ) 0 .
The rest of the proof remains the same. In the end, when A engages in Show to attack the unforgeability of the AC, the challenger extracts (s * , (m * i ) i / ∈I , τ * , v * ). It thus obtain (τ * , v * ) which is a valid type II forgery for the SEP on message m * (which is fresh as explained above). It then proceeds exactly as in Section B.3 to obtain a solution to M-SIS.

In the end, if A has advantage δ in producing a forgery of type (2) for the anonymous credentials system, it holds that δ ≤ sup A ′ PPT Adv EU F -CM A [A ′ ] + negl(λ), where Adv EU F -CM A [A ′ ] denotes the advantage of A ′ in producing a valid forgery (type I or type II) for our signature with efficient protocols.

D Proof of Lemma 4.1

Proof. For clarity, we denote by x = x mod q the vector of representatives in [-q/2, q/2] of a vector x. With such representatives, we have C = C for any integer C in [-q/2, q/2], which simplifies the notations in what follows. We assume that there exists i in

[n] such that w i / ∈ [-2B, 2B].
Let h be a random vector distributed according to U ([-1, 1] n ). For clarity, we define S = [n] \ {i}. We now have

P h [h T w ∈ [-B, B]] = C∈[-q/2,q/2] P h [ j∈S h j w j = C] • P h [ i∈[n] h j w j ∈ [-B, B]| j∈S h j w j = C] = C∈[-q/2,q/2] P h [ j∈S h j w j = C] • P hi [h i w i + C ∈ [-B, B]] = C∈[-q/2,q/2] P h [ j∈S h j w j = C] • {h i : h i w i + C ∈ [-B, B]} 3 ,
where the second equality is a consequence of h i being uniform in [-1, 1]. We now split the sum indexed by C into two complementary parts Σ 1 and Σ 2 as follows.

Σ 1 = C∈(-q 2 +2B, q 2 -2B)∩Z P h [ j∈S h j w j = C] • {h i : h i w i + C ∈ [-B, B]} 3 Σ 2 = C∈[-q 2 ,-q 2 +2B]∪[ q 2 -2B, q 2 ] P h [ j∈S h j w j = C] • {h i : h i w i + C ∈ [-B, B]} 3
We can now focus on bounding the set {h i :

h i w i + C ∈ [-B, B]} in each case. First note that for all h i ∈ [-1, 1], if h i w i + C ∈ [-B, B] (h i + 1)w i + C ∈ [-B, B],
are both satisfied, then there exist r 1 , r 2 ∈ [-B, B] and k 1 , k 2 ∈ Z, such that

h i w i + C = r 1 + k 1 q ∧ (h i + 1)w i + C = r 2 + k 2 q.
Note that the above equations are now over Z, not Z q . Combining these two equations gives us w i = r 2 -r 1 + (k 2 -k 1 )q, which implies that the representative w i is necessarily in [-2B, 2B]. This contradicts the original assumption of w i / ∈ [-2B, 2B]. In other words, we have shown that the set {h i :

h i w i + C ∈ [-B, B]} cannot contain two consecutive numbers.
Now let us consider the situation where both h i and h i + 2 would be in this set. As h i ∈ [-1, 1], this can only occur when h i = -1. This means that:

-w i + C ∈ [-B, B] w i + C ∈ [-B, B],
and hence there exist r 1 , r 2 ∈ [-B, B] and k 1 , k 2 ∈ Z, such that

-w i + C = r 1 + k 1 q (11)
w i + C = r 2 + k 2 q. ( 12
)
This implies that 2w i = r 2 -r 1 + (k 2 -k 1 )q. As w i / ∈ [-2B, 2B], these equations can be satisfied only when

w i = r2-r1±q 2 with r 2 -r 1 ∈ [-2B, 2B]. The latter interval implies that w i ∈ [-q 2 , -q 2 + B] ∪ [ q 2 -B, q 2 ]. But in that case, Equation (11) implies that C = w i + r 1 ∈ [-q 2 , -q 2 + 2B] ∪ [ q 2 -2B, q 2
]. In other words, {h i :

h i w i + C ∈ [-B, B]} contains at most 1 element if C / ∈ [-q 2 , -q 2 + 2B] ∪ [ q 2 -2B, q 2
] and at most two elements otherwise. We thus get the following bounds on Σ 1 and Σ 2 .

Σ 1 ≤ 1 3 C∈(-q 2 +2B, q 2 -2B)∩Z P h [ j∈S h j w j = C] Σ 2 ≤ 2 3 C∈[-q 2 ,-q 2 +2B]∪[ q 2 -2B, q 2 ] P h [ j∈S h j w j = C] Let x denote C∈[-q 2 ,-q 2 +2B]∪[ q 2 -2B, q 2 ] P h [ j∈S h j w j = C]. Then, we have that 1- x is C∈(-q 2 +2B, q 2 -2B)∩Z P h [ j∈S h j w j = C] which yields P h [h T w ∈ [-B, B]] ≤ 1 3 + x 3 .
precisely, we sample the randomness from a ternary distribution instead of a discrete Gaussian. Additionally, we add an extra verification step in order to rely on the HNF-SIS problem with two norm bounds β ∞ , β 2 on the ℓ ∞ norm and ℓ 2 norm respectively (Definition 2.3). Again, now relying on concrete hardness arguments, we obtain an improved condition on q only depending on β ∞ , which is usually much smaller than β 2 . Moreover, as discussed after Definition 2.3, constraining the magnitude of the solution's coefficients seems to be beneficial for both theoretical and concrete hardness.

Rejection Sampling. The second modification we make is to better leverage the rejection sampling result from Corollary E.1 adapted from [Lyu12]. This step ensures that a discrete Gaussian sample shifted by a small enough vector is statistically close to the original discrete Gaussian distribution, thus masking the shift. However, this fact is not used to its full potential in the proof of [YAZ + 19]. Doing so leads to smaller bounds in the verification equations and SIS norm bounds as a result. Additionally, we note when computing the size of the proof (in the non-interactive version), the authors treat the discrete Gaussian vectors as mere vectors over Z q . We can thus reduce the amount of storage needed as they have small coefficients with overwhelming probability, which results in smaller proofs by up to 20%.

Compacted Commitments. The final optimization regards the case when the proof system is run only once. It is sometimes better to increase the size p of the challenges rather than re-iterate the proof several times in order to achieve negligible soundness error. When running it once, we can compact the commitments thus limiting the number of elements to send and the size of the proof as a consequence. We note that compacting the commitments may not be desirable when the proof system is run multiple times as it would involve committing to the witness x multiple times.

E.1 Preliminaries

In what follows we sample the commitment randomness from a small distribution in order to optimize the parameters and the efficiency. For that, we employ the following ternary distribution which we denote by ψ 1 , instead of Gaussian distributions. It outputs 0 with probability 6/16 and -1, 1 both with probability 5/16. This distribution has the advantage of being very efficiently sampleable as it only requires the sampling of 4 uniformly random bits to output a sample of ψ 1 . For x sampled from ψ n 1 , it holds that ∥x∥ 2 2 is distributed according to a binomial distribution with parameter (n, 5/8). As such, Hoeffding's inequality gives the following.

Lemma E.1. Let n be a positive integer. Then for all δ > 0 it holds

P x← ψ n 1 ∥x∥ 2 ≥ (1 + δ) 5 8 n ≤ exp - 25 32 δ 2 n .
The above probability becomes 0 when δ > 3/5.

all the randomness. We denote this event by E 1 . We have the following

P[E 1 ] = v ′ ∈V T h(v ′ )P[E 1 |v = v ′ ] + v ′ / ∈V T h(v ′ )P[E 1 |v = v ′ ] ≥ v ′ ∈V T h(v ′ ) z∈Z g v ′ (z) • min f (z) M g v ′ (z) , 1 = v ′ ∈V T h(v ′ )   z∈S v ′ f (z) M + z / ∈S v ′ g v ′ (z)   ≥ v ′ ∈V T h(v ′ ) z∈S v ′ f (z) M = 1 M v ′ ∈V T h(v ′ )P z∼f [M g v ′ (z) ≥ f (z)] ≥ 1 -ε M v ′ ∈V T h(v ′ ) = 1 -ε M P v∼f [v ∈ V T ] ≥ (1 -ε)(1 -ε ′ ) M .
Further, we also need to lower bound P[E 1 ]. We rely on the fact that v ′ / ∈V T h(v ′ ) = P v∼h [v / ∈ V T ] ≤ ε ′ . We thus get

P[E 1 ] = v ′ ∈V T h(v ′ )P[E 1 |v = v ′ ] + v ′ / ∈V T h(v ′ )P[E 1 |v = v ′ ] ≤ v ′ ∈V T h(v ′ )P[E 1 |v = v ′ ] + v ′ / ∈V T h(v ′ ) ≤ v ′ ∈V T h(v ′ )   z∈S v ′ f (z) M + z / ∈S v ′ g v ′ (z)   + ε ′ ≤ v ′ ∈V T h(v ′ )   z∈S v ′ f (z) M + z / ∈S v ′ f (z) M   + ε ′ = 1 M P v∼h [v ∈ V T ] + ε ′ ≤ 1 M + ε ′ .
Next, let p i be the probability that P i does not output anything. We have proven that

p 1 ∈ [1-1/M -ε ′ , 1-(1-ε)(1-ε ′ )/M ],
and we trivially have p 2 = 1-1/M .

Meanwhile, we have

∆(P 1 , P 2 ) = |p 1 -p 2 | 2 + 1 2 v∈V z∈Z |P 1 (v, z) -P 2 (v, z)| ≤ |p 1 -p 2 | 2 + 1 2 v∈V h(v) z∈Z g v (z) min f (z) M g v (z) , 1 - f (z) M = |p 1 -p 2 | 2 + 1 2 v∈V T h(v) z∈Z g v (z) min f (z) M g v (z) , 1 - f (z) M + 1 2 v / ∈V T h(v) z∈Z g v (z) min f (z) M g v (z) , 1 - f (z) M .
We then bound the two sums separately. First, for all v in V T , it holds that

z∈Z g v (z) min f (z) M g v (z) , 1 - f (z) M = z∈Sv f (z) M - f (z) M + z / ∈Sv g v (z) - f (z) M = z / ∈Sv f (z) M -g v (z) ≤ z / ∈Sv f (z) M = 1 M P z∼f [z / ∈ S v ] ≤ ε M .
This means that the first sum can be bounded by ε

2M P v∼h [v ∈ V T ] ≤ ε 2M .
To bound the second sum, we use the triangle inequality and for all v in V \ V T we get that

z∈Z g v (z) min f (z) M g v (z) , 1 - f (z) M ≤ g v (Z) + f (Z) M = 1 + 1 M ,
as the minimum in the sum can be bounded by 1. As a result, the second sum can be bounded above by

1 2 (1 + 1 M )P v∼h [v / ∈ V T ] ≤ ε ′ (M +1) 2M
. Finally, from the bounds derived on p 1 , we have

|p 1 -p 2 | ≤ max(ε ′ , ε(1 -ε ′ )/M ). We thus get ∆(P 1 , P 2 ) ≤ ε + ε ′ (M + 1) 2M + max ε ′ 2 , ε(1 -ε ′ ) M = max ε ′ + ε + ε ′ 2M , ε M + ε ′ 2 1 + 1 -ε M .
It is easy to verify that when M ≥ 1 and ε ′ = ε, the first term in the maximum above is the largest, and equals ε(1 + 1/M ).

the size of the quadratic constraints set. We also define L = ℓ 1 + ℓ 2 + L x + L M . As is done in [YAZ + 19], we employ the homomorphic commitment scheme from [BDL + 18] over the integers. More precisely, we define

C = I ℓ1 C 1 0 Lx+L M ×ℓ1 I Lx+L M C 2 ∈ Z (ℓ1+Lx+L M )×L q , with C 1 ← U (Z ℓ1×(Lx+L M +ℓ2) q ), C 2 ← U (Z (Lx+L M )×ℓ2 q
). Let p = 2 λ be the maximal magnitude of the challenges, and M > 1 the repetition rate of the rejection sampling procedure. We then set δ, t, T as per Corollary E.1, namely δ = 32 25 log 2 e • λ+1 L , t = (λ + 2)/(π log 2 e) and T = p 5(1 + δ)/(8L). Next define s 2 = (-t + t 2 + ln(M )/π) -1 • T . We define the rejection sampling function by p(v, z) = min(1, D Z L ,s2 (z)/(M • D Z L ,s2 (z -v))) for all v, z ∈ Z L . Finally, let aCommit be an auxiliary commitment scheme with randomness space {0, 1} κ and message space Z k+2(ℓ1+Lx+L M ) q , and that is binding and hiding. The following interactive protocol involves a prover P with public input A ∈ Z k×Lx q , y ∈ Z k q , and M ⊆ [L x ] 3 with |M| = L M and private input x ∈ Z Lx q . The verifier V is only given the public input. In the protocol, P must convince V in zero-knowledge that they know x verifying

Ax = y mod q ∀(h, i, j) ∈ M, x[h] = x[i]x[j] mod q (14)
Theorem E.1. The protocol described in Figure E.1 is complete with completeness error at most δ c = 1 -1/M + negl(λ).

We define β ∞ = 8ps 2 log 2 L and β 2 = 8ps 2 √ L. Assume HNF-SIS ℓ1,L,q,β∞,β2 is δ SIS -hard and that aCommit is δ a b -binding. Then, there exists an extractor E that for any A, y, M and any PPT cheating prover P, if P can convince a verifier V without knowing a witness with probability at least 2/(2p + 1) + ε for a non-negligible ε, then E can extract an x that verifies (14) in polynomial time, except with probability δ SIS .

Finally, assume that HNF-LWE ℓ2,ℓ1+Lx+L M ,q,ψ1 is δ LWE -hard, and that the commitment aCommit is δ a h -hiding. Then, there exists a simulator S that with input A, y, M outputs a transcript that is (δ a h + 2 -λ-1 (1 + 1/M ) + δ LWE )indistinguishable from the transcript of an honest execution of the protocol with a prover knowing a witness x satisfying (14).

Although the proof of Theorem E.1 follows naturally from that of [YAZ + 19], we give it in Section E.3. The above protocol can be turned into a non-interactive zero-knowledge argument of knowledge via the Fiat-Shamir heuristic in the random oracle model. In this case, the resulting proof does not contain the whole transcript as some elements are uniquely determined by the others for the proof to be correct. More precisely, the proof is π = (α, ρ, c 1 , z 0 , z 1 ) where the challenge α = H(A, y, M, C aux ; AU X) with AU X an auxiliary input. The verification algorithm then re-computes t from the verification equation (4), c 2 from

Prover P[A, y, M; x] Verifier V[A, y, M] r ← U (Z Lx q ) t ← Ar mod q s1 ← ψ L 1 s2 ← D Z L ,s2
Let a, b be LM-dimensional vectors For e ∈ [LM], let (h, i, j) be the e-th element of M a

[e] ← r[h] -r[i]x[j] -r[j]x[i] b[e] ← -r[i]r[j] c1 ← Cs1 +    0ℓ 1 x a    mod q c2 ← Cs2 +    0ℓ 1 r b    mod q ρ ← U ({0, 1} κ ) Caux ← aCommit(t∥c1∥c2; ρ) Caux α ← U ([-p, p]) α z0 ← αx + r z1 ← αs1 + s2 Abort with probability 1 -p(αs1, z1) t, c1, c2, ρ, z0, z1
Let d be an LM-dimensional vector For e ∈ [LM], let (h, i, j) be the e-th element of equation ( 5) and C aux from equation (1). We end up with a proof of size

M d[e] ← αz0[h] -z0[i]z0[j] Accept if: (1) Caux = aCommit(t∥c1∥c2; ρ) (2) ∥z1∥ ∞ ≤ s2 log 2 L (3) ∥z1∥ 2 ≤ s2 √ L (4) Az0 = αy + t mod q (5) Cz1 +    0ℓ 1 z0 d    = αc1 + c2 mod q
|π| = ⌈log 2 (2p + 1)⌉ + κ + (ℓ 1 + L x + L M )⌈log 2 q⌉ + L x ⌈log 2 q⌉ + L⌈log 2 (s 2 log 2 L)⌉ (15) = ⌈log 2 (2p + 1)⌉ + κ + (ℓ 1 + 2L x + L M )⌈log 2 q⌉ + L⌈log 2 (s 2 log 2 L)⌉ (16)
The last term in (15) does not appear in the proof size of [YAZ + 19] as they treat z 1 (and z 2 in their case) as vectors in Z q . However, due to the rejection sampling, one has that they are Gaussian vectors and we can therefore reduce the amount of storage needed. Depending on the chosen parameters, this simple observation reduces the proof size by up to 20%.

E.3 Proof of Theorem E.1

Proof. Completeness: Consider an honest execution of the protocol, i.e., between a prover P[A, y, M; x] with x satisfying ( 14), and a verifier V[A, y, M]. Since the execution is honest and since aCommit does not use any internal randomness other than ρ, (1) is trivially verified. Next, due to the rejection sampling, P respond in the third move only with probability p(αs 1 , z 1 ). By Corollary E.1, it holds that the prover responds with probability at least (1-2 -λ )/M , and that z 1 is within statistical distance 2 -λ-1 (1 + 1/M ) of D Z L ,s2 . We further condition on a non-aborting transcript. Lemma 2.3 combined with the union bound gives

P[∥z 1 ∥ ∞ > s 2 log 2 L ∨ ∥z 1 ∥ 2 > s 2 √ L] ≤ 2 -λ-1 1 + 1 M + 2 -2L + 2Le -π log 2 2 L .
Equation ( 4) is easily verified as Az 0 = A(αx+r) = α(Ax)+Ar = αy+t mod q. Now, let e ∈ [L M ] and let (h, i, j) be the e-th element of M. We have

d[e] = αz 0 [h] -z 0 [i]z 0 [j] = α(αx[h] + r[h]) -(αx[i] + r[i])(αx[j] + r[j]) = α 2 (x[h] -x[i]x[j]) + α(r[h] -r[i]x[j] -r[j]x[i]) + (-r[i]r[j]) = αa[e] + b[e] mod q.
As a result, it holds that d = αa + b mod q. It thus yields

Cz 1 +   0 ℓ1 z 0 d   = C(αs 1 + s 2 ) +   0 ℓ1 αx + r αa + b   mod q = α   Cs 1 +   0 ℓ1 x a     +   Cs 2 +   0 ℓ1 r b     mod q = αc 1 + c 2 mod q,
proving (5). Combining it all yields

P[ P[A, y, M; x] , V[A, y, M] ̸ = 1] ≤ 1 -1/M + negl(λ).
Extractor: Now, assume that a cheating prover P can convince the verifier that they possess a witness for (A, y, M) with probability 2/(2p + 1) + ε for some non-negligible ε. We construct the extractor E that uses P via black-box access.

First, E runs P until it obtains an accepting transcript (t, c 1 , c 2 , α, z 0 , z 1 ). Between each run, E rewinds the inner randomness of P to have the same first move response. This first transcript is obtained in expected time T 1 = (2/(2p + 1) + ε) -1 . Then, E re-iterates the same process but sends challenges α ′ ̸ = α to P. Assuming aCommit is δ a b -binding and since the first move always uses the same randomness, E can therefore obtain another accepting transcript

(t, c 1 , c 2 , α ′ , z ′ 0 , z ′ 1 )
in expected time T 2 = (1/(2p + 1) + ε -δ a b ) -1 . It then continues running P with challenges α ′′ / ∈ {α, α ′ } to get a third accepting transcript (t, c 1 , c 2 , α ′′ , z ′′ 0 , z ′′ 1 ) in expected time T 3 = (ε -δ a b ) -1 . The total expected time is therefore T = T 1 + T 2 + T 3 ≤ poly(λ). Finally, the extractor E outputs the witness x = (α ′ -α) -1 (z ′ 0 -z 0 ) mod q. We now analyze the correctness of E. We further define ∆ 1 = α ′ -α and ∆ 2 = α ′′ -α. First, we have

Ax = ∆ -1 1 (Az ′ 0 -Az 0 ) mod q = ∆ -1 1 (α ′ y + t -(αy + t)) mod q (by (4)) = ∆ -1 1 (α ′ -α)y mod q = y mod q.
We now prove that x verifies the quadratic constraints except with probability δ SIS . For that, we define e

′ = z ′ 1 -z 1 , e ′′ = z ′′ 1 -z 1 , f ′ = z ′ 0 -z 0 , f ′′ = z ′′ 0 -z 0 , and g ′ = d ′ -d, g ′′ = d ′′ -d. The verification equation (5) gives                  Ce ′ +   0 ℓ1 f ′ g ′   = ∆ 1 c 1 mod q Ce ′′ +   0 ℓ1 f ′′ g ′′   = ∆ 2 c 1 mod q.
Cancelling the right-hand side provides us with

C(∆ 2 e ′ -∆ 1 e ′′ ) +   0 ℓ1 (∆ 2 f ′ -∆ 1 f ′′ ) (∆ 2 g ′ -∆ 1 g ′′ )   = 0 mod q.
The first block then gives [I ℓ1 |C 1 ](∆ 2 e ′ -∆ 1 e ′′ ) = 0 mod q. Yet, we can bound the norms of ∆ 2 e ′ -∆ 1 e ′′ using the verification equations ( 2) and (3) and get ∥∆ 2 e ′ -∆ 1 e ′′ ∥ ∞ ≤ 8ps 2 log 2 L = β ∞ and ∥∆ 2 e ′ -∆ 1 e ′′ ∥ 2 ≤ 8ps 2 √ L = β 2 . Since we assume that HNF-SIS ℓ1,L,q,β∞,β2 is δ SIS -hard, then no PPT adversary can solve it with advantage more than δ SIS . Hence, we get that ∆ 2 e ′ -∆ 1 e ′′ = 0 except with probability at most δ SIS . We now condition on ∆ 2 e ′ -∆ 1 e ′′ = 0. The second and third blocks in the above yields ∆ 2 f ′ = ∆ 1 f ′′ mod q and ∆ 2 g ′ = ∆ 1 g ′′ mod q. We now define r = z 0 -αx mod q. Then

z ′ 0 -α ′ x = z ′ 0 -∆ 1 x -αx = z ′ 0 -f ′ -αx mod q = r mod q (17) z ′′ 0 -α ′′ x = z ′′ 0 -∆ 2 x -αx = z ′′ 0 -∆ 2 ∆ -1 1 f ′ -αx = z ′′ 0 -∆ 2 ∆ -1 2 f ′′ -αx mod q = r mod q. ( 18
)
Now let e ∈ [L M ] and (h, i, j) be the e-th element of M. We have

d[e] = αz 0 [h] -z 0 [i]z 0 [j] = α(αx[h] + r[h]) -(αx[i] + r[i])(αx[j] + r[j]) = α 2 (x[h] -x[i]x[j]) + α(r[h] -r[i]x[j] -r[j]x[i]) + (-r[i]r[j]) = c[e]α 2 + a[e]α + b[e].
Due to Equations ( 17) and ( 18), we also have

d ′ = α ′ 2 c + α ′ a + b and d ′′ = α ′′ 2 c + α ′′ a + b. Hence, since ∆ -1 1 g ′ = ∆ -1 2 g ′′ mod q, we obtain (α ′ + α)c + a = (α ′′ + α)c + a mod q
which leads to (α ′′ -α)c = 0 mod q. Since α ′′ ̸ = α ′ and q is prime, then α ′′ -α ′ ∈ Z × q and therefore c = 0 mod q. This proves that for all (h, i, j) ∈ M, x[h] = x[i]x[j] mod q. As a result, the output of E is correct except with probability at most δ SIS . Simulator: We construct the following simulator S that simulates the distribution of an honest transcript but only using the public inputs. It proceeds as follows

1. α ← U ([-p, p]) 2. z 0 ← U (Z Lx q ) 3. t ← Az 0 -αy mod q 4. For e ∈ [L M ], let (h, i, j) be the e-the element of M. Then, d[e] ← αz 0 [h] - z 0 [i]z 0 [j] 5. z 1 ← D Z L ,s2 6. c 1 ← U (Z ℓ1+Lx+L M q ) 7. c 2 ← Cz 1 +   0 ℓ1 z 0 d   -αc 1 mod q 8. ρ ← U ({0, 1} κ ) 9. C aux ← aCommit(t∥c 1 ∥c 2 ; ρ) 10. C ′ aux ← aCommit(0; ρ) 11. Output (C aux , α, t, c 1 , c 2 , ρ, z 0 , z 1 ) with probability 1/M and (C ′ aux , α, ⊥) otherwise.
We now prove that the output of S is computationally indistinguishable from the transcript of an honest execution of the protocol. We proceed by game hopping. Game G 0 : This corresponds to an honest execution. Game G 1 : Here, the prover P retrieves the challenge α from the honest verifier by sending aCommit(0; ρ) for some ρ ← U ({0, 1} κ ). It then rewinds the verifier to its initial state including its inner randomness. It then proceeds as follows:

1. r ← U (Z Lx q ) 2. t ← Ar mod q 3. s 1 ← ψ L 1 4. s 2 ← D Z L ,s2 5. For e ∈ [L M ], let (h, i, j) be the e-the element of M. Then, a[e] ← r[h] - r[i]x[j] -r[j]x[i] and b[e] ← -r[i]r[j] 6. c 1 ← Cs 1 +   0 ℓ1 x a   mod q 7. c 2 ← Cs 2 +   0 ℓ1 r b   mod q 8. z 0 ← αx + r 9. z 1 ← αs 1 + s 2 10.
Set the binary variable abort to 1 with probability 1 -p(αs 1 , z 1 ) 11. ρ ← U ({0, 1} κ ) 12. C aux ← aCommit(t∥c 1 ∥c 2 ; ρ) and it sends C aux to the verifier 13. When receiving α ′ from the verifier, the prover aborts if abort = 1 and otherwise sends (t, c 1 , c 2 , ρ, z 0 , z 1 ).

Game G 2 : It is identical to G 1 except in the computation of t and c 2 . They are instead computed to verify equations ( 4) and ( 5) in the verification:

1. t ← Az 0 -αy mod q 2. For e ∈ [L M ], let (h, i, j) be the e-the element of M. Then, d[e] ← αz 0 [h] - z 0 [i]z 0 [j] 3. c 2 ← Cz 1 +   0 ℓ1 z 0 d   -αc 1 mod q Game G 3 : It is identical to G 2 except for the computation of C aux .
1. C aux ← aCommit(0; ρ) if abort = 1 and C aux ← aCommit(t∥c 1 ∥c 2 ; ρ) otherwise.

Game G 4 : It is identical to G 3 except in the computation of z 1 and abort.

1. z 1 ← D Z L ,s2 2. Set abort = 1 with probability 1 -1/M and 0 otherwise Game G 5 : It is identical to G 4 except in the computation of c 1 . 1. c 1 ← U (Z ℓ1+Lx+L M q ) Game G 6 : It is identical to G 5 except in the computation of z 0 1. z 0 ← U (Z Lx q )
We now prove that each game is indistinguishable from the next. First, since the verifier V is honest, the challenge α ′ is fully determined by its inner randomness. As it is rewinded, we always have α ′ = α. All other variables are identically distributed, which gives

∆(View G0 (V), View G1 (V)) = 0. (19)
By the completeness of the protocol, t and c 2 are uniquely determined by the other variables and the verification equations ( 4) and ( 5). Thus

∆(View G1 (V), View G2 (V)) = 0. ( 20
)
Since aCommit is δ a h -hiding, it holds that a PPT adversary A can distinguish between games G 2 and G 3 with advantage at most δ a h .

|P[A(View

G2 (V)) = 1] -P[A(View G3 (V)) = 1]| ≤ δ a h . (21)
Then, by Corollary E.1, it directly holds that the computation of z 1 and abort in G 4 is within statistical distance 2 -λ-1 (1 + 1/M ) of that of game G 3 . Hence

∆(View G3 (V), View G4 (V)) ≤ 2 -λ-1 (1 + 1/M ). (22)
We then use the hiding property of the commitment scheme from [BDL + 18] to argue that G 4 and G 5 are indistinguishable under the LWE assumption.

The details are already provided in [YAZ + 19]. More precisely, since we assume that HNF-LWE ℓ2,ℓ1+Lx+L M ,q,ψ1 is δ LWE -hard, then for any PPT adversary A we get

|P[A(View G4 (V)) = 1] -P[A(View G5 (V)) = 1]| ≤ δ LWE . (23)
In G 5 , z 0 = αx + r where r is uniform in Z Lx q and independent of αx. Hence, z 0 is also uniform in Z Lx q . Thus:

∆(View G5 (V), View G6 (V)) = 0. (24)
Then, the distribution of the transcript in G 6 no longer depends on the witness x and is exactly the same as the output of S. Combining Equations ( 19), ( 20), ( 21), ( 22), ( 23) and (24) yields

P[A(View G0 (V)) = 1] -P[A(S(A, y, M)) = 1] ≤ δ a h + 2 -λ-1 (1 + 1/M ) + δ LWE ,
as desired.

F Instantiating the Protocols

In this section we show how to instantiate the different relations to be proven in zero-knowledge with the proof system of [YAZ + 19]. More precisely, we need to have zero-knowledge arguments for the opening of an Ajtai commitment, and for the verification equation of our signature with efficient protocols. We detail both in Sections F.1 and F.2. For completeness and for performance comparison purposes, we also instantiate the construction Libert et al. [LLM + 16] with the framework of [YAZ + 19].

When concretely evaluating these proofs, we consider the optimizations proposed in Appendix E, consisting in compacting the commitments of the original framework and in better parameter selections, which leads to substantial efficiency improvements.

F.1 Proof of Commitment Opening.

Consider a prover with private input m ∈ {0, 1} m3 and r ′ ∼ D Z m 1 ,σ3 , and public input pp, pk. Recall that by Lemma 2.3, we have ∥r ′ ∥ ∞ ≤ σ 3 log 2 m 1 with overwhelming probability. We can thus define α 3 = ⌈σ 3 log 2 m 1 ⌉ and assume that r ′ ∈ [-α 3 , α 3 ] m1 . The prover wishes to prove that

Ar ′ + Dm = c mod q ∧ ∥r ′ ∥ ∞ ≤ α 3 ∧ m ∈ {0, 1} m1 .
We thus transform this relation into one that fits the Yang et al. framework. For that, we first define a 3 = α 3 1 m1 . Next, we define

r ′′ = r ′ + a 3 ∈ [0, 2α 3 ] m1 . Let k α3 = ⌊log 2 2α 3 ⌋ + 1 and define 11 g α3 = [⌊(2α 3 + 2 i-1 )/2 i ⌋] i∈[kα 3 ] ∈ Z 1×kα 3 ,
and G α3 = I m1 ⊗ g α3 . We then denote by r ′ ∈ {0, 1} m1kα 3 a binary decomposition of r ′′ along g α3 , i.e., that verifies r ′′ = G α3 r ′ . Such a decomposition can be efficiently computed. It now suffices to prove the following

AG α3 r ′ + Dm = c + Aa 3 mod q ∧ r ′ ∈ {0, 1} m1kα 3 ∧ m ∈ {0, 1} m3 . By defining A = [AG α3 |D], x = [r ′ T |m T ] T , y = c + Aa 3 and M = {(i, i, i); i ∈ [m 1 k α3 + m 3 ]}, we have ((A, y, M); x) ∈ R * . The length of the witness is L x = m 1 k α3 + m 3 , and the size of M is L M = L x . Note that since q is prime, the constraint x[i] = x[i] 2 mod q indeed implies that x[i] ∈ {0, 1}.
When m 1 ≫ λ, the fast mode of Section 4.2 compresses the size of the witness and the constraint set as we now prove that Hr ′ has coefficients bounded by σ 3 √ m 1 log 2 λ. It yields a witness of size L x = m 1 +k(⌊log 2 (2σ 3 √ m 1 log 2 λ)⌋+ 1) + m 3 , with k = λ/ log 2 (9/5), and L M = L x -m 1 .

F.2 Proof of Message-Signature Pair Possession.

Here, the prover has a private input m ∈ {0, 1} m3 and (τ, v) ∈ Z q × Z m and has to prove

Av 1 -Bv 2 + τ Gv 2 -Dm = u mod q, where v 1 ∈ Z m1 and v 2 ∈ Z m2 , with ∥v 1 ∥ ∞ ≤ σ 1 log 2 m 1 , ∥v 2 ∥ ∞ ≤ σ log 2 m 2 , τ ∈ T and m ∈ {0, 1} m3 . We define        α 1 = ⌈σ 1 log 2 m 1 ⌉ k α1 = ⌊log 2 2α 1 ⌋ + 1 g α1 = (2α 1 + 2 i-1 )/2 i i∈[kα 1 ] α = ⌈σ log 2 m 2 ⌉ k α = ⌊log 2 2α⌋ + 1 g α = (2α + 2 i-1 )/2 i i∈[kα] k q ′ = ⌊log 2 q ′ ⌋ + 1 g q ′ = ⌊(q ′ + 2 i-1 )/2 i ⌋ i∈[k q ′ ]
Further, we define a 1 = α 1 1 m1 and a = α1 m2 . Next, we set G α1 = I m1 ⊗ g α1 , and G α = I m2 ⊗g α . We define v ′ 1 = v 1 +a 1 , and v ′ 2 = v 2 +a. We then denote v j their respective binary decomposition along g α1 , g α , i.e., such that G

α1 v 1 = v ′ 1 , and G α v 2 = v ′ 2 .
We also denote by τ the binary decomposition of τ along g q ′ such that τ = g q ′ τ . We need however to deal with the product term τ v 2 . We use the same idea as for subset-sums from the framework of Yang et al. [YAZ + 19]. For that, we define u 2 = Gv 2 ∈ Z n , and u ′ 2 = τ u 2 . This gives an additional linear relation, but fewer decompositions. The prover now has to prove that

   AG α1 v 1 -BG α v 2 + u ′ 2 -Dm = u + Aa 1 -Ba mod q GG α v 2 -u 2 = Ga mod q -τ + g q ′ τ = 0 mod q We thus define x = [τ |τ |v 1 |v 2 |m|u 2 |u ′ 2 ] ∈ Z Lx , where L x = 1 + k q ′ + m 1 k α1 + m 2 k α + m 3 + 2n, as well as A =    0 n×1 0 n×k q ′ AG α1 -BG α -D 0 n×n I n 0 n×1 0 n×k q ′ 0 n×m1kα 1 GG α 0 n×m3 -I n 0 n×n -1 g q ′ 0 n×m1kα 1 0 1×m2kα 0 1×m3 0 1×n 0 1×n    and y = [u + Aa 1 -Ba|Ga ′ |0] mod q ∈ Z 2n+1 q . Finally, we define M 1 = {(i, i, i); i ∈ [2, 1 + k q ′ + m 1 k α1 + m 2 k α + m 3 ]},
which corresponds to the coefficients that need to be binary. We then need to add the relations u ′ 2 = τ u 2 . For that, we define

M 2 = {(1 + k q ′ + m 1 k α1 + m 2 k α + m 3 + n + i, 1, 1 + k q ′ + m 1 k α1 + m 2 k α + m 3 + i); i ∈ [n]},
and construct M = M 1 ∪M 2 . The witness has length L x , and M is of size L M = L x -n -1. Using the fast mode instead proves that H 1 v 1 , H 2 v 2 have coefficients bounded by σ 1 √ m 1 log 2 λ and σ √ m 2 log 2 λ respectively. It yields a witness of size

L x = 1 + k q ′ + m 1 + m 2 + m 3 + 2n + k(⌊log 2 (2σ 1 √ m 1 log 2 λ)⌋ + ⌊log 2 (2σ √ m 2 log 2 λ)⌋+2
), with k = λ/ log 2 (9/5), and L M = L x -m 1 -m 2 -n-1.

Remark F.1. In the case where q ′ = q, the tag does not need to be decomposed in binary form. However, when the proof system is run only a few number of times, we need to drastically increase the size of challenges to reach a negligible soundness error. For example, to obtain a negligible soundness error in one iteration, one needs to take challenges of size p = 2 λ . Because the SIS bound for the proof system is β ∞ = poly(λ) • p 2 , one must take q to be polynomially larger than p 2 . In Algorithm 3.1, choosing q ′ = q then leads to a tag space T of size at least poly(λ)2 2λ . As a result, the proof of Lemma 3.2 incurs an exponential reduction loss of 1/|T | = 2 -2λ /poly(λ). To circumvent this limitation, one can choose q ′ = poly(λ) ≪ q to make the reduction loss acceptable. It implies that the signature verification must ensure that τ < q ′ , which we consider when proving possession of a message-signature pair. , where k = ⌈log 2 q⌉. For a fair comparison, we detail here how to use the framework from [YAZ + 19] for the construction of [LLM + 16]. For this section only, we set the parameters differently according to [LLM + 16]. We thus have m = 2nk, σ 1 = σ 1 + 8(N + 1) 2 m 3 . Also, prior to being signed, the message blocks are encoded using b → (1 -b, b). This means that although the relevant message information is of mN bits, it is treated as a message of 2mN bits. To be thorough, one would need to prove that the message is properly encoded in addition to proving that the message is binary. This can be done by proving the additional relation (I mN ⊗ [1 1])m = 1 mN which proves that the consecutive bits b, 1 -b indeed sum to 1. Since the relation is proven modulo q, one must make sure that the coefficients are m are also proven binary. For simplicity, we do not take this into account in the estimations of Table H.1. The matrices A i are uniform in Z n×m q , but the commitment key matrices D i are uniform in Z 2n×2m q . We define H = I 2n ⊗ [2 0 . . . 2 k-1 ]. Since the binary decomposition operator is non-linear, the verification equation has to be splitted into two equations as follows.

Av 1 + A 0 v 2 + i∈[ℓ] A i (τ [i]v 2 ) -Dw = u mod q, Hw = D 0 r -i∈[N ] D i m i mod q,
with ∥v 1 ∥ ∞ , ∥v 2 ∥ ∞ ≤ σ log 2 m, ∥r∥ ∞ ≤ σ 1 log 2 2m as well as τ ∈ {0, 1} ℓ , m ∈ {0, 1} 2mN , and w ∈ {0, 1} 2nk . We define α, α 1 , k α , k α1 , g α , g α1 in a similar way as Section F. We then define a = α1 m , a 1 = α 1 1 2m and set G α = I m ⊗ g α and G α1 = I 2m ⊗ g α1 . Then, we define u i = A i v 2 ∈ Z n , as well as u ′ i = τ [i]u i constituting 2ℓ vectors 12 of Z n . The verification equations thus become , 12 Each bit of the tag not only represents a witness in itself but also entails two full intermediate witnesses ui, u ′ i due to τ [i]v2. It leads to a much larger witness vector, which is a source of inefficiencies. where k = λ/ log 2 (9/5) according to Lemma 4.1.

     AG α v 1 + A 0 G α v 2 + i∈[ℓ] u ′ i -Dw = u + (A + A 0 )a mod q, D 0 G α1 r + i∈[N ] D i m i -Hw = D 0 a 1 mod q, A i G α v 2 -u i = A i
A =         0 AG α A 0 G α 0 • • • 0 I n • • • I n -D 0 • • • • • • 0 -H D 0 G α1 D 1 • • • D N A 1 G α -I n . . . . . . A ℓ G α -I n        

G A Stateless Variant

We now describe how to obtain a stateless version of our signature scheme of Section 3. We describe it for the module version at a high level only. To obtain a stateless variant, one need to find a way to generate tags without encountering collisions to only emit one signature per tag, and without enduring an exponential loss in the security proof due to guesses. The first constraint imposes an exponentially large tag space, which at first glance seems incompatible with the second constraint. To meet the second constraint, we use the prefix guessing method used in [LLM + 16] which we refine to avoid a blowup in the key size and subsequent zero-knowledge proofs. At a high level, when guessing a tag τ ∈ {0, 1} ℓ in [LLM + 16], the authors guess the longest prefix among the emitted tags τ (i) that will match with the prefix of the tag τ * used in the type I forgery. In our case, our tag is a single element of S bin which voids this method as each bit would need to be multiplied to a different matrix A i to cancel the gagdet G when τ = τ * in order to obtain a M-SIS solution.

To mimic the prefix guessing, we remove the Hamming weight condition on the tag τ ∈ S bin and instead decompose it into k parts, say k = 4, as follows. Sample τ 1 , . . . , τ 4 uniformly at random in n/4-1 i=0 {0, 1} • X i . To construct the trapdoor matrix A τ , compute A τ = [A| i∈ [4] τ i B i -B] where B i = X (i-1)n/4 G -AR i mod qR. The B i are added to the public key, and the R i to the secret key. We then have

A τ = [A|τ G -A(R + i∈[4] τ i R i )].
Since τ = τ 1 + τ 2 X n/4 + τ 3 X n/2 + τ 4 X 3n/4 ∈ S bin ⊂ R × q , we can indeed sample preimages using the modified trapdoor R τ = R + i τ i R i . This has the effect of requiring a slightly larger Gaussian width as a result because we must replace ∥R∥ 2 by

∥R τ ∥ 2 ≤ ∥R∥ 2 + i∈[4] ∥τ i ∥ 1 ∥R i ∥ 2 ≤ (1 + n) • ( √ nm 1 + √ nm 2 + t).
It thus entails a mild increase in σ, which only affects the width of v 2 in the signature as the width σ 1 for v 1 smoothes out this increase by requiring σ 1 ≥ ∥Um∥ 2 which is generally larger for a big enough m 3 . Regardless, the factor n, typically 256, only adds log 2 n bits to each coefficient.

With this modification, we can use the prefix guessing method. Concretely, as in [LLM + 16], we simply make a guess on the length ℓ + of the longest prefix common to the forgery tag and the ones from the signature queries. In our case, this guess is correct with probability 1/k. We thus only have to guess the value of τ * ℓ + +1 and construct the key material accordingly. We will thus hide the guessed prefix in the matrix B, and generate the B i simply as B i = AR i for the indices i beyond the prefix length. With this method, we only have a security loss of k2 n/k while having an exponentially large tag space of size 2 n .

H Parameters and Efficiency

In this section, we instantiate the two versions of our signature scheme with concrete parameters in order to reach λ = 128 bits of quantum security. All the concrete hardness estimates for the SIS, LWE, M-SIS, M-LWE problems are done with the Core-SVP methodology, using the BKZ cost model with sieving SVP oracle. In this model, the classical security is given by λ c = 0.292b [BDGL16] and the quantum security by λ q = 0.265b [Laa15], where b is the BKZ blocksize. We explain our choice of parameters for both the standard and module version by encompassing the zero-knowledge arguments of message-signature possession. We however note that for a standard use of the signature schemes, one could choose different parameters. We choose to instantiate it for Q = 2 30 signature queries, representing the number of signature issuance. We believe this choice is reasonable for most applications.

H.1 Instantiating the Standard Signature

We provide in Table H.2 an example parameter set along with the size of the keys, signature, and proof of possession for the signature of Section 3. It makes use of the zero-knowledge framework of [YAZ + 19] improved with the enhanced fast mode from Section 4.2 and the optimizations of Appendix E (except the compacted commitments, as explained below) that we have introduced.

H.2 Instantiating the Module Signature

We now rely on the framework of [LNP22] for the zero-knowledge argument. The module construction no longer suffers from the requirement of a large modulus. Indeed, in the module case, we can choose an exponentially large challenge space while keeping the size of the challenges constant. The same thing occurs for our tag space. Before, we needed to take q ≥ q ′ where q ′ was both the bound on the tags and the size of the tag space. In the module case, we can take binary tags while adjusting the value of w in order to have a sufficiently large tag space, i.e., |T w | ≥ Q. Additionally, because the modulus of the signature q is different from the modulus of the proof system q π = q 1 q, we can first adjust the parameters of our signature before setting the parameters of the proof system. We proceed as in the previous section, accounting for the reduction loss of Lemma 3.5 and 3.6. To choose the parameters of the proof system, we proceed as prescribed in [LNP22, Sec. 6.1], with the challenge space of [LNP22, Fig. 3]. For simplicity, we choose parameters close to those provided in their group signature instantiation. We give the detailed parameter set in Table H.3 with security and efficiency estimates. To avoid collision between our notations and the proof system parameters, we specify the notations used in [LNP22] in the description column.

This construction based on structured lattices leads to drastic efficiency gains in both key and proof sizes as summarized in Table 1.1, which further reinforce the concrete feasibility of efficient privacy-enhancing post-quantum signatures. In particular, it shows that a proof of knowledge of a signature issued on a committed (secret value), one of the main building blocks of privacy-preserving primitives, can represent less than 700 KB, which is a considerable improvement over [LLM + 16] and may have many applications.

Instantiating the Anonymous Credentials. The anonymous credentials follows exactly the same process as for the module signature. The only difference is that we in addition require the hardness of M-ISIS d,2d,q, √ 2nd . The parameters of our signature already overshot the hardness of the latter. We give an example for a vector of 10 attributes of 128 bits each, and the proof size corresponds to the non-interactive transcript size when |I| = 4 attributes are revealed. The message m thus has dimension m 3 = 2d + 10. All the parameters and efficiency estimates of the anonymous credentials are given in Table H.4. We achieve satisfactory sizes of less than 750 KB. Improving our SEP scheme would directly result in similar improvements to the anonymous credentials system.

H.3 Parameter Sets

  For a lattice L of rank n, we define the discrete Gaussian distribution D L,σ,c of support L, width σ and center c by D L,σ,c : x ∈ L → ρ σ,c (x)/ρ σ,c (L), where ρ σ,c (L) = x∈L ρ σ,c (x).

  Input: Public parameters pp as in Algorithm 3.5. Output: (opk, osk) ← KeyGen(pp). ▷ Algorithm 3.6 Algorithm 5.4: UKeyGen Input: Public parameters pp as in Algorithm 3.5. 1. s ← U (S ms bin ). 2. t ← Dss mod qR. Output: (upk, usk) = (t, s). Algorithm 5.5: Issue (Credential Issuance Protocol) Input: Organization O with osk, opk, upk, pp, st, and a user U with m ∈ S m ′ 3 bin and usk, upk, opk, pp, m. User U ←→ Organization O. 1. Run the interactive protocol OblSign from Algorithm 5.1, where O plays the signer and with message m = [usk T |m T ] T . In this syntax, i.e., [FHS19], the signer knows m but not usk. Hence the ZKAoK is adapted to prove knowledge of short (r ′ , s) such that ci Dimi = Ar ′ + Dss mod qR, and additionally that Dss = upk mod qR.

  Fig. B.1. Existential Unforgeability against Chosen Message Attacks game

Fig. C. 1 .

 1 Fig. C.1. Anonymity Game for the Anonymous Credentials System. The index jα is the user index associated to the issuance index j ′ α . The attribute vector m (j ′ α ) is the attribute vector used in the j ′ α issuance, and must satisfy (m

Fig

  Fig. C.2. Unforgeability Game for the Anonymous Credentials System.

Fig

  Fig. E.1. Zero-knowledge Argument of Knowledge for Equation (14) with compacted commitments.

F. 3

 3 Instantiating [LLM + 16] with R * The original construction by Libert et al. [LLM + 16] uses the binary decomposition of the commitment c instead of using the commitment itself. It additionally bases itself on the Boyen signature scheme, and involves an extra matrix D ∈ Z n×2nk q

  a for all i ∈ [ℓ],We thus definex = [τ |v 1 |v 2 |u 1 | . . . |u ℓ |u ′ 1 | . . . |u ′ ℓ |w|r|m 1 | . . . |m N ] ∈ Z Lx, where L x = ℓ + 2mk α + 2ℓn + m + 2mk α1 + 2mN . We then define

  define M 1 = {(i, i, i); i ∈ [ℓ + 2mk α ] ∪ [ℓ + 2mk α + 2ℓn + 1, L]},which corresponds to having all the coefficients of x to be binary, except for the u i , u ′ i . We then need to add the relationsu ′ i = τ [i]u i for i ∈ [ℓ].For that, we defineM 2 = {(ℓ + 2mk α + ℓn + n(i -1) + j, i, ℓ + 2mk α + n(i -1) + j); (i, j) ∈ [ℓ] × [n]},and construct M = M 1 ∪ M 2 . The witness has length L x , and M is of size L xℓn as well. The fast mode of Section 4.2 reduces the witness and relation set sizes to   L x = ℓ(2n + 1) + m(5 + 2N ) + k(2⌊log 2 (2σ √ m log 2 λ)⌋ +⌊log 2 (2σ 1 √ 2m log 2 λ)⌋ + 3) L M = L x -ℓn -4m,

Table 1 .

 1 1. Comparison of efficiency estimates of the signature schemes of [LLM + 16],

		setting λ	|pk| (mb) |sk| (mb) |sig| (kb) |π| (kb)
	[LLM + 16] (exact proof) stand. 128	296 • 10 4	156 • 10 2	862 • 10 102 • 10 5
	[LLM + 16] (fast mode) stand. 128	707 • 10 4	372 • 10 2 139 • 10 2 671 • 10 3
	Sec. 3 (exact proof)	stand. 128	115 • 10	892	261	306 • 10 3
	Sec. 3 (fast mode)	stand. 128	296 • 10	229 • 10	418	177 • 10 2
	Sec. 3.3 (exact proof) module 128	7.8	8.9	273	639

  To circumvent these two shortcomings, we instead use the more recent framework byYang et al. [YAZ + 19]. It combines the perks of Stern-like ZKAoK and Fiat-Shamir with Aborts ZKAoK to reach a framework with standard soundness and inverse polynomial soundness error. This requires fewer iterations as a result. More precisely, the framework of [YAZ+ 19] provides a ZKAoK for the relation

Table H .

 H 1. Selected parameters, security and efficiency estimates of the signature scheme of [LLM+ 16].

	Parameters Description		Exact Proof	Fast Mode
	Parameters Description	Signature	Exact Proof	Fast Mode
	λ	Security parameter	Signature	128	128
	λ n	Security parameter SIS dimension		128 495	128 795
	n q	SIS dimension Modulus		1650 2 155 -31	2550 2 155 -31
	q q ′	Modulus Tag bound		2 155 -31 2 31	2 155 -31 2 31
	ℓ m1	Tag bit-size (λ + 2 log 2 Q) First trapdoor dimension	188 48732	188 78070
	m m2	Trapdoor dimension Second trapdoor dimension	511500 76725	790500 123225
	Nmsg m3	Number of message blocks Message bit-size	1 128	1 128
	σ t	Pre-image sampling width Spectral norm slack	24324 7.5	32014 7.5
	σ1 σ	Commitment randomness width Pre-image sampling width	50335037584951 127285811917979 6015.41 7595.30
	λI/λ * I σ1 λII/λ * II σ2	Required/Reached SIS security (I) σ 2 + σ 2 2 Required/Reached SIS security (II) Commitment randomness width	166/167 6015.42 158/163 12.73	166/167 7595.31 158/170 12.73
	λIII/λ * III λI/λ * I	Required/Reached SIS security (III) Required/Reached SIS security (I)	128/506 158/190	128/629 158/189
	|pk| λII/λ * II	Public key size (MB) Required/Reached SIS security (II)	2963 • 10 3 mb 182/190	7076 • 10 3 mb 182/189
	|sk| |pk|	Secret key size (MB) Public key size (MB)		1559 • 10 1 mb 1148 mb	3725 • 10 1 mb 2956 mb
	|sig| |sk|	Signature size (KB) Secret Key size (MB)		8617 kb 892 mb	13895 kb 2293 mb
	|pp| |sig|	Public parameters size (MB) Signature size (KB)	1640 • 10 1 mb 261 kb	3917 • 10 1 mb 418 kb
	|pp|	Proof Public parameters size (MB)	1.2 mb	1.9 mb
	ℓ1	HNF-SIS dimension	Proof	8350	8000
	ℓ2 ℓ1	HNF-LWE dimension HNF-SIS dimension		7900 7850	7900 7500
	p ℓ2	Size of challenges HNF-LWE dimension		2 λ/2 7850	2 λ/2 7850
	N p	Number of proof iterations Size of challenges	2 2 λ/2	2 2 λ/2
	M N	Rejection sampling repetition rate Number of proof iterations	27 2	27 2
	Lx M	Witness length Rejection sampling repetition rate	74788088 27	6510457 27
	LM Lx	Relation set length Witness length		74477888 2259407	2869057 210777
	δs LM	Soundness error Relation set length		2 -λ 2258911	2 -λ 8686
	λ * SIS,π δs	Reached HNF-SIS security Soundness error	128 2 -λ	129 2 -λ
	λ * LWE,π λ * SIS,π	Reached HNF-LWE security Reached HNF-SIS security	130 128	130 129
	|π| λ * LWE,π	Proof size (KB) Reached HNF-LWE security	10198709 kb 129	671581 kb 129
	|π|	Proof size (KB)		306367 kb	17662 kb

Table H .

 H 2. Selected parameters, security and efficiency estimates of the signature scheme of Section 3.

© IACR 2023. An extended abstract of this work appeared at Crypto 2023. This is the full version.

All along this paper, the words signature and certificate will be used interchangeably.

In this paper, we use "classical" to denote cryptographic constructions that rely on computational assumptions broken by quantum algorithms.

To remain as broad as possible, we use statistical trapdoors and related tools. One could however get further efficiency gains by using a computational instantiation.

In our protocol for signing hidden messages, we will have to enforce this requirement but this can be done easily by setting A as some hash output.

] T , m and the public input is composed of A, B, D, G, u. We defines 1 = [v 1 |v 2 |m|τ ] ∈ R m1+m2+m3+1 and s = [s 1 |σ -1 (s 1 )] ∈ R 2(m1+m2+m3+1) .

Note that the Rényi divergence is taken in the opposite direction than before, hence the presence of the factor (1 + ε)/(1 -ε).

There may be a correctness error which is similar to the completeness error of zeroknowledge arguments.

Choosing gα 3 this way ensures that for any binary vector x, gα 3 x ∈ [0, 2α3].

Acknowledgments. This work has received a French government support managed by the National Research Agency in the France 2030 program, with reference ANR-22-PETQ-0008 PQ-TLS, as well as in the ASTRID program, under the national project AMIRAL with reference ANR-21-ASTR-0016, and finally in the MobiS5 project, with reference ANR-18-CE-39-0019-02 MobiS5. We also thank our anonymous reviewers from Crypto'23.

Note that for all i ∈ [Q], we have

where the contribution in G vanishes only for i = i + , as there is no collision. The adversary B thus forms pp = (D; g; λ, n, m 1 , m 2 , m 3 , m, q, σ, σ 2 , σ 1 ) and the public key pk = (A, B, u), and sends both to A.

Query Stage: We distinguish the queries for i ̸ = i + from the i + -th query. First, consider the i-th query, for i ̸ = i + , on the message m (i) . B samples a fresh randomness r (i) from D Z m 1 ,σ2 and computes the commitment c = Ar (i) + Dm (i) mod q. Since τ (i) -τ (i + ) ∈ Z × q , B computes

Note that v (i) is correctly distributed and passes verification (with overwhelming probability by Lemma 2.2 and 2.3). The signature given to A is sig i = (τ (i) , v (i) ).

Now consider the i + -th query. In this case, B simply computes v (i + ) = vr 0 -Um (i + ) 0 m2 and gives sig i + = (τ (i + ) , v (i + ) ) to A. We analyze later the distribution of v (i + ) , but notice that the verification equation is verified because of the definition of u.

A τ (i + ) v (i + ) = u + A τ (i + ) Um (i + ) 0 m2 mod q = u + AUm (i + ) mod q = u + Dm (i + ) mod q.

Forgery Stage: After at most Q queries, A outputs a Type II forgery (τ * , v * ) on a new message m * . If A fails to output a valid forgery, event that we denote by Abort 1 , then B aborts. We now condition on ¬Abort 1 . At this point, B checks its guess on i + and aborts if τ * ̸ = τ (i + ) . We denote this event Abort 2 , and further condition on ¬Abort 2 . It holds that

As a result, B forms the vector

Finally, it holds that v is statistically close to an elliptical discrete Gaussian distribution, where v 1 is of width m1+m2) . This shows that an honest execution of Issue succeeds with overwhelming probability conditioned on the zero-knowledge argument to pass.

We now consider a successful execution of the credential issuance process, i.e., (⊥; cred) ← Issue O,U ((osk, opk, upk, pp, st, m); (usk, upk, opk, pp, m)). Because the execution did not abort, it means that Verify(pk, m, (τ, v), pp) = 1. Directly from the completeness of the zero-knowledge argument of knowledge, we get that Show U,V ((usk, opk, pp, m, (τ, v)

C.2.2 Anonymity. We now prove that the showing of credentials to verifiers or organizations does not leak information about the user's concealed attributes and credential except that they own a valid credential on the disclosed attributes.

Lemma C.2. The anonymous credentials of Section 5.3 is anonymous based on the zero-knowledge property of the ZKAoK involved in Show.

Proof. We proceed by a single game hop. We define a modified version of the anonymity game of Figure C.1. It is exactly the same game except that when interacting with the adversary in Show C,A ((usk j b , opk, pp, m (j ′ b ) , cred (j ′ b ) , I), •), the challenger C will simulate the interaction, i.e., without resorting to usk j b , (m

. By the zero-knowledge property of the zero-knowledge argument, the advantage of A in the modified game is negligibly close to that it would have in the original game. Now, the view of A only depends on (m

) i∈I , which does not depend on b as we require (m

Thence, the view of A is independent of b and therefore its advantage is 0. It proves that the advantage of A in the original anonymity game is negligible. C.2.3 Unforgeability. We finally prove that a user cannot prove knowledge of a credential they did not receive from a successful execution of the issuance protocol. At a high level, if an adversary is able to do so, then it either breaks the soundness of the ZKAoK or was able to forge a signature.

Our last task is then to find a suitable upper bound on x. More concretely, we want to prove that x ≤ 2 3 . To this end, we will show that, for any vector u uniformly sampled from {-1, 0, 1} n-1 and any vector w ∈ Z n-1 q , the probability (over the choice of u) that j u j w j ∈ (-q 2 , -

when the requirements of our lemma are fulfilled.

In our case, we first recall that the elements of the sets {h j } j∈S are uniformly sampled from {-1, 0, 1} n-1 that we identify to Z 3 seen as an additive group.

where the previous equation holds in

, we define

We then know that

What remains to prove is that this implies that at least one of these representatives is not in

Let us assume, without loss of generality that both Σ u and Σ u ′ are in this set (else, we are done). This means (over Z) that

for some integer k and some r ∈ [-4B, 4B]. Therefore Σ u ′′ = -r -kq and, as it is an element of (-q 2 , q 2 ) (as any representative), this means that

In other words, for all w ∈ Z n-1 q , among the 3 representatives of any element of T , at least one is such that j u j w j is not in this set, which proves that x ≤ 2 3 and hence our lemma.

E Optimizing the Zero-Knowledge Framework

We detail here three independent optimizations of the framework from [YAZ + 19]. We note that the first two optimizations apply as is to the original framework, while the third involves further changes.

Concrete Hardness

Assumptions. The first one consists in changing the underlying hardness assumptions. Instead of using worst-case to average-case connections to standard lattice problems, we use slightly overstretched parameters for which the hardness of LWE is only based on concrete hardness arguments. The goal is to change the distribution of the randomness used to commit to the witness x in the original proof so that it leads to smaller elements. More

Proof. Let x be a random vector whose coefficient are independent and identically distributed according to ψ 1 . Therefore, for all i ∈ [n], x 2 i follows a Bernoulli distribution with parameter 5/8. Then, define the random variable X = ∥x∥

Hence, since X follows a binomial distribution B(n, 5/8). By Hoeffding's inequality, for all t > 0, we have

Since E[X] = 5n/8, then it holds that for all δ > 0, setting t = 5nδ/8 > 0 gives

We also recall the rejection sampling results from [Lyu12,Thm. 4.6,Lem. 4.7], which we adapt slightly to our case. In particular, we allow for a probabilistic bound on the shifts from V , resulting in very small changes in the acceptance probability and statistical distance.

Lemma E.2 (Adapted from [Lyu12,Thm. 4.6,Lem. 4.7]). Let n be a positive integer, and V, Z two countable set of R n . Let T be a positive real, and we define

Let f be a probability distribution on Z, and (g v ) v∈V a family of probability distributions on Z such that

for some ε ≥ 0. We then define two distributions

M gv(z) ). P 2 : Sample v ← h, and z ← f . Output (v, z) with probability 1/M . Then, it holds that P 1 outputs something with probability at least (1-ε)(1-ε ′ ) M , and that

When ε = ε ′ and M ≥ 1, we simply have

We first bound the probability that P 1 outputs something, where the probability is over

We then obtain the following corollary. We formulate it to give the freedom to choose the repetition rate M and the tail bound error. Note that in [Lyu12], M is determined by T , σ and the tail bound error. We instead choose M and the tail bound error, and then determine the minimal σ needed.

Corollary E.1. Let n, p be positive integers. Let L be a lattice of rank n, and let V = [-p, p] n . Let T = p 5n(1 + δ)/8, where δ = 32(λ + 1)/(25n log 2 e). Define h the distribution obtained by sampling α from U ([-p, p]) and s from ψ n 1 and outputting v = αs. Further, let M > 1, t = (λ + 2)/(π log 2 e) and define σ min = (-t + t 2 + ln(M )/π) -1 • T . Let σ ≥ σ min . We now define two distributions

Then, it holds that P 1 outputs something with probability at least (1 -2 -λ )/M , and that

Proof. Due to the definition of h, T, δ and Lemma E.1, we have

Let v ∈ V T , and z ← D L,σ . Then, we have

Except with probability at most 2e -πt 2 = 2 -λ-1 , it holds that |⟨v , z⟩| ≤ σt∥v∥ 2 by Lemma 2.3. We now condition on |⟨v , z⟩| ≤ σt∥v∥ 2 . It yields

The way we defined σ min , we have that T /σ min is the only positive solution to x 2 + 2tx -ln(M )/π = 0. Since, we have σ ≥ σ min , we have that T /σ is between the two solutions of the equation and as such we have that (T /σ) 2 + 2t(T /σ) -ln(M )/π ≤ 0. It can be re-written as

Hence, conditioned on |⟨v , z⟩| ≤ σt∥v∥ 2 , it holds that f (z)/g v (z) ≤ M . We obtain

thus proving Equation ( 13) as required. Then, we can set ε = 2 -λ-1 = ε ′ .

Invoking Lemma E.2 yields the result. The probability of outputting something is at least

The security properties of the zero-knowledge argument rely on the Short Integer Solution (SIS) problem [Ajt96] and the Learning With Errors (LWE) problem [Reg05] in Hermite Normal Form (HNF).

Definition E.1 ((HNF) Short Integer Solution). Let n, m, q be positive integers, and

We say that HNF-SIS is δ-hard if for any probabilistic polynomial-time (PPT) adversary A, the probability of A finding such a vector is at most δ over the randomness of A ′ .

Definition E.2 ((HNF) Learning With Errors).

Let n, m, q be positive integers, and ψ a probability distribution over Z. The Hermite Normal Form Learning With Errors problem, denoted by HNF-LWE n,m,q,ψ , asks to distinguish between the following two distributions: (1) (A, As+e mod q) with A ← U (Z m×n q ), s ← ψ n and e ← ψ m ; (2) (A, b) with A ← U (Z m×n q ) and b ← U (Z m q ). We say that HNF-LWE is δ-hard if for any PPT adversary A, the advantage of A in distinguishing both distributions is at most δ.

Finally, we briefly recall the security properties of a commitment scheme aCommit(m; ρ) which commits to a message m under randomness ρ. We say that aCommit is δ-hiding if a PPT adversary A has advantage at most δ in the following game: A chooses m 0 ̸ = m 1 , receives aCommit(m b ; ρ) where b is a random bit, and outputs b ′ ∈ {0, 1}. A wins if b ′ = b. We say that aCommit is δ-binding if a PPT adversary has advantage at most δ in outputting (m 0 , ρ 0 ), (m 1 , ρ 1 ) such that m 0 ̸ = m 1 and aCommit(m 0 ; ρ 0 ) = aCommit(m 1 ; ρ 1 ).

E.2 The Optimized Protocol.

We now present the main protocol with the optimizations we presented. Let ℓ 1 , ℓ 2 be two positive integers. We denote by L x the size of the witness vector, and L M As explained in Remark F.1, in order to have as few iterations of the proof system as possible, we need to choose large enough challenges, which in turns require to take a sufficiently large modulus. We then start by choosing the number of iterations N and the challenge size p, which imply we must take q ≥ poly(λ)•p 2 . To avoid an exponential reduction loss, we set q ′ ≈ Q. We then fix n so that when the other parameters are set using Algorithm 3.1, we obtain a quantum security of λ. Since the proofs of Lemma 3.2 and 3.3 both have a reduction loss between the advantage of a signature forger (δ = 2 -λ ) and the advantage against SIS (Adv[B]) which can be substantial, we need to take it into account. More precisely, we compute the required SIS security λ I , λ II so that the SIS problem stays hard even with the relations of Lemma 3.2 and 3.3. For our parameter, we need λ I = 189 and λ II = 181 for the respective SIS problems which only slightly differ by their bounds. Hence, we must reach for a root Hermite factor of δ 0 = 1.0026. We also account for key recovery attacks, consisting of recovering R from A, B. This attack is however much more costly than forgeries as R is statistically hidden in (A, B) by the leftover hash lemma. We then set the other parameters of the zero-knowledge argument as described in our optimized framework in Appendix E and taking ℓ 1 , ℓ 2 to reach 128 bits of quantum security for the HNF-SIS and HNF-LWE problems. The security estimates of HNF-LWE are performed using the estimator of Albrecht et al. [APS15]. We note that although we take the secret and error ternary from distribution ψ 1 , we are never in the regime of polynomial algebraic attacks [AG11]. Such attacks for ternary error would require roughly ℓ 3 2 samples. In our cases, we have ℓ 1 + max(L x , L M ) ≪ ℓ 2 2 . We also instantiate the scheme of [LLM + 16]. For a fair comparison, we aim for the same security and make use of the same improvements of the zeroknowledge argument. The relation of [LLM + 16] is instantiated in the framework of [YAZ + 19] in Appendix F.3.

For both our scheme and the one from [LLM + 16], the ZKAoK are instantiated to be run twice, and thus do not include the compacted commitments discussed in Appendix E. Table 1.1 shows the construction of [LLM + 16] leads to intractable parameters and key sizes. We note that one could reduce the value of q at the expense of increasing the number of proof iterations to achieve negligible soundness. However, not only does this approach still leads to intractable key sizes, but it also yields substantially larger proofs. Our results also summarized in Table 1.1 shows the feasibility of signature with efficient protocols based on lattice assumptions, as we gain several orders of magnitude in the size of key materials and proof size, while maintaining the same security. The complete parameter sets used to obtained these results can be found in Tables H.1 and H.2.

Remark H.1. We recall that, although the fast mode reduces the size of the witness vector, it also introduces a soundness gap, which is the object of Lemma 4.1. As a result, the bounds on v * 1 , v * 2 used in Lemma 3.2 and 3.3 are larger as discussed in Remark 4.1. We thus take this increase of the SIS bounds into account when estimating the SIS security, which entails an increase of the dimension n.