Je Voudrais

Shweta Agrawal

Alain Anca

Antonia Angelo

Aurélien

Balthazar, Céline, Chloé, Dahmun Damien Aurore

Édouard, Fabrice, Geoffroy, Georg, Hieu, Hoeteck, Houda, Itai, Jérémy, Julia, Léo, Louiza, Mario David

Mélissa, Michel Michele Minelli

Michele Orrù

Romain Simon

Tancrède Sonia Sylvain

Thomas Peters

Thomas Prest Je Suis Particulièrement Redevable

Michele Minelli Dont

Keywords: cryptography, lattices, zero knowledge, group signatures, e-voting

Le chiffrement à base de réseaux euclidiens a connu un grand essor durant les vingt dernières années. Autant grâce à l'apparition de nouvelles primitives telles que le chiffrement complètement homomorphe, que grâce à l'amélioration des primitives existantes, comme le chiffrement á clef publique ou les signatures digitales, qui commencent désormais à rivaliser avec leurs homologues fondés sur la théorie des nombres. Cela dit les preuves à divulgation nulle de connaissance, bien qu'elles représentent un des piliers des protocols de confidentialité, n'ont pas autant progressé, que ce soit au niveau de leur expressivité que de leur efficacité.

Cette thèse s'attelle dans un premier temps à améliorer l'état de l'art en matière de preuves à divulgation nulle de connaissance. Nous construisons une preuve d'appartenance à un sous ensemble dont la taille est indépendante de l'ensemble en question. Nous construisons de même une preuve de connaissance amortie qui est plus efficace et plus simple que toutes les constructions qui la précèdent.

Notre second propos est d'utiliser ces preuves à divulgation nulle de connaissance pour construire de nouvelles primitives cryptographiques. Nous concevons une signature de groupe dont la taille est indépendante du groupe en question, ainsi qu'un schéma de vote électronique hautement efficace, y compris pour des élections à grand échelle.

Chapter 1 Introduction

From its genesis to less than a century ago, cryptography has been a tool of war. Encrypting messages so they would not fall into enemy hands was done using the now famous Caesar cipher in ancient Rome, and using the state of the art Enigma machines during World War II. A common point between these two cryptosystems, and all the ones that came in-between, is their use of symmetric key cryptography: they allow secure communication between two parties who share a common secret information.

In fact, different types of cryptography were not even conceived before 1970 when James H. Ellis surmised the possibility of "non-secret" encryption, which would allow two parties to communicate securely without prior agreement on a common secret. The first concrete example of public-key cryptography comes from a 1974 work of Ralph C.Merkle who devised a protocol in which two parties can exchange a secret key through an insecure channel without needing to know any common secret information.

Since then cryptography has grown at an impressive rate, with a plethora of new concepts such as identification schemes, which allow an individual to prove his identity via the knowledge of a secret without revealing it, fine-grained public key infrastructures, in which one gets to choose who should be able to decrypt which part of a message, and many more... This boom is due to a change of paradigm in regard to the purpose of cryptography: the emergence of information technology and in particular the internet has created a need for efficient and novel cryptographic tools.

Zero-knowledge proofs of knowledge (ZKPoK) are an important primitive in privacy preserving schemes. A ZKPoK is a two-party protocol in which a prover, Alice, wants to convince a verifier, Bob, that she knows a secret information "x" without revealing any other information about "x". Such proofs are ubiquitous in privacy protocols, they are used to construct digital signatures, authentication schemes, and they gained renewed interest with the rapid expansion of blockchain and cryptocurrencies.

Lattice-Based Cryptography

"When will large scale quantum computers exist?" Ask ten people and you will receive ten different answers. However, the fact remains that tremendous work is being put towards the construction of quantum computers and it is becoming apparent that the existence of large scale quantum computers is really a matter of "when" and not "if". Once such computers are built number theoretic cryptography, which is by and large the only cryptography that is currently being used in practice, will collapse. In the last few years a lot of progress has been made towards constructing post-quantum cryptography, i.e. cryptography that relies on computational assumptions which are believed to resist quantum computers, as is evidenced by the NIST call for "Post-Quantum Cryptography Standardization", and lattice-based cryptography is one of the most promising candidates.

Intuitively a lattice can be seen as a periodic grid in R n , it is formally defined as the set of all integer-valued linear combinations of some basis vectors (b 1 , . . . , b k ).

Cryptography on lattices started with the seminal work of Ajtai [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF] in which he introduces the Short Integer Solution (SIS) problem and proves that this problem is on average as hard as some worst-case well-known problems on lattices. In parallel Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman developed the NTRU encryption scheme [START_REF] Hoffstein | NTRU: A Ring-Based Public Key Cryptosystem[END_REF] based on polynomial rings. While this scheme did not enjoy a theoretical security proof, it has still resisted 20 years of cryptanalysis. In 2005, Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] introduced the Learning With Errors (LWE) problem and proved it to be as hard as standard lattice problems. The LWE problem was a breakthrough in lattice-based cryptography allowing for more efficient schemes and new cryptographic primitives such as fully-homomorphic encryption 1 .

Schemes based on LWE and SIS suffer from one major caveat when compared to schemes based on number theoretic assumptions: they have substantially larger key and ciphertext sizes. To remedy this issue ring variants of these problems R-LWE and R-SIS were introduced respectively by Lyubashevsky, Peikert and Regev [START_REF] Lyubashevsky | On Ideal Lattices and Learning with Errors over Rings[END_REF], and Micciancio [START_REF] Micciancio | Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions[END_REF]. These new problems use polynomials instead of matrices, effectively reducing parameters by up to a square root factor. This increased efficiency comes at a price in security since these problem can only be reduced to standard problems on ideal lattices which are more structured lattices. It is however worth noting that, except for marginal cases, attacks on ideal lattices do not perform better than attacks on standard lattices.

Lattice-Based Zero-Knowledge

The security of lattice-based cryptographic primitives is based on the hardness of recovering a short vector s when given a matrix A and t = As as inputs, this problem is known as the Inhomogeneous Short Integer Solution (ISIS) problem. The operations are performed over some ring R, which most commonly is either Z a or a polynomial ring Z [X] /X d + 1. 2 Depending on the primitive, s can represent the secret key, the randomness used during encryption, the signature of a message, or anything else that one should not be able to obtain just by knowing A and t. In many cryptographic protocols, someone announcing the value t would also need to be able to prove the knowledge of a short pre-image s (the pre-image may not be unique) of t satisfying

A • s = t (1.1)
The first approach developed for constructing such a zero-knowledge proof is using Sterntype proofs for codes [START_REF] Stern | A New Identification Scheme Based on Syndrome Decoding[END_REF] adapted to the lattice setting [START_REF] Kawachi | Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems[END_REF][START_REF] Ling | Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications[END_REF]. The main downside of this technique is that it has rather long proofs. Each run of the protocol has soundness error 2/3, thus requiring over 200 repetitions for 128 bits of security and over 400 repetitions if one would like to have 128 bits of quantum security in the resulting NIZK proof 1 Though the original FHE construction of Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] did not use the LWE problem, all the more recent constructions do. 2 We will use this polynomial ring throughout our paper as it is the one that is almost exclusively used in practice. Instantiations with other monic polynomials are also possible.

constructed via the Fiat-Shamir technique. Even the most basic application, such as proving the knowledge of a solution to a hash function (e.g. the one in [START_REF] Lyubashevsky | SWIFFT: A Modest Proposal for FFT Hashing[END_REF]), would require around 1KB for every round, thus making the total proof size approximately 400 KB. More complicated applications, as well as those in which the inputs are not taken from {0, 1} k , quickly push such proofs to the order of Megabytes.

Another technique for creating zero-knowledge proofs is the "Fiat-Shamir with Aborts" approach which allows to create a proof of knowledge of a vector s with small coefficients (though larger than those in s) and a ring element c with very small coefficients satisfying As = ct [START_REF] Lyubashevsky | Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures[END_REF][START_REF] Lyubashevsky | Lattice Signatures without Trapdoors[END_REF]. As long as the ring R has many elements with small coefficients, such proofs are very efficient, producing soundness of 1 -2 -128 with just one iteration. While these proofs are good enough for constructing practical digital signatures (e.g. [GLP12; DDLL13; BG14]), commitment schemes with proofs of knowledge [START_REF] Benhamouda | Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings[END_REF][START_REF] Baum | Efficient Commitments and Zero-Knowledge Protocols from Ring-SIS with Applications to Lattice-based Threshold Cryptosystems[END_REF], and certain variants of verifiable encryption schemes [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF], they prove less than what the honest prover knows. In many applications where zero-knowledge proofs are used, in particular those that need to take advantage of additive homomorphisms, the presence of the element c makes these kinds of "approximate" proofs too weak to be useful. As of today, we do not have any truly practical zero-knowledge proof systems that give a proof of Equation (1.1).

The situation is considerably more promising when one considers amortized proofs, and the increased efficiency of such proofs has already been exploited in practical multi-party computation [START_REF] Damgård | Multiparty Computation from Somewhat Homomorphic Encryption[END_REF]. A series of works [DPSZ12; BDLN16; CDXY17] have considered how to obtain efficient exact proofs with overwhelming soundness when proving many equations at the same time, resulting in [PL17] in proofs with constant overhead and small slack. These proofs can however only be use when amortized over thousands of equations like (1.1), making them inapplicable in many scenarios. [PLNS17] In this paper we propose a lattice-based electronic voting scheme, EVOLVE (Electronic Voting from Lattices with Verification), which is conjectured to resist attacks by quantum computers. Our protocol involves a number of voting authorities so that vote privacy is maintained as long as at least one of the authorities is honest, while the integrity of the result is guaranteed even when all authorities collude. Furthermore, the result of the vote can be independently computed by any observer. At the core of the protocol is the utilization of a homomorphic commitment scheme with strategically orchestrated zero-knowledge proofs: voters use approximate but efficient "Fiat-Shamir with Aborts" proofs to show the validity of their vote, while the authorities use amortized exact proofs to show that the commitments are well-formed. We also present a novel efficient zero-knowledge proof that one of two lattice-based statements is true (so-called OR proof) and a new mechanism to control the size of the randomness when applying the homomorphism to commitments.

Personal Contributions

Contributions in this Thesis

[PLS18]

In this paper we present a new lattice-based zero-knowledge proof system for proving that a committed value belongs to a particular set of small size. The sets for which our proofs are applicable are exactly those that contain elements that remain stable under Galois automorphisms of the underlying cyclotomic number field of our protocol.

An application of our new proofs is that they allow the use of the selectively-secure signature scheme (i.e. a signature scheme in which the adversary declares the forgery message before seeing the public key) of Agrawal et al. [START_REF] Agrawal | Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE[END_REF] for constructing latticebased privacy protocols. For selectively-secure schemes to be meaningfully converted to standard signature schemes, it is crucial that the size of the message space is small. Using our zero-knowledge proofs, we can strategically pick sets for which we can provide efficient zero-knowledge proofs of membership.

[BBC+18]

In this paper we present a surprisingly simple zero-knowledge proof for preimages of linear relations whose amortized communication complexity depends only logarithmically on the number of relations being proved. This latter protocol is a substantial improvement, both theoretically and in practice, over the previous results in this line of research of Damgård et al. [START_REF] Damgård | Multiparty Computation from Somewhat Homomorphic Encryption[END_REF], Baum et al. [START_REF] Baum | How to Prove Knowledge of Small Secrets[END_REF], Cramer et al. [START_REF] Cramer | Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack[END_REF] and del Pino and Lyubashevsky [PL17].

Other Contributions [BPMW16]

In this paper we study the circuit privacy of fully homomorphic encryption (FHE). We carefully analysis of the noise growth in the FHE scheme of Alperin-Sheriff and Peiker [START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF] and prove that the addition of a small well-chosen noise to the output of computations is sufficient to ensure circuit privacy.

[PLP16] In this paper, we show that by simultaneously considering the secrecy and authenticity requirements of an authenticated key exchange (AKE), we can construct a scheme that is more secure and with smaller communication complexity than a scheme created by a generic combination of a key encapsulation mechanism (KEM) with a signature scheme. We first observe that relaxing the correctness property of the KEM so that it is no longer overwhelming allows for better parameters at virtually no impact in security. Our second improvement is showing that certain hash-and-sign lattice signatures can be used in "message-recovery" mode. In this mode, the signature size is doubled but this longer signature is enough to recover an even longer message -thus the signature is longer but the message does not need to be sent. This is advantageous when signing relatively long messages, such as the public keys and ciphertexts generated by a lattice-based KEM.

[PL17] In this paper we present an amortized zero-knowledge proof of knowledge for latticebased one-way functions. This work is an improvement of a paper by Cramer et al. [START_REF] Cramer | Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack[END_REF] and reduces the number of equations needed for amortization by a parameter ∼ log 2 α at a cost in running time of α. For example, increasing the running time by a factor of 8 allows us to decrease the required number of samples from 69000 to 4500 (a factor of 15).

Organization of this Thesis

In Chapter 2 we define the notations that will be used throughout this thesis, we recall basic notions on lattices and Gaussians, and we give formal definitions as well as lattice-based instantiations of the cryptographic building blocks we will use.

In chapter 3 we define Σ -protocols, and give constructions of proofs of knowledge for: oneway function preimages, commitment openings, disjunction of NP-languages, and subset membership. We also give an amortized proof of knowledge for one-way function preimages.

In chapter 4 we construct a group signature using the proof of subset membership of Chapter 3. We give concrete parameters as well as the resulting signature size.

In chapter 5 we describe a security model for e-voting and use the proof for disjunctions as well as the amortized proof of Chapter 3 to build an e-voting scheme. We fix parameters and present the size and timings obtained from our proof-of-concept implementation. Finally, we conclude in Chapter 6 and present some open questions.

Chapter 2

Chapter 2 Preliminaries

In this chapter we present the notations that will be used throughout this thesis. Then we we give some properties on the invertibility of small polynomials in the ring Z q [X] /X d + 1, which will be useful for the proofs of knowledge of Chapter 3. We give some background on lattices and Gaussian sampling, and we give a succinct overview on the cryptanalysis of lattice problems, which we will use to set the parameters of the schemes presented in this thesis. Finally we give formal definitions, security models and lattice-based constructions for commitments and public key cryptography which we will use in the constructions of Chapters 4 and 5.

Contents

Notations

Sets, Integers. We denote by Z the set of integers, by N the set of non-negative integers, and by R the set of real numbers. For two integers a, b ∈ Z such that a ≤ b, we denote by {a, . . . , b} the set of all integers c ∈ Z such that a ≤ c ≤ b. For a ∈ N such that a > 0, the notation [a] is equivalent to {1, . . . , a}. We denote the size of a finite set S by |S|. For a positive integer q we denote by Z q the ring of integers modulo q for which we will consider the set of representativesq-1 2 , . . . , q-1 2 . Rings, Vectors, Matrices. We will consider vectors and matrices over a ring R which will be either R = Z or R = Z [X] /f (X) for some polynomial f . Elements in R as well as R q = R/qR will be written in lower case (e.g. c ∈ R). Vectors will be in bold lower case (e.g. y ∈ R m ) and will be column vectors. Matrices will be in bold upper case (e.g. A ∈ R n×m ). Vector norms. Polynomials will be identified as the vector of their coefficients for the purposes of norms, i.e. for g = d-1 0 g i X i and a positive integer p, the p norm is defined as

g p = d-1 1 |g i | p 1 p .
Norms are extended to vectors and matrices over R in the natural way, i.e. for v

= (v 1 , . . . , v m ) ∈ R m , v p = m-1 1 v i p p 1 p and for V = (v 1 , . . . , v m ) ∈ R n×m , V p = m-1 1 v i p p 1 p
. Since we will mostly consider the euclidean norm of vectors we will abbreviate the notation • 2 as • . The operator norm of a matrix A ∈ R n×m is defined as

s 1 (A) = max x∈R m \{0} Ax x ,
we also define a matrix norm that will be useful for the amortized zero-knowledge proofs of Chapter 3 which we call "max norm": for A = (a 1 , . . . , a m ) ∈ R n×m ,

A max = max j∈[m]
( a j ) .

Polynomial Rings

For the rest of this thesis we will consider R to be the ring Z [X] /X d + 1 for d a power of two, in the case d = 1 we will simply identify R with Z. For many of our protocols we will require that "small" polynomials are invertible. The following lemmata guarantee such a properties for well chosen power-of-two cyclotomics.

Lemma 2.2.1 (Inverse of differences of monomials [START_REF] Benhamouda | Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures[END_REF] ). Let d be a power of 2, let

a, b ∈ {±X i : i ≥ 0} ∪ {0}. Then 2(a -b) -1 mod X d + 1 only has coefficients in {-1, 0, 1}.
Lemma 2.2.2 (Invertibility of small polynomials [START_REF] Lyubashevsky | Partially Splitting Rings for Faster Lattice-Based Zero-Knowledge Proofs[END_REF]). Let d ≥ k > 1 be powers of 2 and q a prime such that X d + 1 splits into k different irreducible polynomials modulo q. Then any c in Z q [X]/(X d + 1) such that 0 < c < q 1/k has an inverse in the ring.

Chapter 2

Lattices

For this lemma to be meaningful we need to know how X d + 1 splits modulo q, this is specified in [LS17, Corollary 1.2]. Lemma 2.2.3 (Factors of X d + 1). Let d ≥ k > 1 be powers of 2 and q = 2k + 1 mod 4k be a prime. Then the polynomial X d + 1 factors as

X d + 1 = k j=1 (X n/k -r j ) mod q
For distinct r j ∈ Z * q where X n/kr j are irreducible in the ring Z q [X].

Polynomial and matrix products. Products of polynomials in R (and R q ) can be represented by matrix/vector products in Z (and Z q ). For a polynomial a = a i X i ∈ R we will define the rotation matrix of a as

Rot(a) := a | aX | aX 2 | . . . | aX d-1 =          a 0 -a d-1 . . . -a 1 a 1 . . . . . . . . . . . . . . . . . . -a d-1 a d-1 . . . a 1 a 0          It is apparent that if we write as b ∈ Z d the coefficients of b ∈ R then Rot(a) • b ∈ Z d is the vector that contains the coefficients of a • b ∈ R.
Similarly for A ∈ R n×m , we will write Rot(A) ∈ Z dn×dm as the matrix in which we have applied Rot component-wise.

Lattices

Definitions and Properties

An n-dimensional lattice L is a discrete subgroup of R n . Any lattice can be expressed as the set of linear combinations of some linearly independent vectors B = (b 1 , . . . , b k ), i.e.

L = L(B) := k i=1 x i b i | x i ∈ Z = BZ k
B is a called a basis of L and its number of columns k is the rank of the lattice. Since L is a subgroup of R n , we can consider the quotient group

R n /L of cosets. For c ∈ R n the coset of c is c + L = {c + x | x ∈ L} Definition 2.3.1 (Successive minima). Let L ⊂ R n be a lattice of rank k. For i ∈ [k] the i-th successive minimum of L is defined as λ i (L) := inf r | dim Span(L ∩ B(0, r) ≥ i Definition 2.3.2 (Determinant of a lattice). Let L = L(B). The determinant, or volume, of L is defined as Vol(L) := det(L) := det(B T B)
The notion of volume will be useful to estimate the first minimum of a lattice. The Gaussian heuristic surmises that the number of lattice point in a convex body S(we will usually consider a ball) is equal to the volume of S divided by the volume of the lattice.

|L ∩ S| ≈ Vol(S)/Vol(L).

Using this heuristic with a sphere of radius λ 1 (L) gives the following approximation:

λ 1 (L) ≈ n 2πe Vol(L) 1/n
Definition 2.3.3 (Dual Lattice). Let L ⊂ R n be a lattice. The dual of L is the lattice defined as

L * := {y ∈ Span(L) | ∀x ∈ L, x, y ∈ Z}
Gram Schmidt orthogonalization. The Gram-Schmidt orthogonalization (GSO) is an algorithm that takes as input a basis B of a vector space and outputs an orthogonal basis B of the same vector space. The GSO is useful both in cryptography as it is for example used in the sampling of Gaussians over lattice in the GPV sampler of Section 2.3.5, and in cryptanalysis where it is an important component of lattice reduction algorithms.

Definition 2.3.4 (Gram-Schmidt orthogonalization). Let B := b 1 | . . . | b n ∈ R n×n be a basis of R n .
The Gram-Schmidt orthogonalization of B is the matrix B defined as follows:

b1 := b 1 bi := Proj ⊥ b 1 ,...,b i-1 (b i )
Q-ary lattices. In most lattice-based crypto applications we will consider lattices of a very specific form that comes from the SIS problems. For a matrix A ∈ R n×m q , we define the q-ary lattice associated with A as:

L(A) ⊥ q := {x ∈ R m : Ax = 0 mod q} . It is easy to see that L(A) ⊥
q is indeed a lattice, and that it is of dimension dm over R (this lattice can be interpreted over R as L(Rot(A)) ⊥ q ). It is also of rank dm, a simple proof of this being that the vectors of the form (0, . . . , 0, qX i , 0, . . . , 0) ∈ R m (0, . . . , 0, q, 0, . . . , 0) ∈ Z dm are in L(A) ⊥ q and there are dm independent such vectors. For A $ ← R n×m q , with n ≤ m, the lattice L(A) ⊥ q will have with high probability volume Vol(L(A) ⊥ q ) = q dn .

To show this first write

A 1 | A 2 := Rot(A) ,where A 1 ∈ Z dn×dn q
. With high probability A 1 will have an inverse and it is easy to notice that

qI dn A -1 1 A 2 0 I d(m-n)
is a basis of L(Rot(A)) ⊥ q and has determinant q nd .

Gaussians.

Continuous and discrete Gaussians.

For any integer n ≥ 1 and real σ > 0, the n-dimensional spherical Gaussian function ρ σ : R n → (0, 1] is defined as 1 :

ρ σ (x) := exp - x 2 2σ 2
We define the discrete Gaussian over the coset c + L of L ⊂ R n , with standard deviation σ via the following probability density function:

∀x ∈ c + L; D c+L,σ (x) = ρ σ (x) ρ σ (c + L)
where ρ σ (c + L) = u∈L ρ σ (c + u). When L = Z and c = 0 we will ignore the corresponding subscript, we will also write x ← D n σ as an alternative to x ← D Z n ,σ as sampling the n coefficients of x independently results in the same distribution. For a polynomial ring R we will write x ← D R,σ to denote that all the coefficients of x ∈ R are taken according to D σ . Norm Bounds. Using the tail bounds for the 0-centered discrete Gaussian distribution, we can show that for any σ > 0, x ← D σ is likely to be close to σ.

Lemma 2.3.5 (Gaussian tails). For any

k > 0 Pr x←Dσ [|x| > kσ] ≤ 2e -k 2 /2 , (2.1)
and when x is drawn from D n σ , we have Pr

x←D n σ [ x > √ 2n • σ] < 2 -n/4 . (2.2)
Rejection Sampling. We give an important lemma on rejection sampling which will guarantee that the responses used in our zero-knowledge protocols do not leak information.

Algorithm 1 Rej(Z, B, σ) u ← [0, 1) if u > 1 3 exp -2 Z,B + B 2 2σ 2
then return 0 else return 1 Lemma 2.3.6 [START_REF] Lyubashevsky | Lattice Signatures without Trapdoors[END_REF]). Let V be a subset of R n×m with elements of norm less than T, let h be a distribution over V, and B ← h. Consider a procedure that samples Y ← D n×m R,σ and then returns the output of Rej(Z := Y + B, B, σ) where σ ≥ 11 B . The probability that this procedure outputs 1 is within 2 -100 of 1/3. The distribution of Z, conditioned on the output being 1, is within statistical distance 2 -100 of D n×m R,σ .

1 Multiple works define the Gaussian function as ρσ(x)

:= exp -π x 2 σ 2
which is a dilation of the function we use. We choose our definition because it entails that the discrete Gaussian we obtain from it will have standard deviation σ which is conceptually simpler.

Hard Problems on Lattices.

We define some of the computational problems defined on lattice. We will only consider the the problems which will be useful for the security analysis of Section 2. Remark that these problems can be defined for modules over any polynomial ring R but using rings other than Z [X] /X d + 1 makes the definitions rather cumbersome and will not be necessary here.

Definition 2.3.11 (M-SIS q,n,m,β -Module Short Integer Solution [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]). For integers q, n, m > 0, real β > 0, given A $ ← R n×m q , find z ∈ R m such that Az = 0 mod q and 0 < z ≤ β. Definition 2.3.12 (M-LWE q,n,σ -Module Learning With Errors adapted from [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]). For integers q, n > 0, real σ > 0, and s ← D n R,σ , let A q,s,σ be the distribution obtained by sampling a $ ← R n q , e ← D R,σ and outputting (a, a, s + e) ∈ R n q × R q . Given s ← D n R,σ , distinguish between A q,s,σ and U(R n q ), U(R q ) . Both of these problems are shown to be as hard as some standard module-lattice problems in [LS15]2 . It is worth noting that these definition of M-SIS and M-LWE collapse to the aforementioned problems SIS and LWE when d = 1, and to R-SIS and R-LWE when n = 1. Definition 2.3.13 (NTRU q,σ ). For an integer q > 0, a real σ > 0. Let N q,σ be the distribution obtained by sampling f, g ← D R,σ conditioned on g being invertible in R q and outputting h = f /g ∈ R q . Distinguish between N q,σ and U(R q ).

The NTRU problem was only shown to be hard for σ = Ω(d √ q) with a reduction to R-LWE by Stelhé and Steinfield [START_REF] Stehlé | Making NTRU as Secure as Worst-Case Problems over Ideal Lattices[END_REF]. However slightly smaller parameters such as σ = Ω( √ q) are not known to have more efficient cryptanalysis that R-LWE instances of comparable standard deviation.

Cryptanalysis

In this section we succinctly introduce the cryptanalytic tools from which we can evaluate the hardness of M-LWE and M-SIS. Lattice reduction algorithms. First introduced by Lenstra, Lenstra, and Lovász [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF] lattice reduction algorithms aim at outputting a "short" basis of a lattice. Many improvements to the original LLL algorithm have been designed with various tradeoffs between running times and quality of output. We will be interested in the BKZ-β algorithm [START_REF] Schnorr | A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms[END_REF] which is in practice the best available lattice reduction algorithm. The BKZ-β algorithm depends on a parameter called the block size β and uses as a subroutine an algorithm that solves the SV P problem exactly in dimension β, it has running time poly(|B|) • T where B is the input basis and T is the running time of the SVP solving subroutine. Since solving SVP exactly takes exponential time, we usually equate the running time of BKZ-β with the one of the exact solver, different parameters β offer trade offs between the running time of the algorithm and the quality of the output. The BKZ-β algorithm, when run on a lattice L of dimension n, guarantees that the first basis vector it outputs will be b 1 such that:

b 1 ≤ δ n 0 • Vol(L) 1
/n with δ 0 the root Hermite factor:

δ 0 = (πβ) 1/β β 2πe 1 2(β-1)
.

The BKZ-β algorithm can therefore be used to find "somewhat" short vectors by setting δ 0 to be sufficiently small and using the corresponding block size. However this approach will not work when the lattice L has abnormally short vectors (which will typically be true when attacking LWE). Luckily Alkim et al. [START_REF] Alkim | Postquantum Key Exchange -A New Hope[END_REF] have observed that in the presence of a very small vector the BKZ-β algorithm will not behave as expected and as a result the short vector will be detected. The basis B output by BKZ-β is usually (e.g. for random lattices) expected to follow the geometric series assumption: bi = α i-1 b 1 , for α = δ -2n/(n-1) 0 .

On the other hand an invariant of the BKZ-β algorithm guarantees that the vector b n-β+1 will be such that bn-β+1 is the norm of the shortest vector in the lattice obtained by projecting L orthogonally to b 1 , . . . , b n-β . Suppose L contains a very short vector v and that v is taken uniformly on the sphere of radius v , then the expected norm of the projection of v against b 1 , . . . , b n-β will be β n v , while the geometric series assumption gives bn

-β+1 = δ n n-1 (2β-n-1) 0 Vol(L) 1/n ≈ δ 2β-n 0 Vol(L) 1/n .
Which entails that the geometric series assumption will be broken when

β n v < δ 2β-n 0 Vol(L) 1/n .
It has been observed in practice that the BKZ-β detects such cases and that the full vector v can be recovered.

Solving M-SIS and M-LWE. To solve M-SIS q,n,m,B , given A ← R n×m q we want to find a vector z ∈ R m of norm B such that Az = 0 mod q, i.e. we want to find a short vector in the lattice L(A) ⊥ q which is a dm-dimensional lattice of volume q dn . This problem becomes harder when it gets closer to an instance of SVP (without approximation), i.e. when B is the size of the expected smallest vector in L(A) ⊥ q , i.e. B ≈ dm 2πe q n/m . If B is larger, meaning we have an approximate-SVP instance, we will simply compute the root Hermite factor necessary for solving M-SIS q,n,m,B as δ 0 = Bq -n/m 1/dm , find the corresponding block size β and apply BKZ-β to find a short vector z 3 . When B is smaller than the expected value of the shortest vector, meaning we have a unique-SVP instance, we will rely on the other approach we have described. i.e. we will solve

β dm B = δ 2β-dm 0 q n/m
for β (by using the equation between δ 0 and β) and then use BKZ-β.

To solve M-LWE q,n,σ , notice that for a matrix A ∈ R m×n q and a sample b := As + e with s ← D n R,σ and e ← D m R,σ , we have:

Mz = 0 mod q, where M = A | I dm | -b ∈ Z dm×d(m+n)+1 q and z =    s e 1    ∈ Z d(m+n)+1
We are thus looking for a vector of norm d(n n+m) . In all "interesting" instances of M-LWE this vector will be much shorter than the expected shortest vector of L(M) ⊥ q and we will thus search for it by setting δ 0 such that:

+ m)σ 2 + 1 ≈ d(n + m)σ in the lattice L(M) ⊥ q of volume q m/(
βσ = δ 2β-d(n+m) 0
q m/(n+m) Solving SVP. Since the BKZ-β algorithm relies on a subroutine that solves the shortest vector problem exactly in dimension β, it will be crucial to optimize this solver. There are two main approaches to solving SVP exactly. The first one is enumeration, which is in essence an exhaustive search algorithm. Enumeration algorithms run in constant space but they have worst case complexity 2 O(β 2 ) . Due to multiple heuristic optimizations (such as pruning [START_REF] Gama | Predicting Lattice Reduction[END_REF]) enumeration tends to be the most efficient algorithms for "feasible" blocksizes such as β = 40 or 50, however the super exponential behaviour of these algorithms quickly make them unusable for larger block sizes. We thus use sieving algorithms to obtain estimate the complexity of BKZ-β for large block sizes. Sieving algorithms proceed by first sampling an exponential number of lattice vectors, and then obtain increasingly shorter vectors by computing differences of vectors that are close to one another. Since these algorithms start by sampling exponentially many vectors they all require exponential space, on the other hand they also achieve (simply) exponential complexity. The best known sieving 3 This approach can be slightly improved by noticing that we can ignore columns of A by setting the corresponding coefficient of z to 0 and reduce the problem to solving a M-SIS q,n,m ,B instance for m ≤ m, we can then optimize over the value of m . We find that m = n log q log δ 0 gives the best result.

Chapter 2

Trapdoors.

Informally a trapdoored one-way function is a function that is hard invert except when given access to a secret "trapdoor". In the context of lattices the one-way functions we consider are of the form

f A : {x ∈ R m | x ≤ β} → R n x
→ Ax one can observe that the set of elements x s.t. Ax = 0 forms a lattice and that solutions to f A (x) = t are small elements in a coset of this lattice. As such the purpose of a lattice trapdoor will be enable one to sample small vectors in a lattice. Gentry et al. [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] present an algorithm which takes as input a basis B of a lattice L and outputs a sample from D c+L,σ for any coset c + L and for a standard deviation σ which depends on the size of B. Theorem 2.3.14 (GPV sampler [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]). Let ε > 0. There is a PPT algorithm Sample such that, for a basis B of a lattice L ⊂ Z n , a vector c ∈ R n , and a standard deviation

σ ≥ 1 π 1 2 log 2n(1 + 1 ε ) B max . The output of Sample(B, σ, c) is statistically close to D c+L,σ , i.e. ∆ (Sample(B, σ, c), D c+L,σ ) ≤ ε GPV Trapdoor.
To use this theorem one needs to know a short basis of L. While this is a hard problem for a random lattice, a series of work [Ajt99; Pei10; MP12] have tackled the issue of generating a trapdoored-lattice (i.e. with a known small basis) that is induistinguishable from a random lattice for anyone who does not know the trapdoor. We succintly present the result of [START_REF] Micciancio | Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller[END_REF] which uses "gadget"-based trapdoors for q-ary lattices.

Definition 2.3.15 (Gadget matrix [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]). For a modulus q and a base B, let := log B (q) . The gadget vector g ∈ R is defined as

g := 1, 2, 4, . . . , 2 -1
The gadget matrix of dimension n is defined as

G := I n ⊗ g =    g . . . g    ∈ R n×n Theorem 2.3.16 ([MP12] trapdoor). Let σ > 0, Ā $ ← R n×2n q , let R ← D 2n×n R,σ
, and

H ∈ R n×n q with H invertible in R n×n q . Let m = n( + 2), and
A := Ā | ĀR -HG
The matrix A is indistinguishable from uniform under the M -LW E q,n,σ assumption, and the lattice L ⊥ q (A) has an efficiently computable basis B such that indistinguishable from uniform, and a trapdoor B for the lattice L ⊥ q (A). For any t ∈ R n q , and σ ≥ 1

B max ≤ (s 1 (R) + 1) √ B 2 +
π 1 2 log 2n(1 + 1 ε )(s 1 (R) + 1) √ B 2 + 1, one can then sample v ← D n( +2) R,σ
such that Av = t mod q by using Sample(B, σ, c) for any c ∈ R n( +2) q such that Ac = t mod q. NTRU Trapdoors. A simple construction for trapdoored lattices is through the NTRU assumption. Consider the matrix A = 1 h , for h = f /g ← N q,σ as per definition 2.3.13. It is shown in [START_REF] Ducas | Efficient Identity-Based Encryption over NTRU Lattices[END_REF] that by choosing a standard deviation σ = 1.17 q 2d for the coefficients of f and g, one can efficiently compute a basis B of L ⊥ q (A) such that B max ≤ 1.17 √ q.

While such a standard deviation is not sufficient to argue that the NTRU assumption is as hard as the R-LWE assumption, there is no known distinguishing attack that exploits the NTRU structure of A for these parameters.

Basic Cryptographic Primitives

Commitments

Definition 2.4.1 (Commitment scheme). A commitment scheme is a tuple of three probabilistic polynomial time algorithms (CSetup, Com, Open) such that:

• CSetup(1 λ ) → CK generates the public commitment key.

• Com CK (m) → (c, d) generates a commitment c for the message m under the key CK, and an opening d to this commitment.

• Open CK (c, d) → m opens the commitment c using the opening d. If the commitment is not valid then m = ⊥.

For completeness opening any well formed commitment/opening tuple should recover the original message with overwhelming probability, i.e. for any CK ← CSetup(1 λ ) and any message m: Open CK (Com CK (m)) = m with overwhelming probability over the random coins of Com CK . For security the commitment should be binding, meaning that a commitment c should be "openable" to at most one message, and hiding, meaning that one should not be able to distinguish commitments to two different messages. Both the binding and the hiding property can be either statistical or computational, we will only consider commitment schemes that are computationally binding and hiding as we aim to obtain efficient constructions.

Definition 2.4.2 (Security). A valid commitment scheme should achieve the following properties:

• (Computational) Hiding. It is hard for any PPT adversary A to generate to messages m 0 = m 1 such that A can distinguish between Com(m 1 ) and Com(m 2 ). Formally:

Pr b = b CK ← CSetup(1 λ ), (m 0 , m 1 , St) ← A(CK), b $ ← {0, 1} (c, d) ← Com CK (m b ), b ← A(c, St) ≤ 1 2 + negl(λ) • (
Pr m = m ∧ m, m = ⊥ CK ← CSetup(1 λ ), (c, d, d ) ← A(CK) m ← Open CK (c, d), m ← Open CK (c, d ) ≤ negl(λ)
In most applications the commitment key CK will be clear from the context and we will thus omit it when referring to the algorithms Com and Open. Lattice-Based Commitments. We consider a commitment scheme with message space R l q . CSetup(1 λ ) :

• Generate public parameters pp := (q, n, m, l, σ, B Com , C)

• Sample A 1 $ ← R n×(n-m) q , set A 1 = I n A 1 ∈ R n×m q • Sample A 2 $ ← R l×(m-n-l) q , set A 2 = 0 l×n I l A 2 ∈ R l×m q • Set A := A 1 A 2 • Output (pp, A) Com(m ∈ R l q ) • Sample r ← D m R,σ • Output Ar + 0 m , r Open(t ∈ R n+l q , r ∈ R m , c ∈ C) • Parse t as t 1 t 2 with t 1 ∈ R n q and t 2 ∈ R l q • If ct 1 -A 1 r = 0, or r > B Com , or c / ∈ C, output ⊥ • Else, output t 2 -c-1 A 2 r
We could consider an opening algorithm that does not include the c term. However defining Open like this will be useful for Chapter 3, where the knowledge extractor of our proofs of knowledge will only be able to exctract ct for some small polynomial c. In practice the set C will be the set of difference of challenges of our proofs (except 0) and we will always ensure that all the elements in C are small and invertible. For ease of presentation we will sometimes write t := Com(m; r) to denote the commitment of m with the randomness r. Lemma 2.4.4 (Hiding). For any m, m ∈ R l q , if there is an adversary A who can distinguish between Com(m) and Com(m ) with advantage ε, then there exists an algorithm A who runs in the same time and breaks M -LW E q,m-n-l,σ with probability ε/2.

Proof. Given an instance (B, y) ∈ R

(n+l)×(m-n-l) q × R n+l q of M -LW E q,m-n-l,σ , A samples R $ ← R n×l q
and sets:

A := I n R 0 l×n I l • I n+l B
A sends A to the adversary A and receives messages m 0 , m 1 ∈ R l q such that m 0 = m 1 . A samples b $ ← {0, 1}, computes:

t = I n R 0 l×n I l y + 0 m b
and sends t to A. When A returns b , A returns 1 if b = b and 0 otherwise. We first show that the public commitment matrix A is taken according to the correct distribution. Rewrite B as

B 1 B 2 with B 1 ∈ R n×(m-n-l) q
, and B 2 ∈ R l×(m-n-l) q

. Then we have:

A = I n R B 1 + RB 2 0 l×n I l B 2
Since R, B 1 , and B 2 are uniform and independent, the distribution of A is identical to the one output by CSetup.

If y is uniform in R n+l q then t is uniform in R n+l crc r = 0 Additionally the verification equations of the opening entail that A 1 r = ct 1 and A 1 r = c t 1 , and thus:

Proof. Given an instance

A 1 = I n A 1 R n×m q of M -SIS q,m,2B C B Com . A samples
A 1 (c r -cr ) = 0
We also know that r , r ≤ B Com , and c 1 , c 1 ≤ 2B C , from which we obtain

cr -c r ≤ 4B Com B C .
Commitments with different moduli.We present a commitment scheme identical to the previous one except for the fact that the n first rows of the commitment will be taken modulo q 1 , and the l last rows will be taken modulo q 2 . In most applications using different moduli does not give better parameters or security, but we will see in Chapter 4 that it can be of use in our group signature scheme.

CSetup(1 λ ) :

• Generate public parameters pp := (q 1 , q 2 , n, m, l, σ, B Com , C)

• Sample A 1 $ ← R n×(m-n) q 1 , set A 1 = I n A 1 ∈ R n×m q 1 • Sample A 2 $ ← R l×(m-n-l) q 2 , set A 2 = 0 l×n I l A 2 ∈ R l×m q 2 • Set A := A 1 A 2 • Output (pp, A)
For the hiding property to hold we will need to artificially modify the distribution of the randomness in the commitment. Let σ :

= q 1 q 2 σ + 1 + 2d(m -n -l)σ 2 . Com(m ∈ R l q 2 ) • Sample r ← D n R,σ × D m-n R,σ • Output Ar + 0 m , r
The fact that the randomness is skewed is an artefact of the modulus switching we use in the proof of hiding. In practice we will use spherical gaussians as it is very unlikely that different moduli would help in attacking the scheme. Proof. The proof is identical to the one with a single modulus.

Open(t ∈ R n q 1 × R l q 2 , r ∈ R m , c ∈ C) • Parse t as t 1 t 2 with t 1 ∈ R n q 1 and t 2 ∈ R l q 2 • If ct 1 -A 1 r = 0, or r > B Com , or c / ∈ C, output ⊥ • Else, output t 2 -c-1 A 2 r
Lemma 2.4.8 (Hiding). For any m, m ∈ R l q 2 , if there is an adversary A who can distinguish between Com(m) and Com(m ) with advantage ε, then there exists an algorithm A who runs in the same time and breaks M -LW E q 2 ,m-n-l,σ with probability ε/2. . Let ρ : R → Z be a randomized rounding function which maps

Proof. Given an instance (B, y) ∈ R (n+l)×(m-n-l) q 2 × R n+l q 2 of M-LWE q 2 ,m-n-l,σ ,
x ∈ R to ρ(x) ← x + B x-x
, where B x-x is a Bernouilli variable which outputs 1 with probability xx . Remark that for q 1 ≤ q 2 , ρ U( q 1 q 2 Z q 2 ) = U(Z q 1 ). Let B 1 := ρ q 1 q 2 B 1 and y 1 := ρ( q 1 q 2 y 1 ). A samples R $ ← R n×l q 1 and sets:

A := I n R 0 l×n I l • I n 0 n×l B 1 0 l×n I l B 2
where the products are done over the integers and then taken modulo q 1 for the top part and modulo q 2 for the bottom part. A sends A to the adversary A and receives messages m 0 , m 1 ∈ R l q 2 such that m 0 = m 1 . A samples b $ ← {0, 1}, computes:

t = I n R 0 l×n I l y 1 y 2 + 0 m b
where the products are done over the integers and then taken modulo q 1 for the top part and modulo q 2 for the bottom part, and sends t to A. When A returns b , A returns 1 if b = b and 0 otherwise. We first show that the public commitment matrix A is taken according to the correct distribution. We have:

A = I n R B 1 + RB 2 0 l×n I l B 2
Since B 1 is uniform modulo q 1 and independent from R and B 2 , B 1 + RB 2 mod q 1 is uniform modulo q 1 . Since R and B 2 are also uniform, the distribution of A is identical to the one output by CSetup.

If y is uniform in R n+l q 2 then y 1 is uniform in R n q 1 and t is uniform in R n+l q 1 and b = b with probability exactly 1/2. However if y = I n+l B r, write r as

   r 1 r 2 r 3   , with r 1 ∈ R n , r 2 ∈ R l ,
and r 3 ∈ R m-n-l . Applying ρ component-wise to q 1 q 2 (B 1 , B 1 r 3 + r 1 ) we get:

q 1 q 2 B 1 + ∆, q 1 q 2 B 1 r 3 + q 1 q 2 r 1 + δ = q 1 q 2 B 1 + ∆, q 1 q 2 B 1 + ∆ r 3 + q 1 q 2 r 1 + δ -∆r 3 = B 1 , B 1 r 3 + q 1 q 2 r 1 + δ -∆r 3 = B 1 , B 1 r 3 + r 1
where r 1 is subgaussian with parameter

q 1 q 2 α + 1 + r 3 2 ≤ σ . Setting r =    r 1 r 2 r 3    we have that t = Ar + 0 m b
is distributed according to Com(m b ), and A will output b = b with probability 1/2 + ε. A therefore has advantage ε/2 in the M-LWE q 2 ,m-n-l,σ problem.

Public Key Encryption

Definition 2.4.9 (Public Key Encryption). A public key encryption scheme is a tuple of three probabilistic polynomial time algorithms (PKESetup, Enc, Dec) such that:

• PKESetup(1 λ ) → (sk, pk) Generates the secret key and the public key.

• Enc(pk, m) → ct outputs a ciphertext ct which encrypts the message m under the public key pk.

• Dec(sk, ct) → m Decrypts the ciphertext ct to a message m using the secret key sk.

Outputs the error symbol ⊥ if decryption fails. For completeness decrypting any well formed ciphertext should recover the original message with overwhelming probability, i.e. for any (pk, sk) ← PKESetup(1 λ ) and any message m: Dec(sk, Enc(pk, m)) = m with overwhelming probability over the random coins of Enc.

Exp ind-cpa-b (A, λ) : (sk, pk) ← PKESetup(1 λ ) (m 0 , m 1 , st) ← A(pk) ct * ← Enc(pk, m b ) b ← A(ct * , st) Return b
Adv ind-cpa (A, λ) := Pr b $ ←{0,1} Exp ind-cpa-b (A, λ) = b - 1 2
The scheme is secure if this advantage is negligible in λ for any PPT adversary A.

Exp ind-cca-b (A, λ) : S ← Empty list (sk, pk) ← PKESetup(1 λ ) (m 0 , m 1 , st) ← A ODec (pk) ct * ← Enc(pk, m b ) b ← A ODec (ct * , st) If ct * ∈ S
Adv ind-cca (A, λ) := Pr b $ ←{0,1} Exp ind-cca-b (A, λ) = b - 1 2
The scheme is secure if this advantage is negligible in λ for any PPT adversary A.

Lattice-Based PKE. Lyubashevsky introduced in [LPR13] a ring variant of the seminal CPA-secure LWE encryption scheme of Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. We present an adaptation of this scheme to module lattices, we also modify the scheme to accommodate for larger message spaces.

PKESetup(1 λ ):

• Generate public parameters pp := (q, p, n, l, σ)

• Sample A $ ← R n×n q • Sample S, E ← D n×l R,σ • Set B := AS + E • Output (s, (pp, A, B)) Enc((pp, A ∈ R n×n q , B ∈ R n×l q ), m ∈ R l q ): • Sample r, e 1 ← D n R,σ • Sample e 2 ← D l R,σ • Set u := p(A T r + e 1 ) • Set v := p(B T r + e 2 ) + m • Output (u, v) Dec(S ∈ R n×l q , (u ∈ R n q , v ∈ R l q )):
• Output v -S T u mod p Lemma 2.4.12 (Correctness). Let the modulus q be such that:

q > 64pnd √ 2σ 2
then the scheme (PKESetup, Enc, Dec) has overwhelming correctness.

Proof. Decryption will be correct if v -S T u = v -S T u mod q, indeed in that case we have:

v -S T u = p(E T r + e 2 -S T e 1 ) + m
and v -S T u = m mod p. Decryption will thus be correct if

p(E T r + e 2 -S T e 1 ) + m ∞ ≤ q/2p.
Let e, s ← D n R,σ be the first column of E and S, by applying a union bound it is apparent that proving p(e T r + e 2 -s T e 1 ) + m ∞ ≤ q/2p with overwhelming probability is sufficient.

Let x, y ← D R,σ , we have xy ∞ ≤ x 1 y ∞ ≤ √ d x y ∞ . By union bound Pr xy ∞ > 14d √ 2σ 2 ≤ Pr x > √ 2dσ + Pr [ y ∞ > 14σ] ≤ 2 -d/4 + d2e -98
Since e ← D n R,σ , we have e T s ∞ ≤ e i s i ∞ ≤ 14nd √ 2σ 2 with overwhelming probability.

The same argument can be applied to s T e 1 . Since m ∈ Z n p and e 2 ← D k R,σ , we have:

p(e T r + e 2 -s T e 1 ) + m ∞ ≤ 64pnd √ 2σ 2
Lemma 2.4.13 (IND-CPA Security). For any PPT adversary A, there exists a PPT adversary B for the M-LWE q,n,σ such that:

Adv ind-cca (A, λ) ≤ (k + 1)Adv M-LWEq,n,σ (B)
Proof. Let A be an adversary for the IND-CPA security of our scheme. We use a succession of games. Game G 0 : In this game we sample b $ ← {0, 1} run experiment Exp ind-cpa-b (A, λ). Game G 1,0<i≤k : This game is identical to the previous one except for the fact the the i t h column of B is now taken uniformly in R n q . Note that we had b i := As i + e i in the previous game. The advantage of A in distinguishing this game from the previous is thus:

Adv G 1,i A -Adv G 1,i-1 A ≤ Adv M-LWEq,n,σ (A)
Game G 2 : In this game we replace u, v by uniformly random vector. Note that since

B $ ← R n×k q in Game G 1,k-1 , we had A | B $ ← R n×(n+k) q and u v -m := A T B T r + e 1 e 2
was a M-LWE q,n,σ sample. The advantage of distinguishing this game from the previous one is thus:

Adv G 2 A -Adv G 1,k-1 A ≤ Adv M-LWEq,n,σ (A) Since v is uniform in R k q in Game G 2 , A has no advantage in guessing b:
Adv G 2 A = 0 By summing the successive inequalities we obtain the desired result.

Chapter 3

Chapter 3

Lattice-Based Zero-Knowledge

In this chapter we define zero-knowledge proofs of knowledge over lattices through the notion of Σ -protocol introduced in [START_REF] Benhamouda | Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures[END_REF]. We then present the basic "Fiat-Shamir with aborts" from [START_REF] Lyubashevsky | Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures[END_REF] and give two variants: an "exact" protocol and an "approximate" protocol. We then show how to use this Σ -protocol to prove knowledge of openings of commitments and linear relations on openings, we also construct a proof for the disjunction of statements. We present a proof that the opening of a message belongs to a subset of R that is fixed by a set of automorphisms. Finally we present an exact proof with constant overhead for lattice-based one-way functions, this proof is amortized and requires O(λ) equations to be efficient. A zero-knowledge proof of knowledge, abbreviated as ZKPoK, is an interactive protocol in which a prover P must convince a verifier V that a statement is true without revealing any other information about the statement. Consider a binary relation R associated to an NP language L, i.e. for any statement t ∈ L there exists a witness s such that (t, s) ∈ R. A ZKPoK for R should achieve the following properties.

Definitions

P V (t, s) ∈ R t (w, St) ← Commit(t, s) w - c c $ ← C z ← Respond(t, s, w, c, St) z -b ← V erif y(t, w, c, z)
Completeness: A prover with witness s for t ∈ L can convince the verifier.

Soundness:

A prover cannot convince the verifier when t / ∈ L.

Zero-knowledge:

The interaction should not reveal anything to the verifier except that t ∈ L.

In particular, it should not reveal the prover's witness s.

Sigma' Protocols. Σ-protocols (introduced by Cramer in [START_REF] Cramer | Modular design of secure yet practical cryptographic protocols[END_REF]) are three round interactive proofs of knowledge between a prover P who knows (t, s) ∈ R and a verifier V who knows t, c.f. Figure 3.1. In this thesis we will consider Σ -protocols, introduced in [BCK+14], which are an adaptation of Σ-protocols to the context of lattice-based cryptography.

Definition 3.1.1 (Σ -Protocol). Let R ⊂ R be two binary relations, let (P, V) be a two-party protocol where V is PPT. (P, V) is a Σ -protocol for R, R with challenge set C, public input t and private input s, if:

• Three-move form: (P, V) is of the form described in Figure 3.1

• Completeness: There is a constant α > 0 such that whenever (t, s) ∈ R, the verifier accepts with probability at least α.

• Special soundness: There exists a PPT algorithm E, called knowledge extractor, who on input two accepting transcripts, (w, c, z) and (w, c , z ) such that c = c , outputs s such that (t, s) ∈ R .

• Special honest-verifier zero-knowledge: There exists a PPT algorithm S, called simulator, who on input y ∈ L(R) and c ∈ C, outputs (w, s) such that (w, c, s) is indistinguishable from an accepting transcript generated by (P, V).

Chapter 3

Definitions

This definition differs from that of Σ-protocols in two ways. The completeness property has been relaxed from overwhelming to constant, that is to accommodate the use of rejection sampling, in which the prover will only send the reply z with some probability that depends on (s, t, w, c) and abort the protocol otherwise. This step is necessary to ensure that the reply z is independent of the witness s and can be simulated for zero-knowledge, we will ensure that the probability that the protocol does not abort is overwhelmingly close to a constant (which we will take to be 1/3 for simplicity). The second difference is that the soundness extractor does not recover a witness from R but a slightly larger relation R , we will need this relaxation to accommodate the soundness slack that comes with lattice-based zero-knowledge proofs (i.e. the fact that extracted witness s will be "larger" than s) and because some of the Σ -protocols we present will be "approximate" (c.f. Section 3.2).

The special soundness property achieved by Σ-protocol is a stronger variant of the knowledge soundness introduced by Bellare and Goldreich [START_REF] Bellare | On Defining Proofs of Knowledge[END_REF]. We recall this definition as some of our protocols do not achieve special soundness (we will still call such protocols Σ -protocols for ease of presentation). Definition 3.1.2 (Knowledge soundness). Let κ : {0, 1} * → [0, 1], let E be a PPT extractor who gets an input t ∈ R and black box access to a prover P * . (P, V) is κ-knowledge sound (or has soundness error κ) if for any prover P * who has probability ε(t) of convincing V on input t, there exists a constant c such that if ε(t) > κ(t) then E can output a witness s such that (t, s) ∈ R in expected time at most

|t| c ε(t) -κ(t)
where access to P * counts as a single step. Non-interactive proofs. The Fiat-Shamir transform was originally introduced in [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF] to transform a three move proof of knowledge into a digital signature scheme. Using the Fiat-Shamir transform we can obtain a non-interactive proof of knowledge from a Σ -protocol. We will define the non-interactive variant of (P, V) as the pair of algorithms Π(t; s), Verify(t, c, z) given in Algorithm 2 and Algorithm 3, where H is a collision resistant random oracle.

Algorithm 2 Π(t, s)

Require: Public information: t. Private information:

s such that (t, s) ∈ R 1: (w, St) ← Commit(t, s) 2: c ← H(t, w, c) 3: z ← Respond(t, s, w, c, St) 4: return (w, c, z) Chapter 3 Lattice-Based Zero-Knowledge Algorithm 3 Verify(t, c, z) Require: Public information: t ∈ L(R), (w, c, z) ← Π(t; s). 1: if c = H(t, w, c) then 2:
return V erif y(t, w, c, z) 3: elsereturn 0

Exact and Approximate ZKPoKs

Σ -Protocol for one way functions

Our first ZKPoK will consist in proving knowledge of a small preimage s ∈ R m for an image t ∈ R n q of the one-way function defined by a random matrix A ∈ R n×m q . We present in Figure 3.1 a basic Σ -protocol for the following relations:

R = (t, s, 1) ∈ R n q × R m × R | As = t, s ≤ B R = (t, s, c) ∈ R n q × R m × R | As = tc, s ≤ 2B , c
∈ C where C is the set of differences of elements of C except for 0. If R is taken to be Z then the challenge set we bill fixed to C = {0, 1} (and thus C = {1}) resulting in a protocol with soundness 1/2. If R is a polynomial ring then one can chose C to be a larger set (e.g. polynomials of small norm) to obtain soundness 1/ |C|, this comes at a cost since the set C will also be large.

P V A ∈ R n×m q , s ∈ R m , t ∈ R n q A, t s.t As = t y ← D m R,σ w := Ay w - c $ ← C c z := sc + y Abort if Rej(z, sc, σ) = 0 z -Check: z ≤ B Az = tc + w

Proof.

Correctness: Using lemma 2.3.6 we know that since σ ≥ 11B C B ≥ 11 sc the rejection step will accept with probability overwhelmingly close to 1/3 and the vector z output will be statistically close to D m R,σ . By lemma 2. Honest Verifier Zero-Knowledge: We only prove that accepting transcripts do not leak information. The reason for this is that all concrete instantiations of the proofs of knowledge described in this section will be made non-interactive via the Fiat-Shamir transform, in which case only accepting transcripts will matter since aborting runs of the protocol will not output anything. Moreover the protocol of Figure 3.2 can be made zero-knowledge even for non-accepting transcripts by sending B(w) , where B is a commitment, instead of w and then sending the opening of that commitment in the response flow. Let S(A, t) be the following PPT algorithm:

• Sample c $ ← C • Sample z ← D m R,σ • Set w = Az -tc • Output (w, c, z)
It is clear that z verifies with overwhelming probability. We already showed in the proof of correctness that in the real protocol when no abort occurs the distribution of z is within statistical distance 2 -100 of D m R,σ . Since w is completely determined by A, t, z and c, the distribution of (w, c, z) output by S is within distance 2 -100 of the distribution of these variables in the actual protocol.

Multiple criteria come into play when considering the efficiency of a ZKPoK. The main concern will be the communication overhead (or proof size for the non-interactive variant) which we will consider to be |z| / |s| 1 . The soundness error heavily influences the communication overhead of the proof, as a protocol with soundness error C will need to be repeated λ/ log(1/C) times to achieve overwhelming soundness and will thus multiply the overhead by the same amount. Another important attribute of lattice-based zero-knowledge will be the slack of the protocol, defined as z / s . The slack of the proof of knowledge will affect how we set parameters, for example when proving knowledge of a preimage for the one way function defined by A ∈ R n×m q we will of course want this function to be hard to invert for s but also for z, otherwise the solution extracted by the knowledge extractor would be vacuous. Hence a large slack will imply larger parameters and in turn larger overhead. Finally the computation complexity of the protocol can be of importance (though it is often a smaller concern), most of the computational complexity comes from one-way function evaluations (which are matrix/vector products) and discrete Gaussian sampling. As discrete Gaussians can be computationally intensive to sample some applications will forego Gaussians in favor of uniform or other simpler distributions, at a cost in parameters. ZKPoKs over the integers. Here we consider the ring R = Z. In this case the challenge space will be C = {0, 1}, we could consider larger challenge space for better soundness but the slack of the protocol depends on the bound B C on the norm of the challenges which would grow linearly with the size of the challenge space. These parameters result in an "exact" proof of knowledge (since C = {1}) with soundness 1/2 and slack 11 √ 2dm. The main issue here is the constant soundness, meaning that the ZKPoK will need to be repeated λ times to achieve overwhelming soundness, resulting in impractically large proofs. ZKPoKs over polynomial rings. If we consider a ring of dimension larger than one we can obtain new tradeoffs. Let R = Z [X] /X d + 1, for d a power of two. We consider the challenge set

C = {c ∈ R | c 1 = κ, c ∞ = 1}.
Using such a challenge set results in an "approximate" proof of knowledge with soundness error 1

/ |C| = d κ -1
2 -κ and slack 11κ √ 2md, the bound κ will be chosen so that the protocol achieves overwhelming soundness.

Using this challenge set we obtain a proof of knowledge with roughly equivalent slack and without any need for repetition. The downside being that it is no longer clear exactly what this "approximate" proof really proves as the knowledge extractor can only extract z such that Az = tc for some c ∈ C. Lyubashevsky shows in [START_REF] Lyubashevsky | Towards practical lattice-based cryptography[END_REF] that such a ZKPoK can be used for digital signatures, we will also use "approximate" proofs in Chapters 4 and 5 to construct a group signature and an e-voting scheme.

ZKPoKs with monomial challenges. In this paragraph we will also consider the ring

Z [X] /X d + 1 but with the challenge space C = {0} ±X j j<d .
While this challenge set is only of size 2d + 1 it has the property that elements c ∈ C have inverses in R q such that 2c -1 1 ≤ d (cf. lemma 2.2.1). Meaning that we can consider ZKPoKs which extract witnesses from the relation

R = (t, s, 2) ∈ R n q × R m × R | As = 2t, s ≤ 2dB which is such that R ⊂ R as one can map (t, s, c) ∈ R to (t, 2sc -1 , 2) ∈ R .
Using this challenge set we obtain a proof with soundness error 1/(2d + 1) and slack 11d √ 2dm, resulting in proofs that are log(2d + 1) times smaller but with d times more slack than for C = {0, 1}. Once again the proof is "approximate" since extraction recovers a preimage of 2t rather than t but this "fixed" approximation can be better than the solution of the previous paragraph. For example extracted values can be summed, i.e. if As 1 = 2t 1 and

As 2 = 2t 2 then A(s 1 + s 2 ) = 2(t 1 + t 2 )
, such a property does not hold for elements in R , this will come in handy when we construct our e-voting scheme in Chapter 5.

Applications to Commitments

Proof of Opening. We consider a commitment t defined as in Section 2.4.1, i.e. of the form

t = t 1 t 2 = A 1 A 2 r + 0 m
One can prove knowledge of an opening simply by using the protocol of Figure 3.1 to prove knowledge of a preimage of t 1 . Consider the corresponding binary relations:

R = (t 1 , r, 1) ∈ R n q × R m × R | A 1 s = t, r ≤ B R = (t 1 , r, c) ∈ R n q × R m × R | A 1 r = t 1 c, r ≤ 2B , c ∈ C
The soundness extractor of the protocol Π OW F (A 1 , t 1 ; r) will extract a tuple (t 1 , r, c) ∈ R . By definition of the opening of a commitment it is clear that r, c is a valid opening for the message t 2 c -A 2 r as long as r ≤ 2B ≤ B Com . Similarly one can prove knowledge of an opening to a specific message m by proving knowledge of a preimage of t -0 m for the matrix A, i.e. from the proof Π OW F A, t -0 m ; r one can extract r, c such that

tc = Ar + c 0 m
Proofs of Linear Relations. We now consider how to prove that the messages of two commitments verify a certain linear relation. Formally for some public u, v ∈ R, t = Com(m; r) and t = Com(m ; r ) we want a proof that um + vm = 0. We thus consider the following relations:

R = (t, t , r, r , m, m , 1) ∈ R n+l q × R n+l q × R m × R m × R l × R l × R s.t. t = Com(m; r), t = Com(m , r ), r ≤ B, r ≤ B, um + vm = 0 R = (t, t , r, r , m, m , c) ∈ R n+l q × R n+l q × R m × R m × R l × R l × R s.t. ct = Com(cm; r), ct = Com(cm , r ), r ≤ 2B , r ≤ 2B , um + vm = 0
Such a proof can be obtained by applying the proof for one-way functions to a well chosen matrix. Let B be the following matrix

B =    A 1 0 0 A 1 uA 2 vA 2   
observe that if our commitment scheme is binding for randomnesses of norm less than B, then

(t, t , r, r , m, m , 1) ∈ R ⇔ B r r =    t 1 t 1 ut 2 + vt 2    ∧ r ≤ B ∧ r ≤ B The protocol Π OW F   B,    t 1 t 1 ut 2 + vt 2    ; r r  
 is therefore a valid ZKPoK with knowledge extractor in R .

P V t 1 , . . . , t ∈ R n q A, t 1 , . . . , t i ∈ [ ] , s ∈ R m s.t. t i = As
For j = i :

c j $ ← C z j ← D m R,σ w j := Az j -t j • c j y i ← D m σ w i := Ay i w 1 , . . . , w - c c $ ← C c i = c j =i c j z i = sc i + y i Abort if Rej(z i , s i c i , σ) = 0 z 1 , . . . , z k - c 1 , . . . , c k Check: ∀j ∈ [ ] , z j ≤ B ∀j ∈ [ ] , Az j = t j c j + w j c = k 1 c j Figure 3.3:
Proof of knowledge of a preimage s of one of vectors t j .

OR-Proofs

Given Σ-protocols for two relations R 0 and R 1 , one can prove that he knows a witness for either t 0 ∈ L(R 0 ) or t 1 ∈ L(R 1 ) without revealing which is the case. Let b ∈ {0, 1} be such that P knows s b with (t b , s b ) ∈ R b , the prover first computes a transcript using the simulator of the relation for which he does not have a witness, and then uses cc 1-b as a challenge for the relation for the relation for which he knows the witness, where c 1-b is the challenge used in the simulator and c a challenge sent by the verifier. This protocol (given in e.g. [START_REF] Damgård | On Σ-protocols[END_REF]) assumes that the challenges form a group as the verifier should not be able to distinguish whether the prover computed

c 0 = c -c 1 or c 1 = c -c 0 .
The challenge space we used in lattice based ZKPoK typically do not have this property, to remedy this we will endow C with an ad-hoc group law. For any ≥ 2 we describe in Figure 3.3 an or-proof for the relations

R OR = (t 1 , . . . , t , s, 1) ∈ R n q × R m × R | ∃i, As = t i , s ≤ B R OR = (t 1 , . . . , t , s, c) ∈ R n q × R m × R | ∃i, As = t i c, s ≤ 2B , c ∈ C
We will consider ⊕ to be an efficiently computable group law over the challenge space, we will show how to obtain such a group law. Correctness: Using lemma 2.3.6 we know that since σ ≥ 11B C B ≥ sc i the rejection step will accept with probability overwhelmingly close to 1/3 and the vector z i output will be statistically close to D m σ , for i = j the vector z j comes exactly from D m σ . By lemma 2.3.5 we have for all j ∈ [ ] , z j ≤ √ 2mdσ ≤ B with overwhelming probability.

Lemma 3.3.1. Let A ∈ R n×m q , t 1 , . . . , t ∈ R n q , s ∈ R m q , and i ∈ [ ] such that t i := As and s ≤ B. Let B C ≥ max c∈C ( c 1 ), σ ≥ 11B C B,
It is clear that in the honest protocol the response is computed in such a way that the verification equations stand. Honest Verifier Zero-Knowledge: We only prove that accepting transcripts do not leak information. Let S(A, t 1 , . . . , t ) be the following PPT algorithm:

Special

• Sample c $ ← C • Sample c j $ ← C for j < , and set c = c j = c j • Set w j = Az j -t j c j for j ≤ • Output (w 1 , . . . , w , c, z 1 , . . . , z , c 1 , . . . , c )
It is clear that the transcript output by the simulator verifies with overwhelming probability. We already showed in the proof of correctness that in the real protocol when no abort occurs the distribution of z j is within statistical distance 2 -100 of D m σ for all j ∈ [ ]. Since C is a group for ⊕ the vector (c 1 , . . . , c l ) is sampled uniformly over C conditioned on c j = c in both the simulator and the real protocol. Since (w 1 , . . . , w ) is completely determined by A, t , . . . , t l , z 1 , . . . , z l , c 1 , . . . , c l and c, the distribution of the transcript output by S is within distance 2 -100 of the distribution of the one in the actual protocol.

Endowing C with a group structure. If C = {0, 1} or C = {0} ±X j j<d then adding a group law to the challenge space is straightforward, we will thus focus on the case where

C = {c ∈ R | c 1 = κ, c ∞ = 1}.
One can obtain a group law ⊕ by defining a bijection φ from C to Z |C| and setting x ⊕ y := φ -1 (φ(x) + φ(y)), to do so we will need both φ and φ -1 to be efficiently computable. Recall that we have fixed

C = {c ∈ R | c 1 = κ, c ∞ = 1} which is of size |C| = 2 κ d κ (
i = 1 iff the i th non-zero coefficient of c is 1. It is clear that finding an efficient bijection φ : C → Z ( d κ ) is sufficient. For c ∈ C let ind(c) ∈ Z κ
d be such that ind(c) i for 0 ≤ i < κ is the index of the i th non-zero coefficient of c, then we define φ as follows:

φ (c) = κ-1 0 ind(c) i i + 1
where a b = 0 if b > a. This bijection in fact corresponds to ordering C in lexicographic order and can be computed in time O(κd). φ -1 is somewhat more complicated to compute as there is no convenient closed-form expression but the following algorithm was shown in [START_REF] Stern | A method for finding codewords of small weight[END_REF] to compute φ -1 in quadratic time:

Algorithm 4 φ -1 x ∈ Z ( d κ ) i := d j := x k := i κ while i > 0 do k := k • i-κ i if j ≤ k then output 0 k := k else output 1 j := j -k k := k • κ i i := i -1

Subset Membership Proofs

The goal of this section will be to prove that the message m of a commitment t := Com(m) is in a certain fixed subset S ⊂ R l q . A simple approach that works for any set S is to use the OR-proof of Section 3.3 on each element of S, of course such a technique quickly becomes unpractical since the size of the proof would grow linearly with the size of S. A different approach would be to prove that the message belongs to a subring S q of R q by using the Chinese remainder theorem, for example suppose that X d + 1 split into X d + 1 = f g mod q then we could take S q = f R q = {f x : x ∈ R q } and prove that t commits to m ∈ S q by proving that mg = 0 mod q. This can be done with a proof size independent of |S q | by using the linearity proof of Section 3.2.2. A caveat of this solution is that by definition of S q its element will not have an inverse in R q , which is an often important property, e.g. for the group signature of Section 4.2. We will thus prove that the message m ∈ R q is in a subring S q of R q with invertible elements, to do so we will use the automorphisms of R.

Galois Group Structure of Cyclotomic Rings. We will only state the results that are useful in constructing our proof of subset membership, for a more in-depth approach to the Galois group structure of cyclotomic rings we refer the reader to [PLS18]. Consider the following functions for 0 ≤ i < 2d:

ξ i : R → R u(X) → u(X i ) the set Γ := {ξ i : i ∈ Z * 2d } is the so-called Galois group of R 2 .
Γ is a group for composition 2 The definition of the Galois group is in fact more intricate as it is only defined for field extensions. If we Chapter 3

3.4 Subset Membership Proofs 35 Degree k Galois group H Generator α 1 ξ -1 , ξ 5 1 2 ξ -1 , ξ 2 5 X 3072 -X 1024 4 ξ -1 , ξ 4 5 X 3584 -X 512 8 ξ -1 , ξ 8 5
X 3849 -X 256 Table 3.1: Subrings of R q , for d = 4096, of degree at most 8 with generators for the corresponding Galois group H, and generators of the subring.

and the only subset of R that is fixed by Γ is Z (i.e. the polynomials of degree 0)

R/Γ Z.
As a group Γ is isomorph to

Z * 2d Z 2 × Z d/2
and is therefore generated by two elements, these elements are ξ -1 : X → X 2d-1 = X -1 and ξ 5 : X → X 5 . From this we know that the only elements of R fixed by both ξ -1 and ξ 5 are the constant polynomials. To obtain a larger subring we can consider the elements that are fixed by a subgroup of Γ, for any power of two k < d we have: R/ ξ -1 , ξ k 5 Z k . We can thus obtain subrings of R of dimension k for any power of two less than d. However while this is true for R it is not trivial for R q , the set Γ will still be a group of automorphism of R q but it might be possible that, for example, there exists u ∈ R q that is fixed by both ξ -1 , and ξ 5 but is not a constant. Fortunately we prove in [PLS18] that for a well chosen modulus q there are no such problems, i.e.:

R q / ξ -1 , ξ k 5 Z k q .
We can now prove that a message is in a subring of dimension k by proving that it is fixed by ξ -1 and ξ 5 . Moreover such subrings only contain invertible elements, and have a Z q -basis that consists of the power of an efficiently computable polynomial α ∈ R q , i.e.

R/ ξ -1 , ξ k 5 = c 0 + c 1 α + . . . , +c k-1 α k-1 : c i ∈ Z q Theorem 3.4.1 ([PLS18] Theorem 3.2). Let d > k ≥ 1 be powers of 2, let q be a prime congruent to 3 or 5 modulo 8. Let H = ξ -1 , ξ k 5 . The subring R q / ξ -1 , ξ k 5 is of dimension k (and thus size q k ), is generated by α = X d-d 2k -X d 2k
, and all of its elements are invertible in R q .

We give in Table 3.1 a few example of subrings of R q and their generators.

Proving Stability Under Automorphisms. We present in this section a proof of knowledge that a commitment opens to a message m ∈ R l q that is invariant under a certain set of

P V A := A 1 A 2 , r, m, A, t 1 , t 2 , (ξ j ) j∈S⊂Z * m t 1 , t 2 , (ξ j ) j∈S⊂Z * m s.t t 1 t 2 = Com(m; r)
and ∀j ∈ S, m = ξ j (m) automorphisms (ξ j ) j∈S⊂Z * m , as a special case we can show that m ∈ Z l q by proving that it is invariant under two automorphisms (specifically ξ -1 and ξ 5 ).

y ← D m R,σ Aut ∀j ∈ S, y j ← D m R,σ Aut w 1 := A 1 y w 1,j := ξ j (A 1 ) y j w 2,j = A 2 y -ξ j (A 2 ) y j w 1 - w 1,j , w 2,j c $ ← C c z := rc + y z j := ξ j (r) c + y j If Rej ((z, (z j )), (rc, ξ j (r) c), σ Aut ) = 0 Then Abort z, (z j ) j∈S - Check: z ≤ B Aut ∀j ∈ S, z j ≤ B Aut A 1 z = t 1 c + w 1 ∀j ∈ S, ξ j (A 1 ) z j = ξ j (t 1 ) c + w 1,j ∀j ∈ S, A 2 z -ξ j (A 2 ) z j = (t 2 -ξ j (t 2 )) c + w 2,j
R Auto = (t, r, m, 1) ∈ R n+l q × R m × R l × R s.t. t = Com(m; r), r ≤ B Aut , ∀j ∈ S, ξ j (m) = m R Auto = (t, r, m, c) ∈ R n+l q × R m × R l × R s.t. ct = Com(cm; r), r ≤ 2B Aut , ∀j ∈ S, ξ j (m) = m Theorem 3.4.2. Let r ≤ B Aut . Let S be a set of automorphisms of size |S|. Let σ ≥ 11B C B Aut |S| + 1 and B Aut ≥ √ 2mdσ Aut . If B com ≥ 2B Aut , then the protocol consider K := Q(ζ), where ζ is a complex root of X d + 1 then the Galois group Gal(K/Q) is the set of all automorphisms of K that fix Q. This set is exactly ξi : ζ → ζ i : i ∈ Z * 2d .
Π Auto (A, t, S; s, m) of Figure 3.4 is a Σ -protocol for relations R Auto and R Auto with success probability 1/3 and soundness 1/ |C|.

Proof. The arguments for correctness and zero-knowledge are identical to the ones of Theorem 3.2.1, we will focus on special soundness. Let (w 1 , w 1,j , w 2,j , c, z, z j ) j∈S and w 1 , w 1,j , w 2,j , c , z , z j j∈S be two accepting transcripts.

We will prove that there exists a message m such that (zz , m, cc ) is a valid opening of t 1 t 2 and ∀j ∈ S, ξ j ( m) = m. For a fixed j ∈ S, let z = zz , zj = z j -z j , and c = cc .

By taking the difference of the verification equations for both transcripts we obtain:

A 1 z = t 1 c (3.1) ξ j (A 1 ) zj = ξ j (t 1 ) c (3.2) A 2 z -ξ j (A 2 ) zj = (t 2 -ξ j (t 2 ))c (3.3)
If we apply the automorphism ξ -1 j to equation 3.2 we have A 1 ξ -1 j (z j ) = t 1 ξ -1 j (c), we can then multiply this equation by c and equation 3.1 by ξ -1 j (c) and take the difference to get:

A 1 ξ -1 j (z j )c -zξ -1 j (c) = 0 Using verification we know that z ≤ 2B Aut and zj ≤ 2B Aut , which implies ξ -1 j (z j )c -zξ -1 j (c) ≤ 4B C B Aut .
By the binding property of our commitment scheme we obtain that ξ -1 j (z j )c = zξ -1 j (c), or equivalently zj ξ j (c) = ξ j (z)c. We multiply equation 3.3 by ξ j (c) and use the previous equality to obtain:

A 2 zξ j (c) -ξ j (A 2 ) ξ j (z)c = (t 2 -ξ j (t 2 ))cξ j (c) (3.4)
Since c has an inverse in R q we can define m ∈ R l q such that ct 2 = A 2 z + c m. By replacing ct 2 in equation 3.4 we have: m = ξ j ( m)

In conclusion we have extracted z, m, and c such that:

A 1 A 2 z + 0 c m = c t 1 t 2
with z ≤ 2B Aut and m = ξ j ( m). The same argument can be applied for the other j ∈ S.

Amortized Zero-Knowledge

In section 3.2 we present a simple protocol to prove knowledge of a preimage for lattice-based one-way functions. i.e. Given a matrix A and a target vector t = As for a small secret s we describe a proof of knowledge of a vector s with small coefficients (though larger than those in s) and a ring element c with very small coefficients satisfying As = ct. As long as the ring R has many elements with small coefficients, such proofs are very efficient, producing soundness of 1 -2 -128 with just one iteration. While these proofs are good enough for constructing practical digital signatures (e.g. [GLP12; DDLL13; BG14]), commitment schemes with proofs of knowledge [BKLP15; BDOP16], and certain variants of verifiable encryption schemes [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF], they prove less than what the honest prover knows. In many applications where zero-knowledge proofs are used, in particular those that need to take advantage of additive homomorphisms, the presence of the element c makes these kinds of "approximate" proofs too weak to be useful. As of today, we do not have any truly practical zero-knowledge proof systems that give a proof of knowledge for a single preimage. Previous approaches. The situation is considerably more promising when one considers amortized proofs, in which one wants to simultaneously prove knowledge of s 1 , . . . , s such that t j = As j , ∀j ∈ [ ]. The amortized proof given in [START_REF] Damgård | Multiparty Computation from Somewhat Homomorphic Encryption[END_REF] using the protocol from [START_REF] Cramer | On the Amortized Complexity of Zero-Knowledge Protocols[END_REF] showed that a prover only needs to generate λ + vectors to prove the knowledge of equations, which gives an overhead of 1 + λ/ . The main downside of this protocol is that the slack is exponential in .

The works of [START_REF] Baum | How to Prove Knowledge of Small Secrets[END_REF] and [START_REF] Cramer | Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack[END_REF] gave a novel protocol, still using the Fiat-Shamir with Aborts with 0/1 challenges idea, in which the overhead was constant (down to 2), while the slack could be bounded by a small polynomial in the security parameter (To be precise, only by a super-polynomial factor in the first work). The main downside of these protocols is that they require the number of equations to be fairly large before amortization kicks in. In particular one needs to have more than k = 4λ 2 equations. Thus scenarios where one does not have too many (around λ as in [START_REF] Damgård | Multiparty Computation from Somewhat Homomorphic Encryption[END_REF]) equations to prove would not benefit from the protocol.

The work of [PL17] showed that one could decrease the number of equations in the above protocol by a factor of log 2 α by increasing the running time of the proof by a factor of α. It also gave a protocol requiring even fewer equations when the functions are over polynomial rings of dimension d by using the monomial challenge space C = {0} ±X j j<d presented in Section 3.2.1. This further reduces the required number of equations by a factor approximately log d. Nevertheless, one still needs at least a few thousand of them in order to be able to use amortization in a practical manner.

Our construction. We present a surprisingly simple zero-knowledge proof for proving the knowledge of preimages. Formally we consider a Σ -protocol for the following relations

R Amo = (T, S) ∈ R n× q × R m× | AS = T, s 1 (S) ≤ B R Amo = (T, S) ∈ R n× q × R m× | AS = T, S max ≤ 2B
We first give a useful lemma for knowledge extraction. In essence this lemma will be used to show that a prover who can output a verifying output for a challenge c 1 , . . . , c has a high probability of also being able to answer a challenge c 1 , c 2 , . . . , c in which only c 1 = c 1 .

Lemma 3.5.1 ([Dam10]

). Let H ∈ {0, 1} l×k for some k, l > 1, such that a fraction ε of the inputs of H are 1. We say that a row of H is "heavy" if it contains a fraction at least ε/2 of ones. Then more than half of the ones in H are located in heavy rows.

We describe our proof in Figure 3.5. Our first instantiation will be with the challenge set C ×k for C = {0, 1}, this solution allows the extractor of the protocol to obtain exact

P V A ∈ R n×m q , S ∈ R m× , T ∈ R n× q A, T s.t AS = T Y ← D m×k σ W = AY W - C $ ← C ×k C Z := SC + Y Abort if Rej(Z, SC, σ) = 0 Z - Check: Z max ≤ B AZ = TC + W Figure 3
.5: Amortized proof for equations. The ring R can be either Z or Z [X] /X d + 1, the challenge set will be respectively {0, 1} or {0} ±X j j<d preimages of the t i and requires k ≥ λ + 2. This ensures that communication only grows linearly in λ regardless of the size of (since

Z ∈ Z m×λ q ). Theorem 3.5.2. Let C = {0, 1}, and k ≥ λ + 2. Let s 1 (S) ≤ B, σ ≥ 11B √ k, and B ≥ √ 2mdσ.
The protocol Π Amo1 (A, T; S) of Figure 3.5 is a Σ -protocol for relations R Amo and R Amo with success probability 1/3 and soundness error less than 2 -λ .

Proof.

Correctness: Using lemma 2.3.6 we know that since σ ≥ 11B √ k ≥ SC the rejection step will accept with probability overwhelmingly close to 1/3 and the vector Z output will be statistically close to D m×λ R,σ . By lemma 2.3.5 we have Z max ≤ √ 2mdσ ≤ B with overwhelming probability. It is clear that in the honest protocol the response is computed in such a way that the verification equation AZ = TC + W stands.

Honest Verifier Zero-Knowledge: We only prove that accepting transcripts do not leak information. Let S(A, T) be the following PPT algorithm:

• Sample C $ ← C ×k • Sample Z ← D m×λ σ • Set W = AZ -TC • Output (W, C, Z)
It is clear that Z verifies with overwhelming probability. We already showed in the proof of correctness that in the real protocol when no abort occurs the distribution of Z is within statistical distance 2 -100 of D m×λ σ . Since W is completely determined by A, T, Z and C, the distribution of (W, C, Z) output by S is within distance 2 -100 of the distribution of these variables in the actual protocol.

Soundness:

We defer the proof of soundness to lemma 3.5.3, the proof is somewhat more complicated than for the protocols of section 3.2 as we cannot argue special soundness.

Lemma 3.5.3 (Soundness). For any prover P * who succeeds with probability ε > 2 -λ (i.e. ≥ 2 -k+2 ) over his random tape χ ∈ {0, 1} x and the challenge choice C $ ← C ×k , there exists a knowledge extractor E running in expected time poly(λ)/ε who can extract a witness S ∈ R m× , such that AS = T, and S max ≤ 2B .

Proof. For i ∈ [ ], let t i ∈ R n be the ith column of T, and c T i ∈ R 1×k be the ith row of C (note that c T i are not the transpose of the columns of C but really its rows). Note that t i c T i ∈ R n×k and TC = i=1 t i c T i . For any fixed i, we describe an extractor E i who can extract a preimage of t i of norm less than 2B in expected time O(1/ε), and the full result follows by running each extractor (of which there are = poly(λ)). Consider a matrix H i ∈ {0, 1} 2 k( -1)+x ×2 k whose rows are indexed by the value of (χ, c T 1 , . . . , c T i-1 , c T i+1 , . . . , c T ) and whose columns are indexed by the value of c T i . An entry of H i will be 1 if P * succeeds for the corresponding randomness and challenge (i.e. produces an accepting Z). We will say that a row of H i is "heavy" if it contains a fraction of at least ε/2 ones, i.e. if it contains more than 2 k * ε/2 > 2 ones. The extractor E i will proceed as follow:

1. Run P * on random (χ , C ) until it succeeds, and obtains Z that verifies. This takes expected time 1/ε. The extractor E i runs in expected time poly(λ)/ε, and aborts with probability less than 1/2 + 2 -λ . The running time is clear from the definition of E i . To compute the abort probability note that in step 2 all the challenges (χ , C ) considered are in the same row of H i as (χ , C ), if we call Abort the event where E i aborts and Heavy the event that (χ , C ) is in a heavy row of H i , we have:

Pr [ Abort ] = Pr Abort Heavy Pr [ Heavy ] + Pr Abort ¬Heavy Pr [ ¬Heavy ]
According to Lemma 3.5.1, Pr [ ¬Heavy ] < 1/2. On the other hand if the row is heavy then for a random sample, different from (χ , C ), in this row P * has probability at least ε/2 -2 -k > ε/4 of outputting a valid answer (the probability is ε/2 -2 -k and not ε/2 because we want a reply for a challenge different from (χ , C )). Which entails that the probability that P * does not succeed on any of the λ/ε challenges C is:

Pr Abort Heavy < (1 -ε/4) λε < e -4λ < 2 -λ
From this we get:

Pr [ Abort ] < 1/2 + 2 -λ
By running E i O(λ) times we obtain an extractor that runs in expected time poly(λ)/ε and outputs two valid pairs C , Z and C , Z such that ∀j = i, c T j = c T j , and c T i = c T i . Since both transcripts verify we know:

AZ = TC + W = n j=1 t j c T j + W AZ = TC + W = n j=1 t j c T j + W Which implies: A(Z -Z ) = j=1 t j (c T j -c T j ) = t i (c T i -c T i ) If we consider an index l ∈ [ ] such that c T i [l] = c T i [l]
, and assume w.l.o.g that c T i [l]-c T i [l] = 1, then by only considering the l th column of the previous equation we obtain:

A(z l -z l ) = t i where z l -z l ≤ 2B . Our second instantiation uses R = Z [X] /X d + 1 and C = {0}
±X j j<d , in this protocol the extractor will only obtain preimages of 2t i but the number of columns in the response matrix Z can be reduced by a factor of log(2d + 1) as the soundness now only requires that k log(2d + 1) ≥ λ + 2. It is worth noting that in this protocol the values of n and m would typically be chosen to be around d times smaller than in the instantiation with R = Z, that is because A will be a matrix of polynomials of degree d. In this context the language R Amo is unchanged but the language R Amo is somewhat larger.

R Amo = (T, S) ∈ R n× q × R m× | AS = 2T, S max ≤ 2dB Theorem 3.5.4. Let R = Z [X] /X d + 1, C = {0}
±X j j<d , and k ≥ (λ + 2)/ log(2d + 1). Let s 1 (S) ≤ B, σ ≥ 11B √ k, and B ≥ √ 2mdσ. The protocol Π Amo2 (A, T; S) of Figure 3.5 is a Σ -protocol for relations R Amo and R Amo with success probability 1/3 and soundness error less than 2 -λ .

Proof. The proofs for correctness and zero-knowledge are nearly identical to the ones of Theorem 3.5.2. We will prove soundness in Lemma 3.5.5.

Lemma 3.5.5 (Soundness). For any prover P * who succeeds with probability ε > 2 -λ (≥ 2 -k log(2d+1)+2 ) over his random tape χ ∈ {0, 1} x and the challenge choice C ← C ×k there exists a knowledge extractor E who can extract a witness S ∈ R m× , such that AS = 2T, and S max ≤ 2dB, in expected time poly(λ)/ε.

Proof. The first part of the proof (obtaining C , Z and C , Z ) is identical to the one of Lemma 3.5.3 except for the fact that the matrix H i has different dimensions. Let δ = log(2d + 1). Since for each j ∈ [ ], c T j is sampled from a set of size 2 kδ , we have

H i ∈ {0, 1} 2 kδ( -1)+x ×2 kδ
. The heavy rows of H i will contain 2 kδ ε/2 > 2 ones, and the extractor can proceed as in the proof of Lemma 3.5.3.

Assume that E i has extracted C , Z" and C , Z such that ∀j = i, c T j = c T j , and c T i = c T i . As previously we have:

A(Z -Z ) = j=1 t j (c T j -c T j ) = t i (c T i -c T i ) If we consider an index l ∈ [ ] such that c T i [l] = c T i [l], since C = {0}
±X j 0≤j≤d-1 , we have according to Lemma 2.2.1 that there exists a g ∈ R such that 2 -1 (c T i [l] -c T i [l])g = 1 and g 81 ≤ d. Hence:

A(z l -z l )g = 2t i • 2 -1 (c T i [l] -c T i [l])g = 2t i With (z l -z l )g ≤ 2dB .

Introduction

Our Contribution

One application of our new proof system presented in section 3.4 is towards constructing more practical lattice-based privacy protocols. In this chapter we will use the specific example of group signatures. A group signature scheme consists of three parties -the group manager, the opener, and group members. The group manager has a public key and generates secret keys for all the group members. Using their secret keys, the group members can sign messages in a way that anyone can verify that a message was signed by a member of the group, but the identity of the signer remains secret (one should not even be able to tell that two messages were signed by the same member) to everyone except for the opener. The opener should be able to recover the identity of any signer.

A common way of constructing group signatures is via the sign-and-encrypt approach. The group manager's public key is the public key to some signature scheme, and the secret key of a user with identity i is a signature of i. To sign a message, the group member produces a non-interactive ZKPoK that he has the manager's signature of some identity i. 1 Furthermore, the group member encrypts his identity i using the opener's public key, and gives another ZKPoK of the fact that the encryption is of the same identity as was used in the proof.

To create a practical scheme using the above approach, one typically needs to have a very efficient standard model signature scheme that is used by the group manager to sign user identities. 2 While there exist efficient standard model signature schemes based on classical assumptions (e.g. [START_REF] Camenisch | A Signature Scheme with Efficient Protocols[END_REF]) which can be used for constructions of fairly compact group signatures, the non-existence of such signatures based on lattice assumptions is the main culprit in the fact that the only "efficiency" lattice-based group signatures have is asymptotic.

Lattice-based signature schemes in the standard model are built based on Boyen's framework [START_REF] Boyen | Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More[END_REF]. There have been efficiency improvements to this scheme (e.g. [DM15; KY16]) that used polynomial lattices, but they still appear to be unsuitable for producing practical (group) signatures. In fact, the only group signature that we're aware of that actually proposes concrete parameters uses different techniques, and the signatures in it are on the order of 50MB [START_REF] Libert | Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors[END_REF].

While lattice-based signatures in the standard model are inefficient, there is a much more efficient selectively-secure lattice-based digital signature scheme that is implicit from the works of [START_REF] Agrawal | Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE[END_REF][START_REF] Boyen | Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More[END_REF]. A selectively-secure signature scheme is one in which the adversary declares the message that he will forge on prior to seeing the public key. A scheme like this can be converted to a regular signature scheme with a reduction loss of 1/|S|, where S is the message space simply by guessing the message that the Adversary will forge on. Thus for small message spaces, this becomes a signature scheme with a meaningful reduction from hard lattice problems.

There have been several works that utilized the above-mentioned selectively secure scheme for group signatures and related applications [NZZ15; BCN17]. In those papers, proving that the identity i is in a particular set resulted in either a significant increase in the proof size, restrictions on the challenge space, and/or a very noticeable loss in the tightness of the proof. For example, in [START_REF] Phong | Simpler Efficient Group Signatures from Lattices[END_REF], the identity space was all polynomials with only a constant coefficient (i.e. of degree zero). But to prove this fact, the size of the proof of knowledge significantly increased due to the fact that one needed to map integers to a space with small coefficients. In [START_REF] Boschini | Relaxed Lattice-Based Signatures with Short Zero-Knowledge Proofs[END_REF], which used a similar high-level idea with polynomial rings, the message space of the selectively-secure signature scheme was a polynomial in a subfield of R q . The degree of the subfield could not be too small because the soundness error of the ZKPoK inversely depends on the degree of the subfield, and the degree cannot be too large because it would make the security reduction meaningless. Further complicating matters is that the messages have to have small coefficients, yet the proof of knowledge only proves that the coefficients are in a significantly larger space causing an additional loss in the reduction.

In the present work we show how our new proofs for stability under automorphisms gives rise to a fairly straight-forward group signature scheme. In particular, the set of identities will be exactly those elements in R q that are preserved under some set of automorphisms. The size of these sets can be small (as small as q), and so we will only lose a factor of the group size in the reduction. The idea for the ZKPoK will then be to do the proof of knowledge with the commitments of i rather than with i (thus not revealing the identity) and prove that our commitments are to elements in the appropriate set of identities. The only other property that we use from our commitment scheme is that if i • s = u, then Com(i; r) • s = 0 u + Com(0; r ). The encryption to the opener can be done using the main idea from the verifiable encryption scheme from [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF]. A point of note is that the selectively-secure signature scheme requires that the messages come from a set S such that the difference of any two elements from the set is invertible. This is compatible with our definition of sets because they turn out to be subfields of the original ring R q .

Instantiating our scheme with concrete parameters gives group signatures of around 580 KB, which is almost a 2 order of magnitude reduction from [START_REF] Libert | Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors[END_REF]. Our main technique should also applicable to a variety of other privacy applications that require similar proofs of knowledge. For example, one should be able to apply these techniques in a very similar manner to the constructions of anonymous credentials as in [START_REF] Boschini | Relaxed Lattice-Based Signatures with Short Zero-Knowledge Proofs[END_REF].

Overview of our Construction

We will use a particular instantiation of the commitment scheme from Section 2.4.1 where the common reference string public key is

a T 1 a T 2 = 1 a 1 a 2 0 1 a 3 ∈ R 2×3 q (4.1)
The master public key of the group manager will be a public key for the selectively secure signature scheme from [START_REF] Agrawal | Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE[END_REF] adapted to polynomial rings:

[ a T | b T ], u = a T s 1 + b T s 2 + a T 2 s 3 (4.2)
where a T = [a a ] for a uniformly-random a, a ∈ R q and b = [b 1 b 2 ] = a T r 1 r 2 e 1 e 2 where r i , e i are polynomials in R with small coefficients such that (a, b 1 , b 2 ) are indistinguishable from random based on the hardness of the R-LWE problem. The group member identities are polynomials i ∈ S ⊆ R q where the set S is preserved under some set of automorphisms of R q . The secret key of a user with identity i consists of vectors s 1 , s 2 , s 3 that are generated by the group manager using his secret trapdoor key R = r 1 r 2 e 1 e 2 . The group manager first picks a short vector s 3 from a particular distribution, and then "pre-image samples" short vectors s 1 , s 2 such that

[ a T | b T + i • [ 1 √ q] ] • s 1 s 2 = u + a T 2 s 3 . (4.
3)

The matrix [ 1 √ q ] 3 is the "gadget matrix" defined in Section 2.3.5 that allows for efficient pre-image sampling of short vectors s 1 , s 2 as in Equation (4.3) for all i = 0. When i = 0, the group manager can output s 1 , s 2 , -s 3 as the key. 4 The purpose of the a T 2 s 3 part of the construction is only necessary for the proof -it's unclear if it truly serves any security purpose. In the security proof, because b is only computationally-indistinguishable from random (rather than statistically), one needs a "double trap-door" for switching between games and a 2 serves that purpose. Normally, this would decrease the efficiency of the scheme because one would need to include the extra term a 2 • s 3 in the security proof. But in our case, we use the a 2 that appears as the common reference string in our commitment scheme, and this term anyway appears in our proof below. The only downside is that in practice one needs to do the extra sampling of s 3 and multiplication by a 2 in the key generation, and that the size of the solution to the Ring-SIS problem in the security proof is a small (virtually inconsequential) additive factor larger.

Signing. The high level idea for signing is for the user with identity i to prove knowledge of s 1 , s 2 , s 3 that satisfies Equation (4.3). If the proof of knowledge is a Σ-protocol, then it can be converted into a non-interactive proof using the Fiat-Shamir heuristic, which turns the Σ-protocol into a signature scheme if one inputs the message into the random oracle. The main difficulty lies in doing this proof without revealing i.

To hide i in our proof, the signer will commit to i and i √ q using the commitment scheme from Section 2.4.1 and publish his commitments as part of the signature. The main observation is that

0 a T | 0 b T + [Com(i; r) Com(i √ q; r )] • s 1 s 2 = 0 u + a T 2 s 3 + a T 1 a T 2 • r. ( 4.4)
The signer will give an approximate ZKPoK of the short randomnesses r, r that open the commitments to i, i √ q and also that i ∈ S. 5 In other words, he'll prove knowledge of 3 We write √ q instead of √ q for readability. 4 For i = 0, the group manager is able to output many possible valid s1, s2, s3 using his trapdoor and the gadget matrix. For i = 0, however, the gadget matrix disappears and so the group manager is only able to return one s 1 , s 2 , -s3 that he "planted" when creating u in Equation (4.2). For the security proof, it will be necessary that the distribution for all i is the same, and so for this reason, we make the pre-image sampling procedure for all i deterministic. In other words, the randomness used in the sampling will be derived by the group manager using a keyed PRF whose input depends on i. 5 Due to the slack in our zero-knowledge protocols, the proofs will be for larger values of r, r than those used in the commitments. But for simplicity of exposition in the introduction of this paper, we will use the same notation.

a T 1 a T 2 • [r r ] + 0 0 ci ci √ q = c • t (1) 1 t (2) 1 t (1) 2 t (2) 2 . (4.5)
In parallel, the signer will also prove that

a T | b T + [t (1) 2 t (2) 2 ] • s 1 s 2 = cu + a T 2 r . 6 (4.6)
Multiplying Equation (4.6) by c and combining with Equation (4.5) produces the equation

a T | cb T + a T 2 • [r r ] + c • [i i √ q] • cs 1 s 2 = c 2 u + ca T 2 r . (4.7)
We can then show that if an Adversary can produce polynomial vectors r, r , s 1 , s 2 , r , c with small coefficients that satisfy the above equation, then he is able to solve the Ring-SIS problem. The proof is very similar to the proof of selective security for the signature scheme of [START_REF] Agrawal | Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE[END_REF] . Intuitively, suppose that the Adversary in the impersonation game produces a solution (i.e. the extracted values from the PoK) for Equation (4.7) for i = 0. Then, using the fact that b T = a T R and u = a T s 1 + b T s 2 + a T 2 s 3 and writing R = [r r ], Equation (4.7) can be rewritten as

a T cs 1 + cRs 2 -c 2 s 1 -c 2 Rs 2 + a T 2 R s 2 -cr -c 2 s 3 = 0, (4.8)
which is a solution to the Ring-SIS problem because the coefficients of all the terms in parentheses are small relative to q. Of course, the Adversary is not guaranteed to impersonate on identity i = 0, but may choose an arbitrary i ∈ S. To handle this, we use the standard "puncturing" technique. In the security proof we would not choose b T = a T R as part of the public key, but we rather pick a uniformly-random "guess" i ∈ S, and set b T = a T R -[i i

√ q] as part of the public key. It's not hard to see that if the Adversary produces a solution for Equation (4.7) with i = i , then one again obtains the same Ring-SIS solution as in Equation (4.8). If the Adversary cannot tell how b was constructed, even after querying for preimages s 1 , s 2 , s 3 , then there is exactly a 1/|S| chance that i = i . Therefore there is a 1/|S| loss in the tightness of the security reduction. We give a first set of parameters which does not take this loss in tightness into account, there are multiple reason we consider such parameters. First the loss in tightness does not correspond to a practical attack, if we consider how to concretely attack the scheme it is not clear what advantage this reduction from a selective signature would give. The second reason being that the best cryptanalytic algorithms (c.f Section 2.3.4) run in exponential space which would arguably not be affected by a loss in tightness, for our parameters polynomial space algorithms would guarantee much more than 128 bits of security regardless of any complexity leveraging. Finally we include a second set of parameters in Table 4.2 (and the corresponding signature size in Table 4.1) which obtain more than 128 bits of post-quantum security even when accounting for the loss in tightness.

For the purposes of allowing opening, the signer will also create a Ring-LWE encryption of the three polynomials comprising the vector r used in the commitment of i in Equation (4.5) using the one-shot verifiable encryption / proof of plaintext knowledge from [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF] combined with the proofs of knowledge for Equation (4.5). The reason that we encrypt r rather than i is that the coefficients in r are small, whereas i comes from a set that is stable under some automorphism, and such sets contain elements with large coefficients. Once the opener decrypted the r, he knows from Equation (4.5) that a T 1 r = c • t

(1)

1 , and so he can recover c. Then using this c, he can recover i from the equality a T

2 r + ci = c • t (1)
2 . Reducing the Commitment Size. To reduce the size of the signature, we can slightly modify the commitment so that it works over two different moduli, one for the top and another for the bottom part (call them q 1 and q 2 respectively). In our group signature scheme, the value of q 2 needs to be large due to the fact that the Ring-SIS solution in Equation (4.8) is fairly large itself. The value of q 1 , on the other hand, only needs to be set so that the commitments to i and i √ q in Equation (4.5) are binding and hiding. Since a smaller q 1 will result in smaller sizes of t

(1)

1 , t (2)
1 in the commitment, it is sensible to set it as small as possible. We show that our proofs of automorphism stability still work if the two moduli are different.

Our Group Signature

Commitment Scheme

We will use the commitment scheme of Section 2.4.1 for messages in R q 2 . For the purpose of this scheme it will be advantageous to use two different moduli for the "top" and "bottom" part of the commitment. The security of our group signature will rely on the hardness of finding collisions on the bottom part of the commitment matrix (while the binding property of the commitment scheme only needs the top part to be collision resistant), this is why taking a larger modulo q 2 for the bottom part makes sense. While we prove that the hiding property of the scheme when taking two moduli can be reduced to M-LWE if the randomness is taken from a skewed distribution, here we will take r ← S k 1 where S 1 = U ({x ∈ R : x ∞ = 1}). As argued in Section 2.4.1 the fact that the distribution of the randomness is skewed in the commitment with different moduli is mostly an artefact of the reduction. Moreover we chose to take a small uniform distribution rather than Gaussian for simplicity, for a bounded number of samples the cryptanalysis of Section 2.3.4 still represents the best known attacks for such a distribution.

• CSetup(1 λ ) outputs a commitment matrix

A := a T 1 a T 2 with a 1 ∈ R 3 q 1 and a 2 ∈ R 3 q 2 .
• Com(m ∈ R q 2 ) outputs the commitment t := Ar + 0 m , and randomness r ← S 3 1 .

• Open(t, r, c) checks that the commitment is valid and outputs m := t 2c -1 a T 2 r ∈ R q 2 . We have fixed the dimensions of A to 2 × 3 this entails that the scheme relies on the R-LWE problem for hiding and R-SIS problem for binding. ZKPoKs with different moduli. The proofs of knowledge presented in Chapter 3 only consider one modulus q, they can however be seamlessly adapted to two moduli. We will use the proof for linear relations of Section 3.

t 2 open to messages m 1 , m 2 ∈ R q 2 such that m 2 =
√ qm 1 , and the proof of automorphism stability to prove that a commitment t opens to a message m ∈ Z q 2 . We do not recall these ZKPoKs as they are identical to the ones of Section 3.2, we however formally describe the proof output by the signature of a group member in Section 4.2.5. This proof will contain the two aforementioned proofs as well as a proof of verifiable encryption and will be used as a signature using the Fiat-Shamir transform.

Definitions

We first recall the definitions and security model of group signatures. A group signature scheme consists of a tuple of four algorithms (GSetup, Sign, Verify, Open):

• GSetup(1 λ , 1 N ):Takes as input the security parameter λ as well as the maximum number of identities N . Outputs the group public key gpk, the group manager secret key gmsk, and the secret keys of each identity sk 1 , . . . , sk N .

• Sign(sk i , M ) : Takes as input a user secret key sk i and a message M ∈ {0, 1} * . Outputs a signature z of M .

• Verify(gpk, M, z) : Takes as input the group public key gpk, a message M , and a signature z. Outputs 1 if z is a valid signature of M and 0 otherwise.

• Open(gmsk, M, z) : Takes as input the group manager secret key gmsk, a message M , and a valid signature z of M . Outputs an identity id ∈ [N ] or ⊥.

For correctness, we want that for any (gpk, gmsk, sk 1 , . . . , sk n ) ← GSetup(1 λ ), any j ∈ [N ], any M ∈ {0, 1} * , and any z ← Sign(gpk, sk j , M ), with overwhelming probability:

Verify(gpk, M, z) = 1, and Open(gpk, gmsk, M, z) = j

The security of the group signature is captured by two notions: anonymity and traceability [START_REF] Bellare | Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions[END_REF]. For anonymity we consider a PPT adversary A who has access to all the signing keys sk 1 , . . . , sk N but not the manager key gmsk. A chooses a message M and two identities i 0 and i 1 , his goal is to distinguish between signatures of M under these identities. There are multiple flavors of anonymity depending on whether A can access an opening oracle (full anonymity) or not (weak anonymity), intuitively full anonymity will be achieved when the PKE used in the opening is CCA-secure while weak anonymity corresponds to a CPA-secure encryption scheme. In this paper we present a weakly anonymous group signature. The verifiable encryption scheme we use [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF] can achieve CCA security but this comes at a cost in efficiency, moreover it is likely that in real implementations access to the tracing functionality of the scheme will be restricted, in which case weak anonymity seems to be an appropriate notion.

Exp anon-b (A, λ, N ) : (gpk, gmsk, sk 1 , . . . , sk

N ) ← GSetup(1 λ , 1 N ) (i 0 , i 1 , M, St) ← A(gpk, sk 1 , . . . , sk N ) z * ← Sign(gpk, sk i b , M * ) b ← A(z * , St) Return b'
Adv anon (A, λ, N ) := |Pr Exp anon-1 (A, λ, N ) = 1 -Pr Exp anon-0 (A, λ, N ) = 1 |
In full-traceability the adversary A has access to the signing keys (sk i ) i∈S for any arbitrary set S ⊂ [N ] (possible S = [N ]) as well as the manager secret key gmsk, his goal is to produce a valid signature z of some message M (i.e. which passes verification) such that either Open(gpk, gmsk, M, z) = j / ∈ S or Open(gpk, gmsk, M, z) = ⊥. Full-traceability captures the notion that all signatures, even when computed by a collusion of users and the group manager, should trace to a member of the forging coalition.

The Scheme

The group signature we present in this section will be for fixed parameters as per Table 4.2, for which the signatures will be of size 581 KB, as described in appendix 4.3. In particular we consider the power-of-two cyclotomic ring R = Z [X] /X 4096 + 1, and identity set [N ] = Z q 2 . This entails that user identities are exactly the elements x ∈ R q 2 that are left invariant under the automorphisms ξ -1 : X → X -1 = -X d-1 and ξ 5 : X → X 5 . We also use commitments that rely on R-LWE and R-SIS (which can be seen as specific instances of the module variant of the corresponding problems for modules of dimension 1). Using other cyclotomic rings can result in smaller signatures (especially since for some of them only one automorphism is needed to prove that elements belong to Z q 2 ), and using higher dimension commitments that rely on the module variants of LW E and SIS would allow for more fine-tuned parameters. We have chosen the parameters in this section as such for easier presentation and because they allow for simpler implementations. We will first present in this section a group signature scheme without opening, and show in section 4.2.4 how to add an opening. Let δ = √ q 2 , and g T be the gadget matrix 1 δ ∈ R 1×2 q 2 , we will consider the set of identities Id = Z q 2 . GSetup(1 λ ):

OSign(i, M ) : S ← S ∪ {(i, M )} Return Sign(sk i , M ) OCorrupt(i) : C ← C ∪ i Return sk i
• Sample A := a T 1 a T 2 ← CSetup(1 λ ), with a 1 ∈ R 3 q 1 , and a 2 ∈ R 3 q 2 . • Sample a $ ← R 2 q 2 . • Sample R $ ← S 2×2 1 and set b T = a T R ∈ R 1×2 q 2 . • Sample (s 0 1 , s 0 2 , s 0 3 ) ← D R,s × D R,s × D R,r • Set u := a T | b T | a T 2    s 0 1 s 0 2 s 0 3   
• Set gpk := (A, a, b, u)

• For i ∈ Z * q 2 , sample s i 3 ← D 3 R,
• For i ∈ Z * q 2 , sample (s i 1 , s i 2 ) ∈ R 4 s.t a T | b T + ig T s i 1 s i 2 = u -a T 2 s i 3 , and (s i 1 , s i 2 ) ← D 4 R,s • For i ∈ Z q 2 , set sk i := s i := (s i 1 , s i 2 , s i 3 )
Intuitively user i could sign a message M ∈ {0, 1} * by doing a non-interactive proof that he knows a small s ∈ R 6 such that a T | b T + ig T | a T 2 s = u in which the message is part of the hash that generates the challenge. However doing so would reveal his identity, indeed a verifier would need to know the matrix a T | b T + ig T | a T 2 to verify the signature and since a, a 2 , b, and g are public he could recover the identity of the signer. As explained in section 4.1.2 we circumvent this issue by committing to the part of the matrix that depends on i (that is ig T ) and proving that the previous equation still stands but for a commitment of u rather than u itself. Sign(M, s i ):

• Set t := t 1 t 2 = Com(i, r) ∈ R q 1 × R q 2
, where r ← S 3 1 .

• Set t := t 1 t 2 = Com(iδ, r ), where r ← S 3 1 .

• Set v T := a T | b T + t 2 t 2 | a T 2 ∈ R 1×7 q 2 , and s =    s i 1 s i 2 s i 3 -r r s i 2    R 7 , observe that v T s = u • Compute Π 1 = Π lin (t, t , δ; r, r , i, iδ) • Compute Π 2 = Π auto (t, (ξ -1 , ξ 5 ); r, i) Chapter 4
4.2 Our Group Signature 53

• Compute Π 3 = Π OW F (v; s ) • Output the signature z = (t, t , Π 1 , Π 2 , Π 3 )
The proofs Π 1,2,3 will use the Fiat-Shamir heuristic to transform interactive proofs into non-interactive proofs in the random oracle model, we will also include the message M in the random oracle call to obtain a signature. For unforgeability we will need all of these proofs to be executed with the same challenge, i.e. the signer will run all three proofs in parallel and compute a common challenge for all three as a hash of all relevant information. We describe the full non-interactive proof, including the opening, in more details in Section 4.2.5.

To verify a signature one simply verifies the proofs Π 1,2,3 . Verify(t, t , Π 1 , Π 2 , Π 3 ):

• Let t 1 t 2 := t • Let t 1 t 2 := t • Let v T = a T | b T + t 2 t 2 | a T 2
• Verify Π 1 using t, t , δ

• Verify Π 2 using t, ξ -1 , ξ 5

• Verify Π 3 using v

Adding the Opening

To be able to open the group signature scheme of Section 4.2.3 we will add a verifiable encryption to the signature. In essence we want the signer to encrypt his identity, using a public key associated to a decryption key that the group manager possesses, and prove that this encryption is indeed of his identity. To do so we will encrypt the randomness r of t = Com(id; r) and prove that a T 1 r = t 1 , note that encrypting id directly would result in a smaller ciphertext but a very large proof since id itself is not small. We use the verifiable encryption of [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF] which consists in a R-LW E encryption and a proof of knowledge. We let p be the modulus of the plaintext space of our encryption scheme (which we only need large enough to accommodate the decryption slack, see [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF]) and Q the modulus of the ciphertext. PKESetup(1 λ ):

• Sample a $ ← R Q • Sample s, e ← S 3 1 • Set b := as + e ∈ R 3 Q • Output (s, (a, b))
Encryption will consist in creating a standard R-LW E encryption and a proof that the message r encrypted is the randomness in t = Com(id; r). Enc((a, b), r, t 1 ):

• Sample r, e 1 ← S 1

• Sample e 2 ← S 3 1

• Set u := p(ar + e 1 )

• Set v := p(br + e 2 ) + m

• Set M 1 :=     
pa p 0 0 0 0 0 0 pb 1 0 p 0 0 1 0 0 pb 2 0 0 p 0 0 1 0 pb 3 0 0 0 p 0 0 1

     ∈ R 4×8 Q • Set M 2 := 0 1×5 a T 1 ∈ R 1×8 q 1 • Set M := M 1 M 2 • Set x :=      r e 1 e 2 r      ∈ R 8 • Set y :=    u v t 1    ∈ R 4 Q × R q 1 • Set Π := Π OW F (M, y; x) • Output (u, v, Π)
To verify an encryption one simply verifies the proof Π. Verify((u, v, Π), t 1 ) :

• Set M 1 :=     
pa p 0 0 0 0 0 0 pb 1 0 p 0 0 1 0 0 pb 2 0 0 p 0 0 1 0 pb 3 0 0 0 p 0 0 1

     ∈ R 4×8 Q • Set M 2 := 0 1×5 a T 1 ∈ R 1×8 q 1 • Set M := M 1 M 2 • Set y :=    u v t 1    ∈ R 4 Q × R q 1 • Output Verify OW F (Π, M, y)
Chapter 4

4.2 Our Group Signature 55

Decryption is not as simple as standard R-LWE decryption. By completeness we know that honestly generated ciphertexts can be decrypted but soundness should guarantee that as long as the proof verifies one should be able to decrypt. This is not clear since the proof Π does not imply that (u, v) is a valid ciphertext but that there exists some c ∈ C such that (cu, cv) is a valid ciphertext and we do not know which one. In [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF] the authors show that in fact trying random c is a valid approach and will take as many attempts as the number of oracle calls that were needed to generate the proof (in particular only one attempt is necessary if the prover is honest). This will be sufficient for our scheme. Dec((u, v, Π), s) :

• If Verify((u, v, Π), t 1 ) = 1, Let c be the challenge used in Π

• Loop:

• c ← C • c := c -c • r := (v -us)c mod Q • If r ∞ ≤ Q/8B C then: • r := r mod q • return (r, c)
The following lemma shows that if decryption succeeds then the decrypted value (r, c) will essentially be a preimage for the zero-knowledge proof. given (u, v, t 1 ) ∈ R 4 Q × R q 1 there exists rM := (r, ē1 , ē2 , r ∈ R 8 , and c ∈ R such that :

Mr B =    u mod Q v mod Q t 1 mod q 1    and p(ūe + ē2 -ēs) + r ∞ ≤ Q/4B C (4.9)
Then for (r , c ) = Dec(u, v, Π, t 1 ), we have:

r c mod p = r c mod p
Once we have verifiable encryption adding traceability to our group signature is straightforward. During key generation we will create (pk, sk) ← PKESetup(1 λ ), add pk to the group public key and set gmsk = sk. When signing a user will compute an encryption v of his randomness r, which is such that a T 1 r = t 1 mod q 1 , and add v to the signature. For verification one only needs to check the extra proof Π. We consider how to open a signature, this is not completely straightforward because soundness only guarantees that a verifying signature will open to cr for some c ∈ C. Open(msk, z) :

• Parse z as (t, t , Π 1 , Π 2 , Π 3 , v) • Let (r, c) =Dec(msk, t 1 , z) • Set id := c-1 (t 2 -a T 2 r) ∈ R q 2
• If id ∈ Z q 2 then output id, otherwise output ⊥ Note that if decryption succeeds then the proof Π verifies, which entails that there exists r , c such that a T 1 r = c t 1 mod q 1 and by lemma 4.2.3 we know that: r c mod p = r c mod p if we multiply this equation by c and c we have that r c = rc mod p, and since both sides are smaller than p this equation will be true over the integer. From which we get:

a T 1 r = ct 1 mod q 1 which entails that if t = (t 1 , t 2 ) is a well formed commitment the identity returned by the Open algorithm will be its message.

The Full Non-Interactive Proof

We give the full non-interactive zero-knowledge proof that the signer will output. We only consider the parameter choice made in section 4.3. The user i ∈ Z q 2 will use the following elements for his proof:

t := t 1 t 2 = Ar + 0 i ∈ R q 1 × R q 2 t := t 1 t 2 = Ar + 0 iδ ∈ R q 1 × R q 2 v T = a T | b T + t 2 t 2 | a T 2 ∈ R 1×7 q 2 s =    s i 1 s i 2 s i 3 -r r s i 2    ∈ R 7
We first note that since a T 2 = 0 1 a 2 , we can ignore the 5 th coefficient of v T (corresponding to 0) in v T s = u and thus consider v T ∈ R 1×6 q 2 and s ∈ R 6 such that v T s = u. The gain in proof size obtained by discarding one element of this equation may seems negligible at first but it is in fact rather important because the last three coefficients of s will be much larger than the other four. We also recall the matrices needed for the proof of verifiable encryption:

M 1 =      pa p 0 0 0 0 0 0 pb 1 0 p 0 0 1 0 0 pb 2 0 0 p 0 0 1 0 pb 3 0 0 0 p 0 0 1      ∈ R 4×8 Q M 2 = 0 1×5 a T 1 ∈ R 1×8 q 1 M = M 1 M 2
Chapter 4

4.2 Our Group Signature 57

Which are such that :

Mr M =        u mod Q v 1 mod Q v 2 mod Q v 3 mod Q t 1 mod q 1        , for r M =      r e 1 e 2 r     
Rather than just computing all the proofs simultaneously one can optimize the proof. Remark that since the first reply in both Π lin and Πaut is the same z = rc + y, we will only to need to send it once. An important point for proof size will be rejection sampling. After doing rejection sampling Rej(z, a, σ) on a vector z we know by lemma 2.3.6 that all of its coefficients will be statistically close to D σ with σ ≥ 11 a , meaning that for very imbalanced vectors it would be worthwhile to do rejection sampling multiple times. For example if a = (a 1 , a 2 ) with a 2 >> a 1 then by doing two rejection samplings Rej(z 1 , a 1 , σ 1 ) and Rej(z 2 , a 2 , σ 2 ) one obtains a smaller vector z = (z 1 , z 2 ) at the cost of having acceptation probability 1/27, since the proof is non-interactive aborts have a minimal impact and this approach can help reduce the proof size significantly. We will use two rejection samplings for s ∈ R 6 in which the last two coefficients will be much larger than the other four (because they correspond to a product of s i and r, r ). We will thus write s as s = (s 1 , s 2 ) ∈ R 4 × R 2 . We can now write the full zero-knowledge proof of the verifier.

Lemma 4.2.4. Let r, r ← S 3 1 , let s i 1 , s i 2 ← D 2 R,s , let s i 3 ← D 3 R,r , let u, v 1 , v 2 , v 3 ← S 1 . Let t, t , v, s , M, r M be defined as previously. Let σ ≥ 11B C √ 20d, σ 1 ≥ 11B C √ 8ds, σ 2 ≥ 11B C (d √ 24s + √ 2dr) and B ≥ 2 √ 10dσ, B 1 ≥ 2 √ 2dσ 1 , B 2 ≥ 2 √ dσ 2 . If B com ≥ 2B
, then the algorithm Π sign achieves the following properties:

• Correctness: The prover restarts with probability at most 1/27 + 2 -100 , and if he does not abort the verifier accepts with overwhelming probability.

• Honest-Verifier Zero-Knowledge: Signatures can be simulated with statistically indistinguishable distribution.

• Special Soundness: Given two accepting transcripts one can extract

z ∈ R 3 , īd ∈ Z q 2 , z ∈ R 3 , zs ∈ R 7 , zB ∈ R 8 , c ∈ C such that: ct = Com(c īd; z) ct = Com(c īdδ; z ) c        u v 1 v 2 v 3 t 1        = Mz M cu = v T zs such that (z, z , zB ) ≤ 2B ∧ zs 1 ≤ 2B 1 ∧ zs 2 ≤ 2B 2 .
Proof. The proof is simply a combination of the proofs for Theorems 3.2.1 and 3.4.2.

Algorithm 5 Π Sign

Require:

Message M ∈ {0, 1} * . Public information: t, t , v T , B, δ = √ q , ξ -1 , ξ 5 . Private information: r, r , i, s , r B 1: y, y , y -1 , y 5 ← D 3 R,σ 2: y M ← D 8 R,σ 3: y s 1 ← D 4 R,σ 1 4: y s 2 ← D 2 R,σ 2 5: y s = (y s 1 , y s 2 ) 6: w 1 := a T 1 y 7: w 1 := a T 1 y 8: w 1,-1 := a T 1 y -1 9: w 1,5 := a T 1 y 5 10: w 2 := δa T 2 y -a T 2 y 11: w 2,-1 := a T 2 y -ξ -1 (a 2 )y -1 12: w 2,5 := a T 2 y -ξ 5 (a 2 )y 5 13: w s := v T y s 14: w B := By B 15: c := H(t, t , v, B, δ, ξ -1 , ξ 5 , w 1 , w 1 , w 1,-1 , w 1,5 , w 2 , w 2,-1 , w 2,
M := r M c + y M 23: if Rej((z, z , z -1 , z 5 , z M ), (rc, r c, ξ -1 (r)c, ξ 5 (r)c, r M c), σ) = 1∧ Rej(z s 1 , s 1 c, σ 1 ) = 1∧Rej(z s 2 , s 2 c, σ 2 ) = 1 then 24: Output z = (z, z , z -1 , z 5 , z s 1 , z s 2 , z M , c) 25: else 26:
Restart Chapter 4

Fixing the Parameters 59

Algorithm 6 Verify Require:

Message M ∈ {0, 1} * . Signature Π = (z, z , z -1 , z 5 , z s 1 , z s 2 , z M ).Public informa- tion: t, t , v T , M, δ = √ q , ξ -1 , ξ 5 . 1: w 1 := a T 1 z -t 1 c 2: w 1 := a T 1 z -t 1 c 3: w 1,-1 := ξ -1 (a T 1 )z -1 -ξ -1 (t 1 )c 4: w 1,5 := ξ 5 (a T 1 )z 5 -ξ 5 (t 1 )c 5: w 2 := δa T 2 z -a T 2 z -(δt 2 -t 2 ) c 6: w 2,-1 := a T 2 z -ξ -1 (a T 2 )z -1 -(t 2 -ξ -1 (t 2 )) c 7: w 2,5 := a T 2 z -ξ 5 (a T 2 )z 5 -(t 2 -ξ 5 (t 2 )) c 8: w s := v T z s -uc 9: w M := Bz B -(v, v 1 , v 2 , v 3 , t 1 )c ∈ R 4 Q × R q 1 10: if (z, z , z -1 , z 5 , z B ) ≤ B ∧ z s 1 ≤ B 1 ∧ z s 2 ≤ B 2 11: and c = H(t, t , v, M, δ, ξ -1 , ξ 5 , w 1 , w 1 , w 1,-1 , w 1,5 , w 2 , w 2,-1 , w 2,5 , w s , w M ) then 12:
Output 1 13: else 14: Output 0

Fixing the Parameters

We will set the parameters as per Table 4.2. In this section we discuss the bounds that must be verified by these parameters and the resulting security guarantees. We will consider the security of our scheme in terms of "root-hermite factor" δ 0 .

First we fix the dimension to d = 4096, we use this dimension as anything smaller does not allow the existence of parameters that make our scheme secure. For this dimension the challenge set {c ∈ R : c 1 = κ, c ∞ = 1} will be of size greater than 2 256 if we fix

B C = κ = 26.
The standard deviations s and r are fixed by the quality of our trapdoors to s = 6 √ dq 2 and r = 1.17 √ q 2 .

We will need for the hiding property of our commitment that R-LWE is hard for dimension d, errors sampled in S 1 and both modulus q 1 and q 2 . We do not use the reduction of Section 2.4.1 for commitments with multiple moduli as in practice the best attack will be to either solve R-LWE modulo q 1 or modulo q 2 . Since we will have q 2 > q 1 and the hardness of R-LWE decreases as the modulus increases, we will only consider q 2 as being relevant here. The analysis of Section 5.6 shows that for the parameters in table 4.2 we have δ 0 = 1.0036 for R-LWE with modulo q 2 . To fix q 1 we consider the requirements on the binding property of our commitment, from section 4.2 we have that the M-SIS q 1 ,1,3,4B C B problem has to be for vectors of norm

4B C B = 88 • κ 2 • √ 200d, for q 1 ≈ 2 30
, as in table 4.2, we obtain δ 0 = 1.0036. To fix q 2 we will need the M-SIS q 2 ,1,4,B S for B S as per lemma 4.4.3 to be hard. We can compute that

B S = z -s * ≈ 180224 • √ 2 • d 2 • √ q 2 for
q 2 ≈ 2 80 as in table 4.2 the roothermite factor of this problem will be δ 0 = 1.0036.

The only constraint we have on p the plaintext modulus of our verifiable encryption scheme is that if rc = rc mod p for some r, c, r, c extracted in Π Sign then this equation should hold over the integers, i.e. zczc ∞ ≤ p/2. Since the vector z output in Π Sign will have coefficients distributed according to D σ , we will have with overwhelming probability that z ∞ ≤ 12σ (we can add this as an explicit check in the verification algorithm), in which case we will require p ≥ 4 • κ • 12σ ≥ 2 26. 5 . The ciphertext modulus Q will be fixed by equation 4.9 which gives:

Q ≥ 264 √ 34κpd 3/2 ≥ 2 59.5
All the parameters were set to achieve the same root Hermite factor of 1.0036 which corresponds to a block size of β = 450. Resulting in a security of 93 bits in space, 131 bits in time, and 119 bits in time for post-quantum security.

We consider the proof size that results from this parameter choice. The secret key will consist in 4 polynomials of standard deviation s and two polynomials of standard deviation r resulting in a size of 4d log(12s) + 2d log(12r) = 154KB. The signature itself will consist of two commitments, one ciphertext and one zero-knowledge proof, which are respectively of size:

2d log q 1 + 2d log q 2 = 113KB 4d log Q = 123KB
13d log(12σ) + 4d log(12σ 1 ) + 2d log(12σ 2 ) = 345KB

Accounting For Complexity Leveraging

The proof for full-traceability of Section 4.4 reduces the security of our group signature to that of a selectively secure signature by guessing the identity of the forgery, we thus lose a factor of q 2 in the reduction. If we want to account for this security loss when setting the parameters we will need to target a security of 128 + log q 2 bits for the M-SIS q 2 ,1,3,B S problem. The dimension d = 4096 is no longer enough to reach such a security and we will thus be forced to set d = 8192. For this dimension the M-SIS q 2 ,1,3,B S has a root hermite factor of δ 0 = 1.002, corresponding to a block size β = 1000 and thus a a security of 207 bits in space, 292 bits in time, and 262 bits in time for post-quantum security. This is enough to tolerate a loss of log q 2 = 80 bits of security. The R-LWE problem in dimension d = 8192 has a block size of more than β = 1200 resulting in more than 300 bits of security, similarly the M-SIS q 1 ,1,3,4B C B becomes harder with a higher dimension and q 1 can be reduced accordingly.

The rest of the parameters will be changed to the values given in Table 4.2, resulting in a signature size of (c.f. Table 4.1).

Security of the Scheme

Lemma 4.4.1 (Anonymity). Let A be a PPT adversary. Let Adv Hid A (λ) be the advantage of A over the Hiding property of the commitment scheme. Let Adv ind-cpa A (λ) be the advantage of A over the IND-CPA property of the encryption scheme. The advantage of A against the CPA-anonymity of our group signature is at most:

Adv anon A (λ) ≤ 2Adv Hid A (λ) + Adv ind-cpa A (λ) + 2 -λ
Proof. We use a succession of games. Game G 0 : In this game the challenger runs GSetup honestly and gives (gpk, sk 1 , . . . , sk N ) to A. A outputs a message M * and two identities i 0 , i 1 ∈ [N ]. The challenger chooses a bit b $ ← {0, 1} and computes z * := (t, t , e, π) ← Sign(M * , sk i b ) Game G 1 : In this the challenger uses the simulator of the proof Π Sign when queried for Sign(M * , sk i b ). This game is statistically indistinguishable from the previous by the zero-knowledge of Π Sign .

Adv G 1 A -Adv G 0 A ≤ 2 -λ Game G 2 :
In this the challenger replaces the commitment t by a commitment of 0 when answering the query Sign(M * , sk i b ). The proof Π Sign can still be used since it uses the simulator, and this game is indistinguishable from the previous one by the hiding property of the commitment.

Adv G 2 A -Adv G 1 A ≤ Adv Hid A (λ) Game G 3 :
In this the challenger replaces the commitment t by a commitment of 0 when answering the query Sign(M * , sk i b ). This game is indistinguishable from the previous one by the hiding property of the commitment.

Adv G 3 A -Adv G 2 A ≤ Adv Hid A (λ)
Game G 4 : In this the challenger replaces the commitment ciphertext e with an encryption of 0. Since the proof Π Sign uses the simulator it is independent of the decryption of e. This game is indistinguishable from the previous one by the IND-CPA property of the encryption scheme.

Adv G 4 A -Adv G 3 A ≤ Adv ind-cpa A (λ)
The signature (t, t , e, π) output in Game G 3 is independent of i b and the adversary has thus probability 1/2 of outputting b = b. We obtain the desired result by summing the advantages.

We will prove traceability in two steps. We will first prove that an adversary A cannot distinguish between the regular traceability game and the traceability game in which the setup algorithm has been replaced by GSetup * which we define below. We will then prove that a challenger B can extract an M-SIS solution from an adversary who succeeds in producing a forgery in the traceability game with GSetup * . GSetup * (1 λ ):

• Sample i * $ ← Z q 2 • Sample A := a T 1 a T 2 ← CSetup(1 λ ), with a 1 ∈ R 3 q 1 , and a 2 ∈ R 3 q 2 . • Sample a $ ← R 2 q 2 . • Sample R $ ← S 2×2 1 and set b T = a T R ∈ R 1×2 q 2 . • Sample (s i * 1 , s i * 2 , s i * 3 ) ← D R,s × D R,s × D R,r • Set u := a T | b T | a T 2    s i * 1 s i * 2 s i * 3    Game G 5 : B sets a T 2 as [0 | 1 | a 2 ]
, with a 2 $ ← R q 2 and uses the GPV trapdoor of a T | b T + (ii * )g T to sample secret keys for user i. This game is indistinguishable from the previous one under the NTRU q,r assumption.

Adv G 5 A -Adv G 4 A ≤ Adv N T RU A
Note that Game G 5 is exactly the traceability game that uses GSetup * (simply by renaming s 0 to s i * ), the result follows.

Lemma 4.4.3. Let A be a PPT algorithm with advantage ε in the traceability game with GSetup * . Let h be a bound on the number of hash queries made by A.

Let B S ≥ 4B C B 1 + 12B C √ dB 1 + 2B C B 2 + 6 √ dσB 1 + B 2 C (1 + 3 √ d)2 √ ds + B 2 C √ 6ds.
There exists B a challenger for the M-SIS q,1,4,B S such that:

Adv M SIS B (λ) ≥ ε q 2 ε h -2 -λ
Proof. Formally B is given a matrix x T := x 1 , x 2 , x 3 , x 4 ∈ R 4 q 2 and must output y s.t x T y = 0 mod q 2 and y ≤ B S , w.l.o.g we consider x = x 1 , x 2 , x 3 , 1 instead since with high probability one of the x i will have an inverse.

B will set a := (x 1 , x 2 ) and a T 2 := (0, 1, x 3 ) during setup, since x 1 , x 2 , x 3 are uniform in R q 2 this does not change the distribution of GSetup * . When asked signing queries, B runs the signing algorithm honestly, when asked corrupt queries B outputs the corresponding secret key. Suppose the adversary A outputs a forgery z := (t, t , Π, (u, v)) by programming the random oracle with two different challenges B will be able to extract

z ∈ R 3 , īd ∈ Z q 2 , z ∈ R 3 , zs ∈ R 7 , zB ∈ R 8 , c ∈ C such that: ct = Com(c īd; z) ct = Com(c īdδ; z ) c    u v t 1    = Bz B cu = v T zs such that (z, z , zB ) ≤ 2B ∧ z1 , z2 ≤ 2B 1 ∧ z3 ≤ 2B 2 , with (z 1 , z2 , z3 ) := z.
Using the forking lemma of [BN06], B will be able to do this with probability at least ε ε h -2 -λ . Let (r, c) :=Dec(u, v), the parameters set in section 4.3 are such that, by soundness of the verifiable encryption scheme, with overwhelming probability rc = zc over the integers, which implies that Open(z) ∈ Z q 2 i.e. the forgery opens to an identity in Z q 2 and not ⊥. Since i * is taken uniformly at random in GSetup * , z will open to this identity with probability 1/q 2 . Suppose that z opens to i * . Then

ct 2 = a T 2 z + ci * ct 2 = a T 2 z + ci * δ a T | b T + [t 2 | t 2 ] -i * g T | a T 2 zs = cu
If we multiply the third equation by c and replace c[t 2 | t 2 ] we get:

ca T | cb T + [a T 2 z | a T 2 z ] | cā T 2 zs = c2 u Let z = cz 1 + Rcz 2 cz 3 -z z z2
Then a T | āT 2 z = c2 u Since A has to output a valid forgery this means that he has never obtained the key sk i * , we can thus consider that s i * was sampled after receiving the forgery, conditioned on

a T | b | a T 2 s i * = u. Let s * := s i * 1 + Rs i * 2 | s i * 3
, the probability that cs * = z is negligible. Finally we have a solution zcs * to the M-SIS problem defined by a T | a T 2 . Using the bounds on the extracted values and the distribution of s * we have the following bound on the norm of the solution:

z -cs * ≤ z + 2B C s * ≤ 2B C z 1 + 6B C √ d z2 + B C z3 + 3 √ dσ z2 + B 2 C (1 + 3 √ d)(2 √ ds) + B 2 C √ 6ds ≤ 4B C B 1 + 12B C √ dB 1 + 2B C B 2 + 6 √ dσB 1 + B 2 C (1 + 3 √ d)2 √ ds + B 2 C √ 6ds
The largest terms in this solution are by far 2B C B 2 and 6 √ dσB 1 which we will consider when setting the parameters in section 4.3.

Introduction

Given how information technology has penetrated almost every aspect of our world, one could be surprised at the primitive state of technology used in the process that most influences society: elections. Electronic voting machines, which required voters to physically turn up at polling stations to cast their ballots on dedicated machines, saw a brief rise in popularity until the early 2000s, but many countries have since then gone back to paper-and-pencil voting amidst worries about security and reliability.

These are definitely genuine concerns. Researchers discovered serious security flaws in several models of voting machines that were used in elections in the US, the Netherlands, and Germany [FHF07; GH07]. Recent news reports on massive security breaches and suspicions of foreign meddling in national elections have only aggravated those concerns.

Nevertheless, many countries are warming up to the idea of online voting, in which voters cast their ballots using their personal devices from the comfort of their couch. A handful of countries, including Estonia, Switzerland, and Australia, are already using online voting for local and national elections, and it is quite a common tool among private organizations to elect officers and board members.

There are of course many aspects to securing an online voting system, but the underlying cryptographic protocol is obviously an important ingredient. All of the currently deployed electronic voting systems (e.g., Helios [START_REF] Adida | Helios: Web-based Open-Audit Voting[END_REF], the Swiss voting system [START_REF]Swiss Online Voting Protocol[END_REF], and the Estonian one) are based on cryptographic primitives that rely on the hardness of factoring or discrete logarithms for their security. Both of these assumptions are well-known to succumb to attacks by quantum computers, meaning that, as soon as sufficiently powerful quantum computers become available, an adversary could use them to break the vote secrecy of a past election, or to tamper with the result of an ongoing one. The threat of foreign meddling in elections gives additional reason for concern: powerful nation states may very well be the first to build quantum computers, and they may not be particularly vocal about their achievement.

Fortunately, we do have some cryptographic problems that resist attacks by quantum computers. Lattices are the most prominent one, offering a good trade-off between efficiency and security for basic primitives such as signatures and encryption. For more advanced protocols, such as those required for electronic voting, lattices tend to, however, suffer from extremely high bandwidth requirements.

The main difficulty in constructing practical lattice-based privacy schemes is the lack of efficient zero-knowledge proofs, which is an important tool in electronic voting schemes to let voters prove that they cast a valid ballot. Most lattice-based zero-knowledge proofs are either Fiat-Shamir proofs with single-bit challenges or Stern-type proofs [START_REF] Stern | A New Identification Scheme Based on Syndrome Decoding[END_REF] with soundness error 2/3, which have to be repeated many times to reduce the soundness error. Amortization techniques [BDLN16; CDXY17; PL17] exist when performing thousands of proofs in parallel, but these are not very useful when each voter must prove correctness of his own vote. Lyubashevsky's "Fiat-Shamir with Aborts" technique [START_REF] Lyubashevsky | Lattice Signatures without Trapdoors[END_REF] yields much more efficient proofs with large challenges, but only allows to prove correctness of the statement up to a small multiple of the witnesses, which could be quite detrimental in the context of voting, as it may allow an attacker to inflate the weight of this vote.

The only quantum-safe voting protocol that we are aware of [START_REF] Chillotti | A Homomorphic LWE Based E-voting Scheme[END_REF] therefore shuns zero-knowledge proofs completely and uses fully-homomorphic encryption [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] instead. The paper doesn't give any implementation details or concrete parameter choices, so it's

Introduction 67

Voter Auth/Voter Total Size / Voter Time 10ms 3ms Size 28KB 2KB 30KB Table 5.1: Time and space complexity of the voting scheme with 4 authorities. Using the parameters of Section 5.5, each voter ouputs one OR-Proof and four commitments (one per authority), while each authority outputs one proof per voter. hard to make statements about efficiency, but due to the "heavy machinery" being utilized, chances are that the protocol is not efficient enough for medium to large-scale elections.

Our Contributions

We present a new lattice-based electronic voting scheme that does use zero-knowledge proofs, but overcomes their inefficiencies by re-organizing the proofs so that the voting authorities assist the voters by performing amortized proofs. Our protocol provably guarantees vote privacy as long as one of a number of voting authorities is honest, and guarantees consistency (i.e., that honest votes are correctly counted) even if all voting authorities are corrupt, all under standard lattice-based assumptions in the random-oracle model. We suggest concrete choices for the security parameters and implement a prototype of our protocol. Our experimental results (Table 5.1) show that voters need less than 10ms to cast a vote and a complete bulletin (including all commitments and votes) is of size 30KB, which we think is well within practical bounds for a large-scale election. To better understand the technical hurdles to obtain this result, we briefly sketch a voting protocol by Cramer et al. [START_REF] Cramer | Multi-Autority Secret-Ballot Elections with Linear Work[END_REF] on which our protocol is based. Let's say there are N V voters and N A voting authorities that assist in a binary election, i.e., where each voter votes zero or one and the result is the sum of the votes. Let's also say that there is a public bulletin board where voters can post their ballots. The authorities jointly compute the tally and post the result of the election, together with a proof of correctness. The goal is to obtain vote privacy, meaning that as long as one authority is honest, the adversary does not learn anything more about the votes of honest voters than what is already implied by the result, as well as consistency and universal verifiability, meaning that anyone can check that all honest votes were counted correctly, even if all authorities collude to rig the election.

The protocol of Cramer et al. [START_REF] Cramer | Multi-Autority Secret-Ballot Elections with Linear Work[END_REF] begins by letting each voter secret-share his vote among the N A authorities and commit to each of the shares. The voter sends the share and the opening information to each authority, and performs an OR-proof [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF] to show that he secret-shared a zero-or-one vote by exploiting a homomorphism in the commitment scheme. When the voting phase closes, all servers check the openings of the commitments they received. Each authority then publishes the sum of all the shares it received together with valid opening information, again using the homomorphism in the commitments. The result of the election is the sum of all these partial sums.

There are a number of hurdles to overcome when translating this approach into lattice-based primitives. The first is that, as discussed above, lattice-based zero-knowledge proofs are either inefficient or approximate, while amortization doesn't help for proofs by individual voters. The second is that commitments typically use short vectors as randomness (i.e., opening information), but applying homomorphisms accumulates the size of this randomness, which must be compensated for by choosing larger parameters, which comes at a big cost in efficiency. The third problem is that the typical OR-proof technique [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF] of XOR-ing challenge values doesn't work for lattices, because challenges are polynomials with small coefficients in a ring, but do not form a group among them.

We address the first problem by strategically splitting up the burden of the proofs between voters and authorities. Namely, we let voters prove that they secret-shared a zero-or-one vote using approximate proofs, but we let the authorities prove that the commitment they received is well-formed, i.e., has short opening information. The authorities do so for all voters simultaneously, so they can use the more efficient amortized proofs which we designed in Section 3.5.

The second problem we address by letting authorities re-commit to the sum of batches of votes, and by letting them prove in zero knowledge that the new commitment indeed contains the sum of all votes in the batch. By repetitively applying this technique, each authority can keep the randomness growth within bounds, so that it eventually ends up with a commitment to the sum of all received shares with short randomness.

Finally, we solve the problem with the OR proofs by interpreting the challenge space of our zero-knowledge proofs as a group, using the techniques described in Section 3.3.

The proofs outlined above are constructed using quantum-secure building blocks via the Fiat-Shamir transform. While there is a known classical reduction from hard lattice problems to schemes constructed in this manner, there is no quantum reduction known. The underlying reason as to why a general proof is unlikely to come is due to the fact that classically-secure computationally binding commitments are not known to be binding for a quantum committer (c.f. [START_REF] Damgård | Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks[END_REF]). Nevertheless, there are known quantum security proofs in the QROM for Fiat-Shamir schemes of the same form as ours, but in which the parameters are set differently [START_REF] Unruh | Post-quantum Security of Fiat-Shamir[END_REF]. Furthermore, there are currently no known natural counter-examples of Fiat-Shamir zero-knowledge proofs (nor of commitment schemes) which are based on quantum-hard problems via classical reductions, but are broken by quantum adversaries. It therefore seems reasonable to assume that such Fiat-Shamir schemes are secure. If one would like to have a reduction that is in the QROM, one could instantiate the schemes as in [START_REF] Abdalla | Tightly-Secure Signatures from Lossy Identification Schemes[END_REF] and then use the reduction in [START_REF] Unruh | Post-quantum Security of Fiat-Shamir[END_REF]. This would, however, lead to a noticeable increase in the size of the proofs and public keys.

Overview of the Construction

We will make the convention that the voters (and information pertaining to the voters) are numbered 1 through N V using a subscript, whereas the information pertaining to the authorities is numbered 1 through N A and is labeled using a parenthesized superscript. In particular, for elements x (j) i , we will define

x i = N A j=1 x (j) i , x (j) = N V i=1 x (j) i , and x = N V i=1 N A j=1 x (j) i = N A j=1 N V i=1 x (j) i .
We consider an election for N C candidates in which votes will be vectors in {0, 1} N C and the tally will be the sum of all votes. Since voters will commit to values in R q , we assume there exists a ring R and an isomorphism φ : R q → R N C , and we define the set of valid votes as

v ∈ R q : φ(v) ∈ {0, 1} N C . A voter i who wishes to cast a vote v i (which is such that φ(v i ) ∈ {0, 1} N C ), first splits v i 5.1 Introduction 69 into N A parts v (j) i
where the first N A -1 of them are chosen uniformly in R q and the last share v

(N A ) i is chosen such that N A j=1 v (j) i = v i mod q.
The voter i then uses the commitment scheme to commit to each share v

(j) i as t (j) i := Com(v (j) i ; r (j) i ).
(5.1)

All the commitments are published to the bulletin board. Note that because the commitment scheme is additively homomorphic, we have

N A j=1 t (j) i = t i = Com(v i ; r i ),
which is a valid commitment to v i (but with slightly larger randomness r i ). Voter i now creates a zero-knowledge OR-proof that he has knowledge of a vector ri with small coefficients and a ring element ci with very small coefficients such that

ci t i = Com(v i ci , ri ), and φ(v i ) ∈ {0, 1} N C . ( 5.2)
This proof π V i also gets posted to the bulletin board. Each voter now sends to authority j the encryption (under authority j's public key) of the share v (j) i and the randomness under which this share was committed r (j) i from Equation (5.1) (one can alternatively think that the voters simply post this encryption to the bulletin board). Upon receiving all such encryptions from every voter, authority j needs to create a proof of knowledge that the r (j) i all have small coefficients. He uses the Amortized Exact Zero-Knowledge proof to create proofs π A i,j that prove the knowledge of r(

i that satisfy t

(j) i = Com(v (j) i ; r(j) i ). (5.3)
If all N A authorities provide proofs of the above statement, then using the additive homomorphism of the commitment scheme, we obtain a proof of knowledge of an ri such that

t i = N A j=1 t (j) i = N A j=1 Com(v (j) i , r(j) i ) = Com(v i , ri ). (5.4)
Combining this with Equation (5.2) gives two valid openings of the commitment t i . Based on the binding property of Com, this implies that ri = ci ri . One can then rewrite Equation (5.2) as ci

t i = Com( ci v i , ci ri ),
and since we choose the challenge set such that ci is invertible in R q , we can divide by ci to finally obtain

t i = Com(v i , ri ), , and φ(v i ) ∈ {0, 1} N C . ( 5.5)
Because there is no longer the factor ci which could be distinct for every voter, the commitment in Equation (5.5) is additively homomorphic. In particular, if we compute

N V i=1 t i = Com( N V i=1 v i ; r), and φ(v i ) ∈ {0, 1} N C , ( 5.6)
and r is a vector with small coefficients, then the quantity

N V i=1 t i
is a commitment to the sum of the votes that have been cast. If there are many voters, then r = i ri is not small, but we show how to handle this issue later.

For universal verifiability, we therefore would like the value of r to be publicly computable.

For this to happen, each authority simply computes

N V i=1 r (j)
i = r (j) and reveals it by publishing it to the bulletin board. Any verifier can simply check that r (j) is a valid opening of t (j) , i.e. that there exists some message m (j) such that t (j) = Com(m (j) , r (j) ).

(5.7)

We now claim that it must be that

r = N A j=1 r (j) = r.
From Equation (5.3), we know that

t (j) = N V i=1 Com(v (j) i ; r(j
) i ) = Com(v (j) ; r(j) )
Combining this with Equation (5.7) gives two openings of t (j) . Which implies that r(j) = r (j) , and then we have r =

N A j=1 r(j) = N A j=1 r (j) = r.
Plugging the above into Equation (5.6) implies that

t = N V i=1 t i = Com( N V i=1 v i ; r), and φ(v i ) ∈ {0, 1} N C . ( 5.8)
If r is small enough, then the above implies that t is a commitment to the full vote tally

N V i=1
v i , and one can obtain this tally by computing Open(t, r, 1). As long as there are fewer than q voters, we can exactly recover φ(

N V i=1 v i
) over the integers.

Reducing the Randomness

An issue that we still need to deal with is how to make sure that the randomness, when summed over all the voters, does not grow too much. This is crucial in order for the final commitment in Equation (5.6) to be meaningful. A trivial way to accomplish this is to simply set the parameters large enough so that a large set of voters can be accommodated. This is an extremely impractical solution that we would like to avoid.

Our E-Voting Scheme 71

The way that we can overcome this issue is by making the Authorities create votes of partial sums of the vote shares they have, using randomness that is close to the randomnesses used by the individual voters. For example, if voters 1, . . . , l whose commitments to Authority j are t

(j) 1 , . . . , t (j) l of values v (j) 1 , . . . , v (j) l , under randomnesses r (j) 1 , . . . , r (j)
l , then the Authority can create a commitment t of l i=1 v (j) i using a fresh randomness r. The Authority would then publish the "vote" t, proves that there exists some r , m such that t = Com(m , r ), (

and also prove that there exists a slightly larger r such that

t + i t (j) i = Com(0; r) (5.10)
The proof in Equation (5.9) can be "amortized-in" with the proofs π A i,j because the size of the randomness is the same. The proof of Equation (5.10), however, contains larger randomness, and so such proofs should be amortized only among themselves. 1Notice that because the randomness of commitment t = Com( l i=1 v (j) i , r) is as small as in one voter commitment, we have effectively reduced the size of the sum of the randomness in l voter commitments to that of one commitment. If we do this for every block of l voters, then we effectively reduced the sum of the randomness by a factor of l.

It is easy to see that this procedure is repeatable. Once every l blocks of votes have small randomness, we can consider repeating this procedure by summing over l such blocks. This will effectively reduce the total sum of the randomnesses by another factor of l. If we continue this procedure, then we will be effectively adding 2(N V /l + N V /l 2 + . . .) ≈ 2N V /(l -1) extra proofs. The advantage will be that we now only need to worry about the randomness growing by a factor l for the proof in Equation (5.10). We set our parameters so that l = 30.

One can also think of the above procedure as the authority summing up 30 votes, recommitting to the sum using fresh, small randomness, and then giving a proof that he correctly recommitted to the sum of the votes. In particular, proving that the difference between his new commitment and the sum of the 30 commitments is a commitment to 0.

Our E-Voting Scheme

Building Blocks

The Commitment Scheme

We will use the commitment scheme of Section 2.4.1 for messages in R q . We briefly recall the CSetup, Com and Open algorithms.

• CSetup(1 λ ) outputs a commitment matrix A ∈ R (n+1)×(2n+1) q .

• Com(m ∈ R q ) outputs the commitment t := Ar + 0 n m , and randomness r ← D 2n+1 R,σ .

• Open(t, r, c) checks that the commitment is valid and outputs m := t 2c -1 A 2 r ∈ R q .

We have fixed the dimensions of A to n×(2n+1) which implies that the hiding property of our commitment relies on M-LWE q,n,σ and the binding property relies on M-SIS q,2n+1,4B C ,B Com we discuss how to fix q, σ, B C , B Com in Section 5.5.

Embedding votes as polynomials. We will consider elections for multiple candidates in which voters output a {0, 1} vote for each candidate, i.e. if N C is the number of candidates, a vote will be of the form (b 1 , . . . , b N C ) with b i ∈ {0, 1}. As the voters will commit to their vote we will have to embed such vectors as elements of R q (we could consider commitments with message space R N C q but that would be very inefficient). Additionally each voter will have to output a proof that his vote is well formed, that is to say that each of the b i is either 0 or 1, we will need an embedding that allows such proofs to go through. To do so we will consider the splitting properties of X d + 1 given in Lemma 2.2.3. Suppose there are N C ≤ d candidates with N C a power of two. We can choose a modulus q such that X d + 1 splits into exactly N C irreducible factors modulo q, let f 1 , . . . , f N C be these factors. By the Chinese remainder theorem we know that:

Z [X] /X d + 1 Z [X] /f 1 (X) × . . . × Z [X] /f N C (X)
with the isomorphism:

φ : Z [X] /X d + 1 → Z [X] /f 1 (X) × . . . × Z [X] /f N C (X) h → (h mod f 1 , . . . , h mod f N C )
Using the extended Euclidean algorithm one can efficiently obtain polynomials g 1 , . . . , g N C such that φ(g i ) = (0, . . . , 0, 1, 0, . . . , 0) with the 1 in the i th coordinate. To embed a vector (b 1 , . . . , b N C ) ∈ {0, 1} N C in R q a voter will compute the polynomial m := b i g i , by linearity of φ this polynomial is such that φ(m) = (b 1 , . . . , b N C ).

Proof of Correct Vote

We now consider how to prove that a commitment commits to a message m ∈ R q such that φ(m) ∈ {0, 1} N C . Let φ(m) = (m 1 , . . . , m N C ) we want to prove that ∀i ∈ [N C ] , m i ∈ {0, 1}. We will construct a proof that for a fixed i ∈ [N C ] , m i ∈ {0, 1}, running this proof N C times will give the desired proof of knowledge. Fix i ∈ [N C ], observe that m i = 1 ⇔ φ(mg i ) = (0, . . . , 0, 1, 0, . . . , 0) = φ(g i ) ⇔ mg i = g i and similarly m i = 0 ⇔ mg i = 0, which is to say:

m i ∈ {0, 1} ⇔ mg i ∈ {0, g i }
Let t := Com(m; r), we will use OR-Proof of section 3.3 to prove that either mg i = 0 or

mg i = g i . Let A i := A 1 g i A 2 and t i = t 1 g i t 2
, we have that

A i r = t i ⇔ mg i = 0 A i r = t i - 0 n g i ⇔ mg i = g i 5.
3 Building Blocks 73

Which implies that Π OR (A i , t i , t i -0 n g i ; r) is a Σ -Protocol from which we can extract z ∈ R 2n+1 , c ∈ C, m i ∈ R q such that z ≤ 2B OR , ct = Com(cm i ; z), and mg i ∈ {0, g i }.

Finally by simultaneously running this proof for all A i and t i we obtain a proof that φ(m) ∈ {0, 1} N C . We formally present the proof computed by the voter in Algorithm 7 and its verification algorithm in Algorithm 8. If σ V ≥ 11B C B V and B V ≥ 2d(2n + 1)σ V , then this proof of knowledge is a Σ -Protocol for the following languages:

R V ote = (t, r, 1) ∈ R n+1 q ×R 2n+1 ×R | ∃v ∈ R q , t = Com(v; r), r ≤ 2B V , φ(v) ∈ {0, 1} N C R V ote = (t, r, c) ∈ R n+1 q ×R 2n+1 ×R | ∃v ∈ R q , ct = Com(cv; r), r ≤ 2B V , φ(v) ∈ {0, 1} N C Algorithm 7 Π V ote Require: Public information: A, t. Private information: r ∈ R, v ∈ R q , s.t t = Com(v; r) and (v 1 , . . . , v N C := φ(v) ∈ {0, 1} N C 1: A 1 A 2 := A; t 1 t 2 := t 2: for i ∈ [N C ] do 3: A i := A 1 g i A 2 ; t i := t 1 g i t 2 4: c i,1-v i $ ← C 5: z i,1-v i ← D 2n+1 R,σ V 6: w i,1-v i := A i z i,1-v i -c i,1-v i t i + c i,1-v i 0 n (1 -v i )g i 7: y i,v i ← D 2n+1 R,σ V 8:
w i,v i := A i y i,v i 9: c := H(A, t, w 1,0 , . . . , w N C ,0 , w 1,1 , . . . , w N C ,1 ) 10: for i ∈ [N C ] do 11:

c i,v i := c c i,1-v i 12: z i,v i := rc i,v i + y i,v i 13: if Rej(z i,v i , rc i,v i , σ V ) = 0 then 14: Restart 15: return (c i,0 , c i,1 , z i,0 , z i,1 ) i∈[N C ]

Amortized Exact Zero-Knowledge Proofs

The authorities A j will use amortized zero knowledge proofs for two purpose. The first will be to prove that the shares of the commitment they receive from each voter are correctly formed. Let A = A 1 A 2 be the commitment matrix, say A j has the commitments t 1 , .

A i := A 1 g i A 2 ; t i := t 1 g i t 2 5:
w i,0 := A i z i,0c i,0 t i 6:

w i,1 := A i z i,1 -c i,1 t i + c i,1 0 n g i 7: c := H(A, t, w 1,0 , . . . , w N C ,0 , w 1,1 , . . . , w N C ,1 ) 8: for i ∈ [N C ] do 9: if c = c i,0 ⊕ c i,1 ∨ z i,0 > B V ∨ z i,1 > B V then 10:
V ← 0 11: return V formed. The second proof of knowledge will be used during bucketing (c.f. Section 5.4.3) to prove that differences of commitments commit to zero. Say A j has the commitments t 1 , . . . , t which commit to 0 with opening r 1 , . . . , r . Let T := t 1 | . . . | t , and R := r 1 | . . . | r , then the protocol Π Amo2 (A, T; R) is a proof that each commitment is well formed and commits to 0.

We formally present the proof computed by the authorities in Algorithms 9 and 10, and their verification algorithms in Algorithms 11 and 12. If k ≥ (λ + 2)/ log(2d + 1), σ A1 ≥ 11B A1 √ lk and B A1 ≥ 2d(2n + 1)σ A1 , then the protocol Π Auth,1 is a Σ -Protocol for the following languages:

R Auth,1 =    (t 1 , . . . , t , r 1 , . . . , r l ) ∈ R (n+1)× q × R (2n+1)× s.t. ∃(v 1 , . . . , v ) ∈ R q ; ∀i ∈ [ ] , t i = Com(v i , r i ), s 1 r 1 | . . . | r ≤ B A1    R Auth,1 = (t 1 , . . . , t , r 1 , . . . , r l ) ∈ R (n+1)× q × R (2n+1)× s.t. ∃(v 1 , . . . , v ) ∈ R q ; ∀i ∈ [ ] , t i = Com(v i , r i ), r i ≤ 2B A1 If k ≥ (λ+2)/ log(2d+1), σ A2 ≥ 11B A2
√ lk and B A2 ≥ 2d(2n + 1)σ A2 , then the protocol Π Auth,2 is a Σ -Protocol for the following languages:

R Auth,2 =    (t 1 , . . . , t , r 1 , . . . , r l ) ∈ R (n+1)× q × R (2n+1)× s.t. ∀i ∈ [ ] , t i = Com(0, r i ), s 1 r 1 | . . . | r ≤ B A2    R Auth,2 = (t 1 , . . . , t , r 1 , . . . , r l ) ∈ R (n+1)× q × R (2n+1)× s.t. ∀i ∈ [ ] , t i = Com(0, r i ), r i ≤ 2B A2
A 1 A 2 := A 2: for i ∈ [N C ] do 3: t i,1 t i,2 := t i 4: T 1 := t 1,1 | . . . | t ,1 5: W := AZ -T 1 C 6: if C = H(A 1 , T 1 , W) ∨ Z max > B A1 then 7:
return 0 8: return 1

Our E-Voting Scheme

Definitions

We base our syntax and security definitions of one-pass electronic voting schemes on that of Bernhard et al. [START_REF] Bernhard | SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions[END_REF], but there are some differences. First, we explicitly model a multi-authority setting where each authority independently generates its own keys. Second, ballot testing in our scheme must be performed by the authorities, who use their secret key in the process. Verification of the entire election can still be done publicly, though. As ballot testing, tallying, and verification do not require interaction with the voters, the authorities do not need to be online for the first part of the election and only need to run the ballot testing and tallying algorithms once all the ballots have been cast. A multi-authority electronic voting scheme EV is a tuple (Setup, ASetup, Vote, TestB, Tally, Verify) of algorithms and protocols that are used by authorities A 1 , . . . , A N A and voters with identities id ∈ I as follows. We consider binary elections for N C candidates where each voter id ∈ I casts a vote v id ∈ {0, 1} N C and the result of the election is r = id∈I v id . We assume that all voters and authorities have read access and authenticated append-only write access to a public bulletin board BB, meaning that entries can only be appended to the board and entries are authenticated (e.g., signed) under the writer's identity. Moreover, each voter can only write once to the bulletin board; authorities can write as often as they want.

• Setup(1 λ ) generates trusted common parameters par.

• ASetup(par) is used by authority A j to generate a public key pk j and corresponding secret key sk j .

• Vote(par, pk 1 , . . . , pk N A , id, v) is used by voter id ∈ I to cast his vote v ∈ {0, 1} N C . It returns a ballot b that the voter posts on the bulletin board BB.

• TestB(par, pk 1 , . . . , pk N A , sk j , b) allows authority A j to test whether ballot b is valid or not by returning 1 or 0, respectively. The ballot is only considered valid after all N A authorities confirm its validity on the bulletin board BB. This check can be performed as the votes come in, or only after the voting phase has ended. The tallying authorities therefore do not have to be online during the voting phase: rather than interacting 5.4 Our E-Voting Scheme 77 directly with the voters, the tallying authorities can obtain the ballots from the bulletin board after voting has ended and discard invalid ballots if needed.

• Tally(par, pk 1 , . . . , pk N A , BB, sk j ) is an interactive protocol run among the authorities A j , j = 1, . . . , N A , at the end of which they announce the tally r and proof Π.

• Verify(par, pk 1 , . . . , pk N A , BB, r, Π) can be run by anyone to check the correctness of the election result.

Correctness. Correctness guarantees that, when all parties behave honestly, all ballots are deemed valid and the result of the election is correct. Let id 1 , . . . , id N V ∈ I be voter identities and v 1 , . . . , v N V be their respective votes. Let par $ ← Setup(1 λ ); and (pk j , sk j ) $ ← ASetup(par) for j = 1, . . . , N A . For i = 1, . . . , N V and j = 1, . . . , N A let

b i $ ← Vote(par, pk 1 , . . . , pk N A , id i , v i ), BB[i] ← b i ,
and let (r, Π) be the outcome of the protocol when each authority A j runs Tally(par, pk 1 , . . . , pk N A , BB, sk j ), j = 1, . . . , N A . The scheme is correct if for all i = 1, . . . , N V and j = 1, . . . , N A , the following conditions hold with overwhelming probability: r = N V i=1 v i , TestB(par, pk 1 , . . . , pk N A , sk j , b i ) = 1, and Verify(par, pk 1 , . . . , pk N A , BB, r, Π) = 1.

Privacy. Privacy requires that an adversary who corrupts N A -1 authorities and an than what is revealed by the election result. The single-authority BPRIV notion of Bernhard et al. [START_REF] Bernhard | SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions[END_REF] defines this by requiring that the adversary cannot tell a bulletin board for a first set of votes with the real election result and proof from a bulletin board for a second set of votes with the same result and a simulated proof. The BPRIV notion is not easily adapted to the multi-authority setting, because the corrupt authorities would have to be involved in computing the tally for both bulletin boards. We therefore adapt the notion to require that the adversary cannot distinguish between the bulletin boards of two different sets of votes, as long as both sets of votes yield the same election result. The advantage of an adversary A in breaking the privacy of the electronic voting scheme EV is defined through the experiment of Figure 5.1 as

Exp priv,b A (λ): par ← Setup(1 λ ) ; pk 1 ← ASetup(par) ; HV := ∅ (pk 2 , . . . , pk N A , st) ← A(par, pk 1 ) b ← A O,BB (st) HV := {(id, v 0 , v 1 , b) ∈ HV : ∀j ∈ {1, . . . , N A } : "A j approves b"∈ BB} V 0 := (id,v 0 ,v 1 ,b)∈HV v 0 ; V 1 := (id,v 0 ,v 1 ,b)∈HV v 1 If V 0 = V
Adv priv A (λ) = Pr[Exp priv,0 A (λ) = 1] -Pr[Exp priv,1 A (λ) = 1] ,
where A is given access to all oracles in the set O = {OVote, OCast, OTally} as well as read and append-only write access to the bulletin board BB. The OVote and OCast oracles can be queried as many times as A wants, but the OTally oracle can only be queried once. [START_REF] Bernhard | SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions[END_REF] requires that individual ballots can be extracted online. We relax this notion by requiring that, if an election finishes successfully, the result must be "realistic" with respect to the honestly cast votes. Meaning that for each candidate, the result must be at least the number of honest one-votes and at most the total number of votes cast minus the number of honest zero-votes. We strengthen the notion, however, by requiring that this property holds even against corrupt election authorities. Intuitively, our notion is similar to the quantitative verifiability goal of Cortier et al. [START_REF] Cortier | SoK: Verifiability Notions for E-Voting Protocols[END_REF]. Formally, the advantage of an adversary A in breaking the consistency of EV is defined

Exp cons A (λ): par $ ← Setup(1 λ ) ; HV ← ∅ (pk 1 , . . . , pk N A , st) $ ← A(par) (r, Π) $ ← A OVote,BB (st) HV := {(id, v, b) ∈ HV : ∀j ∈ {1, . . . , N A } : "A j approves b"∈ BB} ∀k ∈ {1, . . . , N C }, h 0,k := |{(id, v, b) ∈ HV : v [k] = 0}| ∀k ∈ {1, . . . , N C }, h 1,k := |{(id, v, b) ∈ HV : v [k] = 1}| t ← |{b : ∀j ∈ {1, . . . , N A } : "A j

The Scheme

We instantiate our voting scheme according to the definition given in Section 5.4.1. We split the tallying algorithm in two parts, this algorithm in our E-Voting definition is interactive between authorities A 1 , . . . , A N A . In our instantiation there is no need for interaction, each authority A j can run an algorithm Tally j (par, pk 1 , . . . , pk N V , BB, sk j ) and publish on the bulletin board its partial tally t (j) and proof π A,(j) , anyone can then run Tally(par, pk 1 , . . . , pk N V , BB) to compute the total tally and final proof.

Setup(1 λ ) :

• generate parameters n, q, d, σ.

• A := A 1 A 2 ← CSetup(1 λ ), with A ∈ R (n+1)×(2n+1) q .
• output par := n, q, d, σ, A

Let KGen(1 λ ), Enc, Dec be a CCA-Secure public key encryption scheme, which the authorities will use to obtain the shares of the randomness of each voter. ASetup j (par) :

• (pk j , sk j ) ← KGen(1 λ ) • Give sk j to A j • output pk j
To cast a bulletin, voter i will share his vote into N A additive shares and compute a commitment t (j) i for each of them. He proves that the sum of these commitments is a commitment to v i such thatφ(v i ) ∈ {0, 1} N C and then encrypts the randomness r (j) i under the public key pk j so that each authority can open one share of the vote. He finally posts his vote, proof, commitments, and encryptions on the bulletin board along with a signature. Vote i (par, pk 1 , . . . , pk N A , id i , v i ) :

• v (j) i $ ← R q s.t. v i = N A j=1 v (j) i • r (j) i ← D 2n+1 R,σ • t (j) i := Com v (j) i ; r (j) i • r i := N A j=1 r (j) i • t i := N A j=1 t (j) i • π V i = Π V ote (A, t i ; r i , v i ) • e (j) i = Enc(r (j)
i , pk j )

• b i = id i , π V i , (t (j) i , e (j) i ) j∈[N A ]
• Sign and publish b i on the bulletin board Before tallying the votes each authority A j will check whether the bulletins have been properly cast. i.e. for each bulletin b i , A j checks the signature on b i , the proof that φ(v i ) ∈ {0, 1} N C and that the encryption of r (j)

i under his public key decrypts to a valid randomness. TestB i,j (par, pk 1 , . . . , pk N A , sk j , b i ) :

• id i , π V i , t (1)
i , e

i , . . . , t

(N A ) i , e (N A ) i := b i • Check that b i was signed by voter id i • Verify(A, t i , π V i ) • r (j) i := Dec(e (j)
i , sk j )

• Check r

(j) i ≤ 2d(2n + 1)σ
Each authority A j will compute its share t (j) of the total tally as well as a proof that t (j) has been computed correctly. To do so A j first decrypts e (j) i for each bulletin b i to recover randomness r (j) i . He then proves that for each voter i, r (j) i is a valid opening of t (j) i and finally outputs r (j) , the sum over i of all r (j) i (the share t (j) of the final tally can be obtained by opening t (j) the sum of the t (j) i using the r (j) output by A j ) as well as the proofs he computed. Note that w.l.o.g we will consider in all the following algorithms that all the bulletins on the bulletin board were tested and accepted by all the authorities (otherwise we can just discard the rejected bulletins and adjust N V to the number of remaining bulletins). Tally j (par, pk 1 , . . . , pk N A , BB, sk j )

• id i , π V i , t (1)
i , e

i , . . . , t

(N A ) i , e (N A ) i := b i , For (b i ) i∈N V ∈ BB • ∀i, r (j)
i := Dec(e

(j) i , sk j ) • π A,(j) = π A 1 , . . . , π A N V = Π Auth1 A, t (j)
1 , . . . , t

N V , r

1 , . . . , r

N V • r (j) = N V i=1 r (j) i (j)
• Sign and publish π A,(j) , r (j) on the bulletin board To compute the total tally, anyone can simply recover the randomnesses r (j) published by each authority A j , compute the corresponding commitment t (j) = t

(j)

i and open it to the partial tally t (j) . The total tally is then the sum of the partial tallies. Tally(par, pk 1 , . . . , pk N A , BB)

• For each authority A j , j ∈ [N A ] recover r (j) on BB 5.4 Our E-Voting Scheme 81

• ∀j, t (j) := N V i=1 t (j) i

• ∀j, t (j) := Open(t (j) , r (j) , 1)

• t := N A 1 t (j)
• publish t

The verification algorithm can be run by anyone to check that the final tally is correct (i.e. the voting scheme is publicly verifiable). To do so one simply verifies all the proofs output by the voters and authorities and checks that the opening of the total tally has been done correctly (by computing it again). Verify(par, pk 1 , . . . , pk N A , BB, t)

• For each i ∈ [N V ] , j ∈ [N A ], recover t (j) i , π V i , π A i,j on BB. • ∀i, verify π V i • ∀i, j, verify π A i,j • ∀j, t (j) := N V i=1 t (j) i
• ∀j, t (j) := Open(t (j) , r (j) , 1)

• Check that t = N A 1 t (j) For correctness we need all the proofs to verify correctly, which will be true with overwhelming probability for appropriate parameters (cf. Section 5.5), we also need the test on the norm of r (j) i to succeed, which will be true with overwhelming probability by using Lemma 2.3.5, and we need for the commitment of the partial tallies to open correctly, i.e. we need r (j) ≤ B Com .

We can fix the parameters so that this condition is verified, however the norm of r (j) grows linearly with the number of voters which, as we discuss in the next section, heavily impacts the efficiency of this scheme.

Dealing with Misbehaving Authorities. A malicious authority could prevent a voter from casting his vote by claiming that the voter's ballot is invalid. Since the TestB algorithm requires the secret key of the authority, the authority's claim cannot be publicly verified. This situation can be improved by letting voters store the randomness used in the encryption of e (j) i and, in case their ballot is incorrectly claimed to be invalid, reveal r (j) i and the randomness to show that the authority is at fault.

Improved Voting Scheme

A major caveat in the scheme presented in Section 5.4.2 is that parameters grow linearly in the number of voters. Indeed for correctness a verifier needs to be able to open the sum over all voters of the commitments of the vote shares, this implies that the bound B Com on the size of correct openings grows linearly in the number of voters. Increasing this bound heavily impacts the parameters of the scheme, e.g. if we fix d = 256 and q 2 31 , then for ∼ 100 bits of security we require a dimension n = 7 for 100 voters and n = 12 for 100 000 voters. This nearly doubles the commitment size, proof size and communication cost per voter (another The authority computes a proof that each new randomness is small and that it commits to the right value. Finally the authority publishes all the commitments and proofs as well as the opening, here r 1,2 , of the top level commitment which opens to the sum of the votes (i.e.

Com(v 1,2 ; r 1,2 ) Π(r 1,2 small) Π(v 1,2 = v 1,1 +v 2,1 ) Com(v 1,1 ; r 1,1 ) Π(r 1,1 small) Π(v 1,1 = v 1 + v 2 ) Com(v 1 ; r 1 ) Π(r 1 small) Com(v 2 ; r 2 ) Π(r 2 small) Com(v 2,1 ; r 2,1 ) Π(r 2,1 small) Π(v 2,1 = v 3 + v 4 ) Com(v 3 ; r 3 ) Π(r 3 small) Com(v 4 ; r 4 ) Π(r 4 small)
v 1,2 = v 1 + v 2 + v 3 + v 4 ).
issue with the previous scheme is that privacy is nontrivial, indeed revealing the sum of the randomnesses used makes it so that the privacy cannot be easily proven). We avoid this problem by using the fact that the authorities know the shares of many commitments and can thus create new commitments for the sum of their associated messages (this is the solution discussed in Section 5.1.2.1). e.g. Imagine authority A j has received the commitments and openings t

(j) i = Com(v (j) i ; r (j) i ) from voters 1 to N V , A j can choose l << N V and compute new commitments t (j) 1,1 , . . . , t (j) N V /l,1 , where t (j) i,1 = Com( lk i =l(k-1)+1 v (j) i ; r (j)
i,1 ) with fresh randomnesses r (j) i,1 and publish these commitments on the bulletin board. Notice that t (j) = N V i=1 t

(j) i opens to the same message as t

(j) = N V /l i=1 t (j)
i,1 (assuming both sums are valid commitments). However the randomness in the commitment t (j) will be approximately l times smaller than the one in t (j) which means that t (j) can be a valid commitment even if t (j) is not. By proving in zero knowledge that for i ≤ N V /l the commitment t (j) i,1 is valid and opens to the same value as li i =l(i-1)+1 t

(j)

i we can ensure that the scheme remains secure even if parameters are only set so that t (j) is valid and not t (j) . This effectively allows us to reduce B Com by a factor l. This process can be iterated by summing the t (j) i,1 by buckets of l and outputting new commitments t (j) i,2 to the sum of the corresponding messages with fresh randomnesses, once again accompanied by a proof that each commitment is valid and opens to the same value as a sum of t (j) i,1 (an example of such summations with buckets of size l = 2 is given in Figure 5.3). Each authority can repeat this process until there are less than l commitments to be summed, resulting in a bound B Com that grows linearly in l but remains independent of the number of voters. On the other hand this new protocol will output an overhead of ∼ N V /(l -1) commitments (more precisely N V /l + N V /l 2 + . . . extra commitments) and 2 additional proofs (which can be amortized over) for each new commitment. Tally j (par, pk 1 , . . . , pk N A , BB, sk j )

• id i , π V i , t (j)
1 , e

1 , . . . , t

j) N V , e (
N V := b i , For (b i ) i∈N V ∈ BB 5.4 Our E-Voting Scheme 83 • ∀i ∈ [N V ] , r (j)
i,0 := Dec(e

(j) i , sk j ) • ∀i ∈ [N V ] , v (j) i,0 := Open(t (j) i , r (j)
i , 1)

• For s ∈ (1, . . . , log l (N V ) ): -For u ∈ (1, . . . , N V /l s ): * r (j) u,s ← D 2n+1 R,σ * r (j) u,s := r (j) u,s - ul x=(u-1)l+1 r (j) x,s-1 * v (j) u,s := ul x=(u-1)l+1 v (j) x,s-1 * t (j) u,s := Com v (j) u,s ; r (j) u,s * t (j) u,s := t (j) u,s - ul x=(u-1)l+1 t (j)
x,s-1

• π A,(j) = Π Auth1 A, t (j)
u,s ; r

(j) u,s s ∈ (0, . . . , log l (N V ) ) u ∈ (1, . . . , N V /l s ) • π A,(j) = Π Auth2 A, t (j)
u,s , r

(j) u,s s ∈ (1, . . . , log l (N V ) ) u ∈ (1, . . . , N V /l s ) • t (j) T ot = t (j) u,s s ∈ (1, . . . , log l (N V ) ) u ∈ (1, . . . , N V /l s )
• Sign and publish π A,(j) , π A,(j) , t

T ot , r

1, log l (N V ) on the bulletin board To compute the total tally one only needs to open the commitments t (j) 1, log l (N V ) for each j ∈ [N A ] as these are commitments to the partial tallies of each authority. Tally(par, pk 1 , . . . , pk N A , BB)

• For j ∈ [N A ] recover t (j) 1, log l (N V ) and r (j) 1, log l (N V ) on BB • ∀j ∈ [N A ] , t (j) := Open(t (j) 1, log l (N V ) , r (j) 1, log l (N V ) , 1) • t := N A 1 t (j)
• publish t

To verify the election one needs to verify the proof of each user, the proof of correct opening of each t (j) u,s , and the proof that t (j) u,s opens to zero. The verifier can then recompute the tally and check that it has been done correctly. Verify(par, pk 1 , . . . , pk N A , BB, t)

• For each i ∈ [N V ], recover π V i on BB. • ∀i, verify π V i • ∀j ∈ [N A ] , ∀(s, u) ∈ (1, . . . , log l (N V ) ) × (1, . . . , N V /l s )
• For j ∈ [N A ] recover t (j) 1, log l (N V ) and r (j) 1, log l (N V ) on BB • ∀j ∈ [N A ] , t (j) := Open(t (j) 1, log l (N V ) , r (j)
1, log l (N V ) , 1)

• Check that t = N A 1 t (j)
We prove privacy and consistency in Section 5.6 and we discuss how to set the parameters in Section 5.5.

Parameters

In this section we review the bounds imposed on the parameters of our scheme by the correctness and security of the vote, and we propose concrete parameters in Table 5.2 as well as benchmarks from our implementation of the scheme.

The correctness and security of our scheme impose the following bounds on the parameters: Using the security analysis of Section 5.6, and the cryptanalysis of 2.3.4 to assess the hardness of M-LWE q,n,σ and M-SIS q,2n+1n,B Com we set our parameters as in Table 5.2 (we arbitrarily fix the number of authorities to 4, anything larger than 2 is enough for security and this does not impact performance significantly). For this set of parameters both the M-LWE and M-SIS achieve a block size of β = 450 which corresponds to a security of 93 bits in space, 131 bits in time, and 119 bits in time for post-quantum security. Due to the improved E-voting scheme of Section 5.4.3, the number of voters does not affect the security at all and can thus be taken arbitrarily large.

• Overwhelming soundness of π V : d B C 2 B C > 2 256 • Correctness of π V : B V ≥ N A 2d(2n + 1)σ • Zero-knowledge of π V : B V ≥ 11B C 2d(2n + 1)B V • Amortization of π A and π A : k > (λ + 2)/ log(2d + 1) • Correctness of π A : B A1 ≥ ( 2d(2n + 1) + √ )σ • Zero-knowledge of π A : B A1 ≥ 11 2d k(2n + 1)B A1 • Correctness of π A : B A2 ≥ (l + 1)( 2d(2n + 1) + √ )σ • Zero-knowledge of π A : B A2 ≥ 11 2d k(2n + 1)B A2
We have implemented the complete voting scheme in C. The main computational problems in the scheme are the sampling of discrete Gaussian vectors and multiplication of polynomials in R q . For the sampling we have implemented a two-stage Knuth-Yao sampler. We have taken great care to ensure that the statistical distance between the sampled vectors and the exact discrete distribution is below 2 -100 . This required computing the probabilities and the lookup table for the sampler with a multiprecision library. We used pari [START_REF]PARI/GP version 2.9.0[END_REF] for this task. For the fastest possible multiplication in rings of the given form, one usually chooses the prime q in such a way that Z q contains a 2d-th root of unity. This then implies that the modulus X d + 1 splits into linear factors over Z q and allows for using an NTT-based multiplication algorithm. Unfortunately, the security requirements of our scheme prevent q from being chosen in this way. Instead of completely resorting to a general algorithm that works for multiplication modulo arbitrary polynomials, we have exploited the fact that for our prime q, X n + 1 does in fact split into 16 factors. This allowed us to use a general multiplication algorithm only after 4 stages of NTT. We have used our own NTT implementation and the highly optimized FLINT library [START_REF] Hart | FLINT: Fast Library for Number Theory[END_REF] for the base case multiplication. FLINT uses a variant of Kronecker substitution for this task.

Security Analysis of the Voting Scheme

In this section we prove the privacy and consistency of our E-voting scheme as defined in Section 5.2. For privacy we consider the following advantages for an adversary A:

• Adv CCA A (λ) the advantage of A in the CCA security game of the encryption scheme.

• Adv Hid

A (λ) the advantage of A over the Hiding property of the commitment scheme. Since the zero-knowledge of both the OR-Proof and the amortized proof are statistical, the probability of distinguishing between the simulator and the actual proof is less than 2 -λ . Theorem 5.6.1. The advantage of any PPT adversary A over the privacy of our E-voting scheme is at most:

Adv priv A (λ) ≤ N V 2Adv CCA A (λ) + l l -1 Adv Hid A (λ) + 2 -λ+1 + 2 -λ+2
Proof. We use a game based proof: Game G 0 : In this game we run Exp priv,0 A as defined in Section 5.4.1. The voting, casting and tallying oracle are run honestly by the simulator using choice bit β = 0 and thus votes

v 0,i for i ∈ [N V ].
Game G 1,i≤N V : In this game we modify the honest voting oracle OVote(id, v 0 , v 1 ) so that when it runs Vote(par, pk 1 , . . . , pk N A , id i , v 0 ), the OR-proof for t i = Com(v i ; r i ) is not done honestly but simulated. Note that when simulated the proof is independent of the randomness r i and vote v 0,i . The advantage of the adversary in distinguishing between Game G 1,i-1 and Game G 1,i (where we consider Game G 0 as Game G 1,-1 ) is zero if Vote is never called on id i (i.e. id i corresponds to a corrupted voter) and 2 -λ otherwise.

Adv G 1,i A -Adv G 1,i-1 A ≤ 2 -λ
Game G 2 : In this game we modify the tallying oracle of the first authority (the honest one) to make π A,(1) independent of the decrypted randomnesses (r

(1) i ) i∈[N V ] .
i.e. we modify the Tally 1 (par, pk 1 , . . . , pk N A , BB, sk 1 ) oracle so that the proof π A,(1) is computed using the simulator of the amortized proof.

Adv G 2 A -Adv G 1,N V A ≤ 2 -λ
Game G 3 : In this game we modify the Tally 1 (par, pk 1 , . . . , pk N A , BB, sk 1 ) oracle so that the proof π A,(1) is computed using the simulator of the amortized proof.

Adv G 3 A -Adv G 2
A ≤ 2 -λ Game G 4,i≤N V : In this game we modify the voting oracle for identity id i so that it outputs the encryption e (1) i ). Doing so implies that the commitment t (1) u,s for u = i/l and s = 1 will no longer be a commitment of zero but a commitment of v 1,iv 0,i . This does 5.6 Security Analysis of the Voting Scheme 87 not matter since the proof π A,( 1) is now simulated and thus independent of the existence of a witness that t

(1) u,s commits to zero.

Adv G 5,i A -Adv G 5,i-1 A
≤ Adv Hid A (λ) Game G 6,1≤s≤ log l (N V ) -1,1≤u≤ N V /l s : Now that the votes have been changed from v 0,i to v 1,i we need to change the values of the commitments of the partial sums in order for t (1) u,s to be commitments to zero, this will be needed to change π A,(1) back to an honest proof. To do so we let v 0,u,s = 1,x,s-1 (where v 0,i,0 = v 0,i and v 1,i,0 = v 1,i ). We can now change the commitments t Game G 7,i≤N V : We revert the randomness encryptions to e

(1)

i = Enc(r (1)
i ), this modification is consistent with the tallying scheme as the randomness used have not been modified.

Adv G 7,i A -Adv G 7,i-1 A ≤ Adv CCA A (λ)
Game G 8 : We compute the proof π A,(1) honestly. This is possible because all commitments t

(1) u,s are commitments of zero made with the appropriate randomnesses.

Adv G 8 A -Adv G 7,N V A ≤ 2 -λ
Game G 9 : Similarly we compute the proof π A,(1) honestly.

Adv G 9 A -Adv G 8 A ≤ 2 -λ Game G 10,i≤N V : We compute the proof π i honestly. This is possible because t i is still a commitment to either zero or one with the same randomness as before.

Adv G 10,i A -Adv G 10,i-1 A ≤ 2 -λ
Game G 11 We run Exp priv,1 A , this game is identical to Game G 10,N V .

Adv G 11 A = Adv G 10,N V A
We now consider the consistency of our voting scheme. For a tighter security proof we will assume a slight modification on the algorithm Tally j : Rather than using only the hash of the corresponding commitments to compute the challenges for the proofs π A,(j) and π A,(j) , the authorities will hash the whole bulletin board (which among other things contains the relevant commitments). Let H(BB) = (chl 1 , . . . , chl N A ) and H (BB) = (chl 1 , . . . , chl N A ) be these hashes, the j th authority will then use chl j and chl j as challenges for his proofs π A, (j) and π A, (j) . In doing so we guarantee that we can extract witnesses for all N A proofs π A, (j) in one rewinding of the random oracle O H . Theorem 5.6.2. Let A be an adversary with non negligible advantage Adv cons A (λ) = ε in experiment Exp cons A (λ). Using A we construct an extractor E who breaks the binding property of Com in expected time 1/ε + negl(λ)

Proof. We will assume that when A succeeds in Exp cons A (λ) all the bulletins on BB were accepted by all the authorities, we can make this assumption because any bulletin that was not accepted is effectively discarded (the authorities do not include it in their amortized proofs nor in the final tally). We can thus use N V as the number of accepted tallies. E starts by running A until it succeeds in Exp cons A (λ), i.e. until it outputs a bulletin board BB that verifies correctly and such that ∃k ∈ N C , r[k] < h 1,k or r[k] > N Vh 0,k . Using the soundness of the proofs π A,(j) , E rewinds A and obtains witnesses r(j) i and messages v(j) i , for i ≤ N V and j ≤ N A , such that:

t (j) i = Com(v (j) i ; r(j) i ) (1)
Suppose there exists i ≤ N V such that vi := N A j=1 v(j) i mod q is such that φ(v i ) / ∈ {0, 1} N C , E runs the soundness extractor for π V i and obtains ri , c ∈ R and vi ∈ {0, 1} such that:

ct i = Com(cv i , ri ) (2)
By summing equations (1) over j ∈ [N A ] and multiplying them by c, we obtain the following:

ct i = Com(cv i ; c N A j=1 r(j) i ) (4)
Since we assumed that φ(v i ) / ∈ {0, 1} N C and we know φ(v i ) ∈ {0, 1} N C , if we have ri ≤ B Com and c N A j=1 r(j) i ≤ B Com (which we will ensure in Section 5.5), then E has successfully opened ct i to two different messages and thus broken the binding property of Com. We can now assume that for every i ≤ N V , φ(v i ) ∈ {0, 1} x,s-1 . E runs the soundness extractor for π A,(j) and obtains r(j) u,s such that t (j) u,s = Com(0, r(j) u,s ). Using the extraction for π A,(j) we already have r(j) u,s and messages m (j)

u,s such that: t (j) u,s = Com(m (j) u,s ; r(j) u,s )

Now suppose that for all u, s, j we have m 1, log l N V ; r(j) 1, log l N V ) (6) By construction of v(j) u,s we have v(j) 1, log l N V = N V i=1 v(j) i . Since the bulletin board verifies correctly we know that t (j) 1, log l N V opens to plaintext v (j) such that r = N V j=1 v (j) by the N Vh 0,k which contradicts the fact that A wins experiment Exp cons A (λ). We have thus shown that there exist u, v, j such that m (j) u,s = v(j) u,s , i.e. one of the partial sum does not commit to the proper value. Fix a j ≤ N A for which there exist such a commitment and let u, s be the smallest such triple (in lexicographic order). In particular this implies that s ≥ 1 (as we have proven that all t (j) i open to v(j) i ) and that for x ∈ ((u -1)l + 1, ul) we have the following witness extracted from π A,(j) : t (j)

x,s-1 = Com(v

(j)
x,s-1 , r(j)

x,s-1 )

By summing equation (7) over x ∈ ((u -1)l + 1, ul) and subtracting the extraction for t From the extraction of π A,(j) we had t (j) u,s = Com(0, r(j) u,s ). We know that m

Conclusion

Throughout this thesis we have studied the "Fiat-Shamir with Aborts" technique for constructing lattice-based zero-knowledge proofs of knowledge. We have put forward new constructions which increase the expressiveness as well as the practicality of proofs of knowledge. We have used these protocols as building blocks to create efficient lattice-based privacy protocols.

We proposed proofs of knowledge for the disjunction of NP Languages over lattices, bridging the gap with similar number theoretic constructions. To do so we observed that well chosen challenge spaces can be endowed with an "ad-hoc" group law, allowing for generic OR-Proofs constructions to be applied.

We constructed proofs of knowledge for subset membership for commitments, i.e. proofs that a commitment opens to a message in a fixed subset of the message space. To do so we studied the properties of the automorphisms of polynomial rings and have shown that the so-called Galois automorphisms can be used in conjunction with zero-knowledge proofs in order to show that committed message belong to subrings of variable dimensions. Through this use of the structure of polynomial rings we obtained proofs of subset membership with constant proof size, and maybe more importantly for privacy-preserving applications: these proofs use subsets containing messages that have inverse in the ring.

Another approach taken was to improve the state of the art in amortized zero-knowledge. While previous works already achieved exact amortized zero-knowledge proofs with constant overhead and polynomial slack, they required either to be amortized over more than thousands of equations or were very intensive in running time both for the prover and verifier. We presented a new amortized proof that has substantially the same overhead and slack but can be used with as few as 12 equations. Surprisingly the protocol we presented was conceptually much simpler than previous works.

Building upon our proofs for subset membership we constructed a group signature with size independent of the group size. While such a result already existed, previous constructions were not practical as they required the repetition of a proof of knowledge with constant soundness. In contrast our construction focuses on efficiency and obtains signatures that are barely larger than 500KB.

Lastly we proposed what is to our knowledge the first efficient lattice-based e-voting scheme. Building upon our OR-proofs and amortized proofs we constructed a voting scheme that boasts small ballot size, around 30KB, and very efficient complexity with algorithms that -91 -Chapter 6 Conclusion and Open Questions run in a matter of milliseconds.

Open Questions

Question 6.1. Can we obtain exact proofs of knowledge with overwhelming soundness without any repetition or amortization? Such a proof of knowledge would be the holy grail of lattice-based zero knowledge. However obtaining overwhelming soundness requires a large challenge space, and it is difficult to imagine how to obtain such a challenge space without either increasing the number of equations proven or obtaining a knowledge extractor whose output depends on the challenges.

Question 6.2. Can we obtain proofs without slack?

While the presence of polynomial slack in lattice-based zero knowledge is not terribly inconvenient, having proofs without slack would allow for smaller parameters and more efficient constructions. An idea towards this goal would be the following: Given As = t with s a binary vector, compute a regular lattice based zero-knowledge proof (possible approximate or amortized) with polynomial slack, and add an extra proof that that s is binary. Taking inspiration from proofs for arithmetic circuits on could sample a random vector v and prove that v • s, 1 -s = 0 Question 6.3. Can we obtain smaller group sizes for our group signature?

The way we construct the group in our group signature inherently forces the group size to be at least q 2 . We could maybe obtain a smaller group size if on top of showing that id is invariant under a set of automorphism we also showed that it+is small. Question 6.4. How can we adapt our e-voting scheme to different types of election?

For now our e-voting scheme computes the result of an election as the sum of votes in {0, 1} N C , however we could consider different types or votes or tallies. For example we could prove that voter voted for exactly one candidate by doing an or proof over the possible votes (1, 0, . . . , 0), (0, 1, 0, . . . , 0), etc... However if we want elections where voters vote for exactly two candidates the same method will give proofs of size quadratic in the number of candidates. We could search for better ways to encode votes or prove properties about them.

Notation

Figures

Résumé

Le chiffrement à base de réseaux euclidiens a connu un grand essor durant les vingt dernières années. Autant grâce à l'apparition de nouvelles primitives telles que le chiffrement complètement homomorphe, que grâce à l'amélioration des primitives existantes, comme le chiffrement á clef publique ou les signatures digitales, qui commencent désormais à rivaliser avec leurs homologues fondés sur la théorie des nombres. Cela dit les preuves à divulgation nulle de connaissance, bien qu'elles représentent un des piliers des protocols de confidentialité, n'ont pas autant progressé, que ce soit au niveau de leur expressivité que de leur efficacité.

Cette thèse s'attelle dans un premier temps à améliorer l'état de l'art en matière de preuves à divulgation nulle de connaissance. Nous construisons une preuve d'appartenance à un sous ensemble dont la taille est indépendante de l'ensemble en question. Nous construisons de même une preuve de connaissance amortie qui est plus efficace et plus simple que toutes les constructions qui la précèdent.

Notre second propos est d'utiliser ces preuves à divulgation nulle de connaissance pour construire de nouvelles primitives cryptographiques. Nous concevons une signature de groupe dont la taille est indépendante du groupe en question, ainsi qu'un schéma de vote électronique hautement efficace, y compris pour des élections à grand échelle.

Mots Clés

cryptographie, réseaux euclidiens, preuves de connaissance, signatures de groupe, vote électronique.

Abstract

Lattice based cryptography has developed greatly in the last two decades, both with new and stimulating results such as fully-homomorphic encryption, and with great progress in the efficiency of existing cryptographic primitives like encryption and signatures which are becoming competitive with their number theoretic counterparts. On the other hand, even though they are a crucial part of many privacy-based protocols, zero-knowledge proofs of knowledge are still lagging behind in expressiveness and efficiency.

The first goal of this thesis is to improve the quality of lattice-based proofs of knowledge. We construct new zero-knowledge proofs of knowledge such as a subset membership proof with size independent of the subset. We also work towards making zero-knowledge proofs more practical, by introducing a new amortized proof of knowledge that subsumes all previous results.

Our second objective will be to use the proofs of knowledge we designed to construct novel and efficient cryptographic primitives. We build a group signature whose size does not depend on the size of the group, as well as a practical and highly scalable lattice-based e-voting scheme.

  Computational) Binding. It is hard for any PPT adversary A to come up with a tuple (c, d, d ) such that Open(c, d) = m = ⊥, Open(c, d ) = m = ⊥ and m = m . Formally:

q and b = b with probability exactly 1/ 2 .Lemma 2 . 4 . 5 (

 2245 However if y = I n+l B r, then :t = Ar + 0 m b and A will output b = b with probability 1/2 + ε. A therefore has advantage ε/2 in the M -LW E q,m-n-l,ψ problem. Binding). Let B C ≥ max c∈C (c1 ). If there is an adversary A who can output a commitment t with two valid openings (m, r, c) and (m , r , c ) such that m = m with probability ε, then there is an algorithm A who can break M -SIS q,m,4B C B Com in the same time and with advantage ε.

A 2 .

 2 A 2 := 0 l×n I l A 2 as per CSetup and outputs A = A 1 When A comes up with a commitment t such that Open(t, r, c) = m = ⊥, Open(t, r , c ) = m = ⊥, and m = m . We have m = t 2c -1 A 2 r and m = t 2c -1 A 2 r , which implies cc (mm ) = A 2 (crc r), and since m = m we get:

Figure 2 . 1 :

 21 Figure 2.1: Experiment for IND-CPA security

Contents 3 . 1

 31 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Exact and Approximate ZKPoKs . . . . . . . . . . . . . . . . . . . . 28 3.2.1 Σ -Protocol for one way functions . . . . . . . . . . . . . . . . . . . 28 3.2.2 Applications to Commitments . . . . . . . . . . . . . . . . . . . . . 30 3.3 OR-Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.4 Subset Membership Proofs . . . . . . . . . . . . . . . . . . . . . . . 34 3.5 Amortized Zero-Knowledge . . . . . . . . . . . . . . . . . . . . . . . 37 -25 -

Figure 3 . 1 :

 31 Figure 3.1: Three round form of a Σ-protocol.

Lemma 3 .

 3 1.3 ([Dam10] Theorem 1). Let (P, V) be a Σ -protocol with challenge space C. If (P, V) achieves special soundness then it has soundness error 1/ |C|.

Figure 3 . 2 :Theorem 3 . 2 . 1 .

 32321 Figure 3.2: Generic ZKPoK for lattice-based one-way functions.

3 . 5

 35 we have z ≤ √ 2mdσ ≤ B with overwhelming probability. It is clear that in the honest protocol the response is computed in such a way that the verification equation Az = tc + w stands. Special Soundness: Let w, c, z and w, c , z be two accepting transcripts with c = c . Let z = zz and c = cc , by correctness we have Az = tc, with c ∈ C and z ≤ 2B .

  Soundness: Consider two accepting transcripts (w 1 , . . . , w , c, z 1 , . . . , z , c 1 , . . . , c ) and (w 1 , . . . , w , c, z 1 , . . . , z , c 1 , . . . , c ) with c = c . Since c = c , there exists i ∈ [ ] such that c i = c i . Let zi = z i -z i and ci = c ic i , by correctness we have Az i = t i ci , with ci ∈ C and zi ≤ 2B .

  one can think of choosing c ∈ C as first choosing the κ non-zero coefficients and then choosing their sign). If we define C = c ∈ {0, 1} d , c 1 = κ then any element c ∈ C can be directly decomposed as a pair (a, b) ∈ C × Z κ 2 where a is the "absolute value" of c and b

Figure 3 . 4 :

 34 Figure 3.4: Proof that the opening of a commitment is invariant under a set of automorphisms (ξ j ) j∈S

2 .

 2 Run P * on random (χ , C ) where χ = χ , ∀j = i, c T j = c T j , and c T i is freshly sampled. If after λ/ε attempts P * has not output a valid response, Z abort.

Figure 4 . 1 :

 41 Figure 4.1: Experiment for weak anonymity

Definition 4 . 2 . 2 (

 422 Weak anonymity). For a group signature (GSetup, Sign, Verify, Open), we define full traceability with adversary A via the experiment of Figure4.2. The advantage of A is:Adv trace (A, λ, N ) := Pr Exp trace (A, λ, N ) = 1

  Exp trace-b (A, λ, N ) : S ← Empty List (gpk, gmsk, sk 1 , . . . , sk N ) ← GSetup(1 λ , 1 N ) (M * , z * ) ← A OSign,OCorrupt (gpk, gmsk) If Verify(gpk, M * , z * ) = 0 return 0 If Open(gmsk, M * , z * ) = ⊥ return 1 If Open(gmsk, M * , z * ) = j * ∈ [N ] and j * / ∈ C and (j * , M * ) / ∈ S Then return 1 Else return 0

Figure 4 . 2 :

 42 Figure 4.2: Experiment for full traceability

Lemma 4 . 2 . 3 (

 423 [LN17] Lemma 3.1). Let sk = s, and e be the error in b = as + e. If for

  5 , w s , w B , M ) 16: z := rc + y 17: z := r c + y 18: z -1 := ξ -1 (r)c + y -1 19: z 5 := ξ 5 (r)c + y 5 20: z s 1 := s 1 c + y s 1 21: z s 2 := s 2 c + y s 2 22: z

1: 3 : 4 :

 34 T := t 1 | . . . | t 2: R := r 1 | . . . | r W = AY 5: C := H(A, T, W) ∈ {0, 1} ×k 6: Z := RC + Y 7: if Rej(Z, RC, σ A2 ) = 0 then 8: Restart 9: return (Z, C) Algorithm 11 Verify Auth,1 Require: Public information: A, t 1 , . . ., t , Z, C.1: T := t 1 | . . . | t 2: W := AZ -TC 3: if C = H(A, T, W) ∨ Z max > B A2 thenPublic information: A, t 1 , . . . , t , Z, C. 1:

Figure 5 . 1 :

 51 Figure 5.1: Experiment for privacy arbitrary number of voters does not learn anything more about the votes of honest voters

$←Figure 5 . 2 :

 52 Figure 5.2: Experiment for consistency

5. 4

 4 Our E-Voting Scheme 79 through the consistency experiment of Figure 5.2 as Adv cons A (λ) = Pr[Exp cons A (λ) = 1] .

Figure 5 . 3 :

 53 Figure 5.3: Example of the improved tallying for an authority. At each level s fresh randomnesses r u,s are sampled and the authority commits to the sum of the votes of the previous level.The authority computes a proof that each new randomness is small and that it commits to the right value. Finally the authority publishes all the commitments and proofs as well as the opening, here r 1,2 , of the top level commitment which opens to the sum of the votes (i.e. v 1,2 = v 1 + v 2 + v 3 + v 4 ).

Game G 5 ,i

 5 i , pk 1 ). The simulator also modifies the Tally 1 oracle so that it uses r i≤N V At this point all the values published by the oracles OVote and OTally 1 are independent of the votes (v 0,i ) i∈[N V ] except for the commitments output by OVote. We would like to use the hiding property of the commitment to change t + v 1,iv 0,i , r

  + v 1,u,sv 0,u,s ; r (j)u,s and the partial sums are verified.

  N C . For s ∈ [ log l N V ], u ∈ [ N V /l s ] and j ∈ [N A ], let v

5. 6

 6 Security Analysis of the Voting Scheme 89 binding property of Com we have that v(j) = N V shown that for all i ≤ N V , φ(v i ) ∈ {0, 1} N C this implies that h 1,k ≤ r[k] ≤

  x,s-1 ≤ B Com and r(j) u,s ≤ B Com (which we ensure in Section 5.5) then we have found two distinct openings for t (j) u,s and broken the binding property of Com.

R

  The ring Z [X] /X d + 1 •, •The inner-product•The rounding function|S|Size of a set• • • p,∞,max Norms s (

  Gaussians. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 Hard Problems on Lattices. . . . . . . . . . . . . . . . . . . . . . . 12 2.3.4 Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.5 Trapdoors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Basic Cryptographic Primitives . . . . . . . . . . . . . . . . . . . . . 16 2.4.1 Commitments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4.2 Public Key Encryption . . . . . . . . . . . . . . . . . . . . . . . .

2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 2.2 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 2.3 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 2.3.1 Definitions and Properties . . . . . . . . . . . . . . . . . . . . . . .

9 2.3.2 21 -7 -

  [START_REF] Laarhoven | Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing[END_REF] have a heuristic time complexity of 2 0.292β which can be reduced to a quantum complexity of 2 0.265β [ADPS16] by using Grover's quantum search algorithm. Both algorithms have a space complexity of 2 0.2075β .

	2.3 Lattices algorithms [BDGL16;

  2.2 to prove that two commitments t 1 and

	Without Complexity Leveraging With Complexity Leveraging	Full signature 581 KB 1173 KB	Commitment Ciphertext 113 KB 123 KB 204 KB 254 KB	Proof 345 KB 715 KB	Secret key 146 KB 292 KB
			Table 4.1: Size of a signature

Table 4 .

 4 r 2: Concrete parameters for our Group signature

	Parameter Ring dimension Commitment modulus ("Top") Commitment modulus ("Bottom") Commitment row dimension ("Top") Commitment message dimension Verifiable encryption plaintext module Verifiable encryption ciphertext module Bound on the challenge space Standard deviation of the GPV trapdoor Standard deviation of the NTRU trapdoor	Notation Value d 4096 q 1 ∼ 2 30 q 2 ∼ 2 80 n 1 l 1 p ∼ 2 27 Q ∼ 2 60 B C = κ 26 s ∼ 2 49 r ∼ 2 42	Value with complexity leveraging 8192 ∼ 2 20 ∼ 2 80 1 1 ∼ 2 27 ∼ 2 62 24 ∼ 2 50 ∼ 2 42

  Public information: A, t, (c i,0 , c i,1 , z i,0 , z i,1 ) i∈[N C ]

	Algorithm 8 Verify V ote Require: 1: V := 1 2: A 1 A 2 := A; t 1 := t t 2 3: for i ∈ [N C ] do
	4:
			. . , t N V
	with opening r 1 , . . . , r N A . If we rewrite	t i,1 t i,2	:= t i , T 1 := t 1,1 | . . . | t N V ,1 , and R :=
	r 1 | . . . | r N V , then the protocol Π Amo2 (A 1 , T 1 ; R) is a proof that each commitment is well

  Public information: A, t 1 , . . . , t . Private information: r 1 , . . . , r ∈ R, s.t ∃(m 1 , . . . , m ) ∈ R q , t i = Com(v i ; r i ). Public information: A, t 1 , . . . , t . Private information: r 1 , . . . , r ∈ R, s.t t

	5.3 Building Blocks	75
	Algorithm 9 Π Auth,1 Require: 1: A 1 := A A 2 2: for i ∈ [N C ] do 3: t i,1 t i,2 := t i
	4: T 1 := t 1,1 | . . . | t ,1 5: R := r 1 | . . . | r (2n+1)×k 6: Y ← D R,σ A1 7: W = A 1 Y 8: C := H(A 1 , T 1 , W) ∈ {0, 1} ×k 9: Z := RC + Y 10: if Rej(Z, RC, σ A1 ) = 0 then 11: Restart 12: return (Z, C)
	Algorithm 10 Π Auth,2 Require:

i = Com(0; r i ).

  recover π

	from BB			A,(j) u,s	and π	A,(j) u,s
	• ∀j, u, s verify π	A,(j) u,s	and π	A,(j) u,s

Table 5 .

 5 2: A possible set of parameters for our E-Voting scheme. These parameters achieve a post-quantum security of 119 bits in time and 93 bits in space.

	• Consistency of the vote (equation (1)): 2B V ≤ B Com
	• Consistency of the vote (equation (4)): 2B C N A B A1 ≤ B Com
	• Consistency of the vote (equation (7)): 2d(l + 1)B A1 ≤ B Com
	• Consistency of the vote (equation (8)): 2dB A2 ≤ B Com

In fact M-LWE is only shown to be hard in its decision variant for slightly non-spherical Gaussians but all practical applications consider spherical nonetheless.

3.2 Exact and Approximate ZKPoKs

We do not consider |w| and |c| because w will not be output in non-interactive proofs (as it can be recovered from A, z, t, c) and |c| is usually negligible.

3.5 Amortized Zero-Knowledge

The ZKPoK is a Fiat-Shamir transformation of a Σ-protocol, and so the message that the group member signs is simply added into the random oracle input.

The reason that signature schemes using cryptographic hash functions (and proved secure in the random oracle model) are not suitable is that their lack of algebraic structure makes it very difficult to construct efficient proofs of knowledge that prove something about the identity i when it is an input to the random oracle.

Notice that we combined the a2 • s3 term with a2 • r term to obtain a2 • r . This was the reason that we used exactly a2 from the commitment scheme in the key generation in Equation (4.3).

It is also possible to do these proofs in a non-amortized fashion and only get an approximate proof. In this case, depending on the value of l, the parameters may have to be increased.

Acknowledgments

Acknowledgments same room containing an infinite countable number of boxes, indexed from 0 upwards. Each one of those boxes contains a real number of my choosing -the same in each room. Each of you will go into one copy of this room and will be free to open any number of boxes (even a countable number). However, you have to leave at least one box closed (they can chose which one, and it can be different for each of them), and guess which number is inside this box.

If all but one of you guess correctly, I will let you free. Otherwise, you will be tortured to death." How can the mathematicians make sure they survive this challenge? Je remercie l'administration de l'ENS et de l'INRIA: Joëlle, Lise-Marie, Nathalie, Stéphane, et Valérie. C'est grâce à leur efficacité que j'ai pu me concentrer exclusivement sur la recherche.

I would like to thank Michael Osborne for welcoming me in the Security & Privacy team of IBM Zurich, as well as everyone in the team: Anja, Anna, Björn, Cecilia, Christian, David, Eduarda, Gregor, Gregory, Jan, Maria, Manu, Patrick, Thijs, Tommaso, and Vadim. Working in IBM was an enriching experience and I have learned a lot by interacting with my peers.

Acknowledgments vii

Chapter 4 Group Signature

In this chapter we will show how to use the proofs of knowledge from Chapter 3, specifically the proof of subset membership, to construct efficient group signatures. For ease of comprehension we first describe a group signature without the traceability property and then show how to use the verifiable encryption of [START_REF] Lyubashevsky | One-Shot Verifiable Encryption from Lattices[END_REF] to obtain a group signature with full traceability. We give formal proofs for the anonymity and traceability of our scheme, and derive parameters as well as the corresponding signature size.

We consider the following advantages for an adversary A • Adv trace A (λ) the advantage of A in the traceability game.

• Adv trace * A (λ) the advantage of A in the traceability game where GSetup is replaced with GSetup * .

• Adv N T RU A (λ) the advantage of A in solving the NTRU q,r problem.

Lemma 4.4.2. The advantage of any PPT adversary

A against the traceability game of the group signature is at most:

Proof. We use a succession of games. Game G 0 : The challenger B runs the Group signature protocol honestly. He gives (sk i ) i∈S as well as gmsk to A who has advantage ε in the traceability game.

where f, g ∈← D R,r are taken as in Section 2.3.5. G 2 is indistinguishable from G 1 under the NTRU q,r assumption.

Note that if b T = a T R, B can no longer use the GPV trapdoor of a T | b T + ig T to sample secret keys for user i. To generate keys for i he will instead sample s i 1 , s i 2 ← D 2 s and use his NTRU trapdoor on a 2 to sample s i 3 . This game will be indistinguishable from the previous one by the hardness of M-LWE q,1,s (since a T R is two M-LWE q,1,s samples).

uniform this game is identical to the previous one.

This game is indistinguishable from the previous one under M-LWE q,1,s .

E-Voting

In this chapter we present an e-voting scheme for multiple candidates with multiple tallying authorities.

We define a security model, adapted from the one of [START_REF] Bernhard | SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions[END_REF], in which privacy is guaranteed as long as one of the tallying authorities is honest and unforgeability is guaranteed even if they are all corrupt.

After recalling the building blocks we use from Chapters 2 and 3 we present a first variant of our voting scheme in which the parameters grow with the number of voters.

We then show how to modify this scheme so that the parameters remain independent of the number of voters at virtually no cost.

Finally we give concrete parameters as well as ballot sizes and a formal proof of security.

Abbreviations

List of Illustrations