Practical Implementation of Ring-SIS/LWE Based Signature and IBE

Abstract

Lattice-based signature and Identity-Based Encryption are well-known cryptographic schemes, and having both efficient and provable secure schemes in the standard model is still a challenging task in light of the current NIST post-quantum competition. We address this problem in this paper by mixing standard IBE scheme, à la ABB (EUROCRYPT 2010) on Ring-SIS/LWE assumptions with the efficient trapdoor of Peikert and Micciancio (EUROCRYPT 2012) and we provide an efficient implementation. Our IBE scheme is more efficient than the IBE scheme of Ducas, Lyubashevsky and Prest based on NTRU assumption and is based on more standard assumptions. We also describe and implement the underlying signature scheme, which is provably secure in the standard model and efficient.

1 Introduction

The concept of Identity Based Encryption (IBE) was defined by Shamir [Sha85]. It is considered as an alternative to the classical Public Key Encryption (PKE), often requiring a dedicated infrastructure. Indeed, the public key related to a person is simply its identity, such as her email address or her social security number, and the associated private key is generated by a trusted authority using a master public key. Thus, IBE hugely simplifies keys generation and distribution in a multi-user system. The first IBE constructions appeared in [BF01, Coc01], and were based respectively on bilinear maps and on quadratic residue assumptions.

Since the work of Shor in 1994 [Sho97], the hardness of such number theoretic assumptions is extremely reduced when faced to a quantum computer. This has motivated many research work attempting to achieve quantum security. The first supposedly post-quantum IBE scheme, which was introduced in 2008 by Gentry et al. [GPV08], was based on hard lattice problems. Since then, many improvements have been proposed [CHKP10, ABB10, DLP14].

Lattice-based cryptography. Lattice-based cryptography starts with the work of Ajtai [Ajt96], and uses hard problems on lattices as the foundation of secure cryptographic constructions. A lattice is an infinite arrangement of regularly spaced points, and it can be generated as the set of all linear combinations of m independent vectors in $\mathbb {R}^{n}$, called a basis. One fundamental hard problem on lattices is the Shortest Vector Problem (SVP): given some basis, find the shortest non zero vector of the lattice. Lattice-based cryptography is based on the assumption that this problem and its variants are hard problems even for an approximation factor polynomial in the dimension of the lattice.

Lattice-based cryptographic constructions are mainly based on two well known problems: the Small Integer Solution problem (SIS) and its Inhomogeneous variant (ISIS) [Ajt96], and the Learning With Errors problem (LWE) introduced by Regev [Reg05]. In particular, the ISIS problem consists in finding a short vector $\mathbf {x} \in \mathbb {Z}^{m}$ such that $\mathbf {A x} = \mathbf {u} \mod q$, given an uniformly random matrix $\mathbf {A} \in \mathbb {Z}_{q}^{n \times m}$ and some $\mathbf {u} \in \mathbb {Z}_{q}^{n}$. Ajtai and Regev gave reductions from worst-case lattice problems to the average case LWE and SIS problems.

Few years later, structured variants of the LWE and SIS problems were proposed [Mic07, SSTX09], called Ring-SIS and Ring-LWE. These problems are preferred in practice, since they enjoy smaller storage and faster operations. There also exist reductions from worst-case ideal lattice problems to these structured variants [LPR10, SSTX09, LM06, PR06]. These two problems can be used to construct many basic cryptographic primitives such as PKE (adapting the schemes from [Reg05, GPV08]) and signatures [Lyu12, DDLL13, DM14].

Lattice Trapdoors. To construct IBE or Attribute Based Encryption (ABE), we can use trapdoors for the SIS problem. Initially described by Ajtai [Ajt96], a trapdoor $\mathbf {T_{A}} \in \mathbb {Z}^{m \times m}$ for $\mathbf {A} \in \mathbb {Z}_{q}^{n \times m}$ is a short basis of vectors satisfying $\mathbf {T_{A}} \cdot \mathbf {A} = \mathbf {0} \mod q$, generated together with $\mathbf {A}$. Given only $\mathbf {A}$, it is hard to find such a short basis but, with the knowledge of $\mathbf {T_{A}}$ it is easy to invert the SIS (and the ISIS) problem. Trapdoors constructions were improved by [AP09], and then described for ideal lattices in [SSTX09].

Micciancio and Peikert [MP12] proposed a new construction allowing a faster inversion of the ISIS problem, by reducing it to the inversion of a smaller problem for some structured gadget matrix $\mathbf {G} \in \mathbb {Z}_{q}^{n \times l}$. The matrix $\mathbf {A} \in \mathbb {Z}_{q}^{n \times m}$ is generated with its associated short basis $\mathbf {R} \in \mathbb {Z}^{(m-l) \times l}$, as $\mathbf {A} = ( \mathbf {A}' \, | \, \mathbf {H G} - \mathbf {A}' \mathbf {R} )$ where $\mathbf {A}' \in \mathbb {Z}_{q}^{n \times (m-l)}$ is uniformly sampled, and $\mathbf {H} \in \mathbb {Z}_{q}^{n \times n}$ is an invertible element. In [GM18], Micciancio and Genise improved the inversion of the ISIS problem in the ring variant with an arbitrary modulus.

Lattice-based IBE. The first lattice-based IBE [GPV08] relies on the Dual-Regev encryption scheme. In Dual-Regev, a public key consists in a vector $\mathbf {u} = \mathbf {A} \mathbf {x} \mod q$, for a short vector $\mathbf {x} \in \mathbb {Z}^{m}$ (which is the secret key). To build the IBE, an identity can be mapped to a public key via a hash function $\mathcal {H}: \lbrace 0, 1 \rbrace ^{*} \rightarrow \mathbb {Z}_{q}^{n}$ modeled as a random oracle. The master secret key of the IBE is a short trapdoor $\mathbf {T_{A}}$, that makes it possible to extract a secret key $\mathbf {x}$ associated to any id by inverting $\mathbf {A} \mathbf {x} = \mathcal {H}(id) \mod q$.

This construction was later improved by removing the Random Oracle Model (ROM) [CHKP10, ABB10]. In ABB, a publicly computable matrix $\mathbf {A}_{id} = \left( \mathbf {A} \, | \, F(id) \right) \in \mathbb {Z}_{q}^{n \times (m+m')}$, is associated to an identity id, where $F(\cdot )$ is mapping identities to matrices in $\mathbb {Z}_q^{n \times m'}$. As a result, the secret key for an identity id is a short vector $\mathbf {x} \in \mathbb {Z}^{m+m'}$, such that $\mathbf {A}_{id} \mathbf {x} = \mathbf {u} \mod q$. To find such an $\mathbf {x}=(\mathbf {x}_{1}^{T} | \mathbf {x}_{2}^{T})^{T}$, it is only required to sample a short $\mathbf {x}_{2} \in \mathbb {Z}^{m'}$, and to use $\mathbf {T_{A}}$ to invert the following ISIS problem: find a small $\mathbf {x}_{1} \in \mathbb {Z}^{m}$ such that $\mathbf {A} \mathbf {x}_{1} = \mathbf {u} - F(id) \mathbf {x}_{2}$. In 2014, Ducas et al. [DLP14] gave an NTRU variant of the GPV IBE scheme. In their work, the public key is built using NTRU lattices, which improves the efficiency of the scheme.

Our Contributions. In this paper, we provide the first software implementation of a standard model IBE based on the hardness of Ring-SIS/LWE. Our main goal is to show that IBE schemes can, and without sacrificing efficiency, guarantee better security by being on the standard model and relying on a classical assumption on lattice problems. We instantiate our implemented IBE scheme from the selective secure IBE scheme described in [ABB10] as well as from the recent variant of trapdoor described in [MP12, GM18]. We also describe and implement the underlying signature scheme that achieve a selective notion of unforgeability based on the hardness of Ring-SIS/LWE. We choose to implement these selective secure schemes in the standard model due to their efficiency and also their simplicity compared to other adaptive secure variants [ABB10, DM14]. Our constructions work over polynomial rings $R_{q} = \mathbb {Z}_{q}[x] / (x^n + 1)$ with n a power of two and q a prime modulus congruent to $1 \bmod 2n$. This setting is wide-spread in ideal lattice cryptography due to its efficiency thanks to the Number Theoretic Transform (NTT) representation. Note that our complete implementation can be found at https://github.com/lbibe/code.

We provide our implementation as a general-purpose thread-safe C++ library. We take much care to write plain C++ and not to explicitly include highly specialized instructions, such as AVX2 and NEON, in order to ensure portability over several hardware architectures. Instead, we rely on the GCC 7.2 compiler to make vectorization, and a set of optimization methods and multi-threading have been introduced using a number of C++11 specific features. More importantly, we design our code to be modular and provide three software layers, each of which is of independent interest. The software layers are (1) the different Gaussian sampling techniques based on [DP16, GM18], (2) the Gaussian sampling for trapdoor lattice with arbitrary modulus using [MP12], and (3) the underlying cryptographic constructions (both IBE and the related signature).

We experimentally evaluate the performance of these two constructions. To our surprise, the obtained runtime is fast and even quite close to that of other schemes built in the ROM or/and using different security assumptions. We remind that our goal is not to provide the most efficient IBE or signature scheme, but to show that “good” security properties can still be practical for many scenarios. In Tables 1 and 2, we provide a comparison with state-of-the-art implementations of IBE and signature schemes. We note the security parameter as $\lambda$ (classical bit security in Tables 1, 2, 3, 4, 5 and 6) and the lattice dimension as n.

We obtain our results using dual-core Intel i7 2.6 GHz CPU with standard CPU benchmarks. Concerning the IBE schemes, we notice that our Setup (master key generation), compared to DLP-14, is (much) faster (we note that the DLP-14 Setup could now be improved using the recent results in Falcon [FHK+18]), while decryption and Extract are of the same order of magnitude. However, our encryption is twice slower. For the sake of completeness, we include the timings of the paring-based IBE scheme of Boneh-Franklin. As for the signature scheme, we compare our implementation with Falcon [FHK+18] that is the underlying signature scheme of [DLP14]. In our timings, we did not consider the phase of precomputations that we detail later in Sect. 5 (see Tables 5 and 6).

Table 1. Timings for the different operations of IBE schemes: Setup (master key generation), Extract (user private key generation), encryption and decryption. Since Setup is performed only once, we provide the timing of only one single operation. Extract can measure how many users the system can manage. As for Encrypt/Decrypt, we give their throughput in KB per second.

Table 2. Timings for the different operations of signature schemes: KeyGen (key generation), signature and verification. Since KeyGen is performed only once per user, we provide the timing of only one single operation. As for Sign/Verify, we give the timing as the number of sign/verify operations per second.

Related work. In [EBB13], the authors gave a software implementation of the trapdoor of Micciancio and Peikert [MP12] in both matrix and ring variants. They also included this trapdoor into the signature in the ROM of [GPV08]. Recently, in a concurrent work, a software implementation of the improvement lattice trapdoor [MP12, GM18] is given in [GPR+17, DDP+17], with application to respectively the GPV signature and the ABE scheme of [BGG+14].

The only lattice based IBE given with an implementation we are aware of, is the one of Ducas et al. [DLP14]. In [DLP14], the authors gave a proof-of-concept implementation, recently improved by [MSO17]. This IBE scheme is the IBE of [GPV08], working with structured NTRU lattices. The Gram-Schmidt norm of a NTRU basis is quite small and efficiently computed, then the Gaussian sampling using this basis outputs better quality vectors.

Conclusion and Open Problems. Our main contribution is a software implementation of a lattice-based IBE and signature scheme. Both constructions are proven secure in the standard model under the hardness of Ring-SIS/LWE. Our IBE is a ring-version of the selective ABE scheme, adapted using the MP12 trapdoor, we provide its underlying signature scheme and both security proofs.

We stress that our implementation has an efficiency comparable to NTRU based schemes in the ROM, even if we thought at first that a scheme on the standard model and based on Ring-SIS/LWE would be much less efficient. Then, we find it interesting to observe that even with the constraint on the choice of parameters and using a Gaussian sampling, those constructions, which are not using NTRU lattices, can also be efficient.

There are several open questions which would be interesting to answer. First, we choose to study the selective secure IBE scheme of ABB, and a signature scheme which achieve a selective notion of unforgeability. Both schemes can be improved to a better security by using the adaptive IBE scheme of ABB, and by looking at the standard secure signature of [DM14]. We also discuss in Sect. 2.4 the choice of the encoding hash function used in both schemes, which could be improved using the recent results of [LS18]. Finally, we want to modify NFLlib, which for now only allows us to use parameter q of size 30 or 62 bits. As discussed in Sect. 5, using a parameter q in between would optimize our choice of parameters. Note that using a Module variant, as in [DLL+17], could also be a solution.

2 Preliminaries

Notations. Let D be a distribution over some finite set S, then $x \hookleftarrow D$ means that x is chosen from the distribution D and $x \hookleftarrow U(S)$ denotes the sampling of a uniformly random element x from S. We denote column vectors and matrices in bold, respectively by bold lowercase (e.g. $\mathbf {x}$) and bold uppercase (e.g. $\mathbf {A}$). The euclidean norm of the vector $\mathbf {x}$ is denoted by $\Vert \mathbf {x} \Vert$. The norm of a matrix $\Vert \mathbf {T} \Vert = \max _{i} \Vert \mathbf {t}_{i} \Vert$ is the maximum norm of its column vectors.

Lattices. An m-dimensional full-rank lattice $\varLambda$ is a discrete additive subgroup of $\mathbb {R}^{m}$. A lattice is the set of all integer combinations of some linearly independent basis vectors, $\mathbf {B} = \lbrace \mathbf {b}_{1}, \cdots , \mathbf {b}_{m} \rbrace \in \mathbb {R}^{m \times m}$, $\varLambda (\mathbf {B}) = \lbrace \sum _{i=1}^{m} z_{i} \mathbf {b}_{i} : z_{i} \in \mathbb {Z}\rbrace$. For n a power of two, the polynomial ring $R = \mathbb {Z}[x] / (x^n\,+\,1)$ is isomorphic to the integer lattice $\mathbb {Z}^{n}$, a polynomial $f = \sum _{i=0}^{n-1} f_{i} x^{i}$ in R corresponds to the integer vector of its coefficients $(f_{0}, \cdots , f_{n-1})$ in $\mathbb {Z}^{n}$. The norm of a polynomial $\Vert f \Vert$ is the norm of its coefficients vector. For the rest of the paper we will work with polynomials over R, or ${R_{q} = R / q R = \mathbb {Z}_{q}[x] / (x^n + 1)}$ where q is a prime such that ${q = 1 \mod 2n}$.

Gaussian distribution. The Gaussian function of center $\mathbf {c} \in \mathbb {R}^{n}$ and width parameter $\sigma$ is defined as $\rho _{\sigma , \mathbf {c}} (\mathbf {x}) = \exp (- \pi \frac{\left\| \mathbf {x} - \mathbf {c}\right\| ^2}{\sigma ^2})$, for all $\mathbf {x} \in \mathbb {R}^{n}$. We can extend this definition to a positive definite covariance matrix $\mathbf {\Sigma } = \mathbf {B} \mathbf {B}^{T}$: $\rho _{\sqrt{\varSigma }, \mathbf {c}}(\mathbf {x}) = \exp \left( - \pi (\mathbf {x} - \mathbf {c})^{T} \mathbf {\Sigma }^{-1} (\mathbf {x} - \mathbf {c}) \right)$. The discrete Gaussian distribution over a lattice $\varLambda$ is defined as $D_{\varLambda , \sigma , \mathbf {c}}(\mathbf {x}) = \frac{\rho _{\sigma , \mathbf {c}}(\mathbf {x})}{\rho {\sigma , \mathbf {c}}(\varLambda )}$ where $\rho _{\sigma , \mathbf {c}}(\varLambda ) = \sum _{\mathbf {x} \in \varLambda } \rho _{\sigma , \mathbf {c}}(\mathbf {x})$.

Tailcut. To tailcut less than $2^{-\lambda }$ of a one-dimensional Gaussian, we use the fact that $\text {Pr}_{\mathbf {x} \hookleftarrow D_{\mathbb {Z}, \sigma }} \left[ | x | > t \sigma \right] \le \mathrm {erfc}\left( t / \sqrt{2} \right)$, where $\mathrm {erfc}(x) = 1 - \frac{2}{\pi } \int _{0}^{x} \exp ^{-t^{2}} \, \mathrm {d}t$. For example, $t=12$ for $\lambda = 100$. Then, a vector $\mathbf {x}$ sampled in $D_{\mathbb {Z}^{m}, \sigma }$ would have small norm $\Vert \mathbf {x} \Vert \le t \sigma \sqrt{m}$ with overwhelming probability.

2.1 Cryptographic Problems on Lattices

Ring-SIS/Ring-LWE. We use ring variants of SIS and LWE, proposed by [LM06, PR06] and [SSTX09, LPR10], and proven to be at least as hard as the GapSVP/SIVP problems on ideal lattices.

Definition 1

(Ring-SIS$_{q, m, \beta }$). Given $\mathbf {a} = (a_{1}, \cdots , a_{m})^{T} \in R_{q}^{m}$ a vector of m uniformly random polynomials, find a non-zero vector of small polynomials $\mathbf {x} = (x_{1}, \cdots , x_{m})^{T} \in R^{m}$ such that $\mathbf {a}^{T} \mathbf {x} = \sum _{i=1}^{m} a_{i} \cdot x_{i} = 0 \mod q$ and $0 < \Vert \mathbf {x} \Vert \le \beta$.

Definition 2

(Decision Ring-LWE$_{n, q, D_{R, \sigma }}$). Given $\mathbf {a} = (a_{1}, \cdots , a_{m})^{T} \in R_{q}^{m}$ a vector of m uniformly random polynomials, and $\mathbf {b} = \mathbf {a} s + \mathbf {e}$, where $s \hookleftarrow U(R_{q})$ and $\mathbf {e} \hookleftarrow D_{R^{m}, \sigma }$, distinguish $(\mathbf {a}, \mathbf {b} = \mathbf {a} s + \mathbf {e})$ from $(\mathbf {a}, \mathbf {b})$ drawn from the uniform distribution over $R_{q}^{m} \times R_{q}^{m}$.

2.2 Dual-Regev Public Key Encryption

The Dual-Regev PKE, first described in [GPV08, Sect. 7.1], is the starting point to build an IBE on lattices. We describe its ring variant, with parameters n, m, and q integers and $\zeta$, $\tau$ two real numbers.

• Key Generation: The secret key corresponds to a vector of small norm polynomials $\mathbf {x} \in R^m$, sampled from $D_{R^{m},\zeta }$. The public key contains a uniformly random chosen vector of polynomials $\mathbf {a} \hookleftarrow U(R_{q}^{m})$ and one more polynomial $u = \mathbf {a}^{T} \mathbf {x} \in R_{q}$.

• Encryption: The plaintext message consists in a binary polynomial $M \in R_{2}$. The ciphertext is composed of $m+1$ Ring-LWE samples: $(\mathbf {b} = \mathbf {a} s + \mathbf {e}, c = u \cdot s + e' + \lfloor q / 2 \rfloor M) \in R_{q}^{m} \times R_{q}$, where s is a uniformly chosen polynomial in $R_{q}$, and $e'$, $\mathbf {e}$ follow a discrete Gaussian distribution respectively on R and $R^{m}$ of parameter $\tau$. The ciphertext is then $(\mathbf {b}, c)$.

• Decryption: The recipient uses his private key $\mathbf {x}$ to compute: $\mu = c - \mathbf {b}^{T} \mathbf {x} = e' - \mathbf {e}^{T} \mathbf {x} + \lfloor q / 2 \rfloor M .$ To recover M, he looks at each coefficient of $\mu$, if $\mu _{i}$ is closer to 0 than to $\lfloor q / 2 \rfloor$, the message bit $M_{i} = 0$, otherwise $M_{i} = 1$.

Security. The ring-variant of the Dual-Regev scheme is IND-CPA secure under the hardness of Ring-LWE$_{n, q, D_{R, \tau }}$ [LPR13]. The correctness of the decryption holds if the error term $\Vert e' - \mathbf {e}^{T} \mathbf {x} \Vert$ is small enough, less than $\lfloor q/4 \rfloor$.

2.3 Cryptographic Definition of an IBE Scheme

Identity Based Encryption. Let $\lambda$ be the security parameter of the scheme, an Identity Based Encryption (IBE) is composed of four probabilistic polynomial timealgorithms (Setup, Extract, Encrypt, Decrypt).

Security Game. We describe the ciphertext indistinguishability under a selective-identity chosen-plaintext attack (IND-sID-CPA) as a game between an adversary $\mathcal {A}$ and a challenger. The game proceeds as follows:

Init: The adversary $\mathcal {A}$ chooses the challenge identity $id^{*}$.

Setup: The challenger runs $\textsf {Setup} (1^{\lambda })$, gives the master public key msk to $\mathcal {A}$.

Queries 1: The adversary can make private-key extraction queries on identities $id \ne id^{*}$, and the challenger answers by running $sk_{id} \leftarrow \textsf {Extract} (1^{\lambda }, mpk , msk, id)$.

Challenge: Adversary $\mathcal {A}$ outputs two plaintexts $M_{0}, M_{1} \in \mathcal {M}$. The challenger chooses a random bit $b^{*} \hookleftarrow \lbrace 0, 1 \rbrace$ and, sets the challenge ciphertext to $C^{*} = \textsf {Encrypt} (1^{\lambda }, mpk, id^{*}, M_{b^*})$. The challenge ciphertext $C^{*}$ is sent to $\mathcal {A}$.

Queries 2: Adversary can make additional queries (answered as in Queries 1).

Guess: Eventually, $\mathcal {A}$ outputs a bit b and wins if $b^{*} = b$.

The advantage of the adversary $\mathcal {A}$ playing the IND-sID-CPA security game above is $\text {Adv}(\mathcal {A})^{\text {IND-sID-CPA}}_{\text {IBE}} = \left| \text {Pr} \left[ {b = b^{*}} \right] - \frac{1}{2} \right| .$ An IBE scheme is IND-sID-CPA secure if, for all PPT adversary $\mathcal {A}$, his advantage $\text {Adv}(\mathcal {A})^{\text {IND-sID-CPA}}_{\text {IBE}}$ is negligible.

2.4 Hash Functions

Our IBE and signature schemes use an encoding hash function $H:\mathbb {Z}_q^n \rightarrow R_q$ to map identities in $\mathbb {Z}_q^n$ to invertible elements in $R_q$. The security proof requires the map H to satisfy an injectivity property: the difference of two elements has to be invertible in $R_q$. Such hash functions have been called encoding with Full-Rank Differences (FRD) in [ABB10] and they must satisfy the following properties:

• 1. for all distinct $u,v \in \mathbb {Z}_q^n$, the element $H(u)-H(v) \in R_q$ is invertible; and

• 2. H is computable in polynomial time (in $n\log q$).

Implementation of FRD Hash Functions. An invertible element of $R_q$ in the NTT domain corresponds to n non-zero integers of bit-size k. We implement our encoding in a naive manner, by generating these n integers using an PRNG with the identity id as a seed. In the literature, Ducas and Micciancio [DM14] chose the ring $R_q$, with q a power of 3 because in such ring any polynomial of degree less than n / 2 with coefficients in $\lbrace -1, 0, 1 \rbrace$ is invertible. Recently, Lyubashevsky and Seiler have proposed in [LS18] a way to construct such encoding using the fact that small non-zero polynomials are invertible in cyclotomic rings. They also use that $x^n + 1$ splits modulo q, and perform half of the FFT recursion tree, depending on the logarithm of the number of splittings, and at the end of the FFT tree, for small degree polynomials, multiplications have to be performed using naive or Karatsuba algorithm.

3 Trapdoors on Lattices

The construction of our IBE scheme relies on a kind of trapdoors, introduced by Ajtai [Ajt96], and then improved, in particular in [MP12, GM18]. We define the trapdoor function $f_{\mathbf {A}}(\mathbf {x}) = \mathbf {A} \mathbf {x} \mod q$ which represents the Inhomogeneous SIS problem. The trapdoor consists in a short basis $\mathbf {T_{A}} \in \mathbb {Z}^{m \times m}$ of the m-dimensional integer lattice: $\varLambda ^{\perp }_{q}(\mathbf {A}) := \lbrace \mathbf {x} \in \mathbb {Z}^{m} \; \text {such that} \; \mathbf {A} \mathbf {x} = \mathbf {0} \mod q \rbrace$. Thanks to the short basis $\mathbf {T_{A}}$, we sample from a Gaussian distribution with a small parameter $\sigma$ to obtain short vectors in $\varLambda ^{\perp }_{q}(\mathbf {A})$. Then, solve the SIS, ISIS or LWE problems.

We use the ring version of a second notion of trapdoors (gadget based trapdoors) introduced by [MP12], and recently improved by [GM18], which are more efficient. In this construction, the matrix $\mathbf {A}$ is constructed by picking the first part uniformly at random, and the second part is almost uniformly random by including a structured gadget, to help the inversion of the SIS problem.

3.1 Gadget-Based Trapdoor Construction

Gadget vector. We use the gadget vector $\mathbf {g} \in R_{q}^{k}$ for which the inversion of $f_{\mathbf {g}^{T}}(\mathbf {z}) = \mathbf {g}^{T} \mathbf {z} \in R_{q}$ is easy: it is a vector of constant polynomials, $\mathbf {g} = (1, 2, 4, \cdots , 2^{k-1})^{T} \in R_{q}^{k}$ with $k = \lceil \log _{2} q \rceil$. The lattice $\varLambda ^{\perp }_{q}(\mathbf {g}^{T})$ has a publicly known basis $\mathbf {B}_{q} \in R^{k \times k}$, which satisfies $\Vert \tilde{\mathbf {B}}_{q} \Vert \le \sqrt{5}$.

Trapdoor construction. The trapdoor construction is an almost uniformly random vector of polynomials $\mathbf {a} \in R_{q}^{m}$ starting from a uniformly random vector of polynomials $\mathbf {a}' \in R_{q}^{m-k}$ (Algorithm 3.1.1) that hides the structured vector $\mathbf {g}$, together with a trapdoor $\mathbf {T}$ that enables its owner to recover this structure when needed.

Definition 3

($\mathbf {g}$-trapdoor). Let $\mathbf {a} \in R_{q}^{m}$ and $\mathbf {g} \in R_{q}^{k}$ with $k = \lceil \log _{2} q \rceil$ and $m > k$. A $\mathbf {g}$-trapdoor for $\mathbf {a}$ consists in a matrix of small polynomials $\mathbf {T} \in R^{(m-k) \times k}$, following a discrete Gaussian distribution of parameter $\sigma$, such that for some invertible element $h \in R_{q}$. The polynomial h is called the tag associated to $\mathbf {T}$. The quality of the trapdoor is measured by its largest singular value $s_{1}(\mathbf {T})$.

3.2 Preimage Sampling

Peikert Sampler. To find $\mathbf {x}$ such that $f_{\mathbf {a}^{T}}(\mathbf {x}) = u$, using this trapdoor, the idea is to find a $\mathbf {z}$ satisfying $f_{\mathbf {g}^{T}}(\mathbf {z}) = h^{-1} \cdot (u - \mathbf {a}^{T} \mathbf {p})$ and following a discrete Gaussian distribution of parameter $\alpha$, where $\mathbf {p}$ is a perturbation vector with covariance matrix . Then, , has covariance matrix and satisfies . This idea is summarized in Algorithm 3.2.1 SamplePre.

It uses the two following algorithms:

• SamplePolyG$(\sigma , v) \rightarrow \mathbf {z}$, takes as input a Gaussian parameter $\sigma$ and a target $v \in R_{q}$, outputs $\mathbf {z} \hookleftarrow D_{\varLambda _{q}^{\perp }(\mathbf {g}^{T}), \alpha , v}$, with $\alpha = \sqrt{5} \sigma$,

• SampleP$(q, \zeta , \alpha , \mathbf {T}) \rightarrow \mathbf {p}$, takes as input the ring modulus q, $\zeta$ and $\alpha$ two Gaussian parameters and $\mathbf {T} \hookleftarrow D_{R^{(m-k) \times k}, \sigma }$, outputs $\mathbf {p} \hookleftarrow D_{R^{m}, \sqrt{\varSigma _{\mathbf {p}}}}$, where with $\zeta > s_{1}(\mathbf {T}) \alpha$.

4 Identity-Based Encryption

Our IBE construction is a ring-version of the selective IBE of [ABB10], adapted to use the gadget-based trapdoor of Micciancio and Peikert [MP12] (also adapted to rings, described in Sect. 3). We use the same encoding with Full-Rank Differences H to map identities to invertible elements in $R_{q}$ (defined in Sect. 2.4).

The master public key consists in a uniformly random polynomial $u \in R_{q}$ and a pseudo-random vector of polynomials $\mathbf {a} \in R_{q}^{m}$. The master secret key is a $\mathbf {g}$-trapdoor $\mathbf {T} \in R^{(m-k) \times k}$ for $\mathbf {a}$ with associated tag set to zero: $\mathbf {a} = (\mathbf {a}'^{T} \, | \, - \mathbf {a}'^{T} \mathbf {T})^{T}$.

Then, thanks to $\mathbf {a}$, we can compute a publicly computable vector associated to an identity id:

$$ \mathbf {a}_{id} = \mathbf {a}^{T} + ( \mathbf {0} \, | \, H(id) \mathbf {g} )^{T} = (\mathbf {a}'^{T} \, | \, H(id) \mathbf {g} - \mathbf {a}'^{T} \mathbf {T} )^{T}. $$

The secret key associated to an identity id is a short vector $\mathbf {x} \in R^{m}$, computed thanks to the algorithm SamplePre, which satisfies $\mathbf {a}_{id}^{T} \mathbf {x} = u \in R_{q}$. We also use the Dual-Regev encryption scheme to encrypt (using $\mathbf {a}_{id}$) and decrypt (using $\mathbf {x})$.

4.1 Our Construction

The parameters of the scheme are n, m, q, k, and q integers, and $\sigma$, $\alpha$, $\gamma$, $\tau$, and $\zeta$ are real numbers, and chosen as described in Sect. 4.2.

• 1. Setup$(1^{n}) \rightarrow (mpk,\,msk)$:

  • (a) Compute $\mathbf {a} \in R_{q}^{m}$ associated to its trapdoor $\mathbf {T} \in R^{(m-k) \times k}$, $(\mathbf {a}, \mathbf {T}) \leftarrow \textsf {TrapGen}(q, \sigma , h=0)$, i.e. $\mathbf {a} = (\mathbf {a}'^{T} \, | \, - \mathbf {a}'^{T} \mathbf {T})^{T}$,

  • (b) Sample a uniformly random polynomial $u \hookleftarrow U(R_{q})$,

  • (c) Output $mpk = (\mathbf {a}, u) \in R_{q}^{m+1}$ and $msk = \mathbf {T} \in R^{(m-k) \times k}$.

• 2. Extract$(mpk = (\mathbf {a}, u), msk = \mathbf {T}, id \in \mathcal {ID}) \rightarrow sk_{id}$:

  • (a) Compute the tag $h_{id} = H(id)$,

  • (b) Compute $\mathbf {a}_{id} = \mathbf {a}^{T} + ( \mathbf {0} \, | \, h_{id} \mathbf {g} )^{T} = (\mathbf {a}'^{T} \, \left| \, h_{id} \mathbf {g} - \mathbf {a}'^{T} \mathbf {T} )^{T} \right.$,

  • (c) Sample a short $\mathbf {x} \leftarrow \textsf {SamplePre}\left( \mathbf {T}, \mathbf {a}_{id}, h_{id}, \zeta , \sigma , \alpha , u \right)$, such that $\mathbf {a}_{id}^{T} \mathbf {x} = u$,

  • (d) Output $sk_{id} = \mathbf {x} \in R^{m}$.

• 3. Encrypt$(mpk = (\mathbf {a}, u), id, M \in R_{2}) \rightarrow C$:

  • (a) Compute the tag $h_{id}$, and $\mathbf {a}_{id}$ like above,

  • (b) Sample $s \hookleftarrow U(R_{q})$, $\mathbf {e}_{0} \hookleftarrow D_{R^{m-k}, \tau }$, $\mathbf {e}_{1} \hookleftarrow D_{R^{k}, \gamma }$, and $e' \hookleftarrow D_{R, \tau }$,

  • (c) Compute $\mathbf {b} = \mathbf {a}_{id} s + (\mathbf {e}_{0}^{T} \, | \, \mathbf {e}_{1}^{T} )^{T} \in R_{q}^{m}$, and $c = u \cdot s + e' + \lfloor q / 2 \rfloor M \in R_{q}$,

  • (d) Output $C = (\mathbf {b}, c) \in R_{q}^{m+1}$.

• 4. Decrypt$(sk^{id} = \mathbf {x}, C = (\mathbf {b}, c)) \rightarrow M$:

  • (a) Compute $\text {res} = c - \mathbf {b}^{T} \mathbf {x} = e' - (\mathbf {e}_{0}^{T} \, | \, \mathbf {e}_{1}^{T} ) \mathbf {x} + \lfloor q / 2 \rfloor M \in R_{q}$,

  • (b) For each $\text {res}_{i}$, if it is closer to $\lfloor q / 2 \rfloor$ than to 0, $M_{i} = 1$, otherwise $M_{i} = 0$.

Correctness. Let $\mathbf {x} = (\mathbf {x}_{0}^{T} | \mathbf {x}_{1}^{T})^{T}$ with $\mathbf {x}_{0} \in R_{q}^{m-k}$ and $\mathbf {x}_{1} \in R_{q}^{k}$. To decrypt a ciphertext, we need the error term $e' - (\mathbf {e}_{0}^{T} \, | \, \mathbf {e}_{1}^{T} ) (\mathbf {x}_{0}^{T} | \mathbf {x}_{1}^{T})^{T} = e' - \mathbf {e}_{0}^{T} \mathbf {x}_{0} - \mathbf {e}_{1}^{T} \mathbf {x}_{1}$ to be bounded by $\lfloor q/4 \rfloor$ (see Sect. 4.2 on the choice of the parameters).

Theorem 1

Our IBE construction with parameters n, m, q, k, $\sigma$, $\alpha$, $\gamma$, $\tau$ and $\zeta$ chosen as below is IND-sID-CPA secure in the standard model under the hardness of Ring-LWE$_{n, q, D_{R, \tau }}$.

Proof

To prove the IND-sID-CPA security of the IBE scheme described above, we use a sequence of games starting from the original IND-sID-CPA game (Sect. 2.3). In the final game, the adversary has no information left about the initial message and hence has advantage zero. To ensure that the adversary has a negligible advantage in winning the IND-sID-CPA game, we show that a probabilistic polynomial timeadversary cannot distinguish between games.

Game 0. The original IND-sID-CPA game between an adversary $\mathcal {A}$ and an IND-sID-CPA challenger.

Game 1. In the Game 0, the master public key of the scheme is $mpk = (\mathbf {a}, u)$, with $\mathbf {a}$ generated thanks to $\textsf {TrapGen}(q, \sigma , h=0)$ with an associated trapdoor $\mathbf {T}$ (i.e. $\mathbf {a} = (\mathbf {a}'^{T} \, | \, - \mathbf {a}'^{T} \mathbf {T})^{T}$), and u is a uniform polynomial in $R_{q}$.

In Game 1, we change the generation of the public vector $\mathbf {a}$ by adding information about the challenge identity $id^{*}$ targeted by $\mathcal {A}$. The public parameter $\mathbf {a}$ is now generated thanks to $\textsf {TrapGen}(q, \sigma , \mathbf {a}', -h_{id^{*}})$, i.e. $\mathbf {a} = (\mathbf {a}'^{T} \, | \, -h_{id^{*}} \mathbf {g} - \mathbf {a}'^{T} \mathbf {T} )^{T},$ where the first part $\mathbf {a}' \in R_{q}^{m-k}$ is chosen from the uniform distribution. For the second part, $\mathbf {a}'^{T} \mathbf {T} = \left( \sum _{i=1}^{m-k} a_{i} t_{i, 1}, \cdots , \sum _{i=1}^{m-k} a_{i} t_{i, k} \right)$, is either computationally or statistically indistinguishable from the uniform distribution depending on the trapdoor instantiation we choose. For the computational instantiation, we set $m-k = 2$, and $\mathbf {a}' = (1, a)$ with $a \hookleftarrow U(R_{q})$ and obtain a public vector $\mathbf {a} = \left( 1, a \, \left| \, - (a \cdot t_{2,1} + t_{1,1}), \cdots , - (a \cdot t_{2,k} + t_{1,k}) \right. \right) .$ To ensure such $\mathbf {a}$ looks uniform, we use the Ring-LWE assumption in its normal form: where the secret and the error follow the same distribution.

The adversary $\mathcal {A}$ issues private key queries on identities $id \ne id^{*}$, and the challenger has to answer to these queries. To do that, he computes $\mathbf {a}_{id} = \mathbf {a}^{T} + (\mathbf {0} \, | \, h_{id} \mathbf {g})^{T} = (\mathbf {a}'^{T} \, | \, (h_{id} - h_{id^{*}}) \mathbf {g} - \mathbf {a}'^{T} \mathbf {T})^{T},$ and use $\textsf {SamplePre}(\mathbf {T}, \mathbf {a}_{id}, h_{id} - h_{id^{*}}, \zeta , \sigma , \alpha , u)$ to compute a private key associated to id: $\mathbf {x} \in R^{m}$ satisfying $\mathbf {a}_{id}^{T} \mathbf {x} = u$, because $h_{id} - h_{id^{*}}$ is invertible. Note that for $id = id^{*}$, $\mathbf {a}_{id} = ( \mathbf {a}'^{T} | - \mathbf {a}'^{T} \mathbf {T})^{T}$, and $\mathcal {B}$ can no longer answer private key queries.

Game 2. In the last game, we change how the challenge ciphertext is build. The ciphertext $C^{*}$ is now chosen uniformly in $R_{q}^{m} \times R_{q}$. The last step is to show that Game 1 and Game 2 are computationally indistinguishable for $\mathcal {A}$ by doing a reduction from the Ring-LWE problem. Suppose that $\mathcal {A}$ has non-negligible advantage in distinguishing these two games. Then a simulator $\mathcal {B}$ can use $\mathcal {A}$ to solve the Ring-LWE problem with non-negligible advantage (Sect. 2.1).

The simulator $\mathcal {B}$ receives $m-k+1$ samples $(a_{i}, b_{i})_{0 \le i \le m-k}$ as an instance of the decisional Ring-LWE problem. The simulator also receives the challenge identity $id^{*}$ from the adversary $\mathcal {A}$. Let $\mathbf {a}' = (a_{1}, \cdots , a_{m-k})^{T} \in R_{q}^{m-k}$ and $\mathbf {b}' = (b_{1}, \cdots , b_{m-k})^{T} \in R_{q}^{m}$. The simulator runs $\textsf {TrapGen}(q, \sigma , \mathbf {a}', -h_{id^{*}})$, because $\mathbf {a}'$ is following a uniform distribution thanks to the Ring-LWE assumption, and gets back $\mathbf {a} = (\mathbf {a}'^{T} \, | \,-h_{id^{*}} \mathbf {g} - \mathbf {a}'^{T} \mathbf {T} )^{T}$, as in Game 1. Next, $\mathcal {B}$ sets $u = a_{0}$ and sends $(\mathbf {a}, u)$ to $\mathcal {A}$ as the master public key of the scheme. The adversary $\mathcal {A}$ issues private key queries, and $\mathcal {B}$ answer to these queries like in Game 1.

Then the attacker $\mathcal {A}$ sends two messages $M_{0}, M_{1}$ to $\mathcal {B}$. $\mathcal {B}$ generates a random bit $b^{*}$, and generates the challenge ciphertext $C^{*} = (\mathbf {b}^{*}, c^{*})$ as follows: $\mathbf {b}^{*} = ( \mathbf {b}'^{T} | - \mathbf {b}'^{T} \mathbf {T} + \hat{\mathbf {e}}^{T})^{T}$, $c^{*} = b_{0} + \lfloor q / 2 \rfloor M_{b^{*}},$ where $\hat{\mathbf {e}} \hookleftarrow D_{R^{k}, \mu }$ for some $\mu$ real.

• If the Ring-LWE samples are drawn from the Ring-LWE distribution, we have $\mathbf {b}' = \mathbf {a}' s + \mathbf {e}$ and $b_{0} = a_{0} \cdot s + e_{0},$ for some $s \in R_{q}$, $\mathbf {e} \hookleftarrow D_{R^{m-k}, \tau }$ and $e_{0} \hookleftarrow D_{R, \tau }$. By substitution, $\mathbf {b}^{*} = ( \mathbf {b}'^{T} \, | \, - \mathbf {b}'^{T} \mathbf {T} + \hat{\mathbf {e}}^{T})^{T})^{T} = \mathbf {a}_{id^{*}}^{T} s + ( \mathbf {e}^{T} \, | \, - \mathbf {e}^{T} \mathbf {T} + \hat{\mathbf {e}}^{T})^{T} )^{T}$ $\text { and } \quad c^{*} = b_{0} + \lfloor q / 2 \rfloor M_{b^{*}} = a_{0} \cdot s + e_{0} + \lfloor q / 2 \rfloor M_{b^{*}}.$ For fixed $\mathbf {e}$, the error term $-\mathbf {e}^{T} \mathbf {T} + \hat{\mathbf {e}}^{T}$ is indistinguishable from a sample drawn from the distribution $D_{R^{k}, \gamma }$ with $\gamma ^{2} = (\sigma \Vert \mathbf {e}_{0} \Vert )^{2} + \mu ^{2}$, for $\mu$ well chosen. Then the challenge ciphertext, $(\mathbf {b}^{*}, c^{*})$ follows the same distribution as in the IBE of Game 2.

• If the Ring-LWE samples are uniformly random samples, the ciphertext challenge also looks uniform. Then, the challenge ciphertext $C^{*}$ is always a uniform element in $R_{q}^{m} \times R_{q}$ At the end, the adversary $\mathcal {A}$ outputs a guess b.

If $b = b^{*}$ with overwhelming probability, the simulator concludes that the Ring-LWE instance was drawn from the Ring-LWE distribution, otherwise $\mathcal {B}$ concludes that the Ring-LWE distribution was drawn from the uniform distribution.    $\square$

4.2 Parameter Choices

In our construction, the modulus q is chosen to be a prime of size 14, 30 or 62 bits (implementation purpose of NFLlib [AMBG+16]). We use the computational instantiation of the trapdoor with $m-k = 2$, and $\mathbf {a}'$ corresponds to two polynomials, the first sets to one and the second to a uniform polynomial $a \hookleftarrow U(R_{q})$, as suggested in [EBB13]. We obtain a public vector, associated to tag h: $\mathbf {a} = \left( 1, a \, \left| \, h \cdot g_{1} - (a \cdot t_{2,1} + t_{1,1}), \cdots , h \cdot g_{k} - (a \cdot t_{2,k} + t_{1,k}) \right. \right)$.

• The Gaussian parameter $\sigma$ for the trapdoor sampling is $\sigma > \sqrt{\left( \ln \left( 2 n / \epsilon \right) / \pi \right) }$ [MP12] where n is the maximum length of the ring polynomials, and $\epsilon$ is the desired bound on the statistical error introduced by each randomized-rounding operation. This parameter is also chosen to ensure that the Ring-LWE instance of parameters n, q and $\sigma$ is hard.

• The Gaussian parameter $\alpha$ used for the G-sampling [MP12] is $\alpha = \sqrt{5} \sigma .$

• By [GM18], the parameter $\zeta$ satisfies $\zeta > s_{1} \left( \mathbf {T} \right) \alpha .$ The spectral norm of $\mathbf {T}$ is a subgaussian random matrix of parameter $\sigma$ [MP12, Lemma 2.9]. There exists a universal constant C ($\sim 1 / \sqrt{2 \pi }$), such that for any $t' \ge 0$, we have $s_1 \left( \mathbf {T} \right) \le C \sigma (\sqrt{kn} + \sqrt{2n} + t')$ except with probability at most $2 \exp \left( - \pi (t')^{2} \right)$. Then, we get $\zeta > \sqrt{5} C \sigma ^2 (\sqrt{kn} + \sqrt{2n} + t').$

• Finally, to choose the Gaussian parameters $\gamma , \tau$ for the Dual-Regev encryption, we need $\Vert e' - \mathbf {e}_{0}^{T} \mathbf {x}_{0} - \mathbf {e}_{1}^{T} \mathbf {x}_{1} \Vert < \lfloor q/4 \rfloor$, which thanks to Sect. 2 gives:

  $$ \Vert e' - \mathbf {e}_{0}^{T} \mathbf {x}_{0} - \mathbf {e}_{1}^{T} \mathbf {x}_{1} \Vert \le t \tau \sqrt{n} + 2 t^{2} \tau \zeta n + t^{2} \gamma \zeta kn < \lfloor q/4 \rfloor . $$

• Moreover, $\gamma$ needs to satisfy $\gamma = \sqrt{\sigma ^{2} \Vert \mathbf {e}_{0} \Vert ^{2} + \mu ^{2}}$ so that the security proof holds. We can have an idea of the norm of $\mathbf {e}_{0}$ by using the Sect. 2,

  $$\begin{aligned} \gamma ^{2} = \sigma ^{2} \Vert \mathbf {e}_{0} \Vert ^{2} + \mu ^{2} \le \sigma ^{2} (t \tau \sqrt{2n})^{2} + \mu ^{2} , \end{aligned}$$

  we choose $\mu = t \sigma \tau \sqrt{2n}$, and then $\gamma = 2 t \sigma \tau \sqrt{n}$.

Parameters set. We combine all the conditions to obtain the following set of parameters, used in our implementation. Remark: The bit security of the underlying Ring-SIS instance does not appear here because it dominates the bit security of the Ring-LWE instances.

Table 3. Parameters set for our IBE construction.

4.3 Underlying Signature Scheme

Behind the IBE scheme above, there is an underlying natural signature scheme. The key generation in both scheme consists in creating a public vector $\mathbf {a} \in R_{q}^{m}$ together with its trapdoor $\mathbf {T} \in R^{(m-k) \times k}$. The signature of a message corresponds to the secret key associated to an identity in the IBE scheme. A signature $\mathbf {x}$ of a message M is a solution of $\mathbf {a}_{M}^{T} \mathbf {x} = 0 \mod q$. To check if $\mathbf {x}$ is a valid signature for some message M, we have to check that $\mathbf {x}$ is a non trivial solution to the Ring-SIS instance above ($\mathbf {x} \ne \mathbf {0}$, $\mathbf {a}_{M}^{T} \mathbf {x} = 0 \mod q$ and $\Vert \mathbf {x} \Vert \le t \zeta \sqrt{nm}$).

Construction. The parameters of the scheme are n, m, q, k, and q integers, and $\sigma$, $\alpha$, and $\zeta$ are reals. Let $H : \mathbb {Z}_{q}^{n} \rightarrow R_q$ be a FRD map.

• 1. KeyGen$(1^{n}) \rightarrow (vk, sk)$:

  • (a) Compute $\mathbf {a} \in R_{q}^{m}$ associated to its trapdoor $\mathbf {T} \in R^{(m-k) \times k}$, $(\mathbf {a}, \mathbf {T}) \leftarrow \textsf {TrapGen}(q, \sigma , h=0)$, i.e. $\mathbf {a} = (\mathbf {a}'^{T} \, | \, - \mathbf {a}'^{T} \mathbf {T})^{T}$,

  • (b) Output $vk = \mathbf {a} \in R_{q}^{m}$ and $sk = (\mathbf {a}, \mathbf {T}) \in R_{q}^{m} \times R^{(m-k) \times k}$.

• 2. Sign$(sk = (\mathbf {a}, \mathbf {T}), M \in R_{2}) \rightarrow \nu$:

  • (a) Compute the tag $h_{M} = H(M)$,

  • (b) Compute $\mathbf {a}_{M} = \mathbf {a}^{T} + ( \mathbf {0} \, | \, h_{M} \mathbf {g} )^{T} = (\mathbf {a}'^{T} \, \left| \, h_{M} \mathbf {g} - \mathbf {a}'^{T} \mathbf {T} )^{T} \right.$,

  • (c) Sample a short $\mathbf {x} \leftarrow \textsf {SamplePre}\left( \mathbf {T}, \mathbf {a}_{M}, h_{M}, \zeta , \sigma , \alpha , 0 \right)$, with $\mathbf {a}_{M}^{T} \mathbf {x} = 0$,

  • (d) Output $\nu = \mathbf {x} \in R^{m}$.

• 3. Verify$(vk = \mathbf {a}, M, \nu = \mathbf {x}) \rightarrow \lbrace \text {accept, reject} \rbrace$:

  • (a) Compute the tag $h_{M}$ and $\mathbf {a}_{M}$ like above,

  • (b) Accept if, and only if, $\mathbf {a}_{M}^{T} \mathbf {x} = 0 \mod q$ and $0 < \Vert \mathbf {x} \Vert \le t \zeta \sqrt{mn}$.

Correctness. Thanks to Sect. 2, with high probability the norm of a signature outputted by SamplePre is bounded by $t \zeta \sqrt{nm}$, because it is an integer vector of size nm and of Gaussian parameter $\zeta$.

Theorem 2

Our signature construction with parameters n, m, q, k, $\sigma$, $\alpha$, and $\zeta$ chosen as below is SU-CMA (Selective Unforgeability against Chosen Message Attack) secure in the standard model under the hardness of Ring-SIS$_{q, m-k, \beta }$ with $\beta = (1 + t \sigma \sqrt{(m-k)n}) t \zeta \sqrt{mn}$.

Proof

Let $\mathcal {A}$ be an adversary attacking the signature scheme above through an SU-CMA attack. We build a simulator $\mathcal {B}$ attacking the Ring-SIS problem.

Init. The simulator $\mathcal {B}$ receives $m-k$ uniformly random and independent samples from $R_{q}$, $\mathbf {a}' = (a_{1}, \cdots , a_{m-k})^{T} \in R_{q}^{m-k}$ as an Ring-SIS instance, and the challenge message $M^{*}$ from the adversary $\mathcal {A}$. The simulator runs $\textsf {TrapGen}(q, \sigma , \mathbf {a}', -h_{M^{*}})$, and gets back $\mathbf {a} = (\mathbf {a}'^{T} \, | \, -h_{M^{*}} \mathbf {g} - \mathbf {a}'^{T} \mathbf {T} )^{T}$ together with $\mathbf {T} \hookleftarrow D_{R^{(m-k) \times k}, \sigma }$. Next, $\mathcal {B}$ sends $vk = \mathbf {a} \in R_{q}^{m}$ to $\mathcal {A}$.

Signing queries. The adversary $\mathcal {A}$ issues signing queries on messages $M \ne M^{*}$, and $\mathcal {B}$ has to answer to these queries. To do that, he computes $\mathbf {a}_{M} = \mathbf {a}^{T} + (\mathbf {0} \, | \, h_{M} \mathbf {g})^{T} = (\mathbf {a}'^{T} \, | \, (h_{M} - h_{M^{*}}) \mathbf {g} - \mathbf {a}'^{T} \mathbf {T})^{T},$ and then he can use $\textsf {SamplePre}(\mathbf {T}, \mathbf {a}_{M}, h_{M} - h_{M^{*}}, \zeta , \sigma , \alpha , 0)$ to find a signature $\mathbf {x} \in R^{m}$ satisfying $\mathbf {a}_{M}^{T} \mathbf {x} = 0 \mod q$.

Forgery. Eventually, $\mathcal {A}$ outputs a forgery $\nu ^{*}$ for $M^{*}$, satisfying $\mathbf {a}_{M^{*}}^{T} \nu ^{*} = 0 \mod q$, which gives $\mathbf {a}'^{T} \underbrace{(I_{m-k} \, | \, -\mathbf {T}) \nu ^{*}}_{\mathbf {z}} = 0 \mod q$.

The norm of $\Vert \mathbf {T} \Vert \le t \sigma \sqrt{(m-k)n}$ because each of its columns is a Gaussian vector of size k and of parameter $\sigma$. Then, the vector $\mathbf {z}$ is a solution of the Ring-SIS instance of norm $\Vert \mathbf {z} \Vert = \Vert (I_{m-k} \, | \, -\mathbf {T}) \nu ^{*} \Vert \le \beta =(1 + t \sigma \sqrt{(m-k)n}) \cdot t \zeta \sqrt{mn}$.    $\square$

Parameters choices. The parameters n, m, q, k, q, $\sigma$, $\alpha$, and $\zeta$ follow the same conditions detailed above for the IBE scheme. Moreover, we need to look at the underlying Ring-SIS instance of size $m-k=2$ and of norm $\beta = (1 + t \sigma \sqrt{2n}) t \zeta \sqrt{mn}$ which corresponds to a SIS instance of size n times bigger. The two following conditions $\beta \ge \sqrt{2n} q^{n/2n} = \sqrt{2nq}$ and $q \ge \beta \sqrt{n} \omega (\log n)$ ensure that the SIS problem has a solution and that is hard.

To get an idea of the security achieved by a SIS instance, we follow the general framework of [APS15, CN11]. To ensure that the shortest vector outputted by BKZ is a solution of our SIS instance of norm $\beta = (1 + t \sigma \sqrt{2n}) t \zeta \sqrt{mn}$, the root Hermite factor $\delta$ need to satisfy $\frac{\beta }{q^{n/2n}} = \frac{\beta }{\sqrt{q}} = \delta ^{2n}$. To achieve this Root Hermite factor, we need to run BKZ with block size at least b. The estimated cost of running BKZ with block size b, a number of rounds of $N = \frac{(2n)^2}{b^2} \log (2n)$ and on dimension 2n is $\text {cost}(\text {BKZ}_{b, N}) \approx \frac{(2n)^3}{b^2} \log (2n) \cdot \text {cost}(\text {SVP oracle})$.

Parameters set. We now combine all those conditions to obtain the following set of parameters. Remark: We can also instantiate this scheme such that the public key is statistically close to uniform by using a Regularity Lemma ([SS11, Theorem 3.1]), but in this case, $m-k$is slightly larger and $\sigma$ is much larger.

Table 4. Parameters set for our signature scheme.

5 Implementation

5.1 General Description

Our implementation was carried out in plain C++11 as a general-purpose library. We now discuss the different principles followed during the design of our code:

Cutting-edge compiler. We have always used the latest version available of the GCC compiler to build our binary. Our final timings have been produced using the GCC 7.2 compiler that allows us to perform various optimization and code sanitization that do not exist in older versions.

Thread-Safety. Lattice-based constructions are known to be highly parallelizable. Therefore, we build our library so that it could be simultaneously called from concurrent threads. To this end, we only use the <thread> model of C++11, and not OpenMP or OpenCL, in order to keep the design as simple as possible.

Portability. Modern processors often come with a combination of advanced hardware instructions: SSE 4.1, AVX, AVX2, AVX512+flavors and NEON. These instructions allow developers to boost the performance of their applications. Many developers tend to explicitly include such instructions inside their code to gain in efficiency. However, we do not use this method, since it limits the portability of the code. Instead, we rely on the compiler to insert them depending on the required optimization level and the targeted machine using its own auto-vectorization techniques. Thus, our code can be easily compiled for INTEL and ARM processors without any modification.

Dedicated polynomial ring library. We avoid the use of generic number theory libraries, such as NTL and FLINT, in our implementation. Instead, we preferred to use NFLlib library [AMBG+16] which offers fast implementations of arithmetic operations over the ring. However, NFLlib has a primary drawback: it does not allow developers to natively choose a prime modulus q of size between 30 bits and 62 bits. This has resulted in performance penalty on our implementation when q can be of size 50 bits, since we had to use 62 bits.

Double-precision float. Our implementation does not depend on multi-precision floating-point arithmetic. Instead, all floating-point computations are performed using double-precision arithmetic, as in [GM18].

Modularity. We designed our code to be composed of three software layers. In what follows, we describe these layers and discuss some technical choices concerning our implementation.

5.2 Software Layers

Gaussian Preimage Sampling. This layer implements the Peikert Gaussian sampler. As mentioned in Sect. 3.2, this consists of combining two stages: an off-line (target independent) stage SampleP generating perturbation vectors, and an on-line (target dependent) stage SamplePolyG generating samples from a particular lattice. We note that this layer does not regard the actual implementation of SampleP and SamplePolyG. We also note that we never include the runtime execution of SampleP in our timings for any operation that does need preimage sampling. Indeed, we suppose that the trusted party, or the signer, periodically calls SampleP and stores the resulted outputs. Below, we provide more details about the runtime of this off-line operation.

SampleP and SamplePolyG. This layer implements the recent techniques described in [GM18] and [DP16] for Gaussian sampling. We note that SamplePolyG just calls SampleG (Fig. 2 in [GM18]) n times to build k polynomials in $R_{q}$. For instance, when $n = 1024$ and $k = 30$ bits, SamplePolyG calls the underlying sampler 1024 times, and then builds 30 polynomials in their NTT. This n times sampling constitutes the main bottleneck of our Extract/Sign algorithms. As for SampleP, we use the Fourier representation in the finite field as well as the FFT’s butterfly transformation to speed up all the required multiplication/inversion. To this end, we implement our C++ Cooley-Tukey FFT and optimize it using template class recursion (a template class that recursively uses its own definition).

IBE and Signature. Here, we implement the described signature and IBE schemes using mainly our Gaussian Preimage Sampling and NFLlib to perform arithmetic operations. For the IBE scheme, we build two classes in order to simulate the different roles: the trusted party that generates the master keys and capable of extracting users private keys, and a user that is able to encrypt using the identity of another user as well as to decrypt using its own private key. This abstraction allows us to easily set up our test benchmark with one trusted party and several users. We note that we do not include the timings of the instantiation of the different objects, since it is done only once during the setup of the entire environment, and more importantly, it concerns memory allocations and some initial computations that could be performed otherwise.

5.3 Experimental Results

Our timings have been obtained on an Intel i7-5600 2.6 GHz CPU. Clock cycles were measured with the high_resolution_clock class of C++11. Results are provided in Table 5 (resp. Table 6) for the IBE (resp. signature) scheme.

We underline that we obtained our results using the security parameters in Tables 3 and 4 except for k. Indeed, NFLlib limits the choice of k, then we use $k = 30$ if it is smaller or equal to 30, and $k = 62$ otherwise. We note that modifying NFLlib to take into account arbitrary moduli is possible, but here, we did not and thus provide upper bounds to our implementations. This explains our similar results when signing for two different levels of security (with $n=1024$). Our timings show that performance is still practical for many scenarios. We also notice that timings are almost just multiplied by 2 for twice security.

Table 5. Timings in ms for the different operations of the IBE scheme: Setup, PreCompute, Extract, Encrypt and Decrypt.

Table 6. Timings in ms for the different operations of the Signature scheme: KeyGen, PreCompute, Sign and Verify.

Comparison with related work. Now, we provide more insight about the Tables 1 and 2 in the introduction, as well as Table 7 presented below.

Table 7. Timings for the different proposals of the NIST competition. Refer to Table 2 for the notations.

IBE Scheme. The closest work to our implemented IBE is the one presented in [DLP14] and re-implemented in [MSO17]. Indeed, both requires Gaussian sampling to extract users’ private keys, and our encryption/decryption algorithms are very similar. However, DLP14 relies on NTRU lattices, which allow them to tremendously reduce the size of users keys, and therefore the number of the required Gaussian sampling (only one), while we need n calls to SampleG. Our implementation is then slower for the Extract and Encrypt operations, nevertheless, due to our efficient implementation of [GM18], the difference is quite small. However, our Setup is much faster. We recall that the trusted party generates the private key for each user only once. Therefore, this operation is less critical than the encryption/decryption.

Signature Scheme. We compare our implementation with the lattice-based signature proposals of the NIST competition¹. We compiled and ran the Reference Implementation of each scheme that corresponds to the NIST Security Level 1, namely 128 quantum bit security. Because of some run-time errors, we did not include the timing for pqNTRUsign. We are aware of how different these schemes are in their design and their choice of security parameters. We emphasize that our evaluation study is not complete, especially that we did not implement the secure hash function (as discussed in Sect. 2.4) that might slow down our signature scheme. However, our results allow us to consider our performance compared to highly optimized signature schemes. As for signature, our implementation performs three to four times slower than Dilithium and qTesla, while it outperforms DRS. But our verification is much faster than other schemes. This asymmetry could be useful in case signatures are produced by powerful machines (e.g. a server) and to be verified by constrained devices. These results confirm that our approach remains interesting for both security and performance.

Storage requirements. Here, we give an estimation of the storage requirements of our implementation for the different entities. We note that, in the IBE scheme, the trusted party requires the Gaussian Sampler, while the user requires it for the signature scheme. Our estimations are directly based on the different fields of our classes, which reflects the modular structure of our implementation. We note that the precomputed values take much space, and therefore a trade-off between the number of precomputations and the allocated storage must be found. A direct conclusion can be drawn from our Table 8: lattice-based constructions are not yet ready for constrained devices since, for instance when $n = 512$ and $k = 30$, the public key is of size 61.875 KB, which is quite big for some systems.

Table 8. Storage requirements in bits