Éric Sageloli
email: eric.sageloli@thalesgroup.com

Pierre Pébereau
email: pierre.pebereau@thalesgroup.com

Pierrick Méaux
email: pierrick.meaux@uni.lu

Céline Chevalier
email: celine.chevalier@ens.fr

Shorter and Faster Identity-Based Signatures with Tight Security in the (Q)ROM from Lattices

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

Introduction

Identity-Based Signatures. Secure communication over the Internet heavily relies on the use of digital signatures, which provide authenticity, integrity, and non-repudiation in an asymmetric setting. In textbook schemes, each user needs to generate its own (public key, secret key) pair, and we assume that each user is uniquely identified by its public key. In the real world, this is ensured by the use of public-key infrastructures (PKI) which map public keys to real-world identities such as names or email addresses. This usually involves a hierarchy of trusted certification authorities (CA) that can certify public keys as belonging to a certain user.

To relax the need for such heavy structures, Shamir proposed in his seminal work [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF] the use of so-called identity-based signatures (IBS), where the public key of a user simply is its identity. The corresponding secret key is issued by a trusted authority, which derives it from a master secret key that only the authority knows, and which is assumed to have a way to verify the identity of the user. This simplifies the requirements on PKI and certificates and opens the way to more efficient schemes. In such a scheme, an honest user with identity id can sign a message µ using its secret key sk id , and its signature σ can be publicly verified, given the master public key mpk and its identity id.

The usual security notion for IBS is Existential Unforgeability under Chosen Message Attack (EUF-CMA), where an adversary A can obtain a set of secret keys associated to some identities and get the signatures associated to a certain number of tuples (identity, message) of its choice. It wins the security game if it is able to produce a new tuple (id, message, signature) for an identity and a message not already queried. We say it is adaptive if it can adaptively query the secret keys and signatures (EUF-CMA), non-adaptive otherwise (EUF-naCMA).

The security of cryptographic schemes is usually proved by reduction, meaning that if a (polynomial-time) adversary A is able to break the security of the scheme, then we can reduce it to another (probabilistic polynomial time) adversary B that is able to solve an instance of some hard problem (factoring, discrete logarithm, Short Integer Solution (SIS) [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF]. . . ). The success probability of A is bounded by a factor times the success probability of B. If this factor is a small constant (and does not depend logarithmically, linearly or quadratically on the security parameter), we say that the reduction is tight. This is a desirable probability since a cryptographic scheme with tight reduction does not need to increase the key length to compensate a security loss. Furthermore, with the recent advances made on quantum computers, it is desirable to rely on quantum-safe hard problems, such as those based on lattices. It is sometimes possible to rely only on these hard problems, leading to schemes in the so-called standard model. But in order to gain efficiency, one usually relies on idealized models, such as the random oracle model (ROM). Its quantum equivalent is the quantum ROM (QROM), where a possibly quantum adversary is allowed to quantumly query the oracle. Finally, the goal of this article is thus to present an identity-based signature scheme with tight security, assuming the SIS problem is hard, and relying on the ROM or QROM.

Related Work. There are two main approaches used to construct IBS schemes (see [START_REF] Kiltz | Identity-based signatures[END_REF] for more details), but none of them is directly applicable to tight post-quantum security (more discussion in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF]). The first one, called the certification approach, transforms a standard signature scheme into an IBS scheme [START_REF] Dodis | Strong key-insulated signature schemes[END_REF][START_REF] Bellare | Security proofs for identity-based identification and signature schemes[END_REF]. The generic transformation is not tight, but can be shown tightly secure if the underlying signature scheme is tightly secure in the multi-user setting with adaptive corruption [START_REF] Lee | Tight security for the generic construction of identity-based signature (in the multi-instance setting)[END_REF] (which may be applied to the post-quantum signature scheme designed in [START_REF] Pan | Lattice-based signatures with tight adaptive corruptions and more[END_REF], but then the obtained IBS would not produce short signatures). The second one is to transform a 2-level hierarchical IBE (HIBE) [START_REF] Gentry | Hierarchical ID-based cryptography[END_REF] tightly to an IBS scheme [START_REF] Kiltz | Identity-based signatures[END_REF].

Overcoming these difficulties, Pan and Wagner gave in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] the first identity-based signature scheme with tight security from lattices, and we build upon their construction by improving on it in several ways. They give two constructions, based on either SIS [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF] (unstructured lattices) or Ring-SIS [START_REF] Micciancio | Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worstcase complexity assumptions[END_REF] (structured lattices), which are two assumptions believed to be quantum-safe. The latter one offers better efficiency. Their signatures are short, meaning that they contain only a constant number of elements, with a size independent of the message length. They use the Micciancio-Peikert (MP) trapdoor technique [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] and the Bonsai tree technique [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF].

They first give a generic transformation trans from a non-adaptive IBS to an adaptive one. They use the known transformation for digital signature schemes [START_REF] Krawczyk | Chameleon signatures[END_REF] using (R)SIS-based chameleon hash [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF][START_REF] Ducas | Improved short lattice signatures in the standard model[END_REF] and extend it to the IBS setting ([26, Theorem 1]). They also give a version in the ROM ([26, Theorem 2]), which is more efficient.

Then, they construct a non-adaptive IBS proved in the ROM and in the QROM, assuming the (R)SIS assumption is hard. In a nutshell, the master public key is a random matrix A such that the (R)SIS assumption holds, the master secret key is a MP trapdoor T A for A [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], the identity secret key for id is a trapdoor of (A∥H 1 (id)) obtained through T A using the trapdoor delegation operation of MP and a signature of a tuple (id, µ) is a small vector z computed using the trapdoor such that (A∥H 1 (id)∥H 2 (id, µ)) z = 0, where H 1 and H 2 are simulated as random oracles in the security proof. This finally gives rise to an adaptive IBS in the ROM, and an adaptive IBS in the QROM assuming chameleon hash. In the proof, the adversary has to output the lists AskedSk and AskedSign of secret key queries and signing queries before receiving the master public key (since the scheme is non-adaptive). The key points are that, by programming the random oracles H 1 and H 2 , the reduction can embed a MP trapdoor into both (A∥H 1 (id)) and (A∥H 1 (id)∥H 2 (id, µ)) for all elements of these lists, while the other values are programmed on the form Ax for x small elements, allowing to construct a SIS solution, with high probability, for any valid signature on (id * , µ * ) not queried by A. The programming being indistinguishable by A from random output. This implies that the reduction does not need to guess the forgery (id * , µ * ), making it tight.

While preparing the final version of this paper, we came across a concurrent paper [START_REF] Wang | Identity-based matchmaking encryption with stronger security and instantiation on lattices[END_REF], which also improves the protocol of [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] as one of their contributions, by getting rid of one delegation as we do here. But as compared to our article, they only improve the non-adaptive scheme, only in the ROM case and only based on SIS. As opposed to them, we give here further improvements: We fix some flaws in the proof of [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], propose other choices of distributions, consider QROM and RSIS, lower the number of hash calls needed when applying the transformation from EUF-CMA to EUF-naCMA on it, and give a practical instantiation with concrete parameters.

Our Contributions. In this article, we improve on the work of Pan and Wagner [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] in several ways. We give here an informal description of these improvements and provide a technical overview in Section 2 for the interested reader.

We prove the generic transformation from non-adaptive to adaptive IBS of [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] in the QROM, making it unnecessary to rely on chameleon hashes in this case, we also provide a proof of this transformation in the strong security setting. We use a former reprogramming result restated in Proposition 6. Our protocols are thus more modular: all the intermediate results (reprogramming lemmas) are proved both in ROM and QROM. Furthermore, we improve the transformation by reducing the number of hash functions to 2 instead of 4, making the final scheme simpler and more efficient.

The set of parameters used is easier, since we harmonize the value of the modulus to q = 3 k in both structured and unstructured case, as opposed to [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] which used q prime in the latter case. The main interest is to simplify the use of the MP trapdoor generation algorithms [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], and in particular to get a simpler gadget matrix (of the form [I n 3I n . . . 3 k-1 I n ] in the unstructured case). This comes at the cost of a more difficult proof for the smoothness lemma (Lemma 1).

We make an effort to be "concrete" and avoid universal constants and asymptotic parameters, giving parameters in Tables 6 and7. Note that the two former improvements can be directly applied to the scheme given in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], which enables us to compare both schemes fairly.

Our scheme is simpler thanks of the use of a non-homogeneous equation for the signature. With the same notations as above, a signature of a tuple (id, µ) is a small vector z such that (A∥H 1 (id)) z = H 2 (id, µ) (as compared to (A∥H 1 (id)∥H 2 (id, µ)) z = 0), again obtained using the trapdoors of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]. This has two consequences. First, the signature has fewer coordinates. Then, this allows us to manage to avoid the use of one trapdoor delegation operator DelTrap in Sign, that only consist on a sole application of SampleD. Indeed, we now use the secret matrix to sample the vector z following a discrete Gaussian distribution, meaning that we can reuse the trapdoor of the secret matrix whereas the scheme in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] uses a more complex concatenated matrix, forcing them to delegate one more time a trapdoor. This is obtained at the cost of a more difficult proof, especially in the QROM case. More precisely, we give thinner reprogramming lemmas, of independent interest (see Section 4.4). Another improvement of these lemmas is that we do not always reprogram using a Gaussian distribution, but rather a uniform distribution on {-1, 0, 1} whenever it is possible. In particular, to obtain the result in the structured case, we give an improved version of Regev's claim [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]Claim 5.3] for more general distributions, in Lemma 18, that is applied in Proposition 1 for our case.

Keeping in mind that one DelTrap operation roughly corresponds to k SampleD operations, a first consequence of this simplification is that the time complexity of our signature scheme is at least k times better. Experimentally, this leads to a scheme at least 65 times faster for the same parameters assuming a 128-bit security for our scheme.

A second consequence is that the security we obtain is better, because we get a smaller (R)SIS bound. This implies that the parameters we need to obtain 128-bit security only yields 37-bit security for their improved scheme.

A third consequence is that the signatures generated by our schemes are way shorter than the ones generated in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], because the use of only one trapdoor delegation yields to a smaller standard deviation for the signature, and that we have k fewer coordinates for the signature by design. Experimentally, this leads to a signature half as big, if we use the same parameters for both schemes. If we consider the same security for both schemes, we even get signatures and keys five times smaller than theirs.

Other contributions of independent interest. We highlight a few contributions made for this article that could be used in other contexts: -We give an extended version of Regev's claim [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]Claim 5.3], proven for more general distributions and in a module setting. It is stated and proved in Lemma 18. -We generalize the reprogramming lemma [START_REF] Boneh | Random oracles in a quantum world[END_REF]Lemma 3] in Proposition 7, in order to replace a quantum random oracle by a bounded number of distributions that are close to the random distribution. In the initial lemma, there were only two possible distributions. -We introduce a lemma applicable to a wide class of indistinguability games, that allows to separate the study of classic and quantum calls to the quantum random oracle, provided the classic calls are made first. It is stated and proved in Section B.5. -We prove different results regarding the infinity norm of the minimum of (some) unstructured q-lattices with q power of a prime, in Appendix B.3 . Then, we use it to prove a variation of the smoothness lemma [15, Lemma 5.2] for q-ary lattices with q being a power of 3. -We show a simple characterization of (some) invertibles of R q for q being a power of 3, in Appendix B.2. -To simulate distributions obtained with delegated trapdoors, Proposition 5 and Proposition 4 (such as their counterparts for the structured case, in Appendix B.9) are implicitly used in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] and needed in our scheme. They have an important role to ensure the ability to simulate the correct distributions to an adversary against a scheme without master secret key. They are described in Section 4.

Acknowledgements. This work was supported in part by the French ANR projects CryptiQ (ANR-18-CE39-0015) and SecNISQ (ANR-21-CE47-0014). Pierrick Méaux was supported by the ERC Advanced Grant no. 787390.

Technical Overview

We focus here on the scheme based on the SIS assumption, the ideas being similar for the scheme based on RSIS.

Following [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], we proceed in two steps: first a generic transformation from an EUF-naCMA IBS scheme to an EUF-CMA scheme and then the construction of an EUF-naCMA IBS scheme.

Generic Transformation.

In [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], the authors show that, using a chameleon hash or in the ROM, the non-adaptive security of an IBS scheme can be tightly transformed into adaptive security.

This implies that the only way to get a scheme secure against a quantum adversary is to use both chameleon hashes and other hash functions simulated as quantum random oracles in the proof. In this article, we extend this generic transformation to the QROM with a compatible-with-ROM case proof, using some adaptive reprogramming results of [START_REF] Grilo | Tight adaptive reprogramming in the QROM[END_REF] (restated in Proposition 6).

We can then apply this transformation to our scheme, yielding to a scheme proved in the sole QROM. Furthermore, it is possible to factor these hash functions to reduce their number from four to two, which allows getting a scheme in which fewer queries to hash functions are made.

IBS with Non-Adaptive Security.

In order to exploit the transformation described above, we construct a (weaker) non-adaptively secure IBS scheme, in which an adversary has to commit its user secret key queries and signing queries before receiving the master public key. This weaker security gives rise to a tight construction since in the security proof, the adversary's user secret key queries and signing queries are known in advance. It is thus possible to tightly embed in the reduction the SIS instances in the forgery without having to guess anything.

Description of the Scheme. Similarly to [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], our scheme uses the trapdoor setup of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] that allows to: -Instantiate a trapdoor: create a couple of matrix and trapdoor (A, T A ), where A looks random (meaning that its statistical distance with the uniform distribution is negligible). -Delegate a trapdoor: for any matrix A ′ and trapdoor T A of A, "delegate" the trapdoor T A into a trapdoor T ′ A of (A∥A ′ ), that reveals no information about T A . -Perform Gaussian sampling: for any A, trapdoor T A of A, vector u and sufficiently big s, create x following a discrete Gaussian distribution and verifying Ax = u. Furthermore, the lower bound of s is linear in the singular value of T A , up to a negligible term. Each of these operations is in correspondence with one of the algorithms of our IBS: -The master public key A ∈ Z n×m q and secret key T A ∈ Z (m-nk)×nk q correspond to the matrix and trapdoor created by the trapdoor instantiation.

-The creation of a secret key for an identity id is done by delegating the trapdoor

T A ∈ Z m×nk q of A into a trapdoor of T id of (A∥H 1 (id)) ∈ Z n×(m+nk) q , for H 1 with values in Z n×nk q .
-The signature of a message µ with sk id = T id corresponds to the Gaussian sampling of a vector z such that (A∥H 1 (id))z = H 2 (µ), for H 2 with values in Z n q .

The main difference of our scheme as compared to that of [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] is that their signing algorithm requires one more trapdoor delegation operation before doing the Gaussian sampling relatively to this new trapdoor, which explains the better values for parameters and security for our scheme.

More precisely, to sign a message µ for an identity id of secret key T id , their scheme requires delegating T id into a trapdoor T id,µ of (A∥H 1 (id)∥H 2 (id, µ)) (H 2 with values in Z n×nk q in their scheme), then using T id,µ to make a Gaussian sampling of a small vector z such that

(A∥H 1 (id)∥H 2 (id, µ))z = 0
This makes their signature bigger, on the one hand because it contains an additional component and on the other hand because it uses a bigger delegated matrix T ′′ A , because of the double delegation. This double delegation also has an impact on the SIS bound in their reduction, which is smaller for our scheme. Finally, the additional delegation operation augments the time complexity of their signature, that can be estimated as at least k time slower than ours, as explained in Section 8.1.

Idea of the Proof. Our tight proof follows the same blueprint for QROM and ROM. We denote the list of all identities id for user secret key queries as AskedSk, and the list of all identity-message pairs (id, µ) for signing queries as AskedSign. An adversary A has to output these two lists before receiving the master public key. The key step in our proof is that, by programming the random oracles H 1 and H 2 , it is possible to simulate the EUF-naCMA game for a random A (without the secret key T A ) by hiding the signatures and secret identity keys in the hash values. More precisely, the idea is to embed a trapdoor T id (i.e. a secret key for identity id) into the values H 1 (id) for id ∈ AskedSk and a signature of (id, µ), for the values H 2 (µ, id) for all (µ, id) ∈ AskedSign.

Moreover, for any īd / ∈ AskedSk, ( ĩd, μ) / ∈ AskedSign, we program H( īd) = ARī d and H( ĩd, μ) = Az id,µ for some small random matrix Rī d and vector zid,µ . Note that we use different distributions than [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], which contributes to lower the size of the SIS bound. Thus, a valid signature z * = (z * 1 , z * 2 ) of A for a couple of identity and message (id, µ) such that id / ∈ AskedSk, (µ, id) / ∈ AskedSign leads to an SIS solution x = z * 1 + R id * z * 2 -z id * ,µ * provided that x ̸ = 0, because, by definition of the signature verification, Az * 1 + H 1 (id)z * 2 z = H 2 (µ). Finally, we ensure that x = 0 does not happen more than half of the time by using an indistinguishability technique of [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF].

Preliminaries

The non-negative integers, integers and reals are respectively denoted by N, Z, and R. Unless stated otherwise, we always assume q = 3 k and d = 2 u with k, u ∈ N * . Matrices are written as bold capital letters and vectors as low-case bold letters. Vectors should be understood as column vectors. For a, b ∈ R, we define a, b = [a, b] ∩ Z. For S ⊂ R n , we denote by Span(S) ⊂ R n the R-vector space generated by S. For x ∈ R n , we denote by ∥x∥ its Euclidean norm. For a predicate P, we define P = 1 if P is true and 0 otherwise.

A function f (n) is negligible, written f (n) = negl(n), if ∀c ∈ N, f (n) = o(n -c
). We denote log the logarithm in base 2 and log b the logarithm in a base b ∈ R * ≥0 . For m ∈ N * , ϵ > 0, we define r m,ϵ = ln (2m(1 + 1/ϵ)) /π . Modular arithmetic. For any even (resp. odd) p ∈ N * and any x ∈ Z p , we will denote by x mod ± p the unique representative in -p/2, p/2 (resp. -(p -1)/2, (p -1)/2 ). We extend this definition to vectors and matrices entry-wise. For x ∈ Z p , we define |x| := |x mod ± p|. For any p, n, m ∈ N * and A = (a i,j ) ∈ Z n×m p , we define ∥A∥ 1 = i,j |a i,j |, ∥A∥ = i,j |a i,j | 2 , ∥A∥ ∞ = max i,j |a i,j |. We extend this definition to vectors, considered as matrices with one column.

The Ring R q . We will work in R = Z[X]/(X d +1) and R q = Z q [X]/(X d +1) for d a power of 2. We define S R = { d-1 i=0 a i X i ∈ R : (a 0 , . . . , a d-1 ) ∈ {-4, 0, 4} d/4 ×{-1, 0, 1} d/2 ×{-4, 0, 4} d/4 } ⊂ R. We will consider it as a subset of R 3 k for all k ≥ 2. For a ∈ R, we will denote by Cf(a) ∈ Z d the vector whose coordinates are the coefficients of a and Rot(a) ∈ Z d×d the matrix whose lines are Cf(a) , Cf(Xa) , . . . , Cf X d-1 a . We extend this definition for matrix A ∈ R n×m , that leads to Cf(A) ∈ Z n×dm and Rot(A) ∈ Z dn×dm . We also extend this definition modulo q by Cf(A mod q) := Cf(A) mod q.

General Probabilities. In this article, we only consider discrete probability distributions. If Dist is a probability distribution, x ←$ Dist denotes that x is sampled from Dist. The support of a probability distribution is the set of x such that Pr[Dist = x] > 0. Unless specified otherwise, all the probability distributions we work with have finite support. If S is a set, x ←$ S means that x is sampled uniformly in S and U (S) denote the uniform distribution on S. For sets S ⊂ X and Dist a probability distribution with values in X, we denote by Dist |S the probability distribution x ←$ Dist conditioned to x ∈ S. For two probability distributions Dist, Dist ′ with support in a set X, we define their statistical distance SD Dist, Dist ′ = 1 2 x∈X

Pr[Dist = x] -Pr Dist ′ = x .
To help the reading of the article, some generic results about statistical distance are stated in Appendix A.1. For r ∈]0, 1[, we denote by P r the probability distribution such that Pr[P r = 0] = r, Pr[P r = -1] = Pr[P r = 1] = (1-r)/2. Finally, we denote by P R,1/2 the probability distribution

4P d/4 1/2 × P d/2 1/2 × 4P d/4 1/2 with support S R . Lattices. A lattice of dimension k ∈ N is a Z-submodule Λ ⊂ R k that is finitely generated. It is said full rank if Span(Λ) = R k . A R-lattice of dimension k is defined as a R-submodule of Λ ⊂ R k .
Note that a R-lattice of dimension k becomes a lattice of dimension kd under Cf. We will often identify R-lattices with their associated lattice through Cf and call them (structured) lattices. For A ∈ Z n×k q , u ∈ Z n q , B ∈ R n×k q , v ∈ R n q , we define the following full-rank lattices

Λ q (A)={x ∈ Z n : ∃ s, x=As mod q}, Λ ⊥ u,q (A) := {x ∈ Z k : Ax=u mod q} , Λ R,q (B)={x ∈ R n : ∃ s, x=Bs mod q}, Λ ⊥ v,R,q (B)={x ∈ R k : Bx=v mod q} .
We write Λ ⊥ q (A) (resp Λ ⊥ R,q (B)) if u = 0 (resp. v = 0). The dual Λ * of a full rank lattice Λ of dimension k is the set of all v ∈ R k such that x ⊤ v ∈ Z for all x ∈ Λ. We have qΛ ⊥ q (A) * = Λ q (A ⊤ ). SIS and RSIS problems. Consider n, m, β, q ∈ N * × N * × R × N * . The SIS n,m,β,q problem is defined as follows: for A ←$ Z n×m q , find z ∈ Z m q such that Az = 0 mod q and ∥z∥ ≤ β. The RSIS n,β,q problem is defined as follows: for A ←$ R 1×n q , find z ∈ R n q such that Az = 0 mod q and ∥z∥ ≤ β.

The SIS and RSIS problems are assumed to be hard to solve for quantum adversaries (e.g. [START_REF] Peikert | A decade of lattice cryptography[END_REF]).

Discrete Gaussian Distribution. For x ∈ R n , s > 0, we define ρ s (x) = exp -π∥x∥ 2 /s 2 . For a lattice Λ ⊂ R n , c ∈ R n and s > 0, the discrete Gaussian distribution D Λ+c,s 2 is the probability distribution with support Λ + c such that, for all x ∈ Λ + c, D Λ+c,s (x) is proportional to ρ s (x). When Λ + c ⊂ Z n , we have D Λ+c,s = D n Z,s |Λ+c . For a R q -lattice Λ ⊂ R n q , c ∈ R n q and s > 0 the Gaussian distribution over Λ, denoted by D Λ,c,s , is defined as Cf -1 (D Cf(Λ),Cf(c),s ). For example, D R,c,s = Cf -1 (D d Z,Cf(c),s ). For ϵ > 0, the smoothing parameter of a lattice Λ of dimension n, denoted by η ϵ (Λ), is the smallest s such that ρ 1/s (Λ * -{0}) ≤ ϵ. The smoothing parameter of a R-lattice Λ is defined as η ϵ (Cf(Λ)).

Adversary, games and oracles. PPT stands for "probabilistic polynomial time". We denote by Adv G A the advantage of an adversary A in game G. If the game is applied to a scheme S, we write Adv G A,S or Adv G A if it is clear from context. We denote by A H (resp. A |H⟩ ) an adversary A that can make classic (resp. quantum) queries to a hash function H. For an oracle with possible input x and for an element y, we denote by O x→y the oracle defined by O x→y (z) = y if z = x and O(z) otherwise.

Identity-based signature schemes and security. An Identity-Based Signature (IBS) scheme is a tuple of PPT algorithms IBS = (Setup, KeyExt, Sign, Verify) such that: -(mpk, msk) ← Setup() outputs a master public key and master private key.

sk id ← KeyExt(mpk, msk, id) outputs a secret key for identity id.

σ ← Sign(mpk, sk id , µ) outputs a signature for a message µ and identity id.

b ∈ {0, 1} ← Verify(mpk, σ, µ, id) is deterministic. The scheme IBS is (ξ 1 , ξ 2 )-complete if for all mpk, msk, id, µ, we have P r (mpk,msk)←Setup() P r Verify(mpk, σ, µ, id) = 1 : sk id ← KeyExt(mpk, msk, id),

σ ← Sign(mpk, sk id , µ) ≥ 1 -ξ 1 ≥ 1 -ξ 2 .
The usual security notion for IBS is Existential Unforgeability under Chosen Message Attack (EUF-CMA) (adaptive or non-adaptive), we depict the corresponding security game in Figure 1. We also define the notion of strong Existential Unforgeability. For Q Corr , Q S ∈ N * , we measure the EUF-CMA (resp. sEUF-CMA) security of a scheme IBS against an adversary A that can obtain Q Corr identity secret keys and Q S signatures by the advantage Adv

EUFCMA IBS Q Corr ,Q S A := Pr 1 ← EUFCMA IBS Q Corr ,Q S (A) (resp. Adv sEUFCMA IBS Q Corr ,Q S A := Pr 1 ← sEUFCMA IBS Q Corr ,Q S (A) )
. Note that the signatures and keys can be adaptively queried in EUFCMA IBS Q Corr ,Q S , we speak of adaptive security. We will speak of strong security when using sEUF-CMA or sEUF-naCMA.

EUFCMA IBS Q Corr ,Q S /sEUFCMA IBS Q Corr ,Q S (A) 1 : (mpk, msk) ← Setup() 2 : cpt C := 0, cpt S := 0 3 : AskedSk ← ∅, AskedSign ← ∅, sAskedSign ← ∅ 4 : (id * , µ * , σ * ) ← A O Corrupt ,
AskedSk := AskedSk ∪ {id} cpt C := cpt C + 1 sk id ← KeyExt(mpk, msk, id) return sk id EUFnaCMA IBS Q Corr ,Q S /sEUFnaCMA IBS Q Corr ,Q S (
Fig. 1. EUFCMA IBS Q Corr ,Q S /sEUFCMA IBS Q Corr ,Q S and EUFnaCMA IBS Q Corr ,Q S /sEUFnaCMA IBS Q Corr ,Q S games.
For Q Corr , Q S ∈ N * , we measure the EUF-naCMA (resp. sEUF-naCMA) security against an adversary A that can obtain Q Corr identity secret keys and Q S signature by the advantage

Adv EUFnaCMA IBS Q Corr ,Q S A := Pr 1 ← EUFnaCMA IBS Q Corr ,Q S (A) (resp. by the advantage Adv sEUFnaCMA IBS Q Corr ,Q S A := Pr 1 ← sEUFnaCMA IBS Q Corr ,Q S (A)
). Note that the signatures and keys have to be queried at the beginning in EUFnaCMA IBS Q Corr ,Q S (resp. sEUFnaCMA IBS Q Corr ,Q S ), we speak of non-adaptive security. Singular values and bounds on singular values. The singular value s 1 (A) of a matrix A ∈ R n×m is defined by sup x̸ =0 ∥Ax∥ ∥x∥ . We extend the definition of singular values of matrices with coefficients in R to matrices with coefficients in R by taking s 1 (A) := s 1 (Cf(A)).

Preliminary results

In this section we recall notions and provide technical results that are necessary to prove the security of the generic transformation in Section 5 and IBS schemes in Section 6 and Section 7.

Results on statistical distance

For the security of the IBS scheme, we will use a game-based proof where the statistical distance between uniform distributions and other distributions are crucial for the main argument of the proof. We define these distributions and bound their probability of being close to the uniform distribution. More precisely, Proposition 1 contains results inspired of [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]Claim 5.3] regarding the leftover hash lemma, we generalize this result and prove it in Appendix B.6. Then, Lemma 1 states variations of smoothness [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Lemma 5.2] for the structured and unstructured case with q = 3 k .

For s > 0, m, n, k, l ∈ N, A ∈ Z n×m q , B ∈ R 1×l q , we define: -D k Z,s,A the probability distribution that outputs AR for R ←$ D n×k Z,s and D k R,s,B the probability distribution that outputs BR for R ←$ D n×k R,s (we omit k in the notation if k = 1). -U A the probability distribution that outputs Ax, where x ←$ {-1, 0, 1} m and U R,B the probability distribution that outputs Bx where x ←$ S l R and -P A the probability distribution that outputs Ax, where x ←$ P m 1/2 and P R,B the probability distribution that outputs Bx, where

x ←$ P l R,1/2 . Proposition 1 (Proof in Appendix B.6.). Let m, n, k, l ∈ N, q = 3 k , with k ≥ 4, m ≥ 2nk
and l ≥ max(2k, 21). Then, P r

A∈Z n×m q SD U Z n q , U A > q -n 4 ≤ q -n 4 , P r A∈R 1×l q SD U (R q ) , U R,A > q -d 4 ≤ q -d 4 , P r A∈Z n×m q SD U Z n q , P A > q -0.196n ≤ q -0.196n , P r A∈Z n×m q AZ m q ̸ = Z n q ≤ q n(2k-1) 4k , P r A∈R 1×l q SD U (R q ) , P R,A > q -0.196d ≤ q -0.196d , P r A∈R 1×l q AR l q ̸ = R q ≤ q -d(k-1) 2k . Lemma 1 (Smoothness lemma. Proof in Appendix B.3.). Let n, m, k ∈ N, q = 3 k , m ≥ 2nk. Let ϵ ∈]0, 1/2[ and s ∈ R such that s ≥ 12r m,ϵ . Then, Pr A∈Z n×m q SD D s,A , U Z n q > 2ϵ ≤ 2q -n/4 . (1)
Let d a power of 2, 2k + k/2 ≥ l > 2k and s ≥ 12r ld,ϵ . Then,

Pr A∈R 1×l q SD D s,A , U (R q ) > 2ϵ ≤ q -d/4 + 3 -d (2k-l) 2 ≤ 2 * 3 -d (2k-l) 2 .
(2)

Singular values of random matrix

Let C = 8e 1+2/e ln(9)/ √ π < 38 and f (m, n) = √ m + 2π C √ n + m ln(3) . We will use s 1 (Unif)[n, m] := 2/3f (m, n), s 1 (Gauss)[n, m, s] := s √ 2π f (m, n), and s 1 (Binom)[n, m, r] := (1 -r)f (m, n).
Corollary 1 (Corollary of [START_REF] Genise | Improved discrete gaussian and subgaussian analysis for lattice cryptography[END_REF]Theorem 6.1] and Lemma 8,proof

in Appendix B.1.). Let n, m, k ∈ N, q = 3 k . Let s ∈]0, 1[, a ∈ Z * . Then Pr R←$U({-a,0,a} n×m ) [s 1 (R) ≤ as 1 (Unif)[n, m]] ≥ 1 -2 * 3 -m , Pr R←$D n×m Z,s [s 1 (R) ≤ as 1 (Gauss)[n, m, s]] ≥ 1 -2 * 3 -m , Pr R←$P n×m r [s 1 (R) ≤ as 1 (Binom)[n, m, r]] ≥ 1 -2 * 3 -m .
This can be applied in the ring case, by sampling from the distributions U (S R ), D R,s and P R,r . Note that in order to find an upper bound for U (S R ) and P R,r , the corollary needs to be applied with respectively products of U ({-4, 0, 4}) and products of 4P r .

Lattice trapdoors

The IBS schemes presented in the article follow the framework of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] using trapdoor delegation. In this part we recall the results necessary to instantiate the framework, and prove the adaptations for the cases we consider. More precisely, we use Proposition 2 to instantiate the trapdoor used to create the master key. Note that we use the binomial distribution instead of the Gaussian one in [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] for compactness. Then, we use Proposition 3 to delegate trapdoors and perform Gaussian sampling, to create respectively the secret keys of identities and signatures. Finally, we give two propositions (Proposition 4, Proposition 5) necessary for the simulation in the game-based proof, and motivated by the identity-based property of the signature scheme.

Let g = (1, 3, . . . ,

3 k-1 ) ∈ R k and G = [I n 3I n . . . 3 k-1 I n ] ∈ Z n×nk . A G-trapdoor of a matrix A ∈ Z n×m q is a matrix T A ∈ Z (m-nk)×nk q such that A -T A I nk = G mod q. A g-trapdoor of a matrix A ∈ R 1×l q is a matrix T A ∈ R (l-k)×k q such that Rot(T A ) ∈ Z d(l-k)×dk q is a G-trapdoor of Rot(A) ∈ Z d×dl q
. Equivalently, using the definition and properties6 of Rot,

A -T A I k = g mod q. Proposition 2 (Statistical instantiation of trapdoors (adapted from [25, Section 5.2])). Let n, m, k ∈ N * , q = 3 k , m ≥ 2kn. Let Trap(n, m, q) the algorithm that samples A ←$ Z n×(m-nk) q , T A ←$ P (m-nk)×nk 1/2
and outputs A := A∥G -AT A , T A . Then, T A is a Gtrapdoor of A, and A is distributed with statistical distance at most nkq -0.196n of the uniform distribution.

Proof. A direct computation shows that T A is a G-trapdoor of A. The statistical distance upper bound comes from Proposition 1.

Proposition 3 (Gaussian Sampling and Delegation of trapdoors (adapted from [25, Section 5])). Let n, m, k ∈ N * , q = 3 k , m ≥ 2kn. Let 0 < ϵ < 1/2. There exists algorithms DelTrap, SampleD such that, for A ∈ Z n×m q , T A ∈ Z (m-nk)×nk q a G-trapdoor and s ≥ r nk,ϵ 11 s 1 (T A ) 2 + 1 , we have:

-SampleD(A, u, T A , s) returns z such that Az = u and the statistical distance between the probability distribution of z and

D Λ ⊤ q,u (A),s is bounded by a function γ Sample n,m,ϵ which is negligible if ϵ is. -DelTrap(A ∈ Z n×m , T A ∈ Z (m-nk)×nk , A ′ ∈ Z n×nk , s) returns a G-trapdoor of [A∥A ′ ] (the output T ′ A ∈ Z m×nk satisfies AT ′ A = A ′ -G). Moreover, the probability distribution of the output T ′ A is at statistical distance less than nkγ Sample n,m,ϵ of the distribution D m×nk Z,s with output R conditioned to AR = A ′ -G. More precisely, if we denote by (u 1 ∥u 2 ∥ • • • ∥u nk ) the columns of A ′ -G, the k th column of T ′ A is computed as SampleD(A, u k , T A , s).
The next proposition will be used to replace some instances of KeyExt (that correspond to Dist ModKExt ) by another algorithm that does not use the master secret key (T A ), of probability distribution Dist SimModKExt . Note that the proposition allows making multiple replacements of Dist SimModKExt by Dist ModKExt for the same, fixed, pair of master public and secret keys (output of Dist KExt ). This is important because the adversary of EUFnaCMA IBS Q Corr ,Q S can ask for multiple secret keys of identities in one instance of the game -this can be easily overlooked when applying the framework of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], designed with simple signature schemes in mind which involve only one pair of keys, to identity-based signature schemes.

Proposition 4 (Simulation of delegation of trapdoors. Proof in Appendix

B.7.). Let n, m, k ∈ N * , q = 3 k , m ≥ 2kn. Let s > 0, A ∈ Z n×m and T A ∈ Z (m-nk)×nk q a G-trapdoor of A. We define Dist ModKExt (A, T A , s) as (A ′ , T ′ A ) : R ←$ D m×nk Z,s , A ′ := AR + G, T ′ A ← DelTrap A, T A , A ′ , s ,
and Dist SimModKExt (A, s) as

(A ′ , R) : R ←$ D m×nk Z,s , A ′ := AR + G . Then, if s ≥ √ 11r nk,ϵ s 1 (Binom)[m -nk, nk, 1/2] 2 + 1, we have P r (A,T A )←Trap(n,m,q) SD(Dist ModKExt (A, T A , s), Dist SimModKExt (A, s)) ≤ nkγ Sample n,m,ϵ ≥ 1 -2q -n .
The next proposition shows that the probability distribution of the signatures (Dist Sign ) made with a secret key created by KeyExt (of probability distribution Dist KExt ) is close to a Gaussian distribution (D m+nk Z,s

). This will be useful to show the completeness of the IBS scheme, and also to replace signatures by Gaussian outputs in the proof of Theorem 2. The proposition allows studying multiple signatures for the same secret key, in a situation where a couple of public and master keys (output of Dist KExt ) has been taken, and multiples secret keys of identities have been created. This is crucial because the adversary of EUFnaCMA IBS Q Corr ,Q S can ask for multiple signatures, made by multiple secret keys of identities in one instance of the game.

Proposition 5 (Proof in Appendix B.7.). Let n, m, k ∈ N * , q = 3 k , m ≥ 2kn. For s > 0, s > 0, A ∈ Z n×m , A ′ ∈ Z n×nk and T ′ A ∈ Z m×nk a G-trapdoor of [A∥A ′ ]. We define Dist KExt (A, T A , s) := (A ′ , T ′ A ) : A ′ ←$ Z n×nk q , T ′ A ← DelTrap A, T A , A ′ , s , Dist Sign (A, A ′ , T ′ A , s) = {z : z ← SampleD([A∥A ′ ], u, T ′ A , s), u ←$ Z n q } , ν 1 := 2q -n + nk(2ϵ + γ Sample n,m,ϵ ) + √ 2q -n/8 = negl(n) , ν 2 := 2nkq -0.196n + 4q -n/4 + √ 2q -n/8 = negl(n) . Then, for s ≥ max √ 11r nk,ϵ s 1 (Binom)[m -nk, nk, 1/2] 2 + 1, 12r m,ϵ and
s ≥ max √ 11r nk,ϵ s 1 (Gauss)[m, nk, s] 2 + 1, 12r m+nk,ϵ , we have P r (A,T A )←$Trap(n,m,q) P r (A ′ ,T ′ A )←$Dist KExt (A,T A ,s) SD(Dist Sign (A, A ′ , T A , s), D m+nk Z,s ) ≤ γ Sample n,m+nk,ϵ ≥ 1 -ν 1 ≥ 1 -ν 2 . (3)
The ring equivalent to Proposition 4 is stated and proved in Appendix B.7.

The R q versions of the functions Trap, SampleD, DelTrap are denoted by Trap R , SampleD R , DelTrap R and the ring equivalent of Propositions 2,3,4 are stated and proved in Appendix B.9.

Hash reprogramming in the ROM and the QROM

This section gives two generic lemmas that enable the reprogramming of a hash function, in both the ROM and the QROM (the latter requiring more effort).

The first one is one of the main results of [START_REF] Grilo | Tight adaptive reprogramming in the QROM[END_REF], it deals with the tedious problem of adaptive hash reprogramming in the QROM, for specific situations where only a chunk of the input is controlled by the adversary; the other chunk being chosen uniformly at random. It will be of great use for the ROM and the QROM reductions from

EUFCMA IBS Q Corr ,Q S to EUFnaCMA IBS Q Corr ,Q S of Section 5.
The second one is a generalization of [5, Lemma 3], that allows the challenger to replace the value H(x), by the output of probability distributions Dist i close (in statistical distance) to the uniform distribution. The probability distribution used depending on which set X i contains x, for (X i ) i a partition of the input set, with a bounded number of elements. It will be used for the proof of the EUF-naCMA security of the schemes.

Proposition 6 ([17, Proposition 1], with added ROM case). Let consider m, n ∈ N * , X = {0, 1} m , Y = {0, 1} n and A = (A 1 , A 2 , A 3 ) be any algorithm issuing at most R queries to ReprogramOracleOne and Q quantum queries to O b as defined in Figure 2. Then, it can be shown that the advantage defined by 1 2

|Pr[1 ←$ AdaptReprog 0 (A)] -Pr[1 ←$ AdaptReprog 1 (A)]| is upper bounded by 3R 4 Q |X 1 | . If the queries to O b are classical, the upper bound becomes Q R |X 1 | .
Proof. We assume that for each Dist ∈ S dist , SD(U (Y ) , Dist) ≤ ϵ. We consider the game NoAdaptReprog of Figure 3, with some fixed parameter P ∈ N * . Then, for any quantum adversary A = (A 1 , A 2 , A 3 ) such that A 2 make less than Q c classical queries to H b and A 3 less than Q q queries to |H b ⟩, we have,

The
AdaptReprog b (A) O0 ←$ Y X 1 ×X 2 O1 := O0 ORACLES = {|O b ⟩, ReprogramOracleOne} b ← A ORACLES return b ReprogramOracleOne(x2) (x1, y) ←$ X1 × Y O1 := O (x 1 ∥x 2 )→y 1 return x1
Adv NoAdaptReprog A := Pr[1 ← NoAdaptReprog(A) | b = 1 ] - 1 2 ≤ Q c ϵ + 4Q 2 q √ P ϵ .
5 Generic transformation from EUF-naCMA (resp. sEUF-naCMA) to EUF-CMA security (resp. sEUF-CMA) in the ROM and the QROM

In [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] the authors exhibit two tight transformations from non-adaptive to adaptive IBS schemes:

-With chameleon hash functions [26, Figure 2].

-With hash functions in the ROM [26, Figure 5], as described in Figure 4.

NoAdaptReprog (A) P = (Xi) i∈ 1,p , (Disti) i∈ 1,p ⊂ S dist , |aux⟩ ← A1()
with p ≤ P and In this section we prove that the transformation of Figure 4 is also secure in the QROM. Moreover, the proof is modular, it also applies to the ROM. Afterwards, the transformation will be used to prove the security in the ROM and the QROM of our schemes IBS Z (Figure 5) and IBS R (Section 7, Figure 7) respectively linked to non-adaptive IBS schemes IBS NA,Z (Figure 6) and IBS NA,R (Section 7, Figure 8). We also show that this transformation work in the strong security setting, but this will not be used to prove the security of our schemes. Finally, note that the transformation does not modify the completeness.

P partition of X for x ∈ X then H0(x) ←$ Y for i ∈ 1, p then for x ∈ Xi then H1(x) ←$ Disti(x) b ←$ {0, 1} |aux2⟩ ← A H b 2 P, (Disti) i , |aux⟩ b ← A |H b ⟩ 3 P, (Disti) i , |aux2⟩ return b = b
Theorem 1 (Adaptive security of adapt(IBS) in the ROM and the QROM provided IBS is non-adaptively secure, with or without strong security). We assume that SetId = {0, 1} τ id , SetMess = {0, 1} τmess for τ id ,

τ mess ∈ N * . Let Q Corr , Q S ∈ N * . For a, b, Q ∈ N * , we denote by FindCol Q (a, b) Q the game
FindColMess such that Adv GameSign adapt(IBS) Q Corr ,Q S A is upper bounded by Adv GamenaSign IBS Q Corr ,Q S C + 3 * 2 -τnonce+4 2 Q Hash id (Q Corr + Q S ) + Q Hashmess Q S + Adv FindColId B id + Adv FindColMess Bµ .
Remark 1. Using [32, Theorem 3.1], we know that there exists a universal constant C coll such that the advantage Adv FindColId B id + Adv FindColMess Bµ can be upper bounded by

C coll 2 -τ id (Q Hash id + Q S + Q Corr + 1) 3 + 2 -τmess (Q Hashmess + Q S + 1) 3 . If all queries are classical, Adv GameSign adapt(IBS) Q Corr ,Q S A is upper bounded by Adv GamenaSign IBS Q Corr ,Q S C + 2 -τnonce (Q Hash id + 1)(Q Corr + Q S ) + (Q Hashmess + 1) Q S + 2 -τ id (Q Hash id + Q S + Q Corr + 1) + 2 -τmess (Q Hashmess + Q S + 1) .
Proof. We sum up the changes between games in Table 1.

Hop

Change Security loss From G 0 = GameSign

G 0 to G 1 Prohibition of some colli- sions. ROM 2 -τ id (Q Hash id + 1) (Q Corr + Q S ) + 2 -τ mess (Q Hash mess + 1)Q S QROM Adv FindColId B id + Adv FindColMess B µ G 1 to G 2 Reprogramming of hash function when O Sign or O Corrupt is queried. ROM 2 -τ nonce (Q Hash id (Q Corr + Q S ) + Q Hash mess Q S ) QROM 2 -τ nonce +4 2 3 Q Hash id (Q Corr + Q S ) + Q Hash mess Q S G 2 to G 3
adapt(IBS) Q Corr ,Q S to G 1 :
We denote by (σ * = (t * , s * , σ * ), id * , µ * ) the output of A. We abort the game if one of these two events happens

fail 1 := "∃(r, id) ∈ NoncesSk : Hash id (r, id) = Hash id (t * , id * )" , fail 2 := "∃(t, id, s, µ) ∈ NoncesSign : (t, id, s, µ) ̸ = (t * , id * , s * , µ * ) ∧ Hash id (t, id) = Hash id (t * , id * ) ∧ Hash mess (s, µ) = Hash mess (s * , µ * )" .
Where NoncesSk (resp. NoncesSign) contains the nonces and identities asked to and created by the oracle O Corrupt (resp. nonces, messages and identities asked to and created by the oracle O Sign ). Note that (t * , id * , s * , µ * ) ∈ NoncesSign can led to a valid forgery only in the strong case. In the QROM case, we can create B, playing the game of finding a collision on Hash id or Hash mess . B uses an adversary A against GameSign adapt(IBS) Q Corr ,Q S in order to: -Find a collision on Hash id if A wins and fail 1 is realized. B uses at most Q Hash id + Q Corr + Q S queries to Hash id .

-Find a collision on Hash id or Hash mess if A wins and fail 2 is realized. B uses at most Q Hashmess + Q S queries to Hash mess . Using B, we can then create two adversaries B id and B µ that respectively play to FindColId and FindColMess, and such that the advantage of B is bounded by Adv FindColId

B id + Adv FindColMess Bµ .
We give a better bound in the ROM case than the bound for a collision by noticing that the collisions founds are specific. Indeed, The collision with Hash id (resp. Hash mess ) is searched with the constraint that one of the two elements is on the set NoncesSk (resp. a set linked to NoncesSign) of Q Corr + Q S (resp. Q S ) elements while the other is not and can be found using Q Hash id + 1 (resp. Q Hashmess + 1) Hash queries (the "+1" is for the case where the value is output by the adversary without being queried). The advantage is bounded by 2 -τ id (Q

Hash id + 1) (Q Corr + Q S ) (resp. 2 -τmess (Q Hashmess + 1)Q S ). G 1 to G 2 :
We use the reprogramming algorithm of Proposition 6 for Hash id when O Sign or O Corrupt is queried and for Hash mess when O Sign is queried. For example, when the reprogramming oracle for Hash mess is queried for a message µ, a nonce s is uniformly sampled in {0, 1} τnonce and the Hash value Hash mess (s, µ) is programmed to a uniform value of SetMess.

A double application of Proposition 6 shows that Adv

G 1 A -Adv G 2 A is upper bounded by 2 -τnonce+4 2 3 Q Hash id (Q Corr + Q S ) + Q Hashmess Q S if the hash queries are quantum and 2 -τnonce (Q Hash id (Q Corr + Q S ) + Q Hashmess Q S ) if they are classical. G 2 to G 3 :
In this game, the identities and messages that are sampled by the reprogramming oracles for H 1 and Hash mess are precomputed at the beginning of the game. It is thus possible to precompute the secret keys of identities and signatures computed by O Corrupt and O Sign . The advantage suffers no loss since the distribution of each of these elements remains the same.

Reduction from GamenaSign IBS Q Corr ,Q S to G 3 :
We use the fact that the signatures and keys of O Corrupt and O Sign are precomputed in G 3 to create an adversary C of the

GamenaSign IBS Q Corr ,Q S of IBS that uses A.
Thanks to the event fail 1 and fail 2 that were added in G 1 , we observe that C wins the

GamenaSign IBS Q Corr ,Q S game for IBS each time that A wins G 3 . Thus, Adv G 3 A ≤ Adv GamenaSign IBS Q Corr ,Q S C .
6 IBS Scheme in the ROM and the QROM, based on SIS

The scheme is defined in Figure 5. The parameters and the conditions they must follow are summarized in Table 2.

Setup(n, m) (A, T A ) ← Trap(n, m, q) return (A, T A ) KeyExt(A, T A , id) r ←$ {0, 1} τnonce T id ← DelTrap A, T A , H1(r, id), s id return (r, T id )
Sign(mpk, (r, id, T id ), µ)

s ←$ {0, 1} τnonce u ← H2 (r, s, id, µ) z ← SampleD [A∥H1(r, id)] ,
T id , u, s sign return (r, s, z)

Verify (mpk, id, µ, (r, s, z)) if z = 0 ∨ [A∥H1(r, id)] z ̸ = H2(r, s, id, µ) then return 0 / / z = (z 1 , z 2 ) ∈ Z m q × Z nk q return ∥z1∥ ≤ Bound1 ∧ ∥z2∥ ≤ Bound2 Fig. 5. Scheme IBS Z .
The proof of completeness will use the tail inequality.

Notation Description q := 3 k modulus, power of 3 for k ∈ N, k ≥ 1

SetId Set of identities, of the form {0, 1} τ id for some integer τ id SetMess Set of messages, of the form {0, 1} τmess for some integer τmess SetNonces Set of nonces, of the form {0, 1} τnonce for some integer τnonce n, m number of rows and columns of A ∈ Z n×m q , m ≥ 2nk ϵ used in rx,ϵ = ln (2x(1 + 1/ϵ)) /π , we take ϵ = ϵ(n) = negl(n) H1, H2 hash functions with respective values in Z n×nk q and Z n q s id , s sign standard deviations, with

s id ≥ max √ 11r nk,ϵ s1(Binom)[m -nk, nk, 1/2] 2 + 1, 12rm,ϵ . s sign ≥ max √ 11r nk,ϵ s1(Gauss)[m, nk, s id ] 2 + 1, 12r m+nk,ϵ .
Bound1 bound of ∥z1∥ for signatures z=(z1, z2) Lemma 2 (Tail inequality (e.g. [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF])). Let m ∈ N, σ > 1. Then,

∈ Z m q ×Z nk q , Bound1 ≥ √ 2m s sign Bound2 bound of ∥z2∥ for signatures z=(z1, z2) ∈ Z m q ×Z nk q , Bound2 ≥ √ 2nk s sign
Pr z←$D m Z,σ ∥z∥ > √ 2mσ < 2 -m 4 .
Proposition 8 (completeness). Consider the scheme IBS Z with the parameters of Table 2.

Then,

IBS Z is (ξ 1 , ξ 2 )-complete with ξ 1 = 2q -n +nk(2ϵ+γ Sample n,m,ϵ )+4 √ 2q -n/8 +2 -(nk-1) 4 = negl(n), and ξ 2 = nkq -0.196n + 4q -n/4 + √ 2q -n/8 = negl(n).
Proof. Direct consequence of Proposition 5 and Lemma 2 that shows that P r

(z 1 ,z 2 )←$D m Z,s sign ×D nk Z,s sign ∥z 1 ∥ > √ 2ms sign ∨ ∥z 2 ∥ > √ 2nkσ < 2 -m 4 + 2 -nk 4 < 2 -(nk-1)

4

.

From adaptive security to non-adaptive security. In this part we show the adaptive security of the scheme IBS Z (Figure 5). It consists in three steps. First, we prove the EUF-naCMA property of the scheme IBS NA,Z in Theorem 2 of Section 6. Then, the EUF-naCMA property of IBS NA,Z implies the EUF-CMA property of adapt(IBS NA,Z ) through Theorem 1. Finally, Proposition 9 proves that the EUF-CMA property of adapt(IBS NA,Z ) implies the EUF-CMA property of IBS Z .

Setup(n, m)

(A, T A ) ← Trap(n, m, q) return (A, T A ) KeyExt(A, T A , id) T id ← DelTrap A, T A , H1(id), s id return (id, T id )
Sign(mpk, (id, T id ), µ)

u := H2(id, µ) z ← SampleD [A∥H1(id)] ,
T id , u, s sign return z

Verify(mpk, id, µ, z) Proposition 9 (EUF-CMA security of adapt(IBS Z ) implies the security of IBS Z . ). Let Q Corr , Q S ∈ N and A a PPT adversary of EUFCMA IBS Z Q Corr ,Q S (Figure 5) that makes

if z = 0 ∨ [A∥H1(id)] z ̸ = H2(id, µ) then return 0 / / z = (z 1 , z 2 ) ∈ Z m q × Z nk q return ∥z1∥ ≤ Bound1 ∧ ∥z2∥ ≤ Bound2
Q Corr queries to O Corrupt , Q S queries to O Sign , Q H 1 quantum (resp. classical) queries to H 1 and Q H 2 quantum
(resp. classical) queries to H 2 . Then, there exists a PPT adversary B of EUFCMA

adapt(IBS Z ) Q Corr ,Q S that makes Q H 1 quantum (resp. classical) queries to H 1 , Q H 2 quantum (resp. classical) queries to H 2 , 2(Q H 1 + Q H 2 ) quantum (resp. Q H 1 + Q H 2 classical
) queries to Hash id , and 2Q H 2 quantum (resp.

Q H 2 classical) queries to Hash mess , such that Adv EUFCMA IBS Z Q Corr ,Q S A = Adv EUFCMA adapt(IBS Z ) Q Corr ,Q S B .
Proof. We can see the functions H1 (r, id) := H 1 (Hash id (r, id)) H2 (r, s, id, µ) := H 1 (Hash id (r, id), Hash mess (s, µ)) , are functions if H 1 , H 2 , Hash id , Hash mess are. The adversary B can then use the random functions H1 and H2 for the game that is playing A. This is sufficient to conclude if A make classical queries.

If A make quantum queries, we furthermore need to show that B can simulate queries to Non-adaptive security in the ROM and the QROM. The non-adaptive security of IBS NA,Z is, as for the IBS scheme of [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], an "IBS version" of the proof of the signature scheme of [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF], with the added difficulty of dealing with delegated trapdoors. It is made in two steps: -The first step consists in replacing EUFnaCMA IBS NA,Z Q Corr ,Q S , in an indistinguishable way for the adversary A, by a game G 5 that does not use the trapdoor T A and where A is uniform. It is done by reprogramming H 1 and H 2 , to give outputs indistinguishable from a random function, but that contain "planted" trapdoors, enabling the challenger to respond to secret key and signature queries. Here, we need a more subtle method than the one used in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF]: it was using [5, Lemma 3], which corresponds to a particular case of Proposition 7 with partitions of size 2. However, in our games, the size of the partitions is only bounded by Q IdSign + 1 where Q IdSign is the number of distinct identities for which the adversary queries a signature. Also note that, contrary to [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] that uses distributions of the form D Z,s,A for reprogramming, we use reprogramming with U A whenever it is possible.

|H 1 (Hash id (•, •))⟩ and |H 1 (Hash id (•, •), Hash mess (•, •))⟩ using queries to |H 1 ⟩, |H 2 ⟩,
-The second step is a reduction from SIS to G 5 that is similar to what is done in [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF] and [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF].

Note that we find a better SIS bound than [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF], partly thanks or use of U A for the reprogramming.

Theorem 2 (EUF-naCMA security of IBS NA,Z ). Consider a set of parameters respecting the conditions listed in such that Adv

EUFnaCMA IBS NA,Z Q Corr ,Q S A is upper bounded by 2Adv SIS n,m,Bound SIS ,q B 1 -q -n +4Q 2 H 1 √ 2nkmx+4Q 2 H 2 Q IdSign +1 √ mx + λ CO (n) +Q Corr nk mx+γ Sample n,m,ϵ +Q S γ Sample n,m+nk,ϵ +nk(2ϵ+γ Sample n,m,ϵ )+4q -n/8 +(nk+2)mx +Q IdSign 2q -n 4 +mx +5nkq -0.196n +11q -n 4 + 4q -n 1 -q -n ,
where γ Sample n,m,ϵ is negligible (defined in Section 4.3) and λ CO (n) is negligible and is due to the use of compressed oracles ([33]). If the queries to Q H 1 and Q H 2 are classical, first line of the upper bound becomes 2 1-q -n Adv

SIS n,m,Bound SIS ,q B + Q H 1 nkmx+Q H 2 mx. Hop Change Security loss G 0 to G 1 Reprogramming of H 1 . ROM: (Q H 1 + Q Corr ) nkmx + nkq -0.196n + 3q -n/4 QROM: Q Corr nkmx + 4Q 2 H 1 √ 2nkmx + nkq -0.196n + 3q -n/4 G 1 to G 2 Reprogramming of H 2 . ROM: (Q H 2 + Q S ) mx + Q IdSign (2q -n/4 + mx) + nkq -0.196 QROM: Q S mx + 4Q 2 H 2 (Q IdSign + 1)mx +Q IdSign (2q -n/4 + mx) + nkq -0.196 G 2 to G 3 T A no more used for O Corrupt queries. Q Corr nkγ Sample n,m,ϵ + 2q -n G 3 to G 4 T A no more used for O Sign queries. Q S γ Sample n,m+nk,ϵ + nk(2ϵ + γ Sample n,m,ϵ ) + 4q -n/8 +(1 + nk)mx + 2nkq -0.196n + 6q -n/8 G 4 to G 5 A is taken uniformly. nkq -0.196n
Minoration of advantage of last game:

ROM: Proof. We sum up the changes between games in Table 3.

Adv G 5 A ≤ 2 1-q -n Adv SIS n,m,Bound SIS ,q B + 4q -n 1-q -n QROM: Adv G 5 A ≤ 2 1-q -n Adv SIS n,m,Bound SIS ,q B + 4q -n 1-q -n + λ CO (n)
From G 0 = EUFnaCMA IBS NA,Z Q Corr ,Q S to G 1 : In G 1 , the probability distribution of outputs of H 1 , U Z n×nk q
, is replaced by D nk Z,s id ,A + G for id ∈ AskedSk and U nk A else. Moreover, we abort if the matrix A is sampled in the set

fail 1 = A : SD D Z,s id ,A , U Z n q > ϵ ∨ SD U A , U Z n q > q -n/4 .
Using Lemma 1, Proposition 1 and Proposition 2 we see that Pr[fail 1 ] ≤ nkq -0.196n + 3q -n/4 . Moreover, when fail 1 is not realized, we have

SD D nk Z,s id ,A + G, U Z n×nk q = SD D nk Z,s id ,A , U Z n×nk q ≤ 2nkϵ , SD U nk A , U Z n×nk q ≤ nkq -n/4 . Proposition 7 implies that Adv G 0 A -Adv G 1
A is less than the upper bound indicated in Table 3. From G 1 to G 2 : In G 2 , the probability distribution of outputs of H 2 , U Z n q , is replaced by D Z,s sign ,(A∥H 1 (id)) for (id, µ) ∈ AskedSign and U A else. Moreover, with the notation IdAskedForSign = {id ∈ SetId : ∃µ ∈ SetMess, (id, µ) ∈ AskedSign}, so |IdAskedForSign| = Q IdSign , we abort if the event fail 2 happens, where

fail 2 = ∃id ∈ IdAskedForSign : SD D Z,s sign ,(A∥H 1 (id)) , U Z n q > 2ϵ .
We will use Proposition 7 with the size of partitions bounded by Q IdSign + 1. We note that Pr[fail

2 : A ← Trap(n, m, q) ∧ H 1 as in G 1 ] is upper bounded by Pr ∃id ∈ IdAskedForSign, SD D Z,s sign ,(A∥H 1 (id)) , U Z n q > 2ϵ: A←Trap(n,m,q) H 1 as in G 1 ≤ Pr ∃id ∈ IdAskedForSign, SD D Z,s sign ,((A∥H 1 (id)) , U Z n q > 2ϵ: A←$Z n×m q ∀id : H 1 (id)←$Z nk q + Q IdSign mx + nkq -0.

We can then apply Proposition 7 to deduce that Adv

G 1 A -Adv G 2
A is less than the upper bounds indicated in Table 3. From G 2 to G 3 : In G 3 , for id ∈ AskedSk, the secret key sk id , is defined as the value R id of H 1 (id) := AR id + G, instead of being created by DelTrap. Using Proposition 4, we conclude that

Adv G 2 A -Adv G 3 A ≤ Q Corr nkγ Sample n,m,ϵ + 2q -n . From G 3 to G 4 :
In game G 4 , for (id, µ) ∈ AskedSign, the signatures z id,µ , are defined as the z used to create the hash value H 2 (id, µ) = [A|H 1 (id)]z, instead of being computed by Sign applied to a secret key computed with KeyExt. Thus, the probability distribution of a signature is now D m+nk Z,s sign . Using Proposition 5 and the definitions of fail 1 and fail 2 , we conclude that Adv

G 3 A -Adv G 4
A is less than the upper bound indicated in Table 3.

From G 4 to G 5 :' We replace the A made by Trap by a matrix A ←$ Z n×m q . This is possible because the trapdoor T A is not used in G 4 . We use Proposition 2 to conclude that Adv G 4 A -Adv G 5 A ≤ nkq -0.196n . From G 5 to SIS n,m,Bound SIS ,q : Thanks to the definition of G 5 , we can simulate an instance of G 5 to A from an instance A of the SIS n,m,Bound SIS ,q problem. Note that in order to make the simulation in polynomial time, A cannot precompute all the possibles values of H 1 , H 2 as the challenger do. In the ROM, A can simply make lazy evaluation, by computing the values only when they are queried. In the QROM, A can use the compressed oracle technique of [33] in order to efficiently simulate the Hash functions. More precisely: -Except for a polynomial number of values that can be precomputed, H 1 (id) can be computed as A H 1 (id) with a random oracle H 1 : SetId → {-1, 0, 1} m×nk simulated by a compressed oracle.

-Except for a polynomial number of values that can be precomputed, H 2 (id) can be computed as A H 2 (id) with a random oracle H 2 : SetId → {-1, 0, 1} m simulated by a compressed oracle. Using [33, Lemma 5], we see that the advantage of A with this simulation can only be increased by a function λ CO (n) negligible in n.

Suppose A wins an instance of the game with the answer (z * = (z * 1 , z * 2 ), id * , µ * ). This implies that

[A | H 1 (id)]z * = H 2 (id * , µ * ), ∥z * 1 ∥ ≤ Bound 1 , ∥z * 2 ∥ ≤ Bound 2 , id * /
∈ AskedSk and (id * , µ * ) / ∈ AskedSign. Thus: -There exists R id * which has been sampled uniformly in {-1, 0, 1} m×nk such that H 1 (id) = AR id . -There exists z id * ,µ * which has been sampled uniformly in {-1, 0, 1} m such that H 2 (id, µ) = Az id * ,µ * . This implies that A z * 1 + R id * z * 2 -z id * ,µ * = 0. Moreover, using Corollary 1 and the bounds on z * 1 , z * 2 , we know that with a probability less than at least 1 -2q -n on R id * , we have

z * 1 + R id * z * 2 -z id * ,µ * ≤ ∥z * 1 ∥ + s 1 (R id * ) ∥z * 2 ∥ + z id * ,µ * ≤ Bound 1 + s 1 (Unif)[m, nk] Bound 2 + √ m = Bound SIS . If z * 1 + R id * z * 2 ̸ = z id * ,µ * ,
it is a valid solution of the SIS problem. We show that, for an overwhelming number of A, the case where z * 1 + R id * z * 2 = z id * ,µ * happens with lower probability than the previous case, which implies that the attack fails with probability at most 1/2. Assume that z * 1 + R id * z * 2 = z id * ,µ * . From the point of view of A, the instance of the game G 5 it is playing is identical for each zid * ,µ * ∈ {-1, 0, 1} m such that Az id * ,µ * = Az id * ,µ * . Moreover, Lemma 21 shows that, with a probability more that 1 -q -n in z id * ,µ * , an element zid * ,µ * ∈ {-1, 0, 1} m , z id * ,µ * ̸ = zid * ,µ * , such that Az id * ,µ * = Az id * ,µ * , could have been taken with the same probability as z id * ,µ * for the computation of H 2 (id, µ). Such an element would satisfy z * 1 + R id * z * 2 ̸ = zid * ,µ * . Therefore, from the point of view of the adversary, the probability that z

* 1 + R id * z * 2 ̸ = z id * ,µ * is at least 1/2. We conclude that Adv SIS n,m,Bound SIS ,q B is more than 1-q -n 2 Adv G 5
A + 2q -n in ROM, and more than 1-q -n 2 Adv G 5

A + 2q -n + λ CO (n) in QROM, which leads to the upper bound indicated in Table 3.

IBS Scheme in ROM and the QROM, based on RSIS

The scheme is defined in Figure 7. The parameters and the conditions they must follow are on Table 4.

Setup(n, m) (A, T A ) ← Trap R (l, q) return (A, T A ) KeyExt(A, T A , id) r ←$ {0, 1} τnonce T id ← DelTrap R (A, T A , H1(r, id), s id ) return (r, T id ) Sign(mpk, (r, id, T id ), µ) s ←$ {0, 1} τnonce u ← H2 (r, s, id, µ) z ← SampleD R [A∥H1(r, id)] ,
T id , u, s sign return (r, s, z)

Verify (mpk, id, µ, (r, s, z)) if z = 0 ∨ [A∥H1(r, id)] z ̸ = H2(r, s, id, µ) then return 0 / / z = (z 1 , z 2 ) ∈ R l q × R k q return ∥z1∥ ≤ BoundR,1 ∧ ∥z2∥ ≤ BoundR,2

Notation

Description q := 3 k modulus, power of 3 for k ∈ N, k ≥ 4

SetId Set of identities, of the form {0, 1} τ id for some integer τ id SetMess Set of messages, of the form {0, 1} τmess for some integer τmess SetNonces Set of nonces, of the form {0, 1} τnonce for some integer τnonce l number of columns of the matrix A ∈ R 1×l q , 2k + k/2 ≥ l > max(2k, 21) ϵ used in rx,ϵ = ln (2x(1 + 1/ϵ)) /π , we take ϵ = ϵ(d) = negl(d) H1

hash function 1, with values in R 1×k q H2 hash function 2, with values in Rq s id standard deviation,

s id ≥ max √ 11r dk,ϵ 16ds1(Binom)[l -k, dk, 1/2] 2 + 1, 12r dl,ϵ .
s sign standard deviation,

s sign ≥ max √ 11r dk,ϵ ds1(Gauss)[l, dk, s id ] 2 + 1, 12r d(l+k),ϵ .
BoundR,1 bound of ∥z1∥ for signatures z=(z1, z2) ∈ R l q ×R k q , BoundR,1 ≥ √ 2dls sign BoundR,2 bound of ∥z2∥ for signatures z=(z1, z2) ∈ R l q ×R k q ,BoundR,2 ≥ √ 2dks sign Table 4. Parameters of IBSR and required conditions.

The proof of completeness will use the tail inequality.

Lemma 3 (Tail inequality, ring case (e.g. [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF])). Let l ∈ N, σ > 1, then

Pr z←$D l R,σ ∥z∥ > √ 2dlσ < 2 -dl 4 .
Proposition 10 (completeness). Consider the scheme IBS R with the parameters of Table 4.

Then, it is (ξ 1 , ξ 2 )-complete with ξ 1 = k(2ϵ + γ Sample d,dl,ϵ ) + 3 -d (2k-l) 4 + 3 2 + 2 -(dk-1)

4

= negl(d) and

ξ 2 = 2kq -0.196d + 3 -d (2k-l) 4 +3 = negl(d).
Proof. Direct consequence of Proposition 21 and Lemma 3 that shows that P r

(z 1 ,z 2 )←$D l R,s sign ×D k R,s sign ∥z 1 ∥ > √ 2ldσ ∨ ∥z 2 ∥ > √ 2dkσ < 2 -dl 4 + 2 -dk 4 < 2 -(dk-1)

4

.

From adaptive security to non-adaptive security.

Setup()

(A, T A ) ← Trap R (l, q) return (A, T A ) KeyExt(A, T A , id) T id ← DelTrap R A, T A , H1(id), s id return (id, T id )
Sign(mpk, (id, T id ), µ)

u := H2(id, µ) z ← SampleD R [A∥H1(id)] ,
T id , u, s sign return z

Verify(mpk, id, µ, z) Proposition 11 (EUF-CMA security of adapt(IBS R ) implies the EUF-CMA security of IBS R ). Consider a set of parameters with the conditions indicated in Table 4. Let Q Corr , Q S ∈ N and A a PPT adversary of EUFCMA IBS R Q Corr ,Q S (Figure 7) that makes Q H 1 quantum (resp. classical) queries to H 1 and Q H 2 quantum (resp. classical) queries to H 2 . Then, there exists an adversary B of EUFCMA

if z = 0 then return 0 if [A∥H1(id)] z ̸ = H2(id, µ) then return 0 / / z = (z 1 , z 2 ) ∈ R l q × R k q return ∥z1∥ ≤ BoundR,1 ∧ ∥z2∥ ≤ BoundR,2
adapt(IBS R ) Q Corr ,Q S that makes Q H 1 quantum (resp. classical) queries to H 1 , Q H 2 quantum (resp. classical) queries to H 2 , 2(Q H 1 + Q H 2 ) quantum (resp. Q H 1 + Q H 2 classi- cal) queries to Hash id , and 2Q H 2 quantum (resp. Q H 2 classical) queries to Hash mess , such that Adv EUFCMA IBS R Q Corr ,Q S A = Adv EUFCMA adapt(IBS R ) Q Corr ,Q S B .
Proof. Proof is similar to the proof of Proposition 9.

Non-adaptive Security in the ROM and the QROM. Theorem 3 (EUF-naCMA security of IBS NA,R ). Consider a set of parameters with the conditions indicated in Table 4. Let Q Corr , Q S ∈ N and A a PPT adversary of EUFnaCMA

IBS NA,R Q Corr ,Q S that makes Q H 1 quantum queries to H 1 , Q H 2 quantum
queries to H 2 and such that the signature queries are made for Q IdSign distinct identities. Let also, take Bound RSIS = Bound R,1 + 4 √ ds 1 (Unif)[l, dk] Bound R,2 + 17/2 √ ld and mx = max(2ϵ, q -d/4 ) = negl(d). Then, there exists a PPT adversary B of RSIS l,Bound RSIS ,q such that Adv

EUFnaCMA IBS NA,R Q Corr ,Q S A is upper bounded by 2Adv RSIS l,Bound RSIS ,q B 1 -q -d + 4Q 2 H 1 √ 2kmx + 4Q 2 H 2 Q IdSign + 1 √ mx + λ CO (dl) +Q Corr k mx+γ Sample d,dl,ϵ +5kq -0.196d +3 (-d 2k-l 4 +4) +Q IdSign 2 * 3 -d (2k-l) 2 + mx + Q S γ Sample d,d(k+l)ϵ + k(2ϵ + γ Sample d,dl,ϵ ) + 3 -d (2k-l) 4 + 3 2 + (k + 2)mx + 4q -d 1 -q -d ,
where γ Sample d,dl,ϵ is negligible (defined in Section B.9) λ CO (dl) is negligible and is due to the use of compressed oracles ([33]).

If the queries to Q H 1 and Q H 2 are classical, the upper bound becomes

2Adv RSIS l,Bound RSIS ,q B 1 -q -d + Q H 1 kmx + Q H 2 mx +Q Corr k mx+γ Sample d,dl,ϵ +5kq -0.196d + 3 (-d 2k-l 4 +4) +Q IdSign 2 * 3 -d (2k-l) 2 + mx + Q S γ Sample d,d(k+l)ϵ + k(2ϵ + γ Sample d,dl,ϵ ) + 3 -d (2k-l) 4 + 3 2 + (k + 2)mx + 4q -d 1 -q -d .
Proof. We sum up the changes between games in Table 5.

Hop

Change Security loss

G 0 to G 1 reprogramming of H 1 . ROM: (Q H 1 + Q Corr ) kmx + kq -0.196d + 3 -d (2k-l) 2 +1 QROM: Q Corr kmx + 4Q 2 H 1 √ 2kmx + kq -0.196d + 3 -d (2k-l) 2 +1 G 1 to G 2 reprogramming of H 2 . ROM: (Q H 2 + Q S ) mx + Q IdSign (2 * 3 -d (2k-l) 2 + mx) + kq -0.196d QROM: Q S mx + 4Q 2 H 2 (Q IdSign + 1)mx +Q IdSign (2 * 3 -d (2k-l) 2 + mx) + kq -0.196d G 2 to G 3 T A no more used for O Corrupt queries. Q Corr kγ Sample d,dl,ϵ + 2q -d G 3 to G 4 T A no more used for O Sign queries. Q S γ Sample d,d(k+l)ϵ + k(2ϵ + γ Sample d,dl,ϵ ) + 3 -d (2k-l) 4 + 3 2 +(k + 1)mx + 2kq -0.196d + 3 -d 2k-l 4 +3 . G 4 to G 5 A is taken uniformly. kq -0.196d
Minoration of advantage of last game: From G 0 = EUFnaCMA

ROM: Adv G 5 A ≤ 2 1-q -d Adv RSIS l,Bound RSIS ,q B + 4q -d 1-q -d QROM: Adv G 5 A ≤ 2 1-q -d Adv RSIS l,Bound RSIS ,q B + 4q -d 1-q -d + λ CO (dl)
IBS NA,R Q Corr ,Q S to G 1 : In G 1 , the probability distribution of outputs of H 1 , U R 1×k q , is replaced by D k R,s id ,A + G for id ∈ AskedSk and U k R,A else. Moreover, we abort if A is sampled in the set fail 1 = A : SD D R,s id ,A , U (R q ) > ϵ ∨ SD U R,A , U (R q ) > q -d/4 .
Using Lemma 1, Proposition 1 and Proposition 18 we see that Pr[fail 1 ] ≤ kq -0.196d + 3 -d (2k-l) 2 +1 . Moreover, when fail 1 is not realized, we have

SD D k R,s id ,A + G, U R 1×k q = SD D k R,s id ,A , U R 1×k q ≤ 2kϵ , SD U k R,A , U R 1×k q ≤ kq -d/4 . Proposition 7 implies that Adv G 0 A -Adv G 1 A is less than in the ROM: (Q H 1 + Q Corr ) kmx + kq -0.196d + 3 -d (2k-l) 2 +1 , in the QROM: Q Corr kmx + 4Q 2 H 1 √ 2kmx + kq -0.196d + 3 -d (2k-l) 2 +1 .
From G 1 to G 2 : In G 2 , the probability distribution of outputs of H 2 , U (R q ), is replaced by D R,s sign ,(A∥H 1 (id)) for (id, µ) ∈ AskedSign and U R,A else. Moreover, with notation IdAskedForSign = {id ∈ SetId : ∃µ ∈ SetMess, (id, µ) ∈ AskedSign}, so |IdAskedForSign| = Q IdSign , we abort if the event fail 2 happens, where

fail 2 = ∃id ∈ IdAskedForSign : SD D s sign ,(A∥H 1 (id)) , U (R q ) > 2ϵ .
We use Proposition 7 with the size of partitions bounded by Q IdSign + 1. We note that

Pr[fail 2 : A ← Trap R (l, q) ∧ H 1 programmed as in G 1 ] = Pr ∃id ∈ IdAskedForSign : SD D R,s sign ,(A∥H 1 (id)) , U (R q ) > 2ϵ : A←Trap R (l,q) H 1 as in G 1 ≤ Pr ∃id ∈ IdAskedForSign : SD D R,s sign ,(A∥H 1 (id)) , U (R q ) > 2ϵ : A←$R n×m q ∀id : H 1 (id)←$R k q + Q IdSign mx + kq -0.
196d by definition of fail 1 and Proposition 18

≤ Q IdSign (2 * 3 -d (2k-l) 2
+ mx) + kq -0.196d by Corollary 5.

We can then apply Proposition 7 to deduce that Adv

G 1 A -Adv G 2 A is less than in the ROM: (Q H 2 +Q S ) mx+Q IdSign (2 * 3 -d (2k-l) 2 +mx)+kq -0.196d , in the QROM: Q S mx+4Q 2 H 2 (Q IdSign +1)mx+Q IdSign (2 * 3 -d (2k-l) 2 +mx)+kq -0.196d .
From G 2 to G 3 :

In G 3 , for id ∈ AskedSk, the secret key sk id , instead of being created by DelTrap R , is defined as the value

R id of H 1 (id) := AR id + G. Using Proposition 20, we conclude that Adv G 2 A -Adv G 3 A ≤ Q Corr kγ Sample d,dl,ϵ + 2q -d . From G 3 to G 4 :
In game G 4 , for (id, µ) ∈ AskedSign, the signatures z id,µ , instead of being computed by Sign applied to a secret key computed with KeyExt, are now being defined as the z used to create the hash value H 2 (id, µ) = [A|H 1 (id)]z. Thus, the probability distribution of a signature is now D l+k R,s sign . Using Proposition 21 and the definitions of fail 1 and fail 2 , we conclude that Adv

G 3 A -Adv G 4
A is less than the upper bound indicated in Table 5. From G 4 to G 5 : We replace the A made by Trap by a matrix A ←$ R 1×l q . This is possible because the trapdoor T A is not used in G 4 . We use Proposition 2 to conclude that

Adv G 4 A -Adv G 5 A ≤ kq -0.196d .
From G 5 to RSIS l,Bound RSIS ,q : Thanks to the definition of G 5 , we can simulate an instance of G 5 to A from an instance A of the RSIS l,Bound RSIS ,q problem. Note that in order to make the simulation in polynomial time, A cannot precompute all the possibles values of H 1 , H 2 as the challenger do. In the ROM, A can simply make lazy evaluation, by computing the values only when they are queried. In the QROM, A can use the compressed oracle technique of [33] in order to efficiently simulate the Hash functions. More precisely: -Except for a polynomial number of values that can be precomputed, H 1 (id) can be computed as Aϕ( H 1 (id)) with a random oracle H 1 : SetId → {-1, 0, 1, 2} dl×k simulated by a compressed oracle and ϕ defined coordinate by coordinate, that act as identity except on 2 that is sent to 0, which models that 0 is obtained twice as often as -1 and 1.

-Except for a polynomial number of values that can be precomputed, H 2 (id) can be computed as Aψ( H 2 (id)) with a random oracle H 2 : SetId → {-1, 0, 1, 2} dl simulated by a compressed oracle and ψ, defined coordinate by coordinate as in the previous item. Using [33, Lemma 5], we see that the advantage of A with this simulation can only be increased by a function λ CO (dl) negligible in dl.

Suppose A wins an instance of the game with the answer (z * = (z * 1 , z * 2 ), id * , µ * ). This implies that

[A | H 1 (id)]z * = H 2 (id * , µ * ), ∥z * 1 ∥ ≤ Bound R,1 , ∥z * 2 ∥ ≤ Bound R,2 , (4)
and id * / ∈ AskedSk, (id * , µ * ) / ∈ AskedSign. Thus: -There exists R id * that has been sampled uniformly in S l×k R such that H 1 (id) = AR id .

-There exists z id * ,µ * that has been sampled uniformly in

S l R such that H 2 (id, µ) = Az id * ,µ * . We write z * = (z * 1 , z * 2 ) ∈ R m q × R k q . Equation (4) becomes A z * 1 + R id * z * 2 -z id * ,µ * = 0.
Moreover, using Corollary 1 and Proposition 15, we know that with a probability less that at least 1 -2q -d on R id * , we have

z * 1 + R id * z * 2 -z id * ,µ * ≤ ∥z * 1 ∥ + √ ds 1 (R id * ) ∥z * 2 ∥ + z id * ,µ * ≤ Bound R,1 + 4 √ ds 1 (Unif)[l, dk] Bound R,2 + √ dl 17/2 = Bound RSIS ,
where we use

S l R ≤ d(l/2)(4 2 + 1) = √ dl 17/2. If z * 1 + R id * z * 2 ̸ = z id * ,µ * ,
it is a valid solution of the RSIS problem. We show that, for an overwhelming number of A, the case where z * 1 + R id * z * 2 = z id * ,µ * happens with lower probability than the previous case, which implies that the attack fails with probability at most 1/2. Assume that z * 1 + R id * z * 2 = z id * ,µ * . From the point of view of A, the instance of the game G 5 it is playing is identical for each zid * ,µ * ∈ S l R such that Az id * ,µ * = Az id * ,µ * . Moreover, Lemma 22 shows that, with a probability more that 1 -q -d in z id * ,µ * , an element zid * ,µ * ∈ S l R , z id * ,µ * ̸ = zid * ,µ * , such that Az id * ,µ * = Az id * ,µ * , could have been taken with the same probability as z id * ,µ * for the computation of H 2 (id, µ). Such an element would satisfy z * 1 + R id * z * 2 ̸ = zid * ,µ * . Therefore, from the point of view of the adversary, the probability that z

* 1 + R id * z * 2 ̸ = z id * ,µ * is at least 1/2. We conclude that Adv RSIS l,Bound RSIS ,q B is more than 1-q -d 2 Adv G 5 A -2q -d in ROM and more than 1-q -d 2 Adv G 5
A -2q -d + λ CO (dl) in QROM, which leads to the upper bound indicated in Table 5.

Conclusion 8.1 Parameters (proof of concept) and discussion

We propose parameters to give a rough idea of the efficiency of our IBS scheme. The parameters are not optimized; the main motivation of this proof of concept is to observe the impact of the tight reduction on concrete parameters. We describe the principle behind our parameter selection in the following. First, we only study IBS R since it will be more efficient than IBS Z for the same security. Then, we reduce the study of IBS R to the study of IBS NA,R since the tightness of the transformation between IBS R and IBS NA,R provides only negligible changes of size (only nonces are added, that is, less than 1Ko) and of speed (only hash evaluations are added). It also allows us to directly compare with the non-adaptive scheme IBS NA,PW [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF]Figure 8]. Finally, we take into account the experimental estimations of C (Section 4.2) made in [START_REF] Genise | Improved discrete gaussian and subgaussian analysis for lattice cryptography[END_REF]Section 6] in order to set C = 1 2π or 1 4π depending on the distribution. More precisely, we make the comparison with an improved version IBS + NA,PW of IBS NA,PW , where coefficients of the master secret key T A are sampled with P R,1/2 , as in our scheme (this method was already suggested for the unstructured case in [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] as an example of "statistical instantiation"), and setting l = 2k + 2 instead of l ≥ 2⌈log(q)⌉ + 2 as in our scheme.

We present in Table 6 two sets of parameters, each one giving 128 bits of security for one of the two schemes. Table 7 displays the sizes and security related to the schemes IBS NA,R and IBS + NA,PW for these two sets of parameters. We include in Appendix E the script we use to compute sizes and security bounds for the two schemes, and summarize the principle in the following. Regarding RSIS concrete security against a quantum adversary, we use the security estimation scripts of [START_REF] Ducas | Github repository pq-crystals/security-estimates[END_REF] whose initial aim was to assess the security of Kyber [START_REF] Avanzi | CRYSTALS-Kyber[END_REF] and Dilithium [START_REF] Ducas | CRYSTALS-Dilithium -algorithm specifications and supporting documentation (version 3.1)[END_REF] schemes. For IBS NA,R the parameters values and security bounds directly come from Table 4 and Theorem 3 while the sizes are found by direct computation. For IBS NA,PW the parameters values and security bounds are given in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF]Section 5.2] while the sizes of signatures and keys are given in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF]Page 25]. However, in [START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] the authors use universal constants and asymptotic bounds, that cannot directly give concrete parameters, thus for a fair comparison we instantiate each asymptotic value by the one obtained from our results (that is, the same as for IBS NA,R ). From Table 7 we can conclude that we obtain shorter parameter sizes than with IBS + NA,PW (and thus IBS NA,PW ) for the same security level. More precisely, sizes are around 5 times smaller for the same estimated level of security. Then, regarding time complexity by definition of DelTrap, it uses one call to SampleD to compute each column of the delegated trapdoor, one signature of IBS + NA,PW (resp. IBS NA,PW ) needs to use k times SampleD with the same (resp. a bigger) standard deviation as the one for IBS Z /IBS NA,R . We can thus estimate that the signature algorithm, the slowest part in IBS NA,PW /IBS + NA,PW scheme, is k times faster in our schemes. For a concrete use of IBS scheme, we observe that these sizes are still several orders of magnitude bigger than the optimized lattice-based signature proposed for the NIST standardization contest: 3 for the signatures and public keys for a comparison with Dilithium ([11, Table 1]). Since IBS Z scheme relies on tight security, is not optimized and has the identity-based property, this efficiency difference is expected, however there are different interesting improvements that could reduce the gap. We detail some of them in the following part.

k d l -log(ϵ) log(s id )= log(s) log(s sign )= log(s ′ )

Future work

One of the main improvements on the scheme could come from improving the matrix delegation. Indeed, the size of the delegated trapdoor is responsible for the big size of the secret key of identities. Moreover, the singular value of a delegated trapdoor is directly linked to the size of signatures because it is used to make a lower bound on the standard deviations appearing in our scheme. The use of subgaussian sampling instead of Gaussian one following the work of [START_REF] Genise | Building an efficient lattice gadget toolkit: Subgaussian sampling and more[END_REF] seems to be promising in this direction. Then, it would be interesting to investigate how the notions of approximate trapdoors [START_REF] Chen | Approximate trapdoors for lattices and smaller hash-andsign signatures[END_REF] could also be used in order to have smaller delegated trapdoor. Finally, we also think the condition on l, l ≥ 2k log(q), could be greatly improved and thus directly lead to more competitive sizes.

A Generic probability results

A.1 Results about the statistical distance Lemma 4. Let A, B two sets, X, Y two independent random variables with values in A and

f : A → B a function. Then, SD(f (X), f (Y )) ≤ SD(X, Y ) .
Proof.

SD(f (X), f (Y )) = z∈f (X ) |Pr[f (X) = z] -Pr[f (Y ) = z]| = z∈f (X ) Pr X ∈ f -1 (z) -Pr Y ∈ f -1 (z) = z∈f (X ) t∈f -1 (z) Pr[X = t] -Pr[Y = t] ≤ z∈f (X ) t∈f -1 (z) |Pr[X = t] -Pr[Y = t]| = t∈f -1 (f (X )) |Pr[X = t] -Pr[Y = t]| . Since f -1 (f (X)) ⊂ X , this yields, t∈f -1 (f (X )) | Pr[X = t] -Pr[Y = t]| ≤ t∈X | Pr[X = t] -Pr[Y = t]| .
Therefore, SD(f (X), f (Y )) ≤ SD(X, Y ).

Lemma 5. Let A, B, C three sets, X, Y two independent random variables with values in A and a function f : A × B → C. Then for any random variable Z independent with both X, Y , with values in B, we have

SD(f (X, Z), f (Y, Z)) ≤ SD(X, Y ) . Proof. SD(f (X, Z), f (Y, Z)) ≤ SD((X, Z), (Y, Z)) by the previous lemma. Since the variables are independent, SD((X, Z), (Y, Z)) = SD(X, Y ). Lemma 6. Let m ≥ 1 and X 1 , . . ., X m , Y 1 , . . ., Y m some independent random variables. Let X = (X 1 , . . ., X m ), Y = (Y 1 , . . ., Y m ). Then, SD(X, Y ) ≤ m i=1 SD(X i , Y i ).
Proof. For m = 2, the result holds. By induction, assume the property holds for some m > 1.

Consider X = (X 1 , . . . , X m+1 ), Y = (Y 1 , . . . , Y m+1 ).
Then by triangle inequality

SD(X, Y ) ≤ SD(X, (X 1 , . . . , X m , Y m+1 )) + SD((X 1 , . . . , X m , Y m+1 ), Y ) ≤ SD(X m+1 , Y m+1 ) + SD((X 1 , . . . , X m ), (Y 1 , . . . Y m )) . By induction, this shows SD(X, Y ) ≤ SD(X m+1 , Y m+1 ) + m i=1 SD(X i , Y i ).

A.2 Other probability results

Proposition 12. Let X, Y two independent random variables with values on sets A and B respectively. Let f : A × B → {0, 1} a function. Suppose that there exists ϵ > 0 such that

Pr (a,b)←$(X,Y ) [f (a, b) = 1] ≥ 1 -ϵ. Then, for all λ ∈ [0, 1[, Pr a←$X [Pr b←$Y [f (a, b) = 1] ≥ 1 -λ] ≥ 1 - ϵ λ .
In particular, with λ = √ ϵ,

Pr a←$X Pr b←$Y [f (a, b) = 1] ≥ 1 - √ ϵ ≥ 1 - √ ϵ .
Proof. We define

E(λ) = {a ∈ A : Pr b←$Y [f (a, b) = 1] ≥ 1 -λ}. We have 1 -ϵ ≤ Pr (a,b)←$(X,Y ) [f (a, b) = 1] = a∈E(λ) Pr[X = a] Pr b←$Y [f (a, b) = 1] + a / ∈E(λ) Pr[X = a] Pr b←$Y [f (a, b) = 1] ≤ Pr[X ∈ E(λ)] + (1 -Pr[X ∈ E(λ)]) (1 -λ) = λ Pr[X ∈ E(λ)] + (1 -λ) = λ Pr a←$X [Pr b←$Y [f (a, b) = 1] ≥ 1 -λ] + (1 -λ) .
We can then conclude.

Lemma 7. Let Dist a random variable with values in a set A and a function f : A → B. Then, the following probability distributions are equal

Dist 1 = {(f (a), a) : a ←$ Dist} , Dist 2 = {(b, a) : b ←$ f (Dist), a ←$ Dist |f -1 ({b}) } . Proof. For b ∈ f (X), a ∈ A, we have Pr[Dist 2 = (b, a)] = Pr f (Dist) = b ∧ Dist |f -1 ({b}) = a = Pr Dist ∈ f -1 ({b}) ∧ Dist |f -1 ({b}) = a = Pr Dist ∈ f -1 ({b}) Pr Dist |f -1 ({b}) = a = Pr Dist ∈ f -1 ({b}) Pr Dist ∈ f -1 ({b}) ∈ {a} Pr[Dist ∈ f -1 ({b})] = Pr Dist ∈ f -1 ({b}) ∩ {a} = Pr[Dist = a] if f (a) = b 0 else = Pr[Dist 1 = (b, a)] .

B Proofs of Section 4 B.1 Bound on singular values of random matrices

A random variable X over R is subgaussian with parameter s > 0 if for each t ∈ R, E e 2πtX ≤ e πs 2 t 2 . For k ∈ N * , a random variable X over R k is subgaussian with parameter s > 0 if for each i ∈ 1, k , the i th component of X is subgaussian with parameter s. Lemma 8. Let n, a ∈ N * . The probability distribution D n Z,s is subgaussian with parameter s. The uniform distribution U ({-a, 0, a}) is subgaussian with parameter a 4π 3 . The uniform distribution aP r is subgaussian with parameter a 2π(1 -r).

Proof. The first claim is from [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]Lemma 2.8]. For the last two claims, the proof is an adaptation of the proof of Hoeffding's lemma in [START_REF] Cesa-Bianchi | Prediction, learning and games[END_REF]Lemma A.1]. For example, for U ({-a, 0, a}), we have, E e 2πtX = 1 3 e 2πta + e -2πta + 1 = e ϕ(u) with u = 2πat and ϕ(u) = ln 1 3 + ln (e u + e -u + 1) A direct computation and analysis shows that ϕ(0

) = ϕ ′ (0) = 0 ∀v ∈ R, ϕ ′′ (v) ≤ ϕ ′′ (0) = 2
3 . Thus, by Taylor's Theorem, ∀v, ϕ(v) ≤ u 2 2 ϕ ′′ (0) = 1 3 u 2 . We then conclude that

E e 2πtX ≤ e 1 3 (2πat) 2 = e π a 4π 3 2 t 2
.

Proof of Corollary 1. We want to apply [13, Theorem 6.1] with t = m ln(3), which will show in both cases that with probability 1 -2e

-t 2 = 1 -2 * 3 -m s 1 (R) ≤ σ √ m + C(s 2 /σ 2 ) √ n + ln(3)m ,
where the rows r i are independent, identically distributed, zero-mean, and such that E r i r ⊤ i = σ 2 I. In both cases of the corollary, the coordinates are independent, identically distributed and zero-mean, thus E r i r ⊤ i = σ 2 I where σ is the standard deviation. Lemma 8 and a direct computation of the standard deviation show that: -For the distribution D Z,s , σ = s/ √ 2π and s is the subgaussian parameter.

-For the distribution U ({-a, 0, a}), σ = a 2 3 and s = a 4π 3 . -For the distribution aP r , σ = a (1 -r) and s = a 2π(1 -r). We then apply Theorem 6.1 with these values.

The ring case can be deduced from this corollary thanks to the definition of singular norm in the ring case.

B.2 Invertible elements of R q

In this part we provide a simple condition on the invertibility of R q elements, for q = 3 k . Proposition 13 (Simple condition to be invertible in R q ). We consider

R q = Z q [X]/X d + 1 for d ≥ 2 a power of 2 and q = 3 k for k ≥ 1. Let C 0 , C 1 , C 2 , C 3 subsets of -(q -1)/4, (q -1)/4 such that (-C 0 ) ∩ C 1 ∩ C 2 ⊂ {0} , (5)
C 0 ∩ C 1 ∩ (-C 2 ) ⊂ {0} , (6)
min

x∈C 3 -{0} |x| > ∥C 1 ∥ ∞ + ∥C 2 ∥ ∞ 2 . ( 7
)
Let P ∈ Z[X] of degree < d such that P ̸ = 0 mod 3 and

Cf(P ) mod ± ∈ C 0 × C 1 × C 2 × C 3 .
Then, P is invertible as an element of R q .

Proof. We define Lemma 7] it is observed that the non-zero ideals of R q are

P = C 0 + C 1 X d/4 + C 2 X d/2 + C 3 X 3d/4 with each C i ∈ Z[X] of degree strictly less than d/4. We define Q 1 (X) = X d/2 + X d/4 -1, Q 2 (X) = X d/2 -X d/4 -1 and set I 1 = (Q 1 ), I 2 = (Q 2 ), In the proof of [12,
R q itself I 1 ⊃ 3I 1 ⊃ . . . ⊃ 3 k-1 I 1 , I 2 ⊃ 3I 2 ⊃ . . . ⊃ 3 k-1 I 2 , ( 3
) ⊃ (3 2 ) ⊃ . . . ⊃ (3 k-1 ) .
Thus, P is invertible as an element of R q if and only if

P ̸ = 0 mod (I 1 , 3 k ) P ̸ = 0 mod (I 2 , 3 k ) P ̸ = 0 mod 3 .
Furthermore, we see that

P = 0 mod (I 1 , 3 k ) ⇔ C 0 + C 1 X d/4 + (1 -X d/4 )(C 2 + C 3 X d/4 ) = 0 mod (I 1 , 3 k ) ⇔ (C 0 + C 2 ) + (C 1 + C 3 -C 2 )X d/4 -X d/2 C 3 = 0 mod (I 1 , 3 k ) ⇔ (C 0 + C 2 -C 3 ) + (C 1 + 2C 3 -C 2 )X d/4 = 0 mod 3 k ⇔ C 0 + C 2 -C 3 = 0 mod 3 k ∧ C 1 + 2C 3 -C 2 = 0 mod 3 k ⇔ C 0 + C 2 = C 3 ∧ 2C 3 = C 2 -C 1 because coefficients of P are in -(q -1)/4, (q -1)/4 ⇒ C 3 = 0 ∧ C 0 = -C 2 ∧ C 2 = C 1 by equation (7)
⇒ P = 0 by equation ( 5) , Moreover, we can show with the same method, using Equations ( 7) and ( 6), that P = 0 mod (I 2 , 3 k ) implies P = 0. Thus, P is invertible as an element of R q if and only if P ̸ = 0 mod 3.

Corollary 2 (of Proposition 13). Let k ≥ 4, q = 3 k . We consider S R as a subset of R q . Then

S R = {a -a ′ a, a ′ ∈ S R , a ̸ = a ′ } ⊂ (R q ) ×
Proof. Note that S R is equal to P ∈ R q : Cf(P ) ∈ {-8, -4, 0, 4, 8} d/4 ×{-2, -1, 0, 1, 2} d/2 ×{-8, -4, 0, 4, 8} d/4 .

The proposition can be directly applied.

B.3 Proof of smoothing lemma (Lemma 1)

Unstructured case (Equation (1))

In order to prove it, we introduce Lemmas 9 and 10.

Lemma 9. Let m, k ∈ N * b prime and q = b k . For each r > 0, let B m ∞ (r) = {x ∈ Z m : ∥x∥ ∞ < r}, B m q,∞ (r) = {x ∈ Z m q : ∥x∥ ∞ < r}. Then, ∀0 ≤ l < k, b l Z m q ∩ (B m ∞ (q/4b) mod q) ≤ q b 1+l m . (8)
Proof. Let Rep = -(q -1)/2, (q -1)/2 if b odd and Rep = -q/2, q/2 if b = 2. The infinity norm of x ∈ Z q is the infinity norm of the unique representative of x in Rep.

We will first show that

b l Z m q ∩ B m q,∞ (q/4b) = b l Z m ∩ B m ∞ (q/4b) mod q . (9)
The inclusion "⊂" comes from the fact that B m ∞ (q/4b) ⊂ Rep m , which implies that B m q,∞ (q/4b) = B ∞ (q/4b) m mod q. We now show the reverse inclusion "⊃". Let x ∈ b l Z m q ∩ (B m ∞ (q/4b) mod q) and let x the representative of x in Rep m . Because x ∈ b l Z m q , there exists y ∈ Z m such that

q = b k | x -b l y ⇒ b l | x -b l y ⇒ b l |x because l ≤ k .
We can write x = b l x for x ∈ Z m . We know that x = z mod q for some z ∈ B m ∞ (q/4b) (because B m q,∞ (q/4b) = B m ∞ (q/4b) mod q). But B m ∞ (q/4b) ⊂ Rep m implies that z = x, and therefore x ∈ B m q,∞ (q/4b). This proves the inclusion and therefore Equation ( 9). Observe that

B m ∞ (q/b) ⊂ Rep m implies that b l Z m ∩ B m ∞ (q/4b) = b l Z m ∩ B m ∞ (q/4b) mod q (10) Notice that x ∈ B m ∞ q/4b l+1 → b l x ∈ b l Z m ∩ B m ∞ (q/4b)
is a bijection. We can then use Equations ( 9) and [START_REF] Ducas | Github repository pq-crystals/security-estimates[END_REF] to see that

b l Z m ∩ B m ∞ (q/b) mod q = B m ∞ q/4b l+1 Finally, we show that B m ∞ q/4b l+1 ≤ q b 1+l m . If l = k -1, we have B m ∞ q/4b l+1 = |{0}| = 1 and thus B m ∞ q/4b l+1 ≤ 1 = q b 1+l m . If l < k -1, we have B m ∞ q/4b l+1 = 2 q 4b 1+l -1 m ≤ q 2b 1+l + 1 m ≤ q b 1+l m because q/2b 1+l ≥ q/2b k-1 = b/2 ≥ 1. Lemma 10. Let k, b ∈ N * , b prime. Let m, n ∈ N * , such that m ≥ 2nk. Then, Pr A∈Z m×n [λ ∞ (Λ(A)) ≥ q/4b] ≥ 1 -q -n .
Proof. As in Lemma 9, for each r > 0, we define

B m ∞ (r) = {x ∈ Z m : ∥x∥ ∞ < r}, B m q,∞ (r) = {x ∈ Z m q : ∥x∥ ∞ < r}.
Notice that for any non-zero s ∈ Z n q , there exists 0 ≤ l < k such that s = b l s for s with one invertible coordinate, and we have Thus, taking the union for all non-zero s

Pr A∈Z n×m q A ⊤ s ∞ < q/4b = Pr A∈Z n×m q A ⊤ s ∈ B m q,∞ (q/4b) because q/4b ≤ q/2 = Pr A∈Z n×m q b l A ⊤ s ∈ B m q,∞ (q/4b) because s = b l s = Pr a∈Z m q b l a ∈ B m q,∞ (q/4b) because s has an invertible coordinate = Pr x∈b l Z m q x ∈ B m q,∞ (q/4b) = b l Z m q ∩ B m q,∞ (q/4b) b l Z m q = b l Z m q ∩ B m q,∞ (q/4b) (q/b l ) m q being a
Pr A∈Z n×m q ∃ s ∈ Z n q -{0} : A ⊤ s ∞ < q/b ≤ q n 1 b m = q (n-m k ) because q = b k ≤ q -n because m ≥ 2nk .
Lemma 11. Let n, m, k ∈ N, b prime, q = b k , with m ≥ 2nk and ϵ > 0, then

Pr A∈Z n×m q η ϵ (Λ ⊥ (A)) ≤ 4br m,ϵ ≥ 1 -q -n .
Proof. Lemma 10 and the fact that Λ ⊥ (A) * = q -1 Λ(A ⊤ ) shows that

Pr A∈Z n×m q λ ∞ 1 Λ ⊥ (A) * ≥ 1/(4b) ≥ 1 -q -n .
Moreover, [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]Lemma 2.5] shows that, since

Λ ⊥ (A) is of dimension m, η ϵ (Λ ⊥ (A)) ≤ r m,ϵ • 1/λ ∞ 1 Λ ⊥ (A) * .
Proof of unstructured case ((Equation (1))). This is an adaptation of the demonstration of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Lemma 5.2]. Suppose that AZ m q = Z n q and s ≥ η ϵ (Λ ⊥ q (A)). We recall that Λ ⊥ q (A) ⊂ Z m q is a full-rank lattice. Thus, by [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Corollary 2.8]

SD D m Z,s mod Λ ⊥ q (A), U Z n q mod Λ ⊥ q (A) < 2ϵ .
Then, because AZ m q = Z n q , the application Z m mod Λ ⊥ q (A) → Z n q that send e + Λ ⊥ q (A) to Ae is an isomorphism and we can thus conclude. We thus need AZ m q = Z n q and s ≥ η ϵ (Λ ⊥ q (A)). This is done with Corollary and Lemma 11.

Proof of unstructured part of Lemma 1 (Equation (1)). This is an adaptation of the demonstration of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Lemma 5.2]. Suppose that AZ m q = Z n q and s ≥ η ϵ (Λ ⊥ q (A)). We recall that Λ ⊥ q (A) ⊂ Z m q is a full-rank lattice. Thus, by [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Corollary 2.8]

SD D m Z,s mod Λ ⊥ q (A), U Z n q mod Λ ⊥ q (A) < 2ϵ .
Then, because AZ m q = Z n q , the application Z m mod Λ ⊥ q (A) → Z n q that send e + Λ ⊥ q (A) to Ae is an isomorphism. We thus need to see when these conditions happen and to estimate η ϵ (Λ ⊥ (A)). This is done with Proposition 1 and Lemma 11 and we can conclude.

Structured case (Equation (2))

We need the following lemma for the proof.

Lemma 12 (Part of [START_REF] Ducas | Improved short lattice signatures in the standard model[END_REF]Lemma 7] with reformulation and bound improvement). Let d a power of 2, q = 3 k a power of 3 and l > 2k. We have

Pr A∈R 1×l q η ϵ (Λ ⊥ R,q (A)) ≤ 12r ld,ϵ ≥ 1 -3 -d (2k-l) 2 .
Proof. This proof is a adaptation of the proof of [START_REF] Ducas | Improved short lattice signatures in the standard model[END_REF]Lemma 7] with the condition l > 2k instead of l > 2 log(q) = 2 log 2 (3)k.

The lemma [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]Lemma 2.5] shows that, since Λ ⊥ (A) is of dimension dl,

η ϵ (Λ ⊥ (A)) ≤ r dl,ϵ • 1/λ ∞ 1 Λ ⊥ (A) .
Thus, using Proposition 4 and the fact that the distribution of A * ∈ R l×1 q is uniform if the one of A ∈ R 1×l q is, we see that it is sufficient to prove that

Pr B∈R l×1 q [Λ R,q (B)) ≥ q/12] ≥ 1 -3 -d (2k-l) 2 . We define Q 1 (X) = X d/2 +X d/4 -1, Q 2 (X) = X d/2 -X d/4 -1 and we set I 1 = (Q 1 ), I 2 = (Q 2 ).
We observe that the non-zero ideals of R q are

R q itself I 1 ⊃ 3I 1 ⊃ . . . ⊃ 3 k-1 I 1 , I 2 ⊃ 3I 2 ⊃ . . . ⊃ 3 k-1 I 2 , ( 3
) ⊃ (3 2 ) ⊃ . . . ⊃ (3 k-1
) .

Let C = {v ∈ R d q : ∥v∥ ∞ < q/12}. Fix some x ∈ R d q \ {0} and set J = (x). It is one of the nonzero ideal listed above. We want to estimate Pr B←$R l×1 q

[Bx ∈ C]. Since the function B ∈ R 1×l q → Bx
∈ J is a morphism between additive groups, of image J l , it can be seen that the distribution of Bx is uniform over J l and thus

Pr B←$R 1×l q [Bx ∈ C] = |C ∩ J | |J | l
We proceed by bounding the ratio |C∩J | |J | , by disjunction of cases. Case 1: (J = (3 h ) for h ∈ {0, . . . , k -1}). Observe that

|C ∩ J | ≤ (3 h )Z ∩ -q/12, q/12 d ≤ 3 k-h 6 d ≤ 1 if h = k -1 (it is actually equal). 3 k-h /6 + 1 d ≤ 3 d(k-h-1) if h ∈ 0, . . . , k -2 Thus, |C ∩ J | |J | ≤ 3 k-h 6 1 3 k-h d ≤    1/3 k-h d if h = k -1 3 k-h-1 3 k-h d if h ∈ 0, . . . , k -2 and k ≥ 2. ≤ 3 -d .
Case 2:

(J = (3 h Q i ) for h ∈ {0, . . . , k -1},i ∈ {1, 2}).
Start by noting that any element e of J can be uniquely written e = Q i (X) s where s =

d/2-1 i=0 s i X i ∈ (3 k ) ⊂ R
is a polynomial of degree strictly less than d/2. Also note that ∥e∥ ∞ < q/12 implies ∥s∥ ∞ < q/12. Indeed, for i ∈ {0, . . . , n/4 -1} we have e i = -s i and for i ∈ {n/4, . . . , n/2 -1}, we have e i+n/2 = s i . This fact and the unicity of the s in the decomposition of e imply that

|J ∩ C| |J | ≤ (3 h )Z ∩ -q/12, q/12 d/2 3 -d(k-h) 2 ≤ 3 d(k-h) 6 1 3 k-h d/2 ≤ 3 -d/2 ,
where the last inequalities are proved as for case 1.

We thus deduce that for any x ∈ R x -{0},

Pr B←$R 1×l q [Bx ∈ C] =≤ 3 -dl 2
Taking the union bound over all nonzero x ∈ R q we conclude that

Pr B←$R 1×l q [Bx ∈ C] ≤ q d 3 -dl 2 = 3 d( 2k-l 2 )
Proof of structured part of Lemma 1 (Equation (2)). This is an adaptation of the demonstration of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Lemma 5.2]. Assume AR l q = R q and s ≥ η ϵ (Λ ⊥ (A)). We recall that Λ ⊥ q (A) ⊂ Z ld is a full-rank lattice. Thus, by [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Corollary 2.8]

SD D ld Z,s mod Λ ⊥ R,q (A), U Z ld q mod Λ ⊥ R,q (A) < 2ϵ .
Then, since AR l q = R q , the application: Z ld mod Λ ⊥ R,q (A) → R q that sends e + Λ ⊥ R,q (A) to ACf -1 (e) is an isomorphism.

We estimate η ϵ (Λ ⊥ R,q (A)) with Lemma 12 and establish the conditions for our assumptions to hold with Lemma 1, which yields the conclusion. It is the usual way to embed classical functions into quantum ones. In particular, a quantum query to a hash function H is a query of |H⟩.

B.4 Results about the quantum queries of a classical function

In this section, we will see how, given quantum access to |f ⟩ and |g⟩, we can compute:

-|g • f ⟩ (for f and g composable), see Lemma 13.

-|g × f ⟩ (for f and g with same domain) Lemma 14.

-

|g |Xg ⊔ f |X f ⟩ (for f, g : X g ⊔ X f → Y , and g |Xg ⊔ f |Y f (x) equal to g(x) if x ∈ X g and f (x) if x ∈ X f ),
(x,z)∈{0,1} l ×{0,1} n αx,z |x, 0 m , z⟩, Application of |f ⟩ ⊗ id : (x,z)∈{0,1} l ×{0,1} n αx,z |x, f (x), z⟩, Application of id ⊗ |g⟩ : (x,z)∈{0,1} l ×{0,1} n αx,z |x, f (x), z ⊕ (g • f )(x)⟩, Application of |f ⟩ ⊗ id : (x,z)∈{0,1} l ×{0,1} n αx,z |x, 0 m , z ⊕ (g • f )(x)⟩,
This is a separate state, we return:

(x,z)∈{0,1} l ×{0,1} n αx,z |x, z ⊕ (g • f )(x)⟩ = |g • f ⟩(|ϕ⟩).
Proof. The algorithm shows the result of each step of the calculus.

Lemma 14 (Product of functions). Let l, m, n ∈ N * , f : {0, 1} l → {0, 1} m and g : {0, 1} l → {0, 1} n . It is possible to implement |g × f ⟩ using one query to |f ⟩ and one query to |g⟩.

More precisely. Let V the function

(x,y)∈{0,1} l ×{0,1} m α x,y |x, y⟩ -→ (x,y)∈{0,1} l ×{0,1} m α x,y |y, x⟩ . Then, |f × g⟩ = (id ⊗ V ⊗ id) • (|f ⟩ ⊗ |g⟩) • (id ⊗ V ⊗ id).
Proof. Shown by direct computation.

Lemma 15 (Conditional union of functions

(x,z)∈{0,1} m ×{0,1} n αx,z |x, x, z ⊕ f |X f ⊔ id |Xg (x)⟩,
Application of |g⟩ in the last m + n qubit controlled by the first m qubits with the condition x ∈ Xg:

(x,z)∈{0,1} m ×{0,1} n αx,z |x, x, z ⊕ f |X f ⊔ g |Xg (x)⟩, Application of |id⟩ ⊗ id: (x,z)∈{0,1} m ×{0,1} n αx,z |x, 0 m , z ⊕ f |X f ⊔ g |Xg (x)⟩,
This is a separate state, we return:

(x,z)∈{0,1} m ×{0,1} n αx,z |x, z ⊕ (f |X f ⊔ g |Xg )(x)⟩ = |f |X f ⊔ g |Xg ⟩(|ϕ⟩).
Proof. The algorithm shows the result of each step of the calculus.

B.5 Missing proofs of reprogramming Hash lemmas

A lemma to separate classical from quantum queries Lemma 16. Let m, n ∈ N * . We consider a probabilistic algorithm Setup that, for an input in setup , outputs two functions H 0 , H 1 : X = {0, 1} m → Y = {0, 1} n and an auxiliary output aux setup . We suppose that:

-The output aux setup is determinist in the input in setup : only the computation of H 0 and H 1 is probabilistic. -For each input in setup and b ∈ {0, 1}, the distributions (p b,x ) x∈X , where p b,x is defined by H b (x) : (H 0 , H 1 ) ← Setup(in setup ), are independent. Let consider Q c , Q q ∈ N. Let denote by FindHash Qc,Qq the following game, applied to quantum adversaries

A = (A 1 , A 2 , A 3 ). FindHash Qc,Qq (A = (A 1 , A 2 , A 3 )) 1 : insetup ← A1() 2 : (H0, H1, auxsetup) ← Setup(insetup) 3 : b ←$ {0, 1} 4 : |aux⟩ ← A H b 2 (insetup, auxsetup) 5 : b ← A |H b ⟩ 3 (|aux⟩) 6 : if A2 used H b more than Qc times 7 : ∨ A3 used |H b ⟩ more than Qq times then 8 : b ←$ {0, 1} 9 : return b = b We omit A 2 is Q c = 0 and A 3 if Q q = 0. Finally, Let Adv FindHash Qc,Qq A = Pr 1 ← FindHash Qc,Qq (A) - 1 2 .
It also shows that H 1 can be described as: Now, we bound the expected query magnitude of the x ∈ X such that the oracle changed. Lemma 17 shows that the expected total query probability of any x such that H 0 (x) = y is 2Q 3 2 -m . Let σ be the query magnitude of points x at which we changed the oracle. The alternative construction of H 1 shows that the only elements x where H 1 (x) can differ from H 0 are the ones where the condition of line 4 is verified. Thus,

H 1 (x) 1 : y ←$ H0(x) (i.
E[σ] = p i=1 E     x∈X i : Pr[H 0 (x)=Dist i ]<2 -m (1 -2 m Pr[H 0 (x) = Dist i ]) × (total query magnitude of x)     = p i=1 y∈Y : Pr[y=Dist i ]<2 -m (1 -2 m Pr[y = Dist i ]) × E total query magnitude of all x ∈ X i s.t H 0 (x) = y ≤ p i=1 y∈Y : Pr[y=Dist i ]<2 -m (1 -2 m Pr[y = Dist i ]) × 2Q 3 2 -m by Lemma 17 = 2Q 3 p i=1 y∈Y : Pr[y=Dist i ]<2 -m 2 -m -Pr[y = Dist i ] = Q 3 p i=1 SD(U (Y ) , Dist i ) ≤ Q 3 pϵ ≤ Q 3 P ϵ by hypothesis on SD(U (Y ) , Dist i ) and p.
Thus, the expected Euclidean distance is

E Qσ ≤ Q E[σ] ≤ Q × P Q 3 ϵ = Q 2 √ P ϵ .
We then conclude as in the demonstration of [5, Lemma 3] that the expected statistical distance of the output probability distributions is thus at most 4Q 2 √ P ϵ and therefore the probability distribution of outputs when the oracle is H 0 is at most 4Q 2 √ P ϵ away from the probability distribution of outputs when the oracle is H 1 .

B.6 Generalization of [29, Claim 5.3] and proof of Proposition 1

Lemma 18 (Generalization of [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]Claim 5.3]). Let (A, +, x, 0, 1) be a commutative ring, M an A-module and Dist a probability distribution of A such that

∅ ̸ = Supp(Dist) := {a -a ′ : a, a ′ ∈ Supp(Dist), a ̸ = a ′ } ⊂ A × . Let m ≥ 1. For a = (a i ) i∈ 1,m ∈ A m , and m = (m i ) i∈ 1,m ∈ M m , let ⟨a, m⟩ = i a i m i . For m ∈ M m , let χ m,
Pr m∈M k SD(U (M ) , χ m,Dist ) > Col(Dist) m/4 |M | 1/4 ≤ Col(Dist) k/4 |M | 1/4 . Moreover, if Col(Dist) m < |M | -5 , then, Pr m∈M k [a ∈ Supp(Dist) → ⟨a, m⟩ ∈ M is surjective] ≥ 1 -Col(Dist) m/4 |M | 1/4 . Proof. We have h∈M Pr χ m,Supp(Dist) = h 2 = h∈M Pr a←$Dist m [⟨a, m⟩ = h] 2 = Pr (a,a ′ )←$Dist 2m ⟨a, m⟩ = a ′ , m ≤ Pr (a,a ′ )←$Dist 2m a = a ′ + Pr (a,a ′ )←$Dist 2m a -a ′ , m = 0 a ̸ = a ′ = a∈Supp(D) k Pr[Dist m = a] 2 + Pr (a,a ′ )←$Dist 2m a -a ′ , m = 0 a ̸ = a ′ ≤ (a 1 ,...,am)∈Supp(Dist) m m i=1 Pr[Dist = a i ] 2 + P r (a,a ′ )←$Dist 2m a -a ′ , m = 0 | a ̸ = a ′ = m i=1   a∈Supp(Dist) Pr[Dist = a] 2   + P r (a,a ′ )←$Dist 2m a -a ′ , m = 0 | a ̸ = a ′ = Col(Dist) m + P r (a,a ′ )←$Dist 2m a -a ′ , m = 0 | a ̸ = a ′ .
Taking the expectation in m,

E m h∈M Pr χ m,Supp(Dist) = h 2 ≤ Col(Dist) m + E m Pr (a,a ′ )←$Dist 2m a -a ′ , m = 0 a ̸ = a ′ = Col(Dist) m + m∈M m 1 |M | m Pr (a,a ′ )←$Dist 2m a -a ′ , m = 0 a ̸ = a ′ = m∈M m Pr m ′ ←$M m m ′ = m Pr (a,a ′ )←$Dist 2m a -a ′ , m = 0 a ̸ = a ′ = Pr m←$M m (a,a ′ )←$Dist 2m a -a ′ , m = 0 a ̸ = a ′ = Col(Dist) m + a,a ′ ∈Supp(Dist) m a̸ =a ′ Pr[Dist m = a] Pr Dist m = a ′ P r m∈M m a -a ′ , m = 0 = Col(Dist) m + a,a ′ ∈Supp(Dist) m a̸ =a ′ Pr[Dist m = a] Pr Dist m = a ′ Ker(ϕ a-a ′ ) |M | m . ( 11
)
where ϕ a-a ′ : M m → M is defined by ϕ a-a ′ (m) = ⟨a -a ′ , m⟩.

In order to evaluate this last probability, we will show that ϕ a-a ′ is surjective. Because a, a ′ ∈ Supp(Dist) m and a ̸ = a ′ , there exists i such that a i -a ′ i ∈ Dist ⊂ A × . For m ∈ M , We denote by m the vector such that mi = m and ml = 0 for l ̸ = i. We can see that for each m ∈ M , m = ϕ (a i -a ′ i ) -1 m . Thus ϕ is surjective.

We deduce that

|Ker(ϕ a-a ′ )| ≃ |M | m |Im(ϕ a-a ′ )| = |M | m |M | = |M | m-1 ,
and that, using Equation ( 11),

E m h∈M Pr χ m,Supp(Dist) = h 2 = Col(Dist) m + a,a ′ ∈Supp(Dist) m a̸ =a ′ Pr[Dist m = a] Pr[Dist m = a ′ ] |M | = Col(Dist) m + 1 |M | . (12)
Conclusion: Using Equations ( 13), ( 14) and the equality Dist 1 = Dist SimModKExt , we can conclude that

Pr (A,T A )←$Trap(n,m,q) SD(Dist SimModKExt (A), Dist ModKExt (A, T A , s)) ≤ nkγ Sample n,m,ϵ ≥ 1 -2q -n .
Proof of Proposition 5. The part of Proposition 3 about SampleD and Lemma 19 implies that, when

(i) s ≥ η ϵ Λ ⊥ q (A∥A ′ ) , (ii) (A∥A ′ )Z m+nk = Z n mod q , (iii) s 1 T ′ A ≤ s 1 (Gauss)[m, nk, s] ⇒ s ≥ r nk,ϵ 11 s 1 T ′ A 2 + 1 , we have SD Dist Sign (A, A ′ , T ′ A , s), D m+nk Z,s ≤ γ Sample n,m+nk,ϵ + 2ϵ . (15)
We now study these three conditions. Study of the conditions (i), (ii) Lemma 11 and Proposition 1 show that P r

(A,A ′ )←$Z n×m q ×Z n×nk q s ≥ η ϵ Λ ⊥ q (A∥A ′ ) ∧ (A∥A ′ )Z m+nk = Z n mod q ≥ 1 -2q -n/4 .
This implies, by a general probability fact, shown in additional appendix in Proposition 12, that

P r A←$Z n×m q P r A ′ ←$Z n×nk q s ≥ η ϵ (Λ ⊥ q (A∥A ′ )) ∧ (A∥A ′ )Z m+nk = Z n mod q ≥ 1 - √ 2q -n/8 ≥ 1 - √ 2q -n/8 . (16)
Using the equation ( 16), the fact that the output A ′ of Dist KExt is uniform and Proposition 2, we have P r

(A,T A )←$Trap(n,m,q) P r (A ′ ,T ′ A )←$Dist KExt (A,T A ,s) (i) and (ii) true ≥ 1 - √ 2q -n/8 ≥ 1 - √ 2q -n/8 + nkq -0.196n . ( 17
)
Study of the condition (iii) Lemma 19 (applied nk times) and Proposition 3 shows that if:

(a) s ≥ η ϵ (Λ ⊥ q (A)), (b) AZ m = Z n mod q (c) s 1 (T A ) ≤ s 1 (Binom)[m -nk, nk, 1/2] ⇒ s ≥ r nk,ϵ 11 s 1 (T A ) 2 + 1 , ten, SD T ′ A : (A ′ , T ′ A ) ← Dist KExt (A, T A , s), D m×nk Z,s ≤ nk 2ϵ + γ Sample n,m,ϵ . (18)
Moreover, Corollary 1 shows that

P r R←$D m×nk Z,s s 1 (R) > s 1 (Gauss)[m, nk, s] ≤ 2q -n . (19)
Thus, Equations ( 18) and [START_REF] Krawczyk | Chameleon signatures[END_REF] implies that when (a), (b), (c) are verified,

P r (A ′ ,T ′ A )←Dist KExt (A,T A ,s) s 1 T ′ A ≤ s 1 (Gauss)[m, nk, s] ≥ 1 -2q -n + nk(2ϵ + γ Sample n,m,ϵ ) . (20

Conclusion

We conclude, with equations ( 15), ( 17), [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF] and with Proposition 2 that P r

(A,T A )←Trap(n,m,q) P r

B.8 Links between lattices and R-lattices

We will use the functions Cf : R a×b q → Z a×db q and Rot : R a×b q → Z da×db q defined in Section 3. We define the dual of an element a = d-1 i=0 a i X i ∈ R as a * := a 0 + d-1 i=1 a d-i X i . The dual of a matrix B = (b i,j ) ∈ R n×m is defined as B * := (b * j,i ) ∈ R m×n . We note that (B * ) * = B and B ⊤ * = (B * ) ⊤ . Proof. We note that ∥Cf(A)∥ = ∥A∥, the norm being taken in their respective spaces. We note that ∥Rot(B)∥ = √ d∥B∥. We also note that Cf(AB) = Cf , x ∈ R n q , u ∈ R m q , we have Cf Λ ⊤ u,R,q (A) = Λ ⊤ Cf(u) Rot A ⊤ ⊤ Cf (Λ R,q (A)) = Λ q Rot A ⊤ ⊤ , D Λ ⊤ u,R,q (A)+x,s = Cf -1 D Λ ⊤ Cf(u) (Rot(A))+Cf(x),s .

Proof. We will need some properties about Rot and Cf that are shown in Appendix B.8, Proposition 14. The first equality is proved by

x ∈ Λ ⊤ u,R (A) ⇔ x ⊤ A ⊤ = u ⊤ ⇔ Cf x ⊤ A ⊤ = Cf(u ⊤ ) ⇔ Cf(x ⊤ )Rot(A ⊤ ) = Cf(u ⊤ ) ⇔ Cf(x) ∈ Λ ⊤ Cf(u) Rot A ⊤ ⊤ .
The second by

x ∈ Λ R,q (A) ⇔ ∃s :

x = As ⇔ Cf(x ⊤ ) = Cf s ⊤ A ⊤ ⇔ Cf(x ⊤ ) = Cf(s ⊤ )Rot(A ⊤ ) ⇔ Cf(x) = Rot(A ⊤ ) ⊤ Cf(s) ⇔ Cf(x) ∈ Λ q Rot A ⊤ ⊤ .
The equality of probability distributions is a direct consequence of the first equality.

Corollary 4. For all B ∈ R n×m , we have q Cf Λ ⊥ R,q (B) * = Cf (Λ R,q (B * )) .

Proof. We use Propositions 17 and 14 for q Cf Λ ⊥ R,q (B) * = q Λ ⊥ q Rot B ⊤ ⊤ * by Proposition 17 = Λ q Rot B ⊤ because for A ∈ Z m×n , q Λ ⊥ q (A) * =Λ q A ⊤ = Λ q Rot (B * ) ⊤ ⊤ by Proposition 14

= Cf (Λ R,q (B * )) by Proposition 17.

B.9 Lattice trapdoors over R q

In this section we provide the definitions of the algorithms Trap R ,DelTrap R and SampleD R evoked in Section 4.3. We give the propositions and proofs relative to instantiations on rings, they are the equivalent (on structured lattices) of the ones presented in Section 4.3 on unstructured lattices. We will make an extensive use of the propositions of Appendix B.8 in order to pass from the unstructured to the structured case. Let g = (1, 3, . . . , 3 k-1 ) ∈ R k and G = [I n 3I n . . . 3 k-1 I n ] ∈ Z n×nk . We recall that a gtrapdoor of a matrix A ∈ R 1×l q is a matrix T A ∈ R (l-k)×k q such that Rot(T A ) ∈ Z d(l-k)×dk q is a G-trapdoor (defined in Section 4.3) of Rot(A) ∈ Z d×dl q . Equivalently, A -T A I k = g mod q.

Proposition 18 (Statistical instantiation of trapdoors (from [25, Section 5.2]), ring version). Let l > 2k. We denote by Trap R (l, q) the algorithm that samples A ←$ R 1×(l-k) q , T A ←$ P

Fig. 2 .

 2 Fig. 2. Adaptive reprogramming games AdaptReprog b for bit b ∈ {0, 1}. The adversary only decide the chunk in X2 of the input

Fig. 3 .Fig. 4 .

 34 Fig. 3. Game NoAdaptReprog (A) for A = (A1, A2, A3).

Fig. 6 .

 6 Fig. 6. Scheme IBS NA,Z .

  |Hash mess ⟩ and |Hash id ⟩. This is shown by Lemmas 13 and 15 of Appendix B.4.

  196n by definition of fail 1 and Proposition 2 ≤ Q IdSign (2q -n/4 + mx) + nkq -0.196n by Corollary 5.

Fig. 7 .

 7 Fig. 7. Scheme IBSR.

Fig. 8 .

 8 Fig. 8. Scheme IBS NA,R .

  power of b and bigger than b l

For

  l, m ∈ N * and f : {0, 1} l → {0, 1} m a function, we denote by |f ⟩ the function |f ⟩   (x,y)∈{0,1} n ×{0,1} m α x,y |x, y⟩   = (x,y)∈{0,1} n ×{0,1} m α x,y |x, y ⊕ f (x)⟩ .

  Dist the probability distribution that outputs ⟨a, m⟩ for a ←$ Dist m . Then, E m∈M m [SD(U (M ) , χ m,Dist )] ≤ Col(Dist) m/2 |M |, where Col(Dist) := Pr x,y←Dist [x = y] = x∈Supp(Dist) Pr[Dist = x] 2 . In particular

)Finally, Proposition 1 ,≥ 1 -

 11 Proposition 2, Lemma 11 and Corollary 1 showP r (A,T A )←$Trap(n,m,q) [(a), (b) and (c) true] ≥ 1 -4q -n/4 + nkq -0.196n . (21)We thus have, by equations (20) and (21)P r (A,T A )←$Trap(n,m,q) P r (A ′ ,T ′ A )←Dist KExt (A,T A ,s) (iii) true ≥ 1 -2q -n + nk(2ϵ + γ Sample n,m,ϵ ) 4q -n/4 + nkq -0.196n .

( 8 ≥ 1 -

 81 A ′ ,T ′ A )←Dist KExt (A,T A ) SD Dist Sign (A, A ′ , T A , s), D m+nk Z,s ≤ γ Sample n,m+nk,ϵ + 2ϵ ≥ 1 -2q -n + nk(2ϵ + γ Sample n,m,ϵ ) + √ 2q -n/2nkq -0.196n + 4q -n/4 + √ 2q -n/8 .

Proposition 14 .

 14 Cf and Rot are Z-linear. Moreover, for all A ∈ R n×m , B ∈ R m×l , we haveCf(AB)=Cf(A) Rot(B) Rot(AB)=Rot(A) Rot(B) Rot(A * )=Rot(A) ⊤ .Proof. The fact that Cf and Rot are Z-linear is verified by direct computation.

First, a direct

  calculus shows that for each a, b ∈ R q Cf(ab) = Cf(a)Rot(b). Then, for 1 ≤ i ≤ n, the i th line of Cf(AB) i,j b j,1 ), . . ., m j=1 Cf(a i,j b j,l ) i,j )Rot(b j,1 ), . . .,m j=1 Cf(a i,j )Rot(b j,l )   , = Cf(a i,1 )∥. . .∥Cf(a i,m ) Rot(B) ,which is equal to the i th line of Cf(A)B. The second equation in a direct consequence of the fact that, for a, b ∈ R, Rot(ab) = Rot(a)Rot(b). To see that, we note that for 1 ≤ i ≤ d the i th lines of Rot(ab) and Rot(a)Rot(b) are, by definition, respectively Cf(X i ab) and Cf(X i a)Rot(b) : they are thus equal by an application of the first equality of the proposition. The third equation is a direct consequence of the fact that for all a ∈ R, Rot(a * ) = Rot(a) ⊤ , and the definitions of Rot and the dual of a matrix in R. Proposition 15. For A ∈ R n×m and B ∈ R m×l , we have ∥AB∥ ≤ √ d s 1 (A) ∥B∥.

s 1 ( 2 = d s 1 (√ d s 1 (

 1211 (A) Rot(B). Thus,∥AB∥ = ∥Cf(AB)∥ = ∥Cf(A) Rot(B)∥ ≤ s 1 (Cf(A)) ∥ Rot(B)∥ , = s 1 (A) ∥ Rot(B)∥ ≤ √ d s 1 (A) ∥B∥ . Proposition 16. For A ∈ R n×m , s 1 (Rot(A)) ≤ √ d s 1 (A)Proof. For all 1 ≤ i ≤ d -1, we have s 1 Cf(X i A) = s 1 (Cf(A)). Thus, for any x ∈ R dm , we have,∥Rot(A)x∥ = Cf(A)x, Cf(XA)x, • • • , Cf(X d-1 A)x = Cf(X i A)) 2 ∥x∥ Cf(A)) 2 ∥x∥ 2 = Cf(A)) ∥x∥Proposition 17. For A ∈ R m×n q

  (l-k)×k R,1/2 and outputs the couple A := A∥g -AT A , T A . Then, T A is a g-trapdoor of A, and A has a probability distribution with statistical distance at most kq -0.196d = negl(d) from uniform distribution.

  class IBSParameterSet :# _PW : specific to IBSPW scheme ([START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] Figure 8])) def __init__ ( self , k , d , l , eps ): self . k = k # the modulus is equal to q =3^k self . d = d # Ring dimension self . l = l # Dimension of A self . eps = eps # epsilon # Note that : # -IBSPW does not use the probability P_ (1/2) # but gaussian distribution # to create T_A # -( see their[START_REF] Pan | Short identity-based signatures with tight security from lattices[END_REF] Lemma 12]). # The use of P_ (1/2) led to smaller trapdoor # and thus better # results : we use P_ (1/2) for both , # wich make a better standard deviation s for IBSPanWan . # ( see equations at [26, Section 5.2]) # -We use our estimations of singular values of matrix # for both IBSR and IBSPW because the ones # of IBSPW included universal constants . self . sid = compute_sid (k , d , l , eps ) self . ssign = compute_ssign (k , d , l , eps , self . sid ) # the standard deviations s , s ', s ' '.self . s_PW = compute_s_PW (k , d , l , eps ) self . sp_PW = compute_sp_PW (k , d , l , eps , self . s_PW ) self . spp_PW = compute_spp_PW (k , d , l , eps , self . sp_PW ) # sProof_PW is our estimation of the standard # deviation tilde { s } they used for Hash reprogramming # in the proof of [26, Theorem 4]. # We used Lemma 1 to # estimate it ( it gives a conditon on std such that # A *( Discrete Gaussian ( std )) is near # the uniform distribution ") self . sProof_PW = 12 * r ( d * l , eps ) self . signBoundI = sqrt (2 * d * l ) * self . ssign self . signBoundII = sqrt ( 2 * d * k ) * self . ssign # Bound of the solution , see (([26, Figure 8] self . signBound_PW = sqrt ( d * ( l + 2* k )) * s1gauss (l , d * k , self . spp_PW ) # RSIS Bound of IBSR , from 3 self . RSISBound = self . signBoundI + 4 * sqrt ( d ) * s1unif ( l , d * k ) * self . signBoundII + sqrt ( 17 / 2) * sqrt ( l * d ) # RSIS Bound of IBSPW , constructed by looking at the # demonstration of [26, Theorem 4]) , self . RSISBound_PW = ( 1 + 2 * sqrt ( d ) * s1gauss (l , d * k , self . sProof_PW ) ) * self . signBound_PW # Creation of MSISParams for IBSR and IBSPan # in order to use M S I S _ s u m m a r i z e _ a t t a c k s self . MSISParams_PW = MSISParameterSet ( d , l , 1 , self . RSISBound_PW , 3** k , " l 2 " ) self . MSISParams = MSISParameterSet ( d , l , 1 , self . RSISBound , 3** k , " l 2 " ) self . size_sign = ceil ( l * d * log (2 * self . signBoundI , 2) + k * d * log (2 * self . signBoundII , 2)) # With notation z =( z_1 , z_2 ) we use the fact that # by definition of the scheme ( Figure 7) # | sign_1 | _infty \ leq | sign_1 | _2 \ leq signBoundI # | sign_2 | _infty \ leq | sign_2 | _2 \ leq signBoundII # so they can be stored respectively modulo 2* signBoundI # and 2* signBoundII self . size_sign_PW = ceil ( ( l + 2* k ) * d * log ( min (2 * self . signBound_PW , 3** k ) , 2)) # We use the fact that # by definition # ([26, Figure 8]): # | sign | _infty \ leq | sign | _2 \ leq signBound_PW # so it can be stored modulo min (2* signBound_PW , 3** k ) self . size_pk = ceil ( l * d * log (3** k , 2)) self . size_sk = ceil (( l -k ) * k * d * log (3 , 2)) self . size_sk_id = ceil ( ( l + k ) * k * d * log ( sqrt (2 * d ) * self . sid , 2)) # We use the fact that the ouput is close to discrete # gaussian with standard deviation sid # ( see for example Equation ~(29)) # and the tail inequality ( Lemma ~3) to each coordonate self . size_sk_id_naive = ceil ( ( l + k ) * k * d * log (3** k , 2)) def secu ( self ): MSISsecu_PW = M S I S _ s u m ma r i z e _ a t t a c k s ( self . MSISParams_PW ) secu_PW = MSISsecu_PW [ -2] # -1 because of the factor 2 in the reduction to RSIS print ( " \ n S e c u r i t y o f IBSPW ( c o s t w i t h c o s t s v p ) : " + str ( secu_PW -1)) MSISsecu = M S I S _ s u m m a r i z e _ a t t a c k s ( self . MSISParams )txt += " \ nRSIS bounds : " txt += "IBSR=" + str ( self . RSISBound ) txt += " , o f l o g=" + str ( round ( log ( self . RSISBound , 2) , 2)) txt += "IBSPW=" + str ( self . RSISBound_PW ) txt += " , o f l o g=" + str ( round ( log ( self . RSISBound_PW , 2) , 2)) print ( txt ) def summary ( self ): print ( "PARAMETERS SUMMARY: \ n " ) self . print_params () print ( " SIZES SUMMARY: \ n " ) self . print_sizes () print ( "SECURITY SUMMARY: \ n " ) self . secu () # create the set of parameters paramsI = IBSParameterSet (65 , 2048 , 132 , 2**( -200)) paramsII = IBSParameterSet (153 , 2048 , 308 , 2**( -200)) # Make a summary of parameters values , print ( "Summary f o r p a r a m s I : \ n " ) paramsI . summary () print ( "Summary f o r p a r a m s I I : \ n " ) paramsII . summary ()

  O Sign (mpk)

	6 :	∨ (id * , µ * ) ∈ AskedSign / / for EUF-CMA
	7 :	∨ (id * , µ * , σ * ) ∈ sAskedSign / / for sEUF-CMA
	8 :	∨ cpt C > Q Corr ∨ cpt S > Q S then
	9 :	return 0
	10 : return Verify(mpk, id * , µ * , σ * )
	O Sign (id, µ)
	cpt S := cpt S + 1
	sk id,µ ← KeyExt(mpk, msk, id)
	σ id,µ ← Sign(mpk, sk id,µ , µ)
	AskedSign = AskedSign ∪ {(id, µ)} / / for EUF-CMA
	sAskedSign = sAskedSign ∪ {(id, µ, σ id,µ )} / / for sEUF-CMA
	return σ id,µ
	O Corrupt (id)

5 : if id * ∈ AskedSk

  GivenSign then / / for sEUF-naCMA

		A)
	1 : (mpk, msk) ← Setup()
	2 : (AskedSk, AskedSign, aux) ← A1(mpk)
	3 : if |AskedSk| > Q Corr
	4 :	∨ |AskedSign| > Q S then
	5 :	return 0
	6 : for id ∈ AskedSk :
	7 :	sk id ← KeyExt(mpk, msk, id)
	8 : for (id, µ) ∈ AskedSign :
	9 :	sk id,µ ← KeyExt(mpk, msk, id)
	10 :	σ id,µ ← Sign(mpk, sk id,µ , µ)
	11 : GivenSk = {(id, sk id ), id ∈ AskedSk}
	12 : GivenSign = (id, µ, σ id,µ ),
	13 :	(id, µ) ∈ AskedSign
	14 : (id * , µ * , σ * ) ← A2(mpk, GivenSk,
	15 :	GivenSign, aux)
	19 :	return 0

16 : if id * ∈ AskedSk 17 : ∨ (id * , µ * ) ∈ AskedSign then / / for EUF-naCMA 18 : ∨ (id * , µ * , σ * ) ∈ 20 : return Verify(mpk, id * , µ * , σ * )

  QROM case is proved in [17, Proposition 1]. We only prove the ROM case. The only way A can differentiate O 0 from O 1 is to obtain different values from multiple queries to O b with the same input. If we denote by (x 1 , x 2 ) this input, this implies that one of the R query to ReprogramOracleOne sampled x 1 . Because ReprogramOracleOne is queried less than R times and O b less than Q times, this event has a probability less than RQ |X 1 | .

  of finding a collision for a random function H : {0, 1} a → {0, 1} b with access to at most Q quantum queries to H. In order to simplify the notations, we define the security game FindColId by FindCol Q (τnonce+τ id ,τ id ) Q Hash id +Q Corr +Q S and we also define the security game FindColMess by FindCol

Q (τnonce+τmess,τmess) Q Hashmess +Q S . Let (GameSign, GamenaSign) ∈ {(EUFCMA, EUFnaCMA), (sEUFCMA, sEUFnaCMA)}. Then for each PPT adversary A against GameSign adapt(IBS) Q Corr ,Q S that makes Q Hash id quantum queries to Hash id and Q Hashmess quantum queries to Hash mess , there exists PPT adversaries C against GamenaSign IBS Q Corr ,Q S , B id against FindColId and B µ against

Table 2 .

 2 Parameters of IBS Z and required conditions.

Table 2 .

 2 Let Q Corr , Q S ∈ N and A a PPT adversary of EUFnaCMA IBS NA,Z Q Corr ,Q S that makes Q H 1 quantum queries to H 1 , Q H 2 quantumqueries to H 2 and such that the signature queries are made for Q IdSign distinct identities. Let Bound SIS = Bound 1 +s 1 (Unif)[m, nk] Bound 2 + √ m and mx = max(2ϵ, q -n/4 ) = negl(n). Then, there exists a PPT adversary B of SIS n,m,Bound SIS ,q

Table 3 .

 3 Summary of the changes between the games used for the proof of Theorem 2. Complete games are given in Appendix D.2.

Table 5 .

 5 Summary of the changes between the games used for the proof of Theorem 3. Complete games are similar of the ones of the proof of Theorem 2.

Table 6 .

 6 Parameter set for IBS NA,R and IBS + NA,PW . s id , s sign are the standard deviations for IBS NA,R while s, s ′ , s

	log(s ′′	)

′′

are the standard deviations for IBS + NA,PW .

Table 7 .

 7 Security and size for IBS NA,R and IBS + NA,PW with parameters of Table6

  32. Zhandry, M. A note on the quantum collision and set equality problems. Quantum Inf. Comput. 15, 7&8 (2015), 557-567. https://doi.org/10.26421/QIC15.7-8-2. 33. Zhandry, M. How to record quantum queries, and applications to quantum indifferentiability. In Advances in Cryptology -CRYPTO 2019, Part II (Santa Barbara, CA, USA, Aug. 18-22, 2019), A. Boldyreva and D. Micciancio, Eds., vol. 11693 of Lecture Notes in Computer Science, Springer, Heidelberg, Germany, pp. 239-268.

  see Lemma 15. Lemma 13 (Composition of functions). Let l, m, n ∈ N * , f : {0, 1} l → {0, 1} m and g : {0, 1} m → {0, 1} n , it is possible to implement |g • f ⟩ using 2 queries to |f ⟩ and one query to |g⟩. More precisely, |g • f ⟩ can be implemented as the following quantum algorithm, Comp |f ⟩,|g⟩ |ϕ⟩ = (x,z)∈{0,1} l ×{0,1} n α x,z |x, z⟩ Insertion of separable qubit |0 m ⟩:

  CondUnion |f ⟩,X f ,|g⟩,Xg |ϕ⟩ = (x,z)∈{0,1} m ×{0,1} n α x,z |x, z⟩ Insertion of separable qubit |0 m ⟩:Application of |f ⟩ in the last m + n qubit controlled by the first m qubits with the condition x ∈ X f :

		αx,z |x, 0 m , z⟩,
	(x,z)∈{0,1} m ×{0,1} n
	Application of |id⟩ ⊗ id:	αx,x,z |x, x, z⟩,
	(x,z)∈{0,1} m ×{0,1} n

). Let m, n ∈ N * , f, g : {0, 1} m → {0, 1} n and a partition {0, 1} m = X g ⊔ X f . It is possible to implement |f |X f ⊔ g |Xg ⟩ using one query to |f ⟩ and one query to |g⟩.

  e, sampled with U ({0, 1} m ))

	2 :	/ / we recall that Y = {0, 1} m
	5 :	/ / Note that this condition never happens if ϵ i = 0
	6 :	with probability 1 -2 m Pr[y = Disti] :
	7 :	y ′ ←$ Dist ′ i
	8 :	return y ′

3 : for i ∈ 1, p 4 : if x ∈ Xi ∧ Pr[y = Disti] < 2 -m then 9 : return y

More details in Proposition 14 (Appendix B.8).

The same as in Proposition 3.

Then, there exist quantum PPT adversaries A CQueries , A QQueries such that, Proof. From FindHash to G 1 : Using the notations of the game G 1 of Figure 9, we define

We create an adversary à = (A 1 , Ã2 , Ã3 ) of G 1 such that Adv G 0,Qc,Qq A Analysis of G 1 : we see that,

Pr b=0 in G 1,Qc,Qq b=1 -Pr b=0 in G 1,Qc,Qq b=1

Pr b=0 in G1,Qc,Qq (A) (b c , b q )=(0, 0) -Pr b=0 in G 1,Qc,Qq (A) (b c , b q )=(1, 1)

Pr b=0 in G1,Qc,Qq (A) (b c , b q )=(0, 0) -Pr b=0 in G 1,Qc,Qq (A) (b c , b q )=(0, 1)

Pr b=0 in FindHash 0,Qq (A QQueries ) b=0 -Pr b=0 in FindHash 0,Qq (A QQueries ) b=1

Pr b=0 in FindHash Qc,0 (A CQueries ) b=0 -Pr b=0 in FindHash Qc,0 (A CQueries ) b=1 =Adv FindHash 0,Qq A QQueries

+ Adv

FindHash Qc,0 A CQueries

,

Where the adversary A QQueries is (A 1 , A QQueries,2 ) (A QQueries,2 is described in Figure 11) and the adversary A CQueries is (A 1 , A CQueries,2 ) (A CQueries,2 is described in Figure 11). Note that the two hypotheses about Setup are used in order to have

Proof of Proposition 7 about non-adaptative reprogramming Lemma 17 (Lemma 9 of [START_REF] Boneh | Random oracles in a quantum world[END_REF]). Let A be a quantum algorithm that makes at most Q queries to a quantum random oracle O with codomain {0, 1} m (m ∈ N * ). Fix y in the codomain of O.

The expected value of the total query probability of all x such that O(x) = y is at most 2Q 3 2 m . Proof of Proposition 7. We use Lemma 16 in order to study separately the case were only classical (ROM) or quantum (QROM) queries are made.

Proof of the ROM case

We will show that for each fixed partition P = (X i ) i∈ 1,p , p ≤ P and family of probability distributions (Dist i ) i∈ 1,p such that for each i ∈ 1, p , SD(Dist i , U (Y )) < ϵ, the advantage of A, making only classical queries, is less that ϵ Q. We suppose that A makes Q i queries on X i , Q = i Q i . We create the following games: -G 0 is the game where the oracle is always set to

for the modification of the oracle where Dist k is replaced by U (Y ). We then see that,

Proof of the QROM case

The proof is an adaptation of the demonstration of [START_REF] Boneh | Random oracles in a quantum world[END_REF]Lemma 3] in our more general situation. We will show that for each fixed partition P = (X i ) i∈ 1,p , p ≤ P and family of probability distributions (Dist i ) i∈ 1,p such that for each i ∈ 1, p , SD(Dist i , U (Y )) < ϵ, the advantage of A to distinguish the uniform oracle H 0 and H 1 is less that 4Q 2 √ P ϵ . We first remark that H 0 is the random oracle. Then, as in the demonstration of Lemma [5, Lemma 3], we will describe another way to construct H 1 as follows. For each i ∈ 1, p, , we define ϵ i = SD(Dist i , U (Y )) ≤ ϵ and for each i such that ϵ i > 0, we define Dist ′ i by : Lemma 3] shows that it is a probability distribution using the fact that

Thus,

≤ Col(Dist) m/2 |M | by equation [START_REF] Ducas | Improved short lattice signatures in the standard model[END_REF].

and l ≥ 21, then,

.

Proof. It can be shown by induction on k ≥ 4 than AR l 3 4 = R 3 4 ⇒ AR l q = R q and AZ m 3 = Z n 3 ⇒ AZ m q = Z n q . For example, if we have already shown that AR l 3 u = R 3 u for some u ≥ 4, we write any y ∈ R 3 u+1 as y = 3y u + y 3 mod q with Cf(y u ) ∈ {0, 3 u -1} l , Cf(y 3 ) ∈ {0, 3 -1} l and can thus write y = A(3x 1 + x 2 ) with x u and x u found using the induction hypothesis that AR l 3 u = R 3 u . We then use Lemma 18 with:

The distribution satisfies the condition of the lemma by Proposition 13. Moreover, The condition Col(Dist) l < |M | -5 becomes 1 3 dl < 3 -20d and if satisfied if l ≥ 21.

Proof of Proposition 1. The inequalities about statistical distance are consequences of Lemma 18 with: -A = Z q , M = Z n q and m elements of M . -A = M = R q , with l elements of M . Corollary 2 is used to ensure the distributions satisfy the invertibility condition. The two other inequalities are consequences of Corollary 3.

B.7 Proof of Propositions 4 and 5 about matrix delegation

Lemma 19. Let m, n, q ∈ N * , 0 < ϵ < 1/2, s > 0, A ∈ Z n×m . If AZ m = Z n mod q, then, the two following probability distributions are equal

, we can consider it as a surjective morphism between groups ((Z m q , 0, +) → (Z n q , 0, +)) to deduce that the probability distribution Ax, x ←$ Z m q is uniform on Z n q . Using in addition Λ ⊥ q,Ax (A) = Λ ⊥ q (A) + x, we conclude that Dist 1 = Dist 2 . Note now that Dist 1 and D m Z,s can be expressed as

With this observation and [15, Corollary 2.8], we see

Proof of Proposition 4. We will use an intermediate probability distribution Dist 1 .

We study the statistical distance between Dist KExt and Dist 1 :

We show that Dist 1 and Dist SimModKExt are equal: Dist 1 and Dist SimModKExt are equals because, for any A, the two following probability distributions are equals

This equality comes from a general probability fact proved in Appendix A ( Lemma 7).

We analyze when s ≥ r nk,ϵ 11 s 1 (T A ) 2 + 1 : Proposition 2, Corollary 1 and the condition

Proof. A direct computation shows that T A is a G-trapdoor of A. The statistical distance upper bound comes from Proposition 1.

Proposition 19 ([25], Ring version

a g-trapdoor and s ≥ r dk,ϵ 11 d s 1 (T A ) 2 + 1 , we have:

-SampleD R (A, u, T A , s) returns z ∈ R k q such that Az = u and the statistical distance between the probability distribution of z and D Λ ⊤ R,q,u (A),s is upper bounded by the function

Moreover, the probability distribution of the output

A is computed as SampleD(A, u i , T A , s). Proof. We apply Proposition 3 to Rot(A) with the help of the results of Section B.8. For example, we use the bound s 1 (Rot(T A )) ≤ √ ds 1 (A) of Proposition 16 and the proposition 17 is used to see that

If AR l q = R q Then, the two following probability distributions are equals

Proposition 20 (Simulation of delegation of trapdoors). For s > 0, A ∈ R 1×l and

Proof. We will use an intermediate probability distribution

We study the statistical distance between Dist R,KExt and Dist 1 : Proposition 3 shows

We show that Dist 1 and Dist R,SimModKExt are equal: Dist 1 and Dist R,SimModKExt are equals because, for any A, the two following probability distributions are equals

This equality comes from a general probability fact proved in Appendix A (Lemma 7).

We analyze when s ≥ r dk,ϵ 11 s 1 (T A ) 2 + 1 : Proposition 18, Corollary 1 and the condition

Conclusion: Using Equations ( 23), ( 24) and the equality Dist 1 = Dist R,SimModKExt , we can conclude that P r

Proof. The part of Proposition 3 about SampleD R and the lemma 19 imply that, when

We now study these three conditions. Study of the conditions (i), (ii) Lemma 12 and Proposition 1 show that P r

This implies, by a general probability fact, shown in additional appendix in Proposition 12, that

Using the equation ( 27), the fact that the output A ′ of Dist R,KExt is uniform and Proposition 18, we have P r

Study of the condition (iii) Lemma 20 (applied k times) and Proposition 19 show that if

Moreover, Corollary 1 shows that

Thus, Equations ( 29) and [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF] implies that when (a), (b), (c) are verified,

Finally, Proposition 1 Proposition 18, Lemma 12 and Corollary 1 show P r

We thus have, by equations ( 31) and (33)

Conclusion

We conclude, with equations ( 26), ( 28), (34) Proposition 18 and the fact that 2q

.

C Detailed games for the proof of Theorem 1 of Section 5

G1(A)

: (mpk, msk) ← Setup() : mpk, msk ← Setup() O Corrupt (id)

G2(A)

1 : (mpk, msk) ← Setup(λ)

2 : cpt C := 0, cpt S := 0 O Corrupt (id)

G3(A)

: (mpk, msk) ← Setup(λ) : cpt C := 0, cpt S := 0 : Hash id ←$ SetId {0,1} τnonce ×SetId : Hashmess ←$ SetMess {0,1} τnonce ×SetMess O Corrupt (id)

The game shown in Figure 1 C1(mpk)

/ / We define:

D Proofs of Section 6

D.1 Some intermediary results for the proof of Theorems 2 and 3

Lemma 21 (Adapted from [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]Lemma 4.2]). Let m, n, k ∈ N * , m ≥ 2nk, q = 3 k ,. We have

Proof. We first see that, for z

Consider A as a map Z m q → Z n q . We want to find a bound of the number of z in {-1, 0, 1} m such that there is no other element in {-1, 0, 1} m with image Az ∈ Z n q . In the worst case, q n -1 elements of {-1, 0, 1} m have this property and all the other elements have the same value through multiplication by A. Thus,

the later inequality using m ≥ 2nk.

Lemma 22 (Structured version of

We have

Proof. We first see that, for z ∈ S m R if ∃z ̸ = z ∈ S m R such that Az = Az, then we have Pr z←$S l R z = z Az = Az ≤ 1 2 . Consider A as a map R l q → R q . We want to find a bound of the number of z in S l R such that there is no other element in S l R with image Az ∈ R q . In the worst case, q d -1 elements of S l R have this property and all the other elements have the same value through multiplication by A. Thus,

the later inequality using l ≥ 2k.

Let d a power of 2, l ≥ 2 log(q) + 1 and s ≥ 12r ld,ϵ . Then,

Proof. The proofs of the two inequalities are similar. We prove the first one. Let µ the probability we want to bound. Let Bad the set of matrices X ∈ Z n×(m+l) q such that SD D s,X , U Z n q > 2ϵ. We note that, by Lemma 1,

Thus,

D.2 Detailed games for the proof of Theorem 2 of Section 6

return 0 8 : for id ∈ AskedSk :

10 : for (id, µ) ∈ AskedSign :

Verify(id, µ, z)

Sign(id, T id , µ)

G1 (A = (A1, A2)) G2 (A = (A1, A2)) Sign(id, T id , µ)

1 : u := H2(id, µ)

2 : z ← SampleD ((A∥H1(id)) , T id , u, s sign )

3 : return z Verify(id, µ, z) G3 (A = (A1, A2)) Sign(id, T id , µ) : / / note that T A won't be used G5 (A = (A1, A2))

There is no other changes. SIS n,m,Bound SIS ,q (B) round ( log ( self . sid , 2) , 2)) + " \ n " txt += " s s i g =" + str ( self . ssign ) txt += " , l o g ( s s i d , 2 ) = " + str ( round ( log ( self . ssign , 2) , 2)) + " \ n " txt += " S t a n d a r d d e v i a t i o n s f o r IBSPW : \ n " txt += "s PW=" + str ( self . sid ) txt += " , l o g ( s PW , 2 ) = " + str ( round ( log ( self . s_PW , 2) , 2)) + " \ n " txt += "sp PW=" + str ( self . sid ) txt += " , l o g ( sp PW , 2 ) = " + str ( round ( log ( self . sp_PW , 2) , 2)) + " \ n " txt += "spp PW=" + str ( self . ssign ) txt += " , l o g ( spp PW , 2 ) = " + str ( round ( log ( self . spp_PW , 2) , 2)) print ( txt ) def print_sizes ( self ): txt = "SIGNATURE SIZES : " txt += "IBSR=" + str ( round ( self . size_sign / 10**6 , 2)) + "Mo" txt += " IBSRPW=" + str ( round ( self . size_sign_PW / 10**6 , 2)) + "Mo" txt += " \nPUBLIC KEY SIZE : " txt += "mpk=" + str ( round ( self . size_pk / 10**6 , 2)) + "Mo" txt += " \nSECRET KEY SIZES : " txt += "msk=" + str ( round ( self . size_sk / 10**6 , 2)) + "Mo, " txt += " s k i d=" + str ( round ( self . size_sk_id / 10**6 , 2)) + "Mo"