# Identity-Based Encryption from Lattices Using Approximate Trapdoors

Malika Izabachène, Lucas Prabel, Adeline Roux-Langlois

► To cite this version:

Malika Izabachène, Lucas Prabel, Adeline Roux-Langlois. Identity-Based Encryption from Lattices Using Approximate Trapdoors. ACISP 2023 - 28th Australasian Conference on Information Security and Privacy, Jul 2023, Brisbane, Australia. pp.270-290, 10.1007/978-3-031-35486-1_13. hal-04163136

HAL Id: hal-04163136

https://hal.science/hal-04163136

Submitted on 17 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Identity-Based Encryption from Lattices Using
Approximate Trapdoors

Malika Izabachène¹, Lucas Prabel²(✉), and Adeline Roux-Langlois³

¹ Independent Scholar

² Univ Rennes, CNRS, IRISA, Rennes, France

lucas.prabel@irisa.fr

³ Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France

**Abstract.** Practical implementations of advanced lattice-based constructions have received much attention since the first practical scheme instantiated over NTRU lattices, proposed by Prest et al (Asiacrypt 2014). They are using powerful lattice-based building blocks which allow to build Gaussian preimage sampling and trapdoor generation efficiently. In this paper, we propose two different constructions and implementations of identity-based encryption schemes (IBE) using approximate variants of "gadget-based" trapdoors introduced by Chen et al. (Asiacrypt 2019). Both constructions are proven secure.

Our first IBE scheme is an adaptation of the Bert et al. scheme (PQCrypto 2021) to the approximate setting, relying on the Module-LWE hardness assumption and making use of the Micciancio-Peikert paradigm with approximate trapdoors. The second IBE relies on a variant of the NTRU hardness assumption.

We provide several timings and a comparison analysis to explain our results. The two different instantiations give interesting trade-offs in terms of security and efficiency and both benefit from the use of approximate trapdoors. Though our second IBE construction is less efficient than other NTRU-based IBEs, we believe our work provides useful insights into efficient advanced lattice-based constructions.

**Keywords:** Lattice-based cryptography · approximate trapdoors · Gaussian preimage sampling · module lattices · IBE

# 1 Introduction

Identity-based encryption (IBE) is an advanced public key encryption scheme in which an identity, such as a username, email address, or social security number, acts as the public key. In identity-based encryption, the sender encrypts a message with the unique identity of the recipient, and the recipient then decrypts

This preprint has not undergone peer review (when applicable) or any post-
submission improvements or corrections. The Version of Record of this contribution
is published in Information Security and Privacy - 28th Australasian Conference,
ACISP 2023, Brisbane, QLD, Australia, July 5-7, 2023, Proceedings, and is avail-
able online at https://doi.org/10.1007/978-3-031-35486-1_13.
the ciphertext with their private key to obtain the original message. In this way, one party can send an encrypted message to any other party without requesting the recipient's public key beforehand. The pair "identity" and "associated secret key" acts as a classical public key and secret key pair in a classical public key encryption scheme.

The idea was to eliminate the need for a public certificate across email systems. These schemes allowed secure communication without exchanging user keys. In [31] Shamir presented a solution for an identity-based signature scheme but the first IBE constructions appeared only in 2001 in [6, 10] and were based respectively on bilinear maps and quadratic residue-based assumptions. However, these schemes were vulnerable to quantum attacks due to Shor's algorithm.

**Lattice-based IBE constructions.** In [18], Gentry, Peikert and Vaikuntanathan described the first lattice-based IBE, relying on the Dual-Regev encryption scheme. An important contribution of their work was a sampling algorithm (known as GPV sampling) which showed how to use a short basis as a trapdoor for generating short lattice vectors. This sampler was then used to construct a lattice-based IBE scheme, proven adaptively secure against chosen-plaintext attack in the random oracle model as defined in [6, 10]. However, the master public key and user secret keys had large sizes in $O(n^2)$ bits. Later on, a construction of a Hierarchical IBE (HIBE) scheme in the standard model was proposed in [8] based on a new mechanism for users' keys delegation. This IBE scheme was proven secure in the selective model where the adversary needs to target an identity beforehand. In 2010, Agrawal et al. [1] proposed a Learning With Errors (LWE)-based IBE scheme with a trapdoor structure and with performance comparable to the GPV scheme. Their construction viewed an identity as a sequence of bits and then assigned a matrix to each bit. It used a sampling algorithm to obtain a basis with low Gram-Schmidt norm for the master secret key and formed a lattice family with two associated trapdoors to generate short vectors; one for all lattices in the family and the other one for all but one.

The first Ring-LWE based IBE scheme has been proposed by Ducas, Lyubashhevsky and Prest [11] (DLP-IBE), which is still considered the most efficient scheme to date due to smaller key sizes. The use of the ring variant increased efficiency by reducing the public key size and ciphertext size to $O(n)$. The security of their scheme holds in the random oracle model and is related to the NTRU hardness assumption. An efficient C implementation of the DLP-IBE scheme and a detailed performance analysis was provided in [27]. In 2017, Campbell and Grover introduced a HIBE scheme, called LATTE, which can be viewed as a combination of the DLP scheme with the delegation mechanism from [8]. An optimized implementation and refined analysis of LATTE, has recently been proposed in [33].

The work from [5] constructed an IBE using the notion of gadget-based trapdoors in the ring setting, introduced by [28]. Such trapdoors can be seen as linear transformations mapping hard instances of cryptographic problems on some lattices to easy instances on a lattice defined by a public "gadget matrix".
The IBE from [5] also made use of the efficient Gaussian preimage sampling algorithms from [17] to propose an implementation of their scheme. In [4], this IBE and its associated sampling algorithms were adapted to the module setting and instantiated. The use of module lattices of dimension *nd*, where *d* is the rank module, led to a more flexible choice of parameters. In [32], the authors proposed new efficient gadget sampling algorithms which didn't need floating-point arithmetic, and as fast as the original [17] sampler.

All those constructions generally make use of dedicated trapdoors, needed by
the authority to generate the secret key of a user. In that case, building the trap-
door and sampling particular short vectors are quite costly, and represent the
main bottleneck in the efficiency of such schemes. More recently, [9] introduced
approximate trapdoors to improve the efficiency of schemes built from lattice
trapdoors while keeping the same concrete security. [16] showed that those ap-
proximate trapdoors, relying on the [28] framework, exist on a family of NTRU
lattices. Our work explores the application of those approximate trapdoors, and
in particular of this family of NTRU lattices, to more advanced schemes where
the generation of private keys in a multi-user setting is needed.

**Our contributions.** Our main contribution is to provide and implement two lattice-based IBE schemes (IBE1 and IBE2), which make use of families of gadget-based approximate trapdoors. Our two constructions rely on the LWE problem over modules (Module-LWE) and the inhomogeneous NTRU problem (iNTRU) respectively. We investigate how to instantiate and parametrize the approximate trapdoor preimage sampling over these two families of trapdoors in a way to obtain provable and efficient quantum-safe IBE schemes. The IBE1 construction is an adaptation of the identity-based encryption scheme from [1, 5] to the module setting, using approximate trapdoors. The IBE2 construction follows the same blueprint as the DLP scheme except that it makes use of iNTRU gadget-based approximate trapdoors. As in previous IBE constructions, encryption is based on the Dual-Regev encryption scheme. We provide a complete public and open-source C implementation with performance benchmarking. The implementation is modular and makes it easy to change the building blocks of our algorithms according to the desired properties that we want to get.

Our work explores the use of approximate trapdoors for the construction
of IBE schemes and the potential practical insights we can gain from it. We
first adapted the construction of [4] using approximate trapdoors in our IBE1.
The error induced by the approximate setting requires changes at several levels,
either for the choice of encoding or for the sampling algorithms. As expected,
we obtain better timings for all four algorithms composing our IBE by using
approximate trapdoors rather than exact ones.

The second scheme IBE2 makes use of approximate trapdoors relying on a
variant of NTRU rather than Module-LWE. Our approach was motivated by the
fact that other efficient IBEs, such as DLP and Latte, used the NTRU hardness
assumption. However, unlike us, these last two schemes used the GPV paradigm

https://github.com/lucasprabel/approx_lattice
to generate trapdoors, which significantly changes the way their schemes are constructed compared to ours.

*More details on our implementation choices.* Our IBE1 proof relies on a statistical trapdoor instantiation. Although the size of the parameters increases consequently, the use of approximate trapdoors allowed us to mitigate this loss in efficiency induced by the use of a statistical instantiation. In order to ensure decryption correctness, we also need to use a large modulus (see Section 4.1). This leads us to perform calculations carefully on 64-bit integers, so as not to affect our scheme efficiency. The IBE1 also makes use of a small-norm encoding, instead of the low-degree encoding used in [4] to ensure that the noise is still not too large in order to decrypt. The encoding we use sets constraints on the structure of the ring $R_q$ which is not compatible with the NTT for polynomial multiplications. Instead, we use a "partial NTT" based on [26] results, which reduces multiplication in $R_q$ to multiplication in smaller rings. We also have optimized the underlying CRT representation algorithm compared to [4]. Finally, the sampling algorithms have been adapted to the approximate setting. Table 2 shows some applicable parameter sets together with their concrete bit security using the LWE estimator from [2] with BKZ as a reduction cost model. All the algorithms comprising the IBE1 over module lattices are more efficient than their exact counterpart at the same security level. This improvement concerns in particular Setup and Extract which are optimized by a factor $\approx 1.5$. We give more details in Section 4.2.

The IBE2 scheme is instantiated using gadget-based trapdoors on a family of NTRU lattices. Table 4 provides a set of applicable parameter sets together with their concrete bit security. The computational trapdoors instantiation lowers the bounds on parameters required for the correctness compared to the IBE1 scheme, which allows the use of smaller moduli. For the IBE2 construction, an identity is encoded as $H(id)$ with $H$ having special properties so that we are able to respond to private key queries except for the target identity chosen by the adversary.

<table><caption>Table 1: Timings comparison in ms of the different operations of the IBE2 scheme in this paper and in Latte [33] for different sets of parameters.</caption><thead><tr><th>Scheme</th><th>(n, ⌈log<sub>2</sub>(q)⌋)</th><th>Security level</th><th>Setup</th><th>Extract</th><th>Encrypt</th><th>Decrypt</th></tr></thead><tbody><tr><td>[33]</td><td>(1024, 24)</td><td>128</td><td>102</td><td>0.82</td><td>0.05</td><td>0.06</td></tr><tr><td>[33]</td><td>(2048, 25)</td><td>256</td><td>292</td><td>2.62</td><td>0.10</td><td>0.13</td></tr><tr><td>This paper</td><td>(1024, 25)</td><td>159</td><td>3.32</td><td>5.92</td><td>1.10</td><td>0.07</td></tr><tr><td>This paper</td><td>(2048, 25)</td><td>293</td><td>10.21</td><td>12.79</td><td>2.96</td><td>0.16</td></tr></tbody></table>

In Table 1, we provide timings comparison with the [33] IBE scheme. A more complete and detailed comparison is given in Section 5.2 between our IBE2 scheme and the [11] and [33] IBE schemes which also rely on the NTRU assumption. The use of approximate trapdoors and of the iNTRU assumption allows to obtain better timings for the Setup algorithm and for the Extract
algorithm for some sets of parameters. Unfortunately, we obtain an overhead for encryption which essentially comes from the Gaussian sampling phase. We can save a factor 3.5 using binomial samples as in [11] and [33] but there is still an overhead due to the extra number of samples we need. We make $n(2+m)$ calls to the integer Gaussian sampler while encryption in [11] and [33] makes use of $3n$ binomial sampling calls, where $n$ is the dimension of the underlying polynomial ring and $m$ is the size of one of the vector used in encryption. As an example, we obtain a timing of 0.87ms for one encryption against 0.13 for [33] for a security level of 128 bits.

**Organization of the paper.** The paper is structured as follows: Section 2 reviews the necessary linear algebra and lattice backgrounds. The Section also presents the notions of approximate trapdoor. Then, Section 4 and Section 5 contain a detailed description of the two IBEs, based on the Module-LWE hardness assumption and based on a variant of the NTRU assumption respectively. Both Sections provide a security analysis and detailed performance results together with a comparison of their respective analogue in terms of lattice-based building blocks and assumptions.

## 2 Preliminaries

*Notations.* Throughout the paper, the vectors are written in lowercase bold letters (e.g. $\mathbf{v}$) and matrices in uppercase bold letters (e.g. $\mathbf{A}$). We refer to their entries with a subscript index $v_i$, $A_{i,j}$. We denote $\|\cdot\|$ and $\|\cdot\|_{\infty}$ the euclidean norm and the infinity norm respectively. The norm of a vector over $\mathbb{Z}_q$ is the norm of the corresponding vector over $\mathbb{Z}$ obtained by choosing its entries in the set $\{-\lfloor q/2 \rfloor, \dots, \lfloor q/2 \rfloor\}$. The norm of a polynomial $a = \sum_{i=0}^{n-1} a_i X^i$ is the norm of the coefficients vector $(a_0, \dots, a_{n-1})$. Finally, the norm of a matrix is the maximum norm of its column vectors. If $x$ is sampled from a distribution $D$, we write $x \leftarrow D$. We denote $\mathcal{U}(S)$ the uniform distribution over a finite set $S$.

We say that a function $f$ is negligible when $f(n) = o(n^{-c})$ for all $c > 0$ as $n \to \infty$. An event is said to happen with overwhelming probability if its probability of not happening is negligible. Two distributions $D_0$ and $D_1$ over the same countable domain $\Omega$ are said to be statistically indistinguishable if their statistical distance $\Delta(D_0, D_1) = \frac{1}{2} \sum_{\omega \in \Omega} |D_0(\omega) - D_1(\omega)|$ is negligible. Two distributions are said to be computationally indistinguishable if no probabilistic polynomial time algorithm can distinguish them with non-negligible advantage.

### 2.1 Lattices background and discrete Gaussian distributions.

*Lattices.* A lattice $\Lambda$ in $\mathbb{R}^m$ is the set $\{\sum_{i=1}^k \lambda_i \mathbf{b}_i, \lambda_i \in \mathbb{Z}\}$ of all integer linear combinations of some linearly independent vectors $\mathbf{B} = \{\mathbf{b}_1, \dots, \mathbf{b}_k\} \subset \mathbb{R}^m$. We call $k$ the rank of the lattice and $m$ its dimension. When $k = m$, the lattice is said to be full-rank.
Given $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$ and $\mathbf{u} \in \mathbb{Z}_q^n$, we define the following $m$-dimensional $q$-ary lattice $\Lambda_q^{\perp}(\mathbf{A}) = \{\mathbf{x} \in \mathbb{Z}^m | \mathbf{A}\mathbf{x} = \mathbf{0} \bmod q\}$, and its coset $\Lambda_q^{\mathbf{u}}(\mathbf{A}) = \{\mathbf{x} \in \mathbb{Z}^m | \mathbf{A}\mathbf{x} = \mathbf{u} \bmod q\}$.

Module lattices are particular lattices that have a polynomial structure. We denote $d$ the module rank of those lattices. When $d = 1$, module lattices are in fact ideal lattices. We consider the ones that are based on the rings $\mathcal{R} = \mathbb{Z}[X]/\langle X^n + 1 \rangle$ and $\mathcal{R}_q = \mathbb{Z}_q[X]/\langle X^n + 1 \rangle$, where $n$ is a power of two and $q$ is prime. They are sublattices of the full lattice $\mathcal{R}^m$, which is isomorphic to the integer lattice $\mathbb{Z}^{nm}$.

**Gaussian distributions.** We recall that a symmetric matrix $M \in \mathbb{R}^{n \times n}$ is positive definite (resp. positive semidefinite) if $\mathbf{x}^T M \mathbf{x} > 0$ (resp. $\mathbf{x}^T M \mathbf{x} \ge 0$) for all nonzero $\mathbf{x} \in \mathbb{R}^n$. In this case we write $M \succ 0$ (resp. $M \succeq 0$). We say that $M \succeq N$ when $M - N \succeq 0$, and write $M \succeq \eta$ instead of $M \succeq \eta I_n$ when $\eta \ge 0$ is a real. The spherical continuous Gaussian function of center $c \in \mathbb{R}^n$ and parameter $\sigma$ is defined on $\mathbb{R}^n$ by $\rho_{c,\sigma}(\mathbf{x}) = \exp(-\frac{\pi \|\mathbf{x}-c\|^2}{\sigma^2})$. For a positive definite matrix $\mathbf{\Sigma} \in \mathbb{R}^{n \times n}$, we also define the (skewed) Gaussian function $\rho_{c,\sqrt{\mathbf{\Sigma}}}(\mathbf{x}) = \exp(-\pi(\mathbf{x}-c)^T \mathbf{\Sigma}^{-1}(\mathbf{x}-c))$. Then, for a full-rank lattice $\Lambda \subset \mathbb{Z}^n$, we denote $D_{\Lambda,\sigma,c}$ (respectively $D_{\Lambda,\sqrt{\mathbf{\Sigma}},c}$) the spherical (resp. ellipsoid) discrete Gaussian distribution of center $c \in \mathbb{R}^n$ and parameter $\sigma > 0$, associated with the density $\rho_{c,\sigma}$ (resp. $\rho_{c,\sqrt{\mathbf{\Sigma}}}$).

**Smoothing parameter.** The smoothing parameter of a lattice $\Lambda$, denoted $\eta_{\varepsilon}(\Lambda)$, was first introduced in [29]. Lemma 1 gives an upper bound on it.

**Lemma 1 ([18, Lemma 3.1]).** Let $\Lambda \subset \mathbb{R}^n$ be a lattice with basis $\mathbf{B}$, and $\mathbf{B}$ the Gram-Schmidt orthogonalization of $\mathbf{B}$. Then, for any $\varepsilon > 0$, we have $\eta_{\varepsilon}(\Lambda) \le \|\mathbf{B}\| \cdot \sqrt{\ln(2n(1+1/\varepsilon))}/\pi$.

**Gaussian tailcut.** We will use the following result to bound the euclidean norm of vectors that follow a discrete Gaussian distribution.

**Lemma 2 ([24, Lemma 4.4]).** For any integer $n \ge 1$ and reals $\sigma > 0$, $t > 1$, $\Pr[\|\mathbf{x}\| > t\sigma\sqrt{n} | \mathbf{x} \leftarrow D_{\mathbb{Z}^n,\sigma}] < t^n e^{\frac{n}{2}(1-t^2)}$.

We call $t$ a tailcut of the discrete Gaussian of parameter $\sigma$ when a vector $\mathbf{x}$ sampled from $D_{\mathbb{Z}^n,\sigma}$ verifies the inequality $\|\mathbf{x}\| \le t\sigma\sqrt{n}$ on its euclidean norm with overwhelming probability.

## 2.2 Cryptographic problems on lattices

We work on the rings $\mathcal{R} = \mathbb{Z}[X]/\langle X^n + 1 \rangle$ and $\mathcal{R}_q = \mathbb{Z}_q[X]/\langle X^n + 1 \rangle$, where $n$ is a power of two and $q$ a prime modulus. Let us now define the hard problems on which our constructions rely. In most practical lattice-based schemes, security is based on structured variants of LWE rather than on LWE itself. In the Module-SIS and Module-LWE variants, the parameter $d$ is the rank of the module, and $nd$
is the dimension of the corresponding module lattice. The hardness of those problems is proven by worst-case to average-case reductions from hard problems on module lattices (see [22]).

**Definition 1 (Module-SIS<sub>n,d,m,q,β</sub>).* Given a uniform $\mathbf{A} \in \mathbb{R}_{q}^{d \times m}$, find a vector $\mathbf{x} \in \mathbb{R}^{m}$ such that $\mathbf{A}\mathbf{x} = \mathbf{0} \bmod q$, and $0 < \|\mathbf{x}\| \le \beta$.

**Definition 2 (Decision Module-LWE<sub>n,d,q,σ</sub>).* Given a uniform $\mathbf{A} \in \mathbb{R}_{q}^{d \times m}$ and the vector $\mathbf{b}^{T} = \mathbf{s}^{T}\mathbf{A} + \mathbf{e}^{T}$ mod $q \in \mathbb{R}_{q}^{m}$, where $\mathbf{s} \leftarrow \mathcal{U}(\mathbb{R}_{q}^{d})$ and $\mathbf{e} \leftarrow D_{\mathbb{R}^{m},\sigma}$, distinguish the distribution of $(\mathbf{A}, \mathbf{b})$ from the uniform distribution over $\mathbb{R}_{q}^{d \times m} \times \mathbb{R}_{q}^{m}$.

As stated in [7], the Module-LWE problem remains hard when the short secret $\mathbf{s}$ is sampled from the Gaussian distribution $D_{\mathbb{R}^{d},\sigma}$.

Note that Module-LWE<sub>n,d,q,σ</sub> with rank $d=1$ corresponds to the ring version of LWE, which will be denoted Ring-LWE<sub>n,q,σ</sub>. We define $\mathbf{G} = \mathbf{I}_d \otimes \mathbf{g}^T$ and its associated lattice named the module G-lattice, for which the Module-SIS problem is easy.

To build our second IBE, we use gadget-based trapdoors whose pseudorandomness is based on the inhomogeneous NTRU problem (iNTRU), a variant of NTRU introduced in [15].

**Definition 3 (iNTRU<sub>q,χ</sub>).*** Let $k, q$ be integers and $\chi$ a distribution over $\mathcal{R}$. The input of the iNTRU<sub>q,χ</sub> problem is a vector $\mathbf{a} \in \mathbb{R}_{q}^{k}$ which is either taken uniform in $\mathbb{R}_{q}^{k}$ or either set as $\mathbf{a} = r^{-1}(\mathbf{g} + \mathbf{e})$ where $(r, \mathbf{e})$ is drawn from $\chi^{k+1}$. The goal is to decide which is the case.

In their paper, the authors from [15] showed a reduction of a matrix-variant of iNTRU called MiNTRU from the non-standard Ring-LWE with a trapdoor oracle access problem (more details are given in [15, Section 4.3]). The reduction can be adapted to the iNTRU problem as well.

## 2.3 Encoding identities with full-rank differences

We use the notion of full-rank differences encoding (FRD) in our first scheme, with different properties that the ones used in [1].

**Definition 4 ([4]).** An encoding with full-rank differences from the set $\mathcal{M}$ to a ring $\mathcal{R}$ is a map $H : \mathcal{M} \to \mathcal{R}$ such that:

- for any $m \in \mathcal{M}$, $H(m)$ is invertible,

- for any $m_1, m_2 \in \mathcal{M}$ such that $m_1 \neq m_2$, $H(m_1) - H(m_2)$ is invertible,

- $H$ is computable in polynomial time.

As shown in [4], we construct an FRD encoding in the module setting (i.e. over $\mathbb{R}_{q}^{d \times d}$), by first constructing one in the ring setting (i.e. over $\mathbb{R}_{q}$). The encodings used in our IBE scheme impose a structure on the ring $\mathbb{R}_{q}$ which is not compatible with the Number Theoretic Transform (NTT). To speed up polynomial multiplications and to mitigate the loss of performance due to the inability of using the NTT, we use ideas from [26]. This method can be thought of as a "partial NTT". It is based on the following result.
**Lemma 3 ([26, Corollary 1.2]).** Let $n \ge r > 1$ be powers of 2, and $q$ a prime such that $q \equiv 2r+1 \pmod{4r}$. Then the cyclotomic polynomial $X^n+1$ factors in $\mathbb{Z}_q[X]$ as $X^n+1 = \prod_{i=1}^r (X^{n/r-s_i})$, for some distinct $s_i \in \mathbb{Z}_q^*$ such that the $(X^{n/r-s_i})$ are irreducible in $\mathbb{Z}_q[X]$. Moreover, if $y \in \mathbb{Z}_q[X]/(X^n+1)$ satisfies $0 < \|y\|_{\infty} < \frac{q^{1/r}}{\sqrt{r}}$, then $y$ has an inverse in $\mathbb{Z}_q[X]/(X^n+1)$.

This lemma was used in [4] to build a "low-degree" FRD (the identities were encoded as polynomials of low-degree). In our case, we construct a "small-norm" FRD, encoding polynomials with $\ell_{\infty}$-norm smaller than $\frac{q^{1/r}}{2\sqrt{r}}$. We make use of the "small-norm" FRD described in Proposition 1 rather than "low-degree" FRD encoding so that the correctness of the decryption algorithm still holds when using approximate trapdoors, because they introduce an additional error term that must be bounded.

**Proposition 1.** Let $n \ge r > 1$ be powers of 2, $q$ a prime such that $q \equiv 2r+1 \pmod{4r}$ and $1 \le D \le \frac{q^{1/r}}{2\sqrt{r}}$ an integer. We define $M = \{-D, \dots, D\}^n \setminus \{(0, \dots, 0)\}$ the set of identities. Then the following map $H_M : M \to \mathcal{R}_q$, such that $H_M(m_0, \dots, m_{n-1}) = \sum_{i=0}^{n-1} m_i X^i$ is an FRD encoding.

*Proof.* We have $\|H_M(m)\|_{\infty} \le D < \frac{q^{1/r}}{2\sqrt{r}}$ for all $m$ because of the choice of $M$. So according to Lemma 3, $H_M(m)$ is invertible. For all $m_1, m_2 \in M$, we also have $\|H_M(m_1) - H_M(m_2)\|_{\infty} \le 2D < \frac{q^{1/r}}{\sqrt{r}}$ so $H_M(m_1) - H_M(m_2)$ is invertible. Finally, $H_M$ is an FRD encoding. □

**FRD on modules.** As explained in [4], FRD encoding in the module setting can be built using an existing FRD encoding in the ring setting $H_M : M \to \mathcal{R}_q$ by constructing $H_M(m) \cdot I_d \in \mathcal{R}_q^{d \times d}$ for $m \in M$ and $I_d \in \mathcal{R}_q^{d \times d}$ is the identity matrix.

## 3 Trapdoors on lattices

The two IBE constructions make use of efficient trapdoors, called gadget-trapdoors, introduced in [28]. Such trapdoors were generalized to ideal lattices in [21] and to module lattices in [4]. An efficient instantiation of the sampling algorithms was given in [17]. All those results allow us to efficiently instantiate trapdoor generation and sampling algorithms. Having introduced the G-lattice in the previous Section, we can now define the associated G-trapdoors.

**Definition 5.** A G-trapdoor for a matrix $A \in \mathcal{R}_q^{d \times m}$ is a matrix $R \in \mathcal{R}^{(m-dk) \times dk}$ such that

$$A \left[ \frac{R}{I_{dk}} \right] = HG$$

for some invertible $H \in \mathcal{R}_q^{d \times d}$, called the tag of A.
The knowledge of the trapdoor **R** allows one to compute small vectors on any coset of a given lattice, by sampling on the **G**-lattice first, and then by using **R** to map the sample to a small vector in the given lattice.

**3.1 Approximate trapdoors for module lattices.**

As shown in [9], the gadget trapdoor proposed by Micciancio and Peikert can be
modified to an approximate trapdoor, in a way that further reduces the sizes of
the public matrix, the trapdoor and the preimage.

**Definition 6 (AISIS<sub>n,d,m,q,α,β</sub>).* For any *n*, *d*, *m*, *q* ∈ N and *α*, *β* ∈ R, the approximate inhomogeneous short integer solution problem AISIS<sub>n,d,m,q,α,β</sub> is defined as follows: given **A** ∈ R<sub>q</sub><sup>d×m</sup>, **y** ∈ R<sub>q</sub><sup>d</sup>, find a vector **x** ∈ R<sup>m</sup> such that ||**x**|| ≤ *β* and such that there is a vector **z** ∈ R<sup>d</sup> satisfying: ||**z**|| ≤ *α* and **Ax** = **y** + **z** mod *q*.

**Definition 7 (Approximate Trapdoor).** A string $\tau$ is called an $(\alpha, \beta)$-approximate trapdoor for a matrix $\mathbf{A} \in \mathbb{R}_q^{d \times m}$ if there is a probabilistic polynomial time algorithm that given $\tau$, $\mathbf{A}$ and any $\mathbf{y} \in \mathbb{R}_q^d$, outputs a non-zero vector $\mathbf{x} \in \mathbb{R}^m$ such that $||\mathbf{x}|| \le \beta$ and there is a vector $\mathbf{z} \in \mathbb{R}^d$ satisfying $||\mathbf{z}|| \le \alpha$ and $\mathbf{Ax} = \mathbf{y} + \mathbf{z} \bmod q$.

In practice, we generate approximate trapdoors by dropping $\ell$ entries corresponding to the small powers of $b$ from the gadget matrix $\mathbf{G}$ to get the following matrix: $\mathbf{F} = \mathbf{I}_d \otimes \mathbf{f}^T = \mathbf{I}_d \otimes [b^\ell b^{\ell+1} b^{\ell+2} \dots b^{k-1}] \in \mathbb{R}^{d \times d(k-\ell)}$.

**3.2 Module-LWE Approximate trapdoors.**

In [9], the authors described the approximate trapdoor generation and the ap-
proximate preimage sampling algorithms, adapted from [28] by making use of
the approximate gadget matrix **F** instead of **G**. Its trapdoor generation and
trapdoor preimage sampling algorithms over modules are recalled in Figure 1
and the result of the approximate sampling is stated in Theorem 1.

**Theorem 1 ([9, Theorem 4.1]).** There exists probabilistic, polynomial time algorithms ApproxTrapGen1(·) and ApproxSamplePre1(·) such that:

1. ApproxTrapGen1(H, σ) takes as input public parameters, a tag matrix H ∈ R^d×^d and parameter σ > 0 and returns a matrix-approximate trapdoor pair (A, R) ∈ R^d×^m × R^m×ω where R coefficients are drawn from a Gaussian distribution of parameter σ over R.

2. Let **A** be generated with an approximate trapdoor as above. The following two distributions are statistically indistinguishable:

{{(*A*, *x*, *u*, *y*) | *u* ← U(R_q^d), *x* ← ApproxSamplePre1(*A*, *R*, 0, *u*, *ζ*), *y* = *u* − *Ax* mod *q*}
and {{(*A*, *x*, *u*, *y*) | *x* ← D_R^m, *ζ*, *y* ← D_R^d, *σ*√(b^2*ℓ*−1)/(b^2−1), *u* = *Ax* + *y* mod *q*}
for any *σ* ≥ √b^2 + 1 · ω(√log *d*) and *ζ* ≥ √b^2 + 1 s_1^2(R) / s_2^2(R) η_ε(Z^d*dk*).
### 3.3 iNTRU Approximate trapdoors.

In [16], Genise and Li introduced a family of Ring-SIS approximate trapdoors whose pseudorandomness is based on the iNTRU problem and then showed that the efficient gadget-based trapdoor framework of [28] exists on a family of NTRU lattices. Their trapdoor scheme enjoys small secret keys and is compatible with applications requiring tag matrices.

In their second trapdoor scheme, the matrix $\begin{bmatrix} -e^T \\ rI \end{bmatrix}$ is used as a $f$-trapdoor for $[1 \mathbf{a}] = [1 \ r^{-1}(\mathbf{f}^T + \mathbf{e}^T)]$ where $(r, e) \leftarrow \chi^{k-\ell+1}$ is drawn from a distribution with small entries and $f$ is the approximate gadget vector. They got the following results, similar to the ones from [9].

<table><caption>Fig. 1: Description of the approximate trapdoor generation and preimage sampling algorithms based on [9] (on the left-hand side) and [16] (on the right-hand side) instantiations, where the perturbation is sampled with parameter $\Sigma_p = \zeta^2 I_m - \sigma_g^2 [R_I][R_I^T]$ on the left side and $\Sigma_p = \zeta^2 I_{m+1} - \sigma_g^2 RR^T$ on the right side. Both are independent of the target $\mathbf{u}$. We refer to [9, 16] for more information on the iNTRU based trapdoor generation.</caption><thead><tr><th>ApproxTrapGen1(H, σ)</th><th>ApproxTrapGen2(σ)</th></tr></thead><tbody><tr><td>1. <b>A&#x0304;</b> &larr; U(R<sub>q</sub><sup>d&times;m&#x0304;</sup>)</td><td>1. sample r &larr; D<sub>R<sub>,σ</sub></sub>, e &larr; D<sub>R<sup>m</sup>,σ</sub></td></tr><tr><td>2. <b>R</b> &larr; D<sub>R<sup>m&times;ω</sup>,σ</sub></td><td>2. set <b>a</b>' = r<sup>-1</sup>(<b>f</b> + e) &isin; R<sup>m</sup></td></tr><tr><td>3. set <b>A</b> = [<b>A&#x0304;</b> | <b>HF</b> - <b>A&#x0304;R</b>] &isin; R<sub>q</sub><sup>d&times;m</sup></td><td>3. set <b>a</b> = (1, <b>a</b}') &isin; R<sub>q</sub><sup>m+1</sup></td></tr><tr><td>4. return (<b>A</b>, <b>R</b>)</td><td>4. set <b>R</b> = <b>-e</b><sup>T</sup> / [rI<sub>m</sub>] &isin; R<sup>(m+1)&times;m</sup></td></tr><tr><td>ApproxSamplePre1(a, R, H, u, ζ)</td><td>5. return (<b>a</b>, <b>R</b>)</td></tr><tr><td>1. sample perturbation <b>p</b> &larr; D<sub>R<sup>m</sup></sub>, &radic;<span style="text-decoration: overline">Σ<sub>p</sub></span></td><td>ApproxSamplePre2(a, R, u, ζ)</td></tr><tr><td>2. set coset <b>v</b> = H<sup>-1</sup>(<b>u</b> - <b>Ap</b>)</td><td>1. sample perturbation <b>p</b> &larr; D<sub>R<sup>m+1</sup></sub>, &radic;<span style="text-decoration: overline">Σ<sub>p</sub></span></td></tr><tr><td>3. sample <b>z</b> = (z<sub>1</sub><sup>T</sup>, z<sub>2</sub><sup>T</sup>)<sup>T</sup> &larr; D<sub>Λ<sub>q</sub><sup>v</sup>(G),σ<sub>g</sub></sub></td><td>2. set coset <b>v</b> = (u - <b>a</b><sup>T</sup><b>p</b>) &isin; R<sub>q</sub></td></tr><tr><td>4. set <b>x</b> = <b>p</b> + [<b>R</b>]<b>z</b><sub>2</sub> &isin; R<sup>m</sup></td><td>3. sample <b>z</b> = (z<sub>1</sub><sup>T</sup>, z<sub>2</sub><sup>T</sup>)<sup>T</sup> &larr; D<sub>Λ<sub>q</sub><sup>v</sup>(g<sup>T</sup>),σ<sub>g</sub></sub></td></tr><tr><td>5. return <b>x</b></td><td>4. set <b>x</b> = <b>p</b> + <b>Rz</b><sub>2</sub> &isin; R<sup>m+1</sup></td></tr></tbody></table>

**Theorem 2.** Let $r \leftarrow \chi$ and $e^T \leftarrow \chi^m$ and set the trapdoor function description as $\mathbf{a} = [1 \mathbf{a}'] = [1 \ r^{-1}(\mathbf{f} + \mathbf{e})] \in \mathcal{R}_q^{m+1}$. Let $\eta = \eta_\epsilon(Z^{n \times m})$ and $\sigma_g = \eta_\epsilon(\Lambda_q^\perp(g^T)) \ge \sqrt{b^2 + 1} \cdot \eta_\epsilon(Z^{n \times m})$ for some $\epsilon \in (0, 1)$ and $\zeta \ge \sqrt{\sigma_g^2 RR^T + \eta^2 I_{m+1}}$. Then, the following distributions are within a max-log distance $3 \log \frac{1+\epsilon}{1-\epsilon} \le \frac{6\epsilon}{1-\epsilon}$:
$$ \{(\mathbf{a}, \mathbf{x}, u, y) \mid u \leftarrow U(\mathcal{R}_q), \mathbf{x} \leftarrow \text{ApproxSamplePre2}(\mathbf{a}, \mathbf{R}, u, \zeta), y = u - \mathbf{a}^T \mathbf{x} \in \mathcal{R}_q\} $$
and $$ \{(\mathbf{a}, \mathbf{x}, u, y) \mid \mathbf{x} \leftarrow D_{\mathcal{R}^{m+1}, \zeta}, y \leftarrow D_{\mathcal{R}, \sigma_\epsilon} \mod q, u = \mathbf{a}^T \mathbf{x} + y \in \mathcal{R}_q\} $$
for $\sigma_\epsilon = \sigma_g \sqrt{(b^{2\ell} - 1)/(b^2 - 1)}$.
# 4 An Approximate-IBE scheme on modules

The first IBE scheme we present is the IBE scheme from [1, 5] adapted to the module setting, instantiated using the approximate trapdoors from [9]. At a high level, the scheme will make use of the following blocks:

- The master secret key is an $\mathbf{F}$-approximate trapdoor $\mathbf{R} \in \mathcal{R}^{\bar{m} \times \omega}$ associated with $\mathbf{A}$ with tag $\mathbf{0}$, with subgaussian coefficients of parameter $\sigma$, with $\omega = d(k - \ell)$. The master public key is a tuple consisting of a uniformly random vector $\mathbf{u} \in \mathcal{R}_q^d$ and the matrix $\mathbf{A} \in \mathcal{R}_q^{d \times m}$, with $m = \bar{m} + \omega$ chosen as: $\mathbf{A} = [\bar{\mathbf{A}} | -\bar{\mathbf{A}}\mathbf{R}]$. Taking $\bar{m} = d \log q$, we get that $\bar{\mathbf{A}}$ is full rank with high probability according to [7, Lemma 2.6]. Moreover, by taking $\sigma > 4 \cdot 4^{\frac{1}{id}} \sqrt{n}$, we obtain that $\mathbf{A}$ is statistically close to uniform by Corollary 7.5 from [25].

- A "small-norm" FRD encoding $H_M$ as described in Section 2.3. This allows anyone, with the knowledge of the master public key $\mathbf{A}$, to compute a public matrix $\mathbf{A}_{\text{id}} = \mathbf{A} + [\mathbf{0}_{d,\bar{m}} | \mathbf{H}_{\text{id}}\mathbf{F}]$ associated with the identity id of a user. Then, the secret key for id is an approximate short vector $\mathbf{x}_{\text{id}} \in \mathcal{R}^m$ obtained by using the ApproxSamplePre1 algorithm. Such a vector satisfies the relation $\mathbf{A}_{\text{id}}\mathbf{x}_{\text{id}} \approx \mathbf{u} \bmod q$. We can bound the approximate error in this relation by using Theorem 1 and the fact that we use a small-norm FRD encoding.

- Finally, we use the Dual-Regev encryption scheme for the encryption and decryption algorithms, taking care of the additional error which appears when using approximate trapdoors.

## 4.1 Construction

We detail the first IBE where users' keys are defined based on the approximate preimage sampling from Theorem 1 and encryption is based on the Dual-Regev scheme.

- Setup($1^n$) —→ (mpk, msk):

• $(\mathbf{A}, \mathbf{R}) \leftarrow \text{ApproxTrapGen1}(\mathbf{0}, \sigma) \in \mathcal{R}_q^{d \times m} \times \mathcal{R}^{\bar{m} \times w}, \mathbf{u} \leftarrow \mathcal{U}(\mathcal{R}_q^d)$;

• mpk = $(\mathbf{A}, \mathbf{u})$, msk = $\mathbf{R}$.

- Extract(mpk, msk, id) —→ $\text{sk}_{\text{id}} \mathbf{x} \in \mathcal{R}^m$:

• $\mathbf{H}_{\text{id}} \leftarrow H_M(\text{id}); \mathbf{A}_{\text{id}} \leftarrow \mathbf{A} + [\mathbf{0}_{d,\bar{m}} | \mathbf{H}_{\text{id}}\mathbf{F}] \in \mathcal{R}_q^{d \times m}$;

• $\mathbf{x} \leftarrow \text{ApproxSamplePre1}(\mathbf{A}_{\text{id}}, \mathbf{R}, \mathbf{H}_{\text{id}}, \mathbf{u}, \zeta)$;

- Encrypt(mpk, id, $M$) —→ $C = (\mathbf{b}, c) \in \mathcal{R}_q^{m+1}$:

• $\mathbf{H}_{\text{id}} \leftarrow H_M(\text{id}); \mathbf{A}_{\text{id}} \leftarrow \mathbf{A} + [\mathbf{0}_{d,\bar{m}} | \mathbf{H}_{\text{id}}\mathbf{F}] \in \mathcal{R}_q^{d \times m}$;

• $\mathbf{s} \leftarrow D_{\mathcal{R}_q^d, \tau}, \mathbf{e}_0 \leftarrow D_{\mathcal{R}^{m-w}, \tau}, \mathbf{e}_1 \leftarrow D_{\mathcal{R}^w, \tau}$, and $\mathbf{e}' \leftarrow D_{\mathcal{R}, \tau}$;

• $\mathbf{b} \leftarrow (\mathbf{s}^T \mathbf{A}_{\text{id}})^T + (\mathbf{e}_0^T | \mathbf{e}_1^T)^T$ and $c \leftarrow \mathbf{s}^T \mathbf{u} + \mathbf{e}' + \lfloor q/2 \rfloor M$;

- Decrypt($\text{sk}_{\text{id}}$, $C$) → $M$:
• set $x = sk_{id}$ and compute $res \leftarrow c - b^T x$ which has integer coefficients;

• for each $i$, if the coefficient $res_i \in \mathbb{Z}$ is closer to $\lfloor q/2 \rfloor$ than to 0, then $M_i = 1$, otherwise $M_i = 0$.

*Correctness.* To use approximate trapdoors with the Dual-Regev approach, we need to sample the LWE secret term with a small norm instead of sampling from the uniform distribution, in order to maintain the correctness of the schemes. Let's write $y \in \mathcal{R}_q^d$ the additional error we get by using approximate trapdoors instead of exact ones. The correctness of the decryption holds if the error term $\|e' - (e_0^T | e_1^T)x - s^T y\|$ is small enough, i.e. less than $\lfloor q/4 \rfloor$.

$$ \begin{aligned} \mathrm{res} &= c - b^T x \\ &= u \cdot s + e' + \lfloor q/2 \rfloor M - \left[ (s^T A_{id})^T + (e_0^T | e_1^T)^T \right]^T x \\ &= u \cdot s + e' + \lfloor q/2 \rfloor M - s^T A_{id} x - (e_0^T | e_1^T)x \\ &= u \cdot s + e' + \lfloor q/2 \rfloor M - s^T (u + y) - (e_0^T | e_1^T)x \\ &= e' - (e_0^T | e_1^T)x - s^T y + \lfloor q/2 \rfloor M \in \mathcal{R}. \end{aligned} $$

So we need to choose our parameters properly for the correctness of the Dual-Regev encryption to hold. We can bound as follows the euclidean norms of the quantities that appear in the error term:

- $\|e'\| \le t\tau\sqrt{n}$ from Lemma 2.

- $\|e_0^T x_0\| \le 2t^2\tau\zeta nd$ from Lemma 2 and Theorem 1.

- $\|e_1^T x_1\| \le t^2\gamma\zeta nd(k - \ell)$ from Lemma 2 and Theorem 1.

- $\|s^T y\| \le t^2\tau n^{5/2}d\sigma_g \frac{q^{1/r}}{\sqrt{r}} \sqrt{(b^{2\ell} - 1)/(b^2 - 1)}$ from Lemma 2 and Theorem 1.

By substituting these bounds, we get the following constraints:

$$ \begin{aligned} \|e' - (e_0^T | e_1^T)x - s^T y\| &\le \|e'\| + \|(e_0^T | e_1^T)\| + \|s^T y\| \\ &\le t\tau\sqrt{n} + t^2 nd \left[ \zeta (2\tau + \gamma(k - \ell)) + \tau n^{3/2} \sigma_g \frac{q^{1/r}}{\sqrt{r}} \sqrt{(b^{2\ell} - 1)/(b^2 - 1)} \right] \\ &\le \lfloor q/4 \rfloor. \end{aligned} $$

*Parameter constraints.* The following constraints, combined with the norms bounds above, must be met to ensure correctness:

- The Gaussian parameter $\sigma_g$ used for the $G$-sampling in the ApproxSamplePre1 algorithm must verify $\sigma_g \ge \sqrt{2b} \cdot (2b+1) \cdot \sqrt{\log(2nw(1+1/\epsilon))/\pi}$ (see [17], Corollary 3.1).

- The Gaussian width for preimage sampling $\zeta$ must follow the condition $\zeta > \sqrt{(\sigma_g^2 + 1)s_1^2(\mathbf{R}) + \eta_e^2(\mathbb{Z}^{nm})}$, knowing that $s_1(\mathbf{R}) < 1.1\sigma(\sqrt{2nd} + \sqrt{nw} + 4.7)$ with high probability (see [4], Section A.3), where $s_1(\mathbf{R})$ is the spectral norm of the trapdoor $\mathbf{R}$.
- The Gaussian width for approximate trapdoor generation $\sigma$ must verify $\sigma > 4 \cdot 4^{\frac{1}{nd}} \sqrt{n}$ to ensure the public matrix $\mathbf{A}$ we use is statistically close to uniform (see [25], Corollary 7.5).

- We choose to set the Gaussian parameter $\gamma$ of the Gaussian error $e_1 \in \mathcal{R}^w$ as $\gamma^2 = \sigma^2 \|e_0\|^2 + 2nt^2\sigma^2\tau^2$.

The proof of the following Theorem 3 is standard and can be found in the Supplementary materials, Appendix B.

**Theorem 3.** *The IBE construction with parameters $n, d, m, q, k, \ell, \sigma, \alpha, \zeta, \tau$ and $\gamma$, chosen as in the above description, is IND-sID-CPA secure in the standard model under the hardness of Module-LWE$_{n,d,q,\tau}$.*

## 4.2 Implementation and performance.

The scheme is implemented in C, using [4] libraries, inheriting its modularity. It relies on several basic blocks that can be swapped out: the arithmetic over $\mathbb{Z}_q$ and $\mathcal{R}_q$, a pseudorandom number generator, and a (constant-time) sampler of discrete Gaussian distributions over $\mathbb{Z}$. To generate our specific discrete Gaussian distributions, we make use of the following building blocks: an AES-based pseudorandom number generator (implemented using AES-NI instructions for x86 architectures), and a sampler of discrete Gaussians over $\mathbb{Z}$ similar to Karney's sampler [19]. We chose this sampler as it can generate samples in constant time, independently of the center, Gaussian parameter, and output value. All the computations that deal with non-integers are carried out with floating-point operations that do not involve subnormal numbers. We rely on results from [26, Lemma 3] to reduce multiplications in $\mathcal{R}_q$ to polynomials multiplications in rings of the form $\mathbb{Z}_q[X]/\langle X^n+1 \rangle$. The CRT reduction we used then allowed us to speed up polynomial arithmetic in $\mathcal{R}_q$.

To assess the security of each parameter set, we estimate the pseudorandomness of the public key (corresponding to the LWE security) and the hardness of breaking AISIS. The estimation of the LWE security is done with the LWE estimator of [2] with BKZ as the reduction model. We approximate our instances by an instance of an unstructured LWE problem in dimension $nd$. We follow a very pessimistic core-SVP hardness, where the cost of a BKZ algorithm with blocksize $\kappa$ is taken to be the cost of only one call to an SVP oracle in dimension $\kappa$. For the AISIS problem, we follow the approach of [9] which consists in computing the smallest blocksize achieving the target root Hermite factor corresponding to forging a signature.

*Timings.* As expected, the 4 algorithms are more efficient for low value of $d$. Concerning the Decrypt algorithm, its execution time relies mostly on the value of $n$ rather than $d$. Our timings have been obtained on an Intel i7-8650U CPU running at 1.9 GHz, and then scaled at 4.2GHz to compare ourselves with other schemes. We provide concrete parameters sets and the associated concrete results in Table 2.
<table><caption>Table 2: Proposed IBE parameters for our first construction of Section 4 with different pairs of polynomial ring dimension $n$ and rank $d$, for different moduli sizes and taking $\sigma_g = 54.9$, $\sigma = 64.1$. $\sigma_g$ is the Gaussian parameter for the G-Sampling, $\sigma$ is the Gaussian width of the trapdoor $\mathbf{R}$ used in the Setup algorithm and $\zeta$ is the standard deviation for the Gaussian preimage sampling in the Extract algorithm. Timings in columns Setup-to-Encrypt are given in ms. $M - \text{LWE}_{n,d,q,\tau}$ denotes the concrete bit security of the scheme.</caption><thead><tr><th>log<sub>2</sub> q</th><th>(n, d)</th><th>l</th><th>ζ</th><th>Setup</th><th>Extract</th><th>Encrypt</th><th>Decrypt</th><th>M - LWE<sub>n,d,q,τ</sub></th></tr></thead><tbody><tr><td>58</td><td>(256, 4)</td><td>0</td><td>1137729</td><td>203.52</td><td>56.88</td><td>17.69</td><td>2.72</td><td>81</td></tr><tr><td>58</td><td>(256, 4)</td><td>8</td><td>1068989</td><td>174.94</td><td>49.82</td><td>15.00</td><td>2.40</td><td>80</td></tr><tr><td>58</td><td>(256, 4)</td><td>15</td><td>1004226</td><td>152.70</td><td>41.57</td><td>12.79</td><td>2.19</td><td>78</td></tr><tr><td>60</td><td>(512, 3)</td><td>0</td><td>1398812</td><td>210.85</td><td>67.28</td><td>19.20</td><td>4.06</td><td>110</td></tr><tr><td>60</td><td>(512, 3)</td><td>8</td><td>1315427</td><td>189.35</td><td>59.33</td><td>17.13</td><td>3.80</td><td>109</td></tr><tr><td>60</td><td>(512, 3)</td><td>15</td><td>1236981</td><td>160.33</td><td>53.39</td><td>14.00</td><td>3.22</td><td>107</td></tr></tbody></table>

<table><caption>Table 3: Comparison of timings in ms of the different operations of the IBE scheme between this paper and [4] for parameters giving an equivalent level of security.</caption><thead><tr><th>Scheme</th><th>(n, d)</th><th>Setup</th><th>Extract</th><th>Encrypt</th><th>Decrypt</th></tr></thead><tbody><tr><td>[4] (l = 0)</td><td>(512, 2)</td><td>123.62</td><td>45.80</td><td>13.12</td><td>2.91</td></tr><tr><td>[4] (l = 0)</td><td>(256, 4)</td><td>234.45</td><td>67.90</td><td>17.88</td><td>2.69</td></tr><tr><td>This paper (l = 15)</td><td>(512, 2)</td><td>79.10</td><td>29.44</td><td>10.09</td><td>2.36</td></tr><tr><td>This paper (l = 15)</td><td>(256, 4)</td><td>152.70</td><td>41.57</td><td>12.79</td><td>2.19</td></tr></tbody></table>

*Comparison with related work.* We compare our IBE performance with the IBE from [4], which corresponds to the case $l = 0$, that is to say the use of exact trapdoors instead of approximate ones. We observe that for a fixed pair $(n, d)$, the larger $l$ is, the better timings are. Overall, the use of approximate trapdoors allows us to obtain better timings for all the algorithms comprising the IBE scheme.

## 5 An IBE scheme based on the hardness of iNTRU

In this Section, we introduce the IBE2 scheme, instantiated using gadget-based approximate trapdoors over iNTRU trapdoors combined with the Dual-Regev encryption scheme over modules.

We recall that $m = k - l$ where $k = \lceil \log_b q \rceil$ and that the approximate gadget vector $\mathbf{f}$ is defined as $\mathbf{f}^T = [b^l b^{l+1} b^{l+2} \dots b^{k-1}] \in \mathbb{R}^{k-l}$. Here, the master public key is a vector $\mathbf{a} \in \mathbb{R}^{m+1}$ generated with the ApproxTrapGen2 algorithm and whose pseudorandomness is based on the iNTRU problem. The master secret key $\mathbf{r}, \mathbf{e} \in \mathbb{R}^{m+1}$ defines an $\mathbf{f}$-approximate trapdoor associated with $\mathbf{a}$. An identity is mapped to an element in $\mathbb{R}_q$ by the use of a hash function modeled as a random oracle in the security proof; the secret key associated with an identity $\mathbf{id}$ is an approximate short vector $\mathbf{x} \in \mathbb{R}^{m+1}$.
## 5.1 IBE construction details

We detail below the four algorithms of the IBE2:

- Setup(1^n) → (mpk, msk):

• let $a = [1 \ a_0^T]^T \in \mathcal{R}_q^{m+1}$ and $R = \begin{bmatrix} -e_0^T \\ rI_m \end{bmatrix} \in \mathcal{R}^{(m+1) \times m}$ output by ApproxTrapGen2($\sigma$); and let $\mathcal{H} : \{0, 1\}^* \to \mathcal{R}_q$ a hash function;

• output mpk = ($a, \mathcal{H}$) and msk = $R$.

- Extract(mpk, msk, id) → $x_{id} = x_2 \in \mathcal{R}^m$:

• define the tag $h_{id} = \mathcal{H}(id) \in \mathcal{R}_q$;

• sample a short preimage $x = (x_1, x_2^T)^T \leftarrow \text{ApproxSamplePre2}(a, R, h_{id}, \zeta)$;

- Encrypt(mpk, id, M) → $C = (b, c) \in \mathcal{R}_q^{m+1}$:

• compute $h_{id} = \mathcal{H}(id)$; sample $s \leftarrow D_{\mathcal{R},\tau}$, $e_1 \leftarrow D_{\mathcal{R}^m,\tau}$, $e_2 \leftarrow D_{\mathcal{R},\tau}$;

• compute $b = sa_0 + e_1 \in \mathcal{R}_q^m$ and $c = h_{id} \cdot s + e_2 + \lfloor q/2 \rfloor M \in \mathcal{R}_q$, where a message is encoded as $M \in \mathcal{R}_2$;

- Decrypt($x_{id}, C$) → $M$:

• parse $x_{id}$ as $(x_1, x_2)$; and compute $\text{res} \leftarrow c - b^T x_2$;

• for each $i$, if the coefficient $\text{res}_i \in \mathbb{Z}$ is closer to $\lfloor q/2 \rfloor$ than to 0, $M_i = 1$, otherwise $M_i = 0$.

*Correctness.* We have the following equality:

$$ 
\begin{aligned}
c - b^T x_2 &= h_{id} \cdot s + e_2 + \lfloor q/2 \rfloor M - (sa_0 + e_1)^T x_2 \\
&= s \cdot x_1 + s a_0^T x_2 - y \cdot s + e_2 + \lfloor q/2 \rfloor M - s a_0^T x_2 - e_1^T x_2 \\
&= \lfloor q/2 \rfloor M + s \cdot (x_1 - y) + e_2 - e_1^T x_2.
\end{aligned}
$$

Furthermore, the following bounds apply:

- $\|s \cdot x_1\| \le t^2 \tau \zeta n$ from Lemma 2 and Theorem 2.

- $\|y \cdot s\| \le t^2 \tau \sigma_g \sqrt{(b^{2\ell} - 1)/(b^2 - 1)} n$ from Lemma 2 and Theorem 2.

- $\|e_2\| \le t \tau \sqrt{n}$ from Lemma 2.

- $\|e_1^T x_2\| \le t^2 \tau \zeta nm$ from Lemma 2 and Theorem 2.

By substituting these bounds, we obtain:

$$ 
\begin{aligned}
\|s \cdot (x_1 - y) + e_2 - e_1^T x_2\| &\le \|s \cdot x_1\| + \|y \cdot s\| + \|e_2\| + \|e_1^T x_2\| \\
&\le t^2 \tau \left[ \zeta (m+1) + \sigma_g \sqrt{(b^{2\ell} - 1)/(b^2 - 1)} \right] + t \tau \sqrt{n} \\
&\le \lfloor q/4 \rfloor.
\end{aligned}
$$
*Parameters constraints.* The following constraints combined with the errors norm constraints above should be satisfied:

- The Gaussian parameter $\sigma_g$ used for the $G$-sampling in the ApproxSamplePre2 algorithm must verify $\sigma_g \ge \sqrt{2b} \cdot (2b+1) \cdot \sqrt{\log(2nw(1+1/\epsilon))/\pi}$ (see [17], Corollary 3.1).

- The Gaussian width for preimage sampling $\zeta$ must follow the condition $\zeta > \sqrt{(\sigma_g^2 + 1)s_1^2(\mathbf{R}) + \eta_e^2(\mathbb{Z}^{nm})}$, where $s_1(\mathbf{R})$ is the spectral norm of the trapdoor $\mathbf{R}$ (see [4], Section A.3).

The proof of the following is adapted from the GPV IBE proof [18, Section 7.2] and is given in the Supplementary materials, Appendix C.

**Theorem 4.** *Our IBE construction with parameters $n, m, q, k, \ell, \sigma, \sigma_g, \zeta, \tau$ and $\gamma$ is IND-sID-CPA secure in the random oracle model under the hardness of $\text{iNTRU}_{q, D_{R,\sigma}}$ and Ring-LWE$_{n,q,\tau}$.*

## 5.2 Implementation and performance

In [15], the authors only propose a reduction from a non-standard version of LWE to iNTRU. Therefore, in the absence of a thorough study on the asymptotic and practical security of the iNTRU problem, which we leave for future work, we have chosen to estimate the security of our iNTRU instances by relying on the existing cryptanalysis on NTRU. As explained in [15], there is a syntactic link between NTRU and iNTRU. To the best of our knowledge, there is no known reduction between the two problems and the analysis of the iNTRU assumption might deserve additional study. Still, we additionally consider the practical security of NTRU for our targetted sets of parameters and we take into account the known cryptanalysis efforts on iNTRU.

For security estimation, we follow the same approach as in [16] to assess the concrete security of the IBE2 scheme. We determine the hardness of our underlying lattice problem by computing the root Hermite factor, introduced in [14]. Then, we use the following heuristic relation between the blocksize $\kappa$ and the root Hermite factor $\delta$ to find the smallest blocksize which would break our underlying lattice problem:

$$ \delta \approx \left( \frac{\kappa}{2\pi e} (\pi\kappa)^{1/\kappa} \right)^{1/2(\kappa-1)}. $$

Finally, our experiments estimate the running time of the BKZ algorithm to analyze the concrete security of the scheme. This algorithm makes use of an oracle to solve the Shortest Vector Problem (SVP) in smaller lattices. We chose the "Core-SVP" model introduced in [3] in the sieving regime as the SVP oracle for the BKZ algorithm with time complexity $2^{0.292\kappa+16.4}$ in the blocksize $\kappa$.
*Overstretched parameters.* [23] adapts the attack from [20] on iNTRU, which applies to the parameters originally proposed for the homomorphic encryption scheme from [15]. The attack can be performed when the modulus $q$ is much larger than the dimension of the associated lattices. The target iNTRU instance has an error and secret that follow a uniform binary distribution. Following [20] attack, [23] uses the fact that a very dense sublattice can be found in this NTRU-like lattice, because of the overstretched regime. Relying on a lemma from Pataki and Tural [30, Lemma 1], they can bound the volume of this sublattice and run a BKZ-reduction which leads to a full recovery of the iNTRU secret. [12] improves the asymptotic bound given by Kirchner and Fouque [20] by conducting a refined analysis which lowers the overstretched regime for NTRU with ternary distribution to the value $q = n^{2.484+o(1)}$.

They also provide a concrete analysis, computing a bound on the modulus $q$ for which the attacks exploiting the overstretched regime are more efficient than standard secret key recovery attacks. The authors of [12] run experiments which allow detecting the fatigue "point", which separates these two regimes.

The cryptanalysis carried out by [23] and [12] can be adapted for the iNTRU instances we consider, where the secret and the error both follow a Gaussian distribution. [12] also consider the case where the NTRU secret distributions are Gaussian. Indeed, in both cases, the cryptanalysis in the overstretched regime requires performing lattice reductions on sublattices of a NTRU-like lattice, in order to retrieve the very dense sublattice. We leave the detailed adaptation of this attack to iNTRU and its experimental study for future work. For our concrete parameters analysis, we took care to fall outside the range of parameters affected in the overstretched regime.

*Timings.* Our timings have been obtained on an Intel i7-8650U CPU running at 1.9 GHz, and then scaled at 4.2GHz to compare ourselves with other schemes. Results are provided in Table 4. The use of the efficient gadget-based approximate trapdoor framework together with the iNTRU hardness assumption allows us to obtain efficient algorithms. The slowest of the 4 algorithms of the IBE2 scheme are the Setup and Extract algorithms, which correspond respectively to the approximate trapdoor generation and preimage sampling phases of the scheme. However, the Setup algorithm is usually not performed often, and the subroutine algorithms used by Extract for sampling are really modular, leaving the way for possible future improvements. Moreover, our Setup and Extract algorithms are competitive with other NTRU-based IBE (see Table 5 and Table 6).

*Comparison with related works.* We compare the IBE2 timings with the ones of [11] (re-implemented in [27]) and with [33], two IBE schemes whose security is based on the NTRU hardness assumption. Our comparison experiments were carried out using equivalent parameters sets between the different schemes. In particular, we have been careful to use equivalent module sizes and equivalent noise rates when performing Gaussian Sampling.
<table><caption>Table 4: Timings of the different operations for different values of *n*, given in ms from Setup to Decrypt.</caption><thead><tr><th>(n, q)</th><th>[log<sub>2</sub>(q)]</th><th>Setup</th><th>Extract</th><th>Encrypt</th><th>Decrypt</th><th>Bit security</th></tr></thead><tbody><tr><td>(256, 1073741441)</td><td>30</td><td>1.01</td><td>2.13</td><td>0.39</td><td>0.03</td><td>64</td></tr><tr><td>(512, 1073741441)</td><td>30</td><td>2.12</td><td>3.79</td><td>0.74</td><td>0.06</td><td>115</td></tr><tr><td>(1024, 1073741441)</td><td>30</td><td>4.08</td><td>7.65</td><td>1.49</td><td>0.11</td><td>223</td></tr><tr><td>(256, 16777601)</td><td>25</td><td>0.78</td><td>1.66</td><td>0.23</td><td>0.02</td><td>35</td></tr><tr><td>(512, 16777601)</td><td>25</td><td>1.48</td><td>3.00</td><td>0.49</td><td>0.04</td><td>82</td></tr><tr><td>(1024, 16777601)</td><td>25</td><td>3.32</td><td>5.92</td><td>1.10</td><td>0.07</td><td>159</td></tr></tbody></table>

<table><caption>Table 5: Timings comparison of the different operations of the IBE scheme between this paper and [11] (the timings are extracted from the [27] article, scaled up to account for CPU differences) for different parameter sets. The timings are given in ms, except for the Setup algorithm from [11], which is given in seconds.</caption><thead><tr><th>Scheme</th><th>(n, [log<sub>2</sub>(q)])</th><th>Security level</th><th>Setup</th><th>Extract</th><th>Encrypt</th><th>Decrypt</th></tr></thead><tbody><tr><td>[11]</td><td>(512, 26)</td><td>&lt; 80</td><td>3.84s</td><td>1.77</td><td>0.10</td><td>0.05</td></tr><tr><td>[11]</td><td>(1024, 26)</td><td>&lt; 192</td><td>23.93s</td><td>6.95</td><td>0.27</td><td>0.09</td></tr><tr><td>This paper</td><td>(512, 25)</td><td>82</td><td>1.48</td><td>3.00</td><td>0.49</td><td>0.04</td></tr><tr><td>This paper</td><td>(1024, 25)</td><td>159</td><td>3.32</td><td>5.92</td><td>1.10</td><td>0.07</td></tr></tbody></table>

<table><caption>Table 6: Timings comparison of the different operations of the IBE scheme in this paper and in [33] for different sets of parameters in ms.</caption><thead><tr><th>Scheme</th><th>(n, [log<sub>2</sub>(q)])</th><th>Security level</th><th>Setup</th><th>Extract</th><th>Encrypt</th><th>Decrypt</th></tr></thead><tbody><tr><td>[33]</td><td>(1024, 24)</td><td>128</td><td>102</td><td>0.82</td><td>0.05</td><td>0.06</td></tr><tr><td>[33]</td><td>(2048, 25)</td><td>256</td><td>292</td><td>2.62</td><td>0.10</td><td>0.13</td></tr><tr><td>[33]</td><td>(1024, 36)</td><td>80</td><td>165</td><td>26.4</td><td>0.08</td><td>0.09</td></tr><tr><td>[33]</td><td>(2048, 38)</td><td>160</td><td>643</td><td>57.8</td><td>0.16</td><td>0.18</td></tr><tr><td>This paper</td><td>(1024, 25)</td><td>159</td><td>3.32</td><td>5.92</td><td>1.10</td><td>0.07</td></tr><tr><td>This paper</td><td>(2048, 25)</td><td>293</td><td>10.21</td><td>12.79</td><td>2.96</td><td>0.16</td></tr><tr><td>This paper</td><td>(1024, 30)</td><td>191</td><td>4.08</td><td>7.65</td><td>1.49</td><td>0.11</td></tr><tr><td>This paper</td><td>(2048, 30)</td><td>412</td><td>12.51</td><td>16.03</td><td>3.89</td><td>0.23</td></tr></tbody></table>

We observe that we obtain better timings for the Setup algorithm than [11] and [33] and for the Extract for some sets of parameters. Furthermore, our Decrypt algorithm is slightly faster than [11]. However, the Encrypt algorithm is less efficient than theirs. The use of binomial distribution improves the timings for encryption. An improvement can be obtained in our case by using the binomial distribution, but we need more samples in our case which still affects performance for encryption; we make $n(2 + m)$ calls to the integer Gaussian sampler while encryption in [11] and [33] can make use of only $3n$ binomial sampling calls. As in [33], our Extract algorithm is slower than the Sign algorithm from the Falcon signature scheme [13]. Note also that for a similar security level, Falcon can use smaller parameters than us.
We obtain an overhead in terms of parameters sizes compared to [11] and [33], but the trapdoor generations rely on a different paradigm. Results on public and secret sizes are provided in Appendix D. Nonetheless, as stated in [9], the use of approximate trapdoors instead of exact ones helps us to reduce the sizes of the public key and signatures by up to two times. Therefore, as expected, our obtained sizes for the master and the users' private keys and the ciphertexts are close to the ones of [16] whose signature scheme relies on the same paradigm as the IBE2 scheme.

**Acknowledgements.** This work is supported by the ANR ASTRID project AMIRAL (ANR-21-ASTR-0016).
# Supplementary materials

## A Definition of an IBE scheme

An IBE scheme is composed of 4 polynomial time algorithms defined as follows:

Setup(1$^n$) → (mpk, msk): takes as input a security parameter $n$ and outputs the master public key mpk and the master secret key msk. We assume public parameters which are part of mpk are taken as input to all 3 next algorithms.

Extract(mpk, msk, id) → sk<sub>id</sub>: takes as input the security parameter, the master keys mpk, msk and an identity id ∈ ID and outputs a private key sk<sub>id</sub> associated with the identity id.

Encrypt(mpk, id, M) → C: takes as input the security parameter, the master public key mpk, an identity id and a message M and outputs a ciphertext C which is the encryption of M for identity id.

Decrypt(mpk, sk<sub>id</sub>, C) → M or Error: takes as input the master public key mpk, a private key sk<sub>id</sub> associated with the identity id and a ciphertext C, it outputs either a message M or an Error message indicating the ciphertext is invalid.

**Correctness.** An IBE is correct if for any message $M$ in the message space and identity id such that (mpk, msk) ← Setup(1$^n$) and sk<sub>id</sub> ← Extract(mpk, msk, id), Decrypt(mpk, sk<sub>id</sub>, Encrypt(mpk, id, M)) = M holds with overwhelming probability.

**Security Game.** We describe the notion of ciphertext indistinguishability under a selective-identity chosen-plaintext attack (IND-sID-CPA), meaning that the adversary indicates the identity on which he would like to be challenged. The notion is defined as a game between an adversary $\mathcal{A}$ and a challenger, and works as follows:

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

- **Setup**: The challenger runs Setup(1$^n$) and gives the master public key msk to $\mathcal{A}$.

- **Extract queries - Phase 1**: The adversary can make private-key extraction queries on identities id ≠ id*, and the challenger answers by running sk<sub>id</sub> ← Extract(mpk, msk, id).

- **Challenge**: The adversary $\mathcal{A}$ outputs two plaintexts $M_0, M_1$. The challenger chooses a random bit $b^* \leftarrow \{0, 1\}$ and sets the challenge ciphertext to $C^* = \text{Encrypt}(\text{mpk}, \text{id}^*, M_{b^*})$. The challenge ciphertext $C^*$ is sent to $\mathcal{A}$.

- **Extract queries - Phase 2**: The adversary can make additional queries (answered as in Phase 1).

- **Guess**: The adversary 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{IBE}}^{\text{ind-sID-cpa}}) = |\Pr(b = b^*) - \frac{1}{2}|$. An IBE scheme is IND-sID-CPA secure if, for all PPT adversary $\mathcal{A}$, his advantage $\text{Adv}(\mathcal{A}_{\text{IBE}}^{\text{ind-sID-cpa}})$ is negligible.
## B Proof of Theorem 3

*Proof.* The proof proceeds in a sequence of games $G_i$ where the first game $G_0$ is identical to the original IND-sID-CPA game. In the last game in the sequence, the adversary has no information left about the initial message and hence has advantage zero. We show that a PPT adversary cannot distinguish between the intermediate games.

**Game $G_0$.** This is the initial IND-sID-CPA game between an adversary $\mathcal{A}$ and an IND-sID-CPA challenger.

**Game $G_1$.** In this game, we change the way the challenger generates the public matrix $\mathcal{A}$ by adding information about the identity $id^*$ that $\mathcal{A}$ targets for his attack. In Game 0, $\mathcal{A}$ was generated thanks to ApproxTrapGen1(0, $\sigma$), together with the associated trapdoor $\mathbf{R}$. We had $\mathcal{A} = [\bar{\mathcal{A}} | -\bar{\mathcal{A}}\mathbf{R}]$. The public matrix $\mathcal{A}$ is now generated in $G_1$ thanks to the algorithm ApproxTrapGen1(-$\mathbf{H}_{id^*}$, $\sigma$), so that we have $\mathcal{A} = [\bar{\mathcal{A}} | -\mathbf{H}_{id^*}\mathbf{F} - \bar{\mathcal{A}}\mathbf{R}] \in \mathcal{R}_q^{d \times m}$.

This matrix $\mathcal{A}$ is statistically indistinguishable from a uniformly random matrix.

The challenger answers $\mathcal{A}$'s private key queries on identities $id \neq id^*$ by calling Extract((A, u), R, id) and then using ApproxSamplePre1(A_id, R, H_id, u, $\zeta$). We have $A_{id} = [\bar{A} | (H_{id} - H_{id^*})F - \bar{\mathcal{A}}\mathbf{R}]$ and $H_{id} - H_{id^*}$ is invertible because of the FRD construction, which allows the challenger to get a private key associated with the identity id.

**Game $G_2$.** This game is identical to $G_1$ except that the challenge ciphertext $C^*$ is chosen as a uniformly random element in $\mathcal{R}_q^{m+1}$ instead of being chosen by calling Encrypt((A, u), id^*, $M_{b^*}$).

*Reduction from Module-LWE.* We show that $G_2$ and $G_1$ are computationally indistinguishable for the adversary $\mathcal{A}$ under the Module-LWE assumption.

Suppose $\mathcal{A}$ has a non-negligible advantage in distinguishing $G_2$ and $G_1$. We will use $\mathcal{A}$ to construct a simulator $\mathcal{B}$ who will be able to solve the Module-LWE problem with non-negligible advantage.

The simulator $\mathcal{B}$ receives $\bar{m} + 1$ samples $(A_i, b_i)_{0 \le i \le \bar{m}}$ with $A_i \in \mathcal{R}_q^d$ and $b_i \in \mathcal{R}_q$ as an instance of the decisional Module-LWE problem. The simulator also receives the identity $id^*$ targeted by the adversary $\mathcal{A}$. The simulator sets $A' = (A_1, \dots, A_{\bar{m}}) \in \mathcal{R}_q^{d \times \bar{m}}$ and $b' = (b_1, \dots, b_{\bar{m}}) \in \mathcal{R}_q^{\bar{m}}$ and then runs ApproxTrapGen1(-$\mathbf{H}_{id^*}$, $\sigma$) to get $\mathcal{A} = [A' | -\mathbf{H}_{id^*}\mathbf{F} - A'R]$ together with the trapdoor. Next, $\mathcal{B}$ sets $u = A_0 \in \mathcal{R}_q^d$ and he sends $(A, u)$ to $\mathcal{A}$ as the master public key. Then, $\mathcal{B}$ answers $\mathcal{A}$'s private key queries as in $G_1$.

Afterwards, the adversary outputs two plaintexts $M_0, M_1$ and sends them to $\mathcal{B}$. The simulator generates a random bit $b^*$, and the challenge ciphertext $C^* = (b^*, c^*)$ as follows:

$$b^* = (b'^T | -b'^T R + \hat{e}^T)^T, c^* = b_0 + \lfloor q/2 \rfloor M_{b^*},$$
where $\hat{e} \leftarrow D_{\mathbb{R}^w, \mu}$ for some real $\mu$, that is explicited below.

*Samples from the LWE distribution.* If the Module-LWE samples are drawn from the Module-LWE distribution, we have:

$$b^T = s^T A' + e^T \text{ and } b_0 = s^T A_0 + e_0,$$

for some $s \in \mathbb{R}_q^d$, $e' \leftarrow D_{\mathbb{R}^m, \tau}$ and $e_0 \leftarrow D_{\mathbb{R}, \tau}$. Therefore, the first part of the ciphertext is $b^* = A_{id^*}^T s + (e^T | - e^T R + \hat{e}^T)^T$ and the second part is $c^* = s^T A_0 + e_0 + \lfloor q/2 \rfloor M_{b^*}$.

Then, for a fixed error $e'$, the term $-e^T R$ is distributed as $D_{\mathbb{R}^w, \sigma || e' ||}$ since $\mathbb{E}[e^T R] = e^T \mathbb{E}[R] = 0$ and $\text{cov}(e^T R) = \sigma^2 e^T e' I_w = \sigma^2 ||e'||^2 I_w$ by linearity of expectation and bilinearity of covariance. Moreover, the random variable $\hat{e}$ follows the Gaussian distribution $D_{\mathbb{R}^w, \mu}$ and is independent from the random variable $e^T R$. Therefore, $-e^T R + \hat{e}$ is indistinguishable from a sample drawn from the distribution $D_{\mathbb{R}^w, \gamma}$ for $\mu$ satisfying $\gamma^2 = (\sigma ||e'||)^2 + \mu^2$.

Then, the challenge ciphertext $(b^*, c^*)$ follows the same distribution as in $G_1$.

*Samples from the uniform distribution.* If the Module-LWE samples are drawn from the uniform distribution, the ciphertext challenge also looks uniform as in $G_2$.

Finally, the adversary $\mathcal{A}$ outputs a guess $b$. Because we supposed $\mathcal{A}$ has a non-negligible advantage in distinguishing $G_1$ and $G_2$, if $b = b'$ with overwhelming probability, the simulator concludes that the challenged instance was drawn from the Module-LWE distribution. Otherwise, $\mathcal{B}$ concludes that the Module-LWE instance was drawn from the uniform distribution.

## C Proof of Theorem 4

For the sake of completeness, we give the IND-sID-CPA proof of the IBE2 scheme, which is directly adapted from [18, Theorem 7.2].

*Proof.* The idea of the proof is to simulate the view of the adversary given a Ring-LWE instance $(a'_i, b'_i)$ for $0 \le i \le m$ for which we build an attacker $\mathcal{S}$ who makes $Q_{\mathcal{H}}$ queries to $\mathcal{H}$.

We construct a new simulation game given $\mathbf{a}_0 = [a'_1 \dots a'_m]$. $\mathcal{S}$ chooses an index $i^*$ at random in $[1, Q_{\mathcal{H}}]$ and sets $h_{id^*} = a'_0$.

A hash query on input $id$ is answered as follows: it first checks whether an entry of the form $(id, *, *, *)$ already exists in the hash table. If it is not the case, it responds with a value $u_{id}$ such that an approximated preimage for $\mathcal{H}(id) = h_{id}$ is known i.e: it samples $\mathbf{x} \leftarrow D_{\mathbb{R}^{m+1}, \zeta}$ and $y_{id} \leftarrow D_{\mathbb{R}, \sigma_e}$ such that $y_{id} = (x_1^T, x_2^T)^T [1 \mathbf{a}_0]$, sets $h_{id} = (x_1^T, x_2^T)^T [1 \mathbf{a}_0] - y_{id}$ and adds the tuple $(id, h_{id}, x_2, y_{id})$ in the hash table.

An extraction query for an identity $id$ is responded as follows: assuming that an entry for $id$ already exists in the table, the corresponding $x_2$ is output by $\mathcal{S}$.
Note that the response to the extract queries is close to the response provided in the real game by Theorem 2 if $\mathcal{H}$ is modeled as a random oracle and the way the public key is generated is indistinguishable from that in the real game under the iNTRU assumption.

When the attacker outputs two messages $m_0, m_1$ and $\mathit{id}^*$, if $\mathit{id}^*$ has not been queried to $\mathcal{H}$, then $\mathcal{S}$ aborts; otherwise the challenger sets the challenger ciphertext as:

$$ (b, c) = ([b'_1 \dots b'_m], b'_0 + \lfloor q/2 \rfloor m_b) \in \mathcal{R}_q^{m+1}. $$

The attacker $\mathcal{S}$ outputs the same bit as $\mathcal{A}$. Assuming no abort has occurred, they both have the same advantage, which concludes the proof.

## D Parameters' sizes comparison

The use of the [28] paradigm doesn't make us competitive compared to [11] and [33] in terms of parameters sizes. As explained in Section 5.2, the trapdoor generations rely on a different paradigm. However, for completeness, we provide comparisons with [11] in Table 7 and with [33] in Table 8 in terms of parameters' sizes.

<table><caption>Table 7: Parameters sizes comparison between IBE2 parameters sizes and [11] for different sets of parameters at a similar security level, in Bytes.</caption><thead><tr><th>Scheme</th><th>(n, ⌈log<sub>2</sub>(q)⌋)</th><th>Security</th><th>mpk</th><th>msk</th><th>sk<sub>id</sub></th><th>Ciphertext</th></tr></thead><tbody><tr><td>[11]</td><td>(512, 23)</td><td>&lt; 80</td><td>1536</td><td>6144</td><td>1375</td><td>1625</td></tr><tr><td>[11]</td><td>(1024, 27)</td><td>&lt; 192</td><td>3584</td><td>14336</td><td>3375</td><td>3750</td></tr><tr><td>This paper</td><td>(512, 25)</td><td>≈ 80</td><td>14720</td><td>16192</td><td>16192</td><td>16192</td></tr><tr><td>This paper</td><td>(1024, 25)</td><td>≈ 192</td><td>32000</td><td>35200</td><td>35200</td><td>35200</td></tr></tbody></table>

<table><caption>Table 8: Parameters sizes comparison between IBE2 parameters sizes and [33] for different sets of parameters at a similar security level, in Bytes.</caption><thead><tr><th>Scheme</th><th>(n, ⌈log<sub>2</sub>(q)⌋)</th><th>Security</th><th>mpk</th><th>msk</th><th>sk<sub>id</sub></th><th>Ciphertext</th></tr></thead><tbody><tr><td>[33]</td><td>(1024, 36)</td><td>80</td><td>4608</td><td>18432</td><td>4608</td><td>9248</td></tr><tr><td>[33]</td><td>(1024, 24)</td><td>128</td><td>3072</td><td>12288</td><td>3072</td><td>6176</td></tr><tr><td>[33]</td><td>(2048, 25)</td><td>256</td><td>6400</td><td>25600</td><td>6400</td><td>12832</td></tr><tr><td>This paper</td><td>(512, 25)</td><td>&gt; 80</td><td>14720</td><td>16192</td><td>16192</td><td>16192</td></tr><tr><td>This paper</td><td>(1024, 25)</td><td>&gt; 128</td><td>32000</td><td>35200</td><td>35200</td><td>35200</td></tr><tr><td>This paper</td><td>(2048, 25)</td><td>&gt; 256</td><td>64000</td><td>70400</td><td>70400</td><td>70400</td></tr></tbody></table>

We observe that using approximate trapdoors instead of exact ones can help reduce the size of public keys and signatures by up to two times.
## References

[1] S. Agrawal, D. Boneh, and X. Boyen. "Efficient Lattice (H)IBE in the Standard Model". In: *EUROCRYPT*. LNCS. Springer, 2010.

[2] M. R. Albrecht, R. Player, and S. Scott. "On the concrete hardness of Learning with Errors". In: *J. Mathematical Cryptology* (2015).

[3] E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe. "Post-quantum Key Exchange - A New Hope". In: *USENIX Security Symposium*. 2016.

[4] P. Bert, G. Eberhart, L. Prabel, A. Roux-Langlois, and M. Sabt. "Implementation of Lattice Trapdoors on Modules and Applications". In: *PQCrypto*. Lecture Notes in Computer Science. Springer, 2021.

[5] P. Bert, P. Fouque, A. Roux-Langlois, and M. Sabt. "Practical Implementation of Ring-SIS/LWE Based Signature and IBE". In: 2018.

[6] D. Boneh and M. K. Franklin. "Identity-Based Encryption from the Weil Pairing". In: *CRYPTO*. LNCS. Springer, 2001.

[7] K. Boudgoust, C. Jeudy, A. Roux-Langlois, and W. Wen. "On the Hardness of Module Learning With Errors with Short Distributions". In: *J. Cryptology* 28.1 (2023).

[8] D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert. "Bonsai Trees, or How to Delegate a Lattice Basis". In: *EUROCRYPT*. 2010.

[9] Y. Chen, N. Genise, and P. Mukherjee. "Approximate Trapdoors for Lattices and Smaller Hash-Sign Signatures". In: *ASIACRYPT*. 2019.

[10] C. C. Cocks. "An Identity Based Encryption Scheme Based on Quadratic Residues". In: *IMACC*. Springer, 2001.

[11] L. Ducas, V. Lyubashevsky, and T. Prest. "Efficient Identity-Based Encryption over NTRU Lattices". In: *ASIACRYPT*. 2014.

[12] L. Ducas and W. P. J. van Woerden. "NTRU Fatigue: How Stretched is Overstretched?" In: *ASIACRYPT (4)*. 2021.

[13] P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang. *FALCON: Fast-Fourier Lattice-based Compact Signatures over NTRU*. 2017.

[14] N. Gama and P. Q. Nguyen. "Predicting Lattice Reduction". In: *EUROCRYPT*. Lecture Notes in Computer Science. Springer, 2008.

[15] N. Genise, C. Gentry, S. Halevi, B. Li, and D. Micciancio. "Homomorphic Encryption for Finite Automata". In: *ASIACRYPT*. 2019.

[16] N. Genise and B. Li. "Gadget-Based NTRU Lattice Trapdoors". In: *IN-DOCRYPT*. 2020.

[17] N. Genise and D. Micciancio. "Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus". In: *EUROCRYPT*. 2018.

[18] C. Gentry, C. Peikert, and V. Vaikuntanathan. "Trapdoors for hard lattices and new cryptographic constructions". In: *STOC*. 2008.

[19] C. F. F. Karney. "Sampling Exactly from the Normal Distribution". In: *ACM Trans. Math. Softw.* 42.1 (2016), 3:1–3:14.

[20] P. Kirchner and P. Fouque. "Revisiting Lattice Attacks on Overstretched NTRU Parameters". In: *EUROCRYPT (1)*. Vol. 10210. Lecture Notes in Computer Science. 2017, pp. 3–26.
[21] R. W. F. Lai, H. K. F. Cheung, and S. S. M. Chow. "Trapdoors for Ideal Lattices with Applications". In: *Inscrypt*. 2014.

[22] A. Langlois and D. Stehlé. "Worst-case to average-case reductions for module lattices". In: *DCC* 75.3 (2015), pp. 565–599.

[23] C. Lee and A. Wallet. *Lattice analysis on MiNTRU problem*. Cryptology ePrint Archive, Paper 2020/230, 2020.

[24] V. Lyubashevsky. "Lattice Signatures without Trapdoors". In: *EUROCRYPT*. Vol. 7237. LNCS. Springer, 2012, pp. 738–755.

[25] V. Lyubashevsky, C. Peikert, and O. Regev. "A Toolkit for Ring-LWE Cryptography". In: *EUROCRYPT*. Springer, 2013.

[26] V. Lyubashevsky and G. Seiler. "Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs". In: *EUROCRYPT*. 2018.

[27] S. McCarthy, N. Smyth, and E. O'Sullivan. "A Practical Implementation of Identity-Based Encryption Over NTRU Lattices". In: 2017.

[28] D. Micciancio and C. Peikert. "Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller". In: *EUROCRYPT*. 2012.

[29] D. Micciancio and O. Regev. "Worst-Case to Average-Case Reductions Based on Gaussian Measures". In: *SIAM J. Comput*. (2007).

[30] G. Pataki and M. Tural. "On sublattice determinants in reduced bases". In: *arXiv preprint arXiv:0804.4014* (2008).

[31] A. Shamir. "Identity-Based Cryptosystems and Signature Schemes". In: *CRYPTO*. 1984.

[32] S. Zhang and Y. Yu. "Towards a Simpler Lattice Gadget Toolkit". In: *Public Key Cryptography*. 2022.

[33] R. K. Zhao, S. McCarthy, R. Steinfeld, A. Sakzad, and M. O'Neill. *Quantum-safe HIBE: does it cost a Latte?* ePrint Archive. 2021.