Trapdoors for Ideal Lattices with Applications

Abstract

There is a lack of more complicated ideal-lattice-based cryptosystems which require the use of lattice trapdoors, for the reason that currently known trapdoors are either only applicable to general lattices or not well-studied in the ring setting. To facilitate the development of such cryptosystems, we extend the notion of lattice trapdoors of Micciancio and Peikert (Eurocrypt ’12) into the ring setting with careful justification. As a demonstration, we use the new trapdoor to construct a new hierarchical identity-based encryption scheme, which allows us to construct public-key encryption with chosen-ciphertext security, signatures, and public-key searchable encryption.

This work is supported by grants 439713, 14201914 from Research Grants Council (RGC), and grants 4055018, 4930034 from The Chinese University of Hong Kong. Sherman Chow is supported by the Early Career Award from RGC. Part of the work was done while the second author is with Department of Information Engineering.

1 Introduction

Lattice-based cryptography is a promising alternative to create cryptosystems that are secure even against quantum adversaries. Many powerful primitives including fully-homomorphic encryption [1–4], homomorphic signatures [5, 6], multilinear map [7], (hierarchical) identity-based encryption [8, 9] (which is also useful for achieving other cryptographic goals like public-key encryption with chosen-ciphertext security, signatures, and public-key searchable encryption), and much more can be realized by lattices. Security reductions of some of these constructions are directly based on the now well-studied (ring-)$\mathsf {LWE}$ (learning with errors) or (ring-)$\mathsf {SIS}$ (short integer solutions) problems, which are both as hard as the corresponding worst-case (ideal) lattice problems.

Hard Lattice Problems. An instance of the $\mathsf {LWE}$ problem is defined by a random $n$ by $m$ integer matrix $A$ and a vector $\mathbf {b}$, where $\mathbf {b} = A^T \mathbf {s} + \mathbf {e} ~ \mathrm{mod} ~ q$ for some secret vector $\mathbf {s}$ and small noise vector $\mathbf {e}$. The problem is to find the vector $\mathbf {s}$. As a “dual” problem to $\mathsf {LWE}$, an instance of the $\mathsf {SIS}$ problem is defined by the same random matrix $A$, where one is asked to find a short vector $\mathbf {x}$ so that $A\mathbf {x} = 0 ~\mathrm{mod} ~q$.

The “ring” versions of $\mathsf {LWE}$ and $\mathsf {SIS}$, named $\text {ring-}\mathsf {LWE}$ and $\text {ring-}\mathsf {SIS}$ respectively, are specific instances of $\mathsf {LWE}$ and $\mathsf {SIS}$ respectively defined for some structured matrix $A$ to be explained below.

Ideal Lattices. In ideal lattices, or the so called “ring setting”, the matrix $A$ above is required to have some additional algebraic structures. One commonly used example is to interpret each column of $A$ as coefficients of a degree-$(n-1)$ polynomial $p(x)$, and require that $x p(x) ~ \mathrm{mod} ~ (x^n+1)$ is also contained in some column of $A$. In such case, the matrix multiplications by $A$ are equivalent to polynomial multiplications. We can therefore view each vector $\mathbf {v}$ as an element $\mathbf {v}$ in the ring $R_q = \mathbb {Z}_q[x]/\langle x^n + 1 \rangle$, and each $n$-by-$n$ sub-matrix $A_i$ in $A$ a ring element $\mathbf {a}_i$ in $R_q$. As the (ring-)$\mathsf {LWE}$ and (ring-)$\mathsf {SIS}$ problems have such simple forms, the operations performed in the corresponding cryptosystems are rather efficient.

Due to the algebraic structure of ideal lattices, cryptosystems based on ideal lattices (with security based on the $\text {ring-}\mathsf {LWE}$ or $\text {ring-}\mathsf {SIS}$ assumptions) are more efficient than their counterparts in general lattices: (1) The size of some parameters, which are originally matrices, is reduced by a factor of $n$, as each $n$-by-$n$ sub-matrix is now represented as a ring element; (2) The multiplications of ring elements in $R_q$ can be implemented on hardware by a variant of Fourier transform [3].

Lattice Trapdoors. For more complicated primitives, a “trapdoor” is generated together with a random lattice so that, while it is still hard for the adversary to solve the (ring-)$\mathsf {LWE}$ or (ring-)$\mathsf {SIS}$ problems, the problems become easily solvable with the help of the trapdoor.

Initiated by the work of Gentry et al. [10], a (old-type) trapdoor [10, 11] of (the lattice defined by) a matrix $A$ is a short basis of the lattice $\varLambda ^\perp _q(A)$, which contains all the vectors $\mathbf {x}$ such that $A \mathbf {x} = \mathbf {0} ~ \mathrm{mod} ~ q$. Using the trapdoor, one can sample short vectors $\mathbf {x}$ so that $A \mathbf {x} = \mathbf {u} ~ \mathrm{mod} ~ q$ for any target vector $\mathbf {u}$. Moreover, the owner of the trapdoor of $A$ can “delegate” the trapdoor of an extended matrix $(A,B)$ for any matrix $B$.

Micciancio and Peikert [12] developed a new type of trapdoors for general lattices which is simpler and more efficient to use when compared to the old trapdoors. A new-type trapdoor of $A$ is a matrix $T$ with small norm so that $A \left[ \begin{matrix}T \\ I \end{matrix} \right] = HG$ for some invertible matrix $H$, which is referred as the tag of the trapdoor, and a nicely structured matrix $G$ called the primitive matrix, where the inversions of $\mathsf {SIS}$ (also known as “Gaussian sampling”) and $\mathsf {LWE}$ involving $G$ are easy and efficient.¹ At the high-level sense, $T$ can be considered as a secret transformation from $A$ to $G$ which reduces the originally difficult inversions of $\mathsf {SIS}$ and $\mathsf {LWE}$ involving $A$ to the much easier inversions involving $G$. Notice that the new-type trapdoors have the additional ability to invert $\mathsf {LWE}$, which is not the case for the old-type trapdoors. In addition, the size of the new-type trapdoors is much (at least 4 times) smaller than that of the old-type.

However, despite the increase of efficiency, there is a lack of cryptosystems in ideal lattices that require the use of trapdoors. One possible reason for this is that, the trapdoors introduced by Gentry et al. [10] and improved by Alwen and Peikert [11] are based on general lattices. Stehlé [13] attempted to extend the trapdoor algorithms to ideal lattices, but the result is based on a non-standard ideal-$\mathsf {LWE}$ assumption which, unlike the $\text {ring-}\mathsf {LWE}$ assumption, does not have search-to-decision reduction. Later, Micciancio and Peikert [12] introduced a new notion of lattice trapdoors which have even greater functionality, namely, to invert not only $\mathsf {SIS}$ but also $\mathsf {LWE}$. More importantly, the new trapdoors can be translated to the ring setting, as mentioned in [12] but unfortunately without much details.

Our Contributions. In this work, we extend the trapdoors from Micciancio and Peikert [12] to the ring setting. As a result, the sizes of the “primitive vectors”, the public vectors and trapdoors are reduced by a factor of $n$. As in other recent cryptosystems [2, 3, 14] that are based on $\text {ring-}\mathsf {LWE}$, we work with the “preferred” choice of ring $R := \mathbb {Z}[x] / \langle x^n+1 \rangle$ where $n$ is a power of $2$. For such choice of ring $R$, the general strategy of transforming the trapdoors to the ring setting is to interpret each $n$ by $n$ submatrix in the construction of [12] as a ring element in $R$. By breaking down elements in $R$ in terms of the “power basis” $1,x,x^2,\ldots ,x^{n-1}$, we show that some of the algorithms in [12] can be reused. We also justify the correctness of such transformation carefully by replacing certain theorems and lemmas by those proven in the ring setting.

Finally, we demonstrate the power of the new trapdoors by constructing a new identity-based encryption (IBE) scheme which improves the IBE scheme constructed by Agrawal et al. [8] in three aspects, namely, being ideal-lattice-based, having reduced trapdoor size, and being secure against chosen-ciphertext attack.

2 Preliminary

Notations. Let $\lambda$ be the security parameter. Let $f(x) = f_\lambda (x) \in \mathbb {Z}[x]$ be a polynomial of degree $n = n(\lambda )$. Let $q = q(\lambda ) \in \mathbb {Z}$ be a prime integer, $p = p(\lambda ) \in \mathbb {Z}^*_q$ be relatively prime to $q$. Let $R := \mathbb {Z}[x] / \langle f(x) \rangle$ and $R_q := R/qR$. Let $\chi$ be a distribution over the ring $R$. “$|$” denotes row concatenation of vectors or matrices. If $S$ is a set, then $x \leftarrow S$ denotes the sampling of a uniformly random element $x$ from $S$. If $X$ is a distribution, then $x \leftarrow X$ denotes the sampling of a random element $x$ according to the distribution $X$. If $\mathcal {A}$ is an algorithm, then $x \leftarrow \mathcal {A}$ means that $x$ is the output of the algorithm $\mathcal {A}$. To distinguish between elements, vectors and matrices of $\mathbb {Z}$ and $R$, we follow the notations listed in Table 1. We denote the $k$-by-$k$ identity matrix over $R$ by $\mathbf {I}_k$ and the $k$-by-$l$ zero matrix over $R$ by $\mathbf {0}_{k \times l}$. Without further specifications, $\Vert \mathbf {x}\Vert$ denotes the $L_2$ norm of the vector $\mathbf {x}$ and is extended naturally to $\Vert \mathbf {x}\Vert$ via the coefficient embedding.

Table 1. Notations of elements, vectors and matrices of $\mathbb {Z}$ and $R$

2.1 Lattice Background

Statistical Distance. Let $X$ and $Y$ be two random variables taking values in some finite set $\varOmega$. The statistical distance $\varDelta (X;Y)$ is defined as

$$\begin{aligned} \varDelta (X;Y) := \frac{1}{2} \sum _{s \in \varOmega }|\Pr [X=s]-\Pr [Y=s]|. \end{aligned}$$

We say that the ensembles of random variables $X(\lambda )$ and $Y(\lambda )$ are statistically close if $\varDelta (X;Y)$ is a negligible function in $\lambda$.

Integer Lattices. We consider three types of integer lattices. For an integer modulus $q$, $A \in \mathbb {Z}^{n \times m}_q$ and $u \in \mathbb {Z}^n_q$, define:

$$\begin{aligned} \varLambda _q(A^T)&:= \{\mathbf {x} \in \mathbb {Z}^m : \exists \ \mathbf {s} \in \mathbb {Z}^n_q \ s.t.\ A^T\mathbf {s} = \mathbf {x} ~ \mathrm{mod} ~ q\}\\ \varLambda ^\perp _q(A)&:= \{\mathbf {x} \in \mathbb {Z}^m : A\mathbf {x} = \mathbf {0} ~ \mathrm{mod} ~ q\}\\ \varLambda ^{\mathbf {u}}_q(A)&:= \{\mathbf {x} \in \mathbb {Z}^m : A\mathbf {x} = \mathbf {u} ~ \mathrm{mod} ~ q\} \end{aligned}$$

Note that for any $t \in \varLambda ^{\mathbf {u}}_q(A)$, $\varLambda ^{\mathbf {u}}_q(A) = \varLambda ^{\perp }_q(A) + \mathbf {t}$ is a shift of $\varLambda ^{\perp }_q(A)$.

Ideal Lattices. Correspondingly, we consider three types of ideal lattices. For an integer modulus $q$, $\mathbf {\mathbf {a}} \in R^k_q$ and $\mathbf {u} \in R_q$, define:

$$\begin{aligned} \varLambda _q(\mathbf {\mathbf {a}})&:= \{\mathbf {\mathbf {x}} \in R^k : \exists \ \mathbf {s} \in R_q \ s.t.\ \mathbf {\mathbf {a}}\mathbf {s}=\mathbf {\mathbf {x}} ~ \mathrm{mod} ~ q\}\\ \varLambda ^\perp _q(\mathbf {\mathbf {a}}^T)&:= \{\mathbf {\mathbf {x}} \in R^k : \mathbf {\mathbf {a}}^T\mathbf {\mathbf {x}}=\mathbf {0} ~ \mathrm{mod} ~ q\}\\ \varLambda ^{\mathbf {u}}_q(\mathbf {\mathbf {a}}^T)&:= \{\mathbf {\mathbf {x}} \in R^k : \mathbf {\mathbf {a}}^T\mathbf {\mathbf {x}}=\mathbf {u} ~ \mathrm{mod} ~ q\} \end{aligned}$$

Note that for any $\mathbf {\mathbf {t}} \in \varLambda ^\mathbf {u}_q(\mathbf {\mathbf {a}}^T)$, $\varLambda ^\mathbf {u}_q(\mathbf {\mathbf {a}}^T) = \varLambda ^\perp _q(\mathbf {\mathbf {a}}^T) + \mathbf {\mathbf {t}}$ is a shift of $\varLambda ^\perp _q(\mathbf {\mathbf {a}}^T)$.

Discrete Gaussian. Let $L \subset \mathbb {Z}^n$, $c \in \mathbb {R}^n$, $\sigma \in \mathbb {R}^+$. Define:

$$\begin{aligned} \rho _{\sigma ,c}(x) = \exp (-\pi \frac{\Vert x-c\Vert ^2}{\sigma ^2}) \text { and } \rho _{\sigma ,c}(L) = \sum _{x \in L}\rho _{\sigma ,c}(x). \end{aligned}$$

The discrete Gaussian distribution over $L$ with center $c$ and parameter $\sigma$ is defined as

$$\begin{aligned} \forall x \in L, \mathcal {D}_{L,\sigma ,c}(x) = \frac{\rho _{\sigma ,c}(x)}{\rho _{\sigma ,c}(L)}. \end{aligned}$$

For $c = 0$, denote $\rho _{\sigma ,0}$ as $\rho _\sigma$ and $\mathcal {D}_{L,\sigma ,0}$ as $\mathcal {D}_{L,\sigma }$.

Gram-Schmidt Norm. Let $T = \{t_1,\ldots ,t_k\} \subset \mathbb {R}^m$ be a set of real vectors, and $\Vert T\Vert$ denotes the $L_2$-norm of the longest vector in $T$, i.e., $\Vert T\Vert := \max _{j=1}^k \Vert t_j\Vert$, $\widetilde{T}:=\{\widetilde{t_1},\ldots ,\widetilde{t_k}\}$ denotes the Gram-Schmidt orthogonalization of the vectors $\widetilde{t_1},\ldots ,\widetilde{t_k}$ taken in that order. $\Vert \widetilde{T}\Vert$ is called the Gram-Schmidt norm of $T$.

2.2 Assumptions

The learning with errors ($\mathsf {LWE}$) problem defined by Regev [15] is now a well-studied hard problem that is as hard as some worst-case lattice hard problems such as the shortest vector problem ($\mathsf {SVP}$), via either quantum or classical reductions [15, 16]. An $\mathsf {LWE}$ instance is defined by a matrix $A \in \mathbb {Z}^{n \times m}_q$ and a vector $\mathbf {b} \in \mathbb {Z}^m_q$. The search version of $\mathsf {LWE}$ is to find a secret vector $\mathbf {s} \in \mathbb {Z}^n$ so that $A^T \mathbf {s} + \mathbf {e} = \mathbf {b}$ for some short error vector $\mathbf {e} \in \mathbb {Z}^m$. The decision version is to decide whether such a pair of $(A,\mathbf {b})$ comes from the uniform distribution or the $\mathsf {LWE}$ distribution, i.e. $A^T \mathbf {s} + \mathbf {e} = \mathbf {b}$ for some short error vector $\mathbf {e} \in \mathbb {Z}^m$.

To define $\mathsf {LWE}$ in the ring setting, namely $\text {ring-}\mathsf {LWE}$, $A$ is restricted to have a certain algebraic structure. We interpret the entries in a column of $A$ as the coefficients of a degree-$(n-1)$ polynomial $p(x)$, and require that the vector given by the coefficients of $xp(x) ~ \mathrm{mod} ~ f(x)$, for some degree-$n$ polynomial $f(x)$, is also contained in some column of $A$. Assuming that $m=nk$ for some integer $k$, we can then interpret the $i$-th $n$-by-$n$ sub-matrix of $A$ as a ring element $\mathbf {a}_i$ in $R_q$, the vector $\mathbf {s}$ as $\mathbf {s}$ in $R$, $\mathbf {e}$ as $(\mathbf {e}_1,\ldots ,\mathbf {e}_k)^T$ in $R^k$ and $\mathbf {b}$ as $(\mathbf {b}_1,\ldots ,\mathbf {b}_k)^T$ in $R^k_q$. Multiplications between a sub-matrix of $A$ and the vector $\mathbf {s}$ correspond to the multiplications of the ring elements $\mathbf {a}_i$ and $\mathbf {s}$. Apparently, the search version of $\text {ring-}\mathsf {LWE}$ is then to find $\mathbf {s}$ given $\{\mathbf {a}_i,\mathbf {b}_i = \mathbf {a}_i \mathbf {s} + \mathbf {e}_i\}_{i = 1}^k$. The decision version of $\text {ring-}\mathsf {LWE}$ is to distinguish the distribution of the given samples from the uniform distribution. For the detailed definitions and reductions related to $\text {ring-}\mathsf {LWE}$, we refer to the comprehensive work of Lyubashevsky et al. [3, 14].

In this work, we further restrict the polynomial $f(x)$ such that $f(x) = x^n+1$, which is the preferred choice in recent $\text {ring-}\mathsf {LWE}$-based cryptosystems [2, 3, 14] due to its simplicity. In this case, the $\text {ring-}\mathsf {LWE}$ assumption has a much simpler form. This special case is named as polynomial $\mathsf {LWE}$ ($\mathsf {PLWE}$) by Brakerski and Vaikuntanathan [2].

Definition 1

($\mathsf {PLWE}$ assumption [2]). For all $\lambda \in \mathbb {N}$, $l = \mathsf {poly}(\lambda )$, $\mathbf {a}_i, \mathbf {u} \leftarrow R_q$, $\mathbf {e}_i, \mathbf {s} \leftarrow \chi$, the $\mathsf {PLWE}^{(l)}_{f,q,\chi }$ assumption states that the distribution of $\{(\mathbf {a}_i,\mathbf {a}_i \mathbf {s} + p\mathbf {e}_i)\}_{i=1}^l$ is computationally indistinguishable from the distribution of $\{(\mathbf {a}_i,\mathbf {u}_i)\}_{i=1}^l$.

Theorem 1

[2, Theorem 1]. Let $\lambda$ be the security parameter. Let $k \in \mathbb {N}$ and let $m = 2^{\lfloor \log {\lambda } \rceil }$ be a power of two. Let $\varPhi _m(x) = x^n + 1$ be the $m$-th cyclotomic polynomial of degree $n = \varphi (m) = m/2$. Let $\sigma \ge \omega (\sqrt{\log {n}})$ be a real number, and let $q \equiv 1 \pmod {m}$ be a prime integer. Let $R = \mathbb {Z}[x]= \langle \varPhi _m(x) \rangle$. Then there is a randomized reduction from $(n^2 q/r) \cdot (n(l + 1)/ \log (n(l + 1)))^{1/4}$-approximate R-$\mathsf {SVP}$ to $\mathsf {PLWE}^{(l)}_{\varPhi _m,q,\chi }$ where $\chi = \mathcal {D}_{\mathbb {Z}^n,\sigma }$ is the discrete Gaussian distribution. The reduction runs in time $\mathsf {poly}(n,q,l)$.

3 Primitive Vectors in Ideal Lattices

Although Micciancio and Peikert [12] mentioned that their trapdoors can be extended to ideal lattices, they did not explain it in details. In this section, we first extend their notion of primitive matrices for general lattices to the notion of primitive vectors (of ring elements) for ideal lattices. We will then show in Sect. 4 how to use the primitive vectors to generate trapdoors for ideal lattices. The general strategy used in these sections is to interpret each $n$-by-$n$ submatrices in the notion of trapdoors for general lattices as ring elements in $R_q$.

3.1 Construction of Primitive Vectors

Recall from [12] that a matrix $G\in \mathbb {Z}^{n\times m}_q$ is primitive if its columns generate all of $\mathbb {Z}^n_q$, i.e., $G\cdot \mathbb {Z}^m = \mathbb {Z}^n_q$. For some nicely structured primitive matrices, $\mathsf {LWE}$ inversion and Gaussian sampling can be done efficiently. Given such a primitive matrix, the crux of the trapdoor generation algorithm is to perform a random transform on the primitive matrix.

As mentioned in [12, Sect. 4.3], the primitive vector $\mathbf {\mathbf {g}} = (1,2,\ldots ,2^{k-1})^T$ in $R^k_q$ can be used in the ring setting to replace the previous primitive matrix $G$ by interpreting the values in the ring $R_q$ instead of $\mathbb {Z}_q$. Furthermore, the inversion and Gaussian sampling algorithms can be obtained in the ring setting as well.

Intuitively, to obtain a primitive vector in the ring setting, we need to find a primitive matrix (in the general lattices setting) in which each $n$-by-$n$ sub-matrix is rotational, i.e., a column is obtained by shifting the previous column by one entry and adding a negative sign to the first entry. One way is to permute the columns of the previous primitive matrix $G$ to obtain such a structure. An example of $G$ is as follows [12]:

$$\begin{aligned} G := \begin{bmatrix} \ldots \mathbf {g}^T \ldots&&\\&\ldots \mathbf {g}^T \ldots&\\&\ddots&\\&&\ldots \mathbf {g}^T \ldots \end{bmatrix} \text {, } \mathbf {g}^T = \begin{bmatrix} 1&2&4&\ldots&2^{k-1} \end{bmatrix}\in \mathbb {Z}^{1\times k}_q \end{aligned}$$

We permute columns of $G$ so that identical terms forms $n$-by-$n$ diagonal block matrices. As a result, we obtain:

$$\begin{aligned} G' := [I_n|2I_n|\ldots |2^{k-1}I_n]. \end{aligned}$$

Since $G'$ is obtained by permutation of columns of $G$, $G'$ is still primitive. By the same permutation on the basis $S$ of $\varLambda ^\perp _q(G)$, we obtain the basis $S'$ of $\varLambda ^\perp _q(G')$, where

$$\begin{aligned} S' := \begin{bmatrix} 2 I_n&&&q_0 I_n \\ -I_n&2I_n&&q_1 I_n \\&-I_n&&q_2 I_n \\&&\ddots&\\&&2 I_n&q_{k-2} I_n\\&&-I_n&q_{k-1} I_n \end{bmatrix} \in \mathbb {Z}^{nk\times nk} \text {. } \end{aligned}$$

The matrices $G'$ and $S'$ correspond to the collections of vectors of ring elements $\mathbf {\mathbf {g}} = (1,2,\ldots ,2^{k-1})^T \in R^k_q$ and $(\mathbf {\mathbf {s}}_1,\ldots ,\mathbf {\mathbf {s}}_k) \in R^{k \times k}_q$ respectively, where $\mathbf {\mathbf {s}}_i = (0,\ldots ,0,2,-1,0,\ldots ,0)^T$ for $i < k$, and $\mathbf {\mathbf {s}}_k = (q_0,q_1,\ldots ,q_{k-1})^T$, where $q = \sum _{i=0}^{k-1}2^i q_i$ and $q_i \in \{0,1\}$.

Theorem 2 summarizes the result of primitive vectors in the ring setting, with explanation deferred to the later subsections.

Theorem 2

For any $q = \sum _{i=0}^{k-1}2^i q_i < 2^k$ where $q_i \in \{0,1\}$ and $k\ge 1$, there exists $\mathbf {\mathbf {g}} = (1,2,\ldots ,2^{k-1})^T \in R^k_q$ and $\mathbf {S} = (\mathbf {\mathbf {s}}_1,\ldots ,\mathbf {\mathbf {s}}_k) \in R^{k \times k}_q$ (thus $\mathbf {\mathbf {g}}^T \mathbf {S} = \mathbf {0}_{1 \times k} \in R^k_q$), such that:

• We have $\Vert \tilde{\mathbf {\mathbf {s_i}}}\Vert < \sqrt{5}$ in the coefficient embedding.

• The storage requirement of $\mathbf {\mathbf {g}}$ and $\mathbf {S}$ are further reduced by a factor of $n$ compared to their counterparts in general lattices.

• Inverting $\alpha _{\mathbf {\mathbf {g}}}(\mathbf {z},\mathbf {\mathbf {e}}) := \mathbf {\mathbf {g}}\mathbf {z} + \mathbf {\mathbf {e}} ~ \mathrm{mod} ~ q$ can be performed in quasilinear $O(n \cdot \log ^c n)$ time for any $\mathbf {z} \in R$ and any $\mathbf {\mathbf {e}} \in q \cdot \mathbf {B}^{-T}\cdot [-\frac{1}{2},\frac{1}{2})^{nk}$, where $\mathbf {B}$ can denote either $\mathbf {S}$ or $\tilde{\mathbf {S}}$. Moreover, the algorithm is perfectly parallelizable, running in polylogarithmic $O(\log ^c n)$ time using $n$ processors.

• Preimage sampling for $\beta _{\mathbf {\mathbf {g}}}(\mathbf {\mathbf {x}}) = \mathbf {\mathbf {g}}^T \mathbf {\mathbf {x}} ~ \mathrm{mod} ~ q$ with Gaussian parameter $\sigma \ge \Vert \tilde{\mathbf {S}}\Vert \cdot w(\sqrt{\log n})$ can be performed in quasilinear $O(n \cdot \log ^c n)$ time, or parallel polylogarithmic $O(\log ^c n)$ time using $n$ processors.

3.2 Inversion for Primitive Vectors

Given a $\mathsf {PLWE}$ instance $\mathbf {\mathbf {b}} = \mathbf {\mathbf {g}} \mathbf {z} + \mathbf {\mathbf {e}}$, which is equivalent to $\mathbf {b}_i = 2^i \mathbf {z} + \mathbf {e}_i$ for $i = 0,\ldots ,k-1$, we can expand $\mathbf {b}_i$, $\mathbf {z}$ and $\mathbf {e}_i$ in terms of the power basis $1, x, x^2, \ldots , x^{n-1}$ so that the problem is equivalent to solving $b_{ij} = 2^i z_j + e_{ij}$ independently for $j = 0,\ldots , n-1$, where $\mathbf {b}_i = \sum ^{n-1}_{j=0} b_{ij} x^j$, $\mathbf {z} = \sum ^{n-1}_{j=0} z_{j} x^j$ and $\mathbf {e}_i = \sum ^{n-1}_{j=0} e_{ij} x^j$. Recombining the terms according to $i$, the problem becomes solving $\mathbf {b}_j = \mathbf {g} z + \mathbf {e}_j$ where $\mathbf {g} = (1,2,\ldots ,2^{k-1})^T \in \mathbb {Z}^k_q$. Let $S = (\mathbf {s}_1, \ldots , \mathbf {s}_k)$ be a basis of $\varLambda ^\perp _q(\mathbf {g}^T)$. Then $V = qS^{-T} = (\mathbf {v}_1,\ldots ,\mathbf {v}_k)$ is a basis of $\varLambda _q(\mathbf {g})$. We can then use Babai’s nearest plane algorithm to recover $z \in \mathbb {Z}_q$ from $\mathbf {b} = \mathbf {g} z + \mathbf {e}$:

Algorithm 3

 [17] Babai’s Nearest Plane Algorithm

Input: $\{\mathbf {v}_1, \ldots , \mathbf {v}_k\}$ a basis of $\varLambda _q(\mathbf {g})$, $\mathbf {b}$.

Output: $z$ and $\mathbf {e}$.

• 1. Compute Gram-Schmidt basis $\mathbf {v}_1^*, \ldots , \mathbf {v}^*_{k}$.

• 2. For $j = k \rightarrow 1$:

  • (a) Compute $l_j = <\mathbf {b}_j, \mathbf {v}^*_j> / <\mathbf {v}^*_j, \mathbf {v}^*_j>$.

  • (b) Set $\mathbf {b}_{j-1} = \mathbf {b}_j - (l_j - \lfloor l_j \rceil ) \mathbf {v}^*_j - \lfloor l_j \rceil \mathbf {v}_j$.

• 3. Return $z = \sum _{j=1}^k \lfloor l_j \rceil c_j ~ \mathrm{mod} ~ q$, $\mathbf {e} = \mathbf {b} - \mathbf {g} z$, where $\mathbf {v}_j = c_j \mathbf {g} ~ \mathrm{mod} ~ q$.

3.3 Gaussian Sampling for Primitive Vectors

We first recall that the goal of Gaussian sampling in [12] is to sample a vector from $\varLambda ^{\mathbf {u}}_q(G)$. This can be done by repeating $n$ times of the sampling from $\varLambda ^{u_j}_q(\mathbf {g}^T)$ for a desired syndrome $u_j \in \mathbb {Z}_q$, where $j = 0,\ldots ,n-1$.

For the later task, there are two extreme approaches and one hybrid approach. In the one extreme, we first pre-compute a large set of samples from $\mathcal {D}_{\mathbb {Z}^k,\sigma }$ and bucket them according to the different values of $u$. The sampling algorithm simply draws one sample from the appropriate bucket. This approach requires large storage so that each bucket can be filled with sufficient number of samples. The other extreme exploits the fact that if $q$ is a power of $2$, then we have the orthogonalized basis $\tilde{S}_k = 2I_k$. In this case, there is a simple and efficient way to perform Babai’s nearest plane algorithm [17]. In this algorithm, we first pre-compute two large sets of samples from $\mathcal {D}_{2\mathbb {Z},\sigma }$ and $\mathcal {D}_{2\mathbb {Z}+1,\sigma }$. The sampling algorithm draws each coefficient of $x$ one by one from the appropriate set. This approach requires less storage space but takes $k$ steps to complete. Naturally, there is a hybrid approach that pre-computes samples from $\mathcal {D}_{\mathbb {Z}^l,\sigma }$ for some $l < k$ and fills in the coefficients of $x$ in blocks of $l$.

To perform Gaussian sampling in the ring setting, we can of course use the sampling algorithm for general lattices and perform the permutation mentioned above to the preimage. More formally, recall that our task is to sample a vector of ring elements $\mathbf {\mathbf {x}}$ from $\varLambda ^\mathbf {u}_q(\mathbf {\mathbf {g}}^T)=\{\mathbf {\mathbf {x}} \in R^k: \mathbf {\mathbf {g}}^T \mathbf {\mathbf {x}} = \mathbf {u} ~ \mathrm{mod} ~ q \}$ where $\mathbf {u} \in R_q$. That is, $\sum ^{k-1}_{i=0}2^i \mathbf {x}_i = \mathbf {u}$. By expanding $\mathbf {x}_i$ in the power basis $1,x,x^2,\ldots ,x^{n-1}$, this is equivalent to $\sum ^{k-1}_{i=0}2^i x_{ij} = u_j$ for $j = 0,1,\ldots ,n-1$, where $\mathbf {x}_i = \sum ^{n-1}_{j=0} x_{ij} x^j$ and $u = \sum ^{n-1}_{j=0} u_{j} x^j$. Thus, we can use the same sampling algorithms for each equation $\sum ^{k-1}_{i=0}2^i x_{ij} = u_j$ in the ring setting, since $x_{ij}$ and $u_j$ are integers modulo $q$. However, notice that the reduction of $\text {ring-}\mathsf {LWE}$ in [2, 3, 14] requires that $q = 1 ~ \mathrm{mod} ~ 2n$, which means that $q$ cannot be a power of $2$. Therefore, practically we can only use the first approach for Gaussian sampling in the ring setting.

4 Trapdoors in Ideal Lattices

Analogous to the trapdoors for general lattices defined in [12], we extend the notion to the ring setting. This includes the derivation of old-type trapdoors from Gentry et al. [10] (Sect. 4.1), the generation of (new-type) trapdoors (Sect. 4.2), $\text {ring-}\mathsf {LWE}$ inversion (Sect. 4.3), Gaussian sampling (Sect. 4.4) and trapdoors delegation (Sect. 4.5).

Definition 2

Let $\mathbf {\mathbf {a}} \in R^{l+k}_q$ and $\mathbf {\mathbf {g}} \in R^k_q$. A $\mathbf {\mathbf {g}}$-trapdoor for $\mathbf {\mathbf {a}}$ is a collection of linearly independent vectors of ring elements $\mathbf {R} = (\mathbf {\mathbf {r}}_1,\ldots ,\mathbf {\mathbf {r}}_k) \in R^{l \times k}_q$ such that $\mathbf {\mathbf {a}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \end{bmatrix} = \mathbf {h} \mathbf {\mathbf {g}}^T$, for some non-zero ring element $\mathbf {h} \in R_q$. $\mathbf {h}$ is referred as the $tag$ or $label$ of the trapdoor. The $qulity$ of the trapdoor is measured by its largest singular value $s_1(\mathbf {R})$, which is computed as the largest singular value of the matrix obtained by interpreting $\mathbf {R}$ as a matrix in $\mathbb {Z}^{ln \times kn}_q$.

4.1 Derivation of Old Trapdoors

Lemma 1

Let $\mathbf {\mathbf {g}} \in R^k_q$ and $\mathbf {S} = (\mathbf {\mathbf {s}}_1,\ldots ,\mathbf {\mathbf {s}}_k) \in R^{k \times k}$ be linearly independent with $\mathbf {\mathbf {g}}^T \mathbf {\mathbf {s}}_i = \mathbf {0} \in R_q$ for $i = 1,\ldots ,k$. Let $\mathbf {\mathbf {a}} \in R^{l+k}_q$ have trapdoor $\mathbf {R} = (\mathbf {\mathbf {r}}_1,\ldots ,\mathbf {\mathbf {r}}_k) \in R^{k \times k}$ with tag $\mathbf {h} \in R_q$. Then the lattice $\varLambda ^\perp _q(\mathbf {\mathbf {a}}^T)$ is generated by

$$\begin{aligned} \mathbf {S}_{\mathbf {\mathbf {a}}} = \begin{bmatrix} \mathbf {I}_l&\mathbf {R}\\ \mathbf {0}_{k \times l}&\mathbf {I}_k \end{bmatrix} \begin{bmatrix} \mathbf {I}_l&\mathbf {0}_{l \times k}\\ \mathbf {W}&\mathbf {S} \end{bmatrix}, \end{aligned}$$

where $\mathbf {W} \in R^{k \times l}$ is an arbitrary solution to $\mathbf {\mathbf {g}}^T \mathbf {W} = -\mathbf {h}^{-1}\mathbf {\mathbf {a}}^T \left[ \mathbf {I}_l | \mathbf {0}_{l \times k} \right] ^T ~ \mathrm{mod} ~ q$.

Moreover, the basis $\mathbf {S}_{\mathbf {\mathbf {a}}}$ satisfies $\Vert \widetilde{\mathbf {S}_{\mathbf {\mathbf {a}}}}\Vert \le s_1 \left( \begin{bmatrix} \mathbf {I}_l&\mathbf {R}\\ \mathbf {0}_{k \times l}&\mathbf {I}_k \end{bmatrix} \right) \cdot \Vert \tilde{\mathbf {S}} \Vert \le (s_1(\mathbf {R})+1) \cdot \Vert \tilde{\mathbf {S}} \Vert$, when $\mathbf {S}_{\mathbf {\mathbf {a}}}$ is orthogonalized in suitable order and interpreted as a matrix in $\mathbb {Z}^{[(l+k)n] \times [(l+k)n]}$ by the coefficient embedding.

Proof

Compared to the derivation in general lattices, the non-trivial part is to construct a matrix $\mathbf {W}$ of ring elements, or equivalently, a matrix $W$ consisting of $k \times l$ blocks of $n \times n$ rotational matrices. Otherwise, the rest of the proof follows the proof of [12, Lemma 5.3]. To construct such a matrix $\mathbf {W}$, let $\mathbf {\mathbf {a}}=(\mathbf {a}_1, \mathbf {a}_2, \ldots , \mathbf {a}_{l+k})^T \in R^{l+k}_q$ and let

$$\begin{aligned} \mathbf {W}=\begin{bmatrix} \mathbf {w}_{1,1}&\ldots&\mathbf {w}_{1,l} \\ \vdots&\ddots&\vdots \\ \mathbf {w}_{k,1}&\ldots&\mathbf {w}_{k,l} \end{bmatrix} \end{aligned}$$

where $\mathbf {w}_{i,j} \in R_q$.

Now, $\mathbf {\mathbf {g}}^T \mathbf {W} = -\mathbf {h}^{-1}\mathbf {\mathbf {a}}^T \left[ \mathbf {I}_l | \mathbf {0}_{l \times k} \right] ^T ~ \mathrm{mod} ~ q$ implies

$$\begin{aligned}{}[1|2|\ldots |2^{k-1}]\mathbf {W} = [1|2|\ldots |2^{k-1}] \begin{bmatrix} \mathbf {w}_{1,1}&\ldots&\mathbf {w}_{1,l} \\ \vdots&\ddots&\vdots \\ \mathbf {w}_{k,1}&\ldots&\mathbf {w}_{k,l} \end{bmatrix} = -\mathbf {h}^{-1} \begin{bmatrix} \mathbf {a}_1&\mathbf {a}_2&\ldots&\mathbf {a}_l. \end{bmatrix} \end{aligned}$$

This equation implies that for each $j = 1,\ldots ,l$, we need to independently solve

$$\begin{aligned}{}[1|2|\ldots |2^{k-1}] \begin{bmatrix} \mathbf {w}_{1,j}\\ \vdots \\ \mathbf {w}_{k,j} \end{bmatrix} = -\mathbf {h}^{-1}\mathbf {a}_i \in R_q. \end{aligned}$$

By expanding $\mathbf {w}_{i,j}$ and $\mathbf {a}_j$ with respect to the power basis $1, x, x^2, \ldots , x^{n-1}$, the problem is equivalent to solving the system for each coefficient independently.    $\Box$

Although the derivation of the old-type trapdoors for ideal lattices is merely theoretical, it solves an open problem in [10] which asked how trapdoors can be generated together with random looking ideal lattices.

4.2 Generation of New Trapdoor

As in [12], the derivation of old trapdoors from the new trapdoors is just a proof of concept and will not be used in the rest of this work. In this subsection, we extend their trapdoors for general lattices to our ring version in Algorithm 4.

Algorithm 4

$\mathsf {ringGenTrap}^\mathcal {D}(\mathbf {\mathbf {a}}_0, \mathbf {h})$

Input:

• a vector of ring elements $\mathbf {\mathbf {a}}_0=(\mathbf {a}_1,\ldots ,\mathbf {a}_l)^T\in R^l_q$;

• a non-zero ring element $\mathbf {h} \in R_q$;

• a distribution $\chi ^{l \times k}$ over $R^{l\times k}$. (If no particular $\mathbf {\mathbf {a}}_0$, $\mathbf {h}$ are given as input, then the algorithm may choose them itself, e.g. picking $\mathbf {\mathbf {a}}_0 \leftarrow R^l_q$ uniformly, and setting $\mathbf {h}=1$.)

Output:

• a vector of ring elements $\mathbf {\mathbf {a}} = (\mathbf {\mathbf {a}}^T_0,\mathbf {\mathbf {a}}^T_1)^T \in R^{l+k}_q$;

• a trapdoor $\mathbf {R} = (\mathbf {\mathbf {r}}_1,\ldots ,\mathbf {\mathbf {r}}_k) \in R^{l\times k}$ with tag $\mathbf {h} \in R_q$.

• 1. Choose a collection of linearly independent vectors of ring elements $\mathbf {R} = (\mathbf {\mathbf {r}}_1,\ldots ,\mathbf {\mathbf {r}}_k) \in R^{l \times k}$ from distribution $\chi ^{l \times k}$,

• 2. Output $\mathbf {\mathbf {a}}=(\mathbf {\mathbf {a}}^T_0,\mathbf {h} \mathbf {\mathbf {g}}^T - \mathbf {\mathbf {a}}^T_0 \mathbf {R})^T \in R^{l+k}_q$ and trapdoor $\mathbf {R} \in R^{l\times k}$.

Moreover, the distribution of $\mathbf {\mathbf {a}}$ is close to uniform (either statistically or computationally) as long as the distribution of $(\mathbf {\mathbf {a}}^T_0,-\mathbf {\mathbf {a}}^T_0 \mathbf {R})$ is.

The correctness of Algorithm 4 is immediate. To show that the distribution of $(\mathbf {\mathbf {a}}^T_0,-\mathbf {\mathbf {a}}^T_0 \mathbf {R})$ is close to uniform, we need to show that the distribution of $\mathbf {\mathbf {a}}^T_0 \mathbf {R}$ is close to uniform and hence is independent to that of $\mathbf {\mathbf {a}}_0$, or equivalently the distribution of $\mathbf {\mathbf {a}}^T_0 \mathbf {\mathbf {r}}_i$ is close to uniform and independent to that of $\mathbf {\mathbf {a}}_0$ for all $i$. As for the trapdoors for general lattices, the uniformity of $\mathbf {\mathbf {a}}$ can be instantiated to be either statistical by using a regularity lemma or computational by the $\text {ring-}\mathsf {LWE}$ assumption.

Lemma 2

[3, Sect. 7] (Regularity Lemma) Let $\mathbf {a}_i \leftarrow R_q$ and $\mathbf {r}_i \leftarrow \chi$ for $i = 1,\ldots ,l$. Then $\mathbf {b} = \sum _{i=1}^l \mathbf {a}_i \mathbf {r}_i$ is within $2^{-\varOmega (n)}$ statistical distance to the uniform distribution over $R_q$. Moreover, the case where $l = 2$ corresponds to the normal form of $\text {ring-}\mathsf {LWE}$.

4.3 $\text {ring-}\mathsf {LWE}$ Inversion from New Trapdoors

Given a trapdoor $\mathbf {R}$ for $\mathbf {\mathbf {a}} \in R^{l+k}_q$ and a $\mathsf {PLWE}^{(l)}_{f,q,\chi }$ instance $\mathbf {\mathbf {b}} = \mathbf {\mathbf {a}} \mathbf {s} + \mathbf {\mathbf {e}} ~ \mathrm{mod} ~ q$, the $\text {ring-}\mathsf {LWE}$ inversion algorithm given in Algorithm 5 is to find the solution $\mathbf {s}$ to the instance.

Algorithm 5

$\mathsf {ringInvert}^\mathcal {O}(\mathbf {R}, \mathbf {\mathbf {a}}, \mathbf {\mathbf {b}})$

Input:

• an oracle $\mathcal {O}$ for inverting the function $\alpha _{\mathbf {\mathbf {g}}} (\mathbf {s}', \mathbf {\mathbf {e}}')$ when $\mathbf {\mathbf {e}}' \in R^k$ is suitably small;

• a vector of ring element $\mathbf {\mathbf {a}} \in R^{l+k}_q$;

• $\mathbf {\mathbf {g}}$-trapdoor $\mathbf {R} \in R^{l \times k}$ for $\mathbf {\mathbf {a}}$ with tag $\mathbf {h}$;

• vector $\mathbf {\mathbf {b}} = \mathbf {\mathbf {a}} \mathbf {s} + \mathbf {\mathbf {e}}$ for any $\mathbf {s} \in R_q$ and suitably small $\mathbf {\mathbf {e}} \in R^{l+k}$.

Output: $\mathbf {s}$ and $\mathbf {\mathbf {e}}$.

• 1. Get $(\mathbf {s}', \mathbf {\mathbf {e}}') \leftarrow \mathcal {O}([\mathbf {R}^T|\mathbf {I}_k]\mathbf {\mathbf {b}})$.

• 2. return $\mathbf {s} = \mathbf {h}^{-1} \mathbf {s}'$ and $\mathbf {\mathbf {e}} = \mathbf {\mathbf {b}} - \mathbf {\mathbf {a}} \mathbf {s}$ (interpreted as a vector in $R^{l+k}$ with where each entry has coefficients in $[-\frac{q}{2}, \frac{q}{2})$).

The correctness of Algorithm 5 is indicated by Theorem 6 stated below.

Theorem 6

Suppose that $\mathcal {O}$ in Algorithm 5 correctly inverts $\alpha _{\mathbf {\mathbf {g}}}(\mathbf {s}', \mathbf {\mathbf {e}}')$ for any small error vector $\mathbf {\mathbf {e}}' \in \mathcal {D}_{\mathbb {Z}^n, \sigma \sqrt{l \sigma ^2 \cdot \omega (\log n) + k}} ^k$. Then for any $\mathbf {s} \in R_q$ and $\mathbf {\mathbf {e}} \leftarrow \chi ^{l+k}$, Algorithm 5 correctly inverts $\alpha _{\mathbf {\mathbf {a}}}(\mathbf {s}, \mathbf {\mathbf {e}})$ with overwhelming probability over the choice of $\mathbf {\mathbf {e}}$.

Proof

We first show that $\mathbf {\mathbf {b}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix}$ gives a correct input to the oracle $\mathcal {O}$.

$$\begin{aligned} \mathbf {\mathbf {b}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix}&= (\mathbf {\mathbf {a}}^T \mathbf {s} + \mathbf {\mathbf {e}}^T) \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} \\&= \mathbf {\mathbf {a}}^T \mathbf {s} \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} + \mathbf {\mathbf {e}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} \\&= \mathbf {s} [\mathbf {\mathbf {a}}^T_0 | \mathbf {h} \mathbf {\mathbf {g}}^T - \mathbf {\mathbf {a}}^T_0 \mathbf {R}] \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} + \mathbf {\mathbf {e}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} \\&= \mathbf {s} (\mathbf {\mathbf {a}}^T_0 \mathbf {R} + \mathbf {h} \mathbf {\mathbf {g}}^T - \mathbf {\mathbf {a}}^T_0 \mathbf {R}) + \mathbf {\mathbf {e}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} \\&= \mathbf {\mathbf {g}}^T \mathbf {h} \mathbf {s} + \mathbf {\mathbf {e}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} \\&= \mathbf {\mathbf {g}}^T \mathbf {s}' + \mathbf {\mathbf {e}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix} \end{aligned}$$

Now we need to show that $\mathbf {\mathbf {e}}' = \mathbf {\mathbf {e}}^T \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \\ \end{bmatrix}$ has the appropriate distribution. Consider

$$\begin{aligned} \mathbf {e}'_j = \sum _{i=1}^{l} \mathbf {e}_i \mathbf {r}_{ij} + \sum _{i=l+1}^{l+k} \mathbf {e}_i \ \ \ \ \forall j = 1, \ldots , k \end{aligned}$$

where $\mathbf {e}'_j = j$-th component of $\mathbf {\mathbf {e}}'$, $\mathbf {e}_i = i$-th component of $\mathbf {\mathbf {e}}$, $\mathbf {r}_{ij} = ij$-th component of $\mathbf {R}$. Since each entry of $\mathbf {\mathbf {e}}$ and $\mathbf {R}$ are sampled from $\chi = \mathcal {D}_{\mathbb {Z}^n, \sigma }$, then the distribution of $\mathbf {e}_i \mathbf {r}_{ij}$ is statistically close to $\mathcal {D}_{\mathbb {Z}^n, \sigma ^2 \cdot \omega (\sqrt{\log n})}$ [3, Lemma 8.7]. Hence, the distribution of $\mathbf {e}'_j$ is statistically close to $\mathcal {D}_{\mathbb {Z}^n, \sigma \sqrt{l \sigma ^2 \cdot \omega (\log n) + k}}$ [3, Lemma 8.6]. Therefore, the distribution of $\mathbf {\mathbf {e}}'$ has the correct distribution.    $\Box$

4.4 Gaussian Sampling from New Trapdoors

Given a trapdoor $\mathbf {R}$ for $\mathbf {\mathbf {a}} \in R^{l+k}_q$ and $\mathbf {u} = \beta _{\mathbf {\mathbf {a}}}(\mathbf {\mathbf {x}}) = \mathbf {\mathbf {a}}^T \mathbf {\mathbf {x}} ~ \mathrm{mod} ~ q$, the Gaussian Sampling algorithm given in Algorithm 7 is to find the solution $\mathbf {\mathbf {x}}$ to the instance.

Algorithm 7

$\mathsf {ringSampleD}^\mathcal {O}(\mathbf {R},\mathbf {\mathbf {a}}_0,\mathbf {h},\mathbf {u},\sigma )$

Input:

Offline phase:

• an oracle $\mathcal {O}(\mathbf {v})$ for Gaussian sampling over a desired coset $\varLambda ^{\mathbf {v}}_q(\mathbf {\mathbf {g}}^T)$ with parameter $\sigma$, where $\mathbf {v} \in R_q$;

• a vector of ring elements $\mathbf {\mathbf {a}}_0 \in R^l_q$;

• a trapdoor $\mathbf {R} \in \ R^{l \times k}$;

• a Gaussian parameter $\sigma$.

Online phase:

• a non-zero tag $\mathbf {h} \in R_q$ defining $\mathbf {\mathbf {a}} = (\mathbf {\mathbf {a}}^T_0, \mathbf {h} \mathbf {\mathbf {g}}^T- \mathbf {\mathbf {a}}^T_0 \mathbf {R})^T \in R^{l+k}_q$ ($\mathbf {h}$ may instead be provided in the offline phase, if it is known);

• syndrome $\mathbf {u} \in R_q$.

Output: A vector $\mathbf {\mathbf {x}}$ drawn from a distribution statistically close to $\mathcal {D}_{\varLambda ^\mathbf {v}_q(\mathbf {\mathbf {a}}_0^T),\sigma '}$ for some Gaussian parameter $\sigma '$.

Offline phase:

• 1. Choose fresh perturbations $\mathbf {\mathbf {p}}_1\leftarrow \chi _1^l$ and $\mathbf {\mathbf {p}}_2\leftarrow \chi _2^k$ for some distributions $\chi _1$ and $\chi _2$ over $R$.

• 2. Compute $\mathbf {w}_0= \mathbf {\mathbf {a}}^T_0 (\mathbf {\mathbf {p}}_1 - \mathbf {R}\mathbf {\mathbf {p}}_2) \in R_q$ and $\mathbf {w}_1 = \mathbf {\mathbf {g}}^T \mathbf {\mathbf {p}}_2 \in R_q$.

Online phase:

• 1. Let $\mathbf {v} \leftarrow \mathbf {h}^{-1}(\mathbf {u}-\mathbf {w}_0) - \mathbf {w}_1 = \mathbf {h}^{-1} (\mathbf {u}- \mathbf {\mathbf {a}}^T\mathbf {\mathbf {p}} )\in R_q$, and choose $\mathbf {\mathbf {z}} \leftarrow \mathcal {D}_{\varLambda ^\mathbf {v}_q(\mathbf {\mathbf {g}}^T),\sigma }$ by calling $\mathcal {O}(\mathbf {v})$.

• 2. Return $\mathbf {\mathbf {x}} \leftarrow \begin{bmatrix} \mathbf {\mathbf {p}}_1 \\ \mathbf {\mathbf {p}}_2 \end{bmatrix} + \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \end{bmatrix} \mathbf {\mathbf {z}}$.

Theorem 8

Algorithm 7 is correct.

Proof

Let $\mathbf {\mathbf {x}} \leftarrow \mathsf {ringSampleD}^\mathcal {O}(\mathbf {R},\mathbf {\mathbf {a}}_0,\mathbf {h},\mathbf {u},\sigma )$. Then

$$\begin{aligned} \mathbf {\mathbf {a}}^T \mathbf {\mathbf {x}}&= [\mathbf {\mathbf {a}}^T_0| \mathbf {h} \mathbf {\mathbf {g}}^T- \mathbf {\mathbf {a}}^T_0 \mathbf {R}] \left( \begin{bmatrix} \mathbf {\mathbf {p}}_1 \\ \mathbf {\mathbf {p}}_2 \end{bmatrix} + \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \end{bmatrix} \mathbf {\mathbf {z}} \right) \\&= \mathbf {\mathbf {a}}^T_0 \mathbf {\mathbf {p}}_1 + \mathbf {\mathbf {a}}^T_0 \mathbf {R} \mathbf {\mathbf {z}} + \mathbf {h} \mathbf {\mathbf {g}}^T \mathbf {\mathbf {p}}_2 - \mathbf {\mathbf {a}}^T_0 \mathbf {R} \mathbf {\mathbf {p}}_2 + \mathbf {h} \mathbf {\mathbf {g}}^T \mathbf {\mathbf {z}} - \mathbf {\mathbf {a}}^T_0 \mathbf {R} \mathbf {\mathbf {z}} \\&= \mathbf {\mathbf {a}}^T_0 (\mathbf {\mathbf {p}}_1 - \mathbf {R} \mathbf {\mathbf {p}}_2) + \mathbf {h} \mathbf {\mathbf {g}}^T \mathbf {\mathbf {p}}_2 + \mathbf {h} \mathbf {v} \\&= \mathbf {w}_0 + \mathbf {h} \mathbf {w}_1 + \mathbf {u}-\mathbf {w}_0 - \mathbf {h}\mathbf {w}_1 \\&= \mathbf {u} \end{aligned}$$

Now, consider $\mathbf {\mathbf {x}} = \begin{bmatrix} \mathbf {\mathbf {p}}_1 \\ \mathbf {\mathbf {p}}_2 \end{bmatrix} + \begin{bmatrix} \mathbf {R} \\ \mathbf {I}_k \end{bmatrix} \mathbf {\mathbf {z}}$. Since each entry of $\mathbf {R}$ and $\mathbf {\mathbf {z}}$ are sampled from $\chi = \mathcal {D}_{\mathbb {Z}^n,\sigma }$, and each entry of $\mathbf {\mathbf {p}}_1$ and $\mathbf {\mathbf {p}}_2$ are sampled from $\chi _1 = \mathcal {D}_{\mathbb {Z}^n,\sigma ^2 \cdot \omega \sqrt{\log n}}$ and $\chi _2 = \mathcal {D}_{\mathbb {Z}^n,\sigma \sqrt{\sigma ^2 (k+1) \cdot \omega (\log n) - 1}}$, respectively, then the distributions of all entries of $\mathbf {\mathbf {x}}$ are statistically close to $\chi ' = \mathcal {D}_{\mathbb {Z}^n,\sigma '}$, where $\sigma ' = \sigma ^2 \sqrt{k+1} \cdot \omega (\sqrt{\log {n}})$. [3, Lemma 8.6 & 8.7].    $\Box$

4.5 Trapdoors Delegation

Using the trapdoor of $\mathbf {\mathbf {a}}$, there is an efficient trapdoor delegation algorithm given in Algorithm 9 that generates a trapdoor for the vector $(\mathbf {\mathbf {a}}^T,\mathbf {\mathbf {a}}^T_1)^T$.

Algorithm 9

$\mathsf {ringDelTrap}^\mathcal {O}(\mathbf {\mathbf {a}}'=(\mathbf {\mathbf {a}}^T,\mathbf {\mathbf {a}}^T_1)^T,\mathbf {h}',\sigma )$

Input:

• an oracle $\mathcal {O}$ for discrete Gaussian sampling over cosets of $\varLambda _q^\perp (\mathbf {\mathbf {a}}^T)$ with parameter $\sigma '$;

• a vector of ring elements $\mathbf {\mathbf {a}}'=(\mathbf {\mathbf {a}}^T,\mathbf {\mathbf {a}}^T_1)^T \in R^{m+k}_q$;

• a non-zero ring element $\mathbf {h}' \in R_q$.

Output: a trapdoor $\mathbf {R} \in R^{(m+k) \times k}$ for $\mathbf {\mathbf {a}}'$ with tag $\mathbf {h}'$.

• Using $\mathcal {O}$, sample each column of $\mathbf {R}$ independently from a discrete Gaussian with parameter $\sigma '$ over the appropriate cosets of $\varLambda _q^\perp (\mathbf {\mathbf {a}}^T)$, so that $\mathbf {\mathbf {a}}^T \mathbf {R} = \mathbf {h}' \mathbf {\mathbf {g}}^T - \mathbf {\mathbf {a}}^T_1$.

5 INDr-ID-CCA-Secure (H)IBE in Ideal Lattices

5.1 Identity-Based Encryption

Identity-based encryption (IBE) is a generalization of public-key encryption [18]. In an IBE, to encrypt a message to an identity $id$, the encrypter does not need to lookup the public key for the intended identity $id$. Instead, the encryption algorithm simply takes the public parameters, the identity $id$ and the message as input and outputs a ciphertext encrypting the message to $id$. The identity $id$ obtains its secret key derived from the master secret key through the key generation algorithm for decrypting all ciphertexts encrypted to $id$. Formally, the syntax of IBE is defined as follows.

Definition. An identity-based encryption (IBE) scheme consists of four PPT algorithms $(\mathsf {Setup},$ $\mathsf {Extract},$ $\mathsf {Encrypt},$ $\mathsf {Decrypt})$. The $\mathsf {Setup}$ algorithm outputs a public parameter $PP$ and a master key $MK$. Using $MK$, the $\mathsf {Extract}$ algorithm extracts a secret key $SK_{id}$ for an identity $id$. Unlike public-key encryption, the $\mathsf {Encrypt}$ algorithm in IBE can encrypt messages directly to an identity $id$. The user with identity $id$ uses her secret key $SK_{id}$ to $\mathsf {Decrypt}$ a ciphertext.

Hierarchical identity-based encryption (HIBE) is an extension of IBE such that an identity $ID = [id_1|\ldots |id_d]$ is a hierarchy of identities with depth $d$. There is an additional algorithm $\mathsf {Derive}$ that inputs a secret key $SK_{[id_1|\ldots |id_{j-1}]}$ in the $(j-1)$-th level and an identity $ID = [id_1|\ldots |id_j]$ in the $j$-th level and outputs the secret key $SK_{ID}$ for identity $ID$.

Security. In addition to the (adaptive) chosen-plaintext-attack (CPA(2)) security or (adaptive) chosen-ciphertext-attack (CCA(2)) security as in public-key encryption, an (H)IBE scheme should also be secure against chosen-identity-attack (ID). A weaker security model called selective-identity-attack (sID) is also considered, where the adversary must choose the identity she is going to perform CPA(2) or CCA(2) before receiving the public parameter. The indistinguishability (IND) of ciphertexts under the combinations of attacks in the two sets of variants give us eight security model, namely, IND-ID-CCA(2), IND-sID-CCA(2), IND-ID-CPA(2) and IND-sID-CPA(2). In [8], a stronger security guarantee in which the ciphertexts are indistinguishable from random (INDr) elements in the ciphertext space is considered. This implies both semantic security (of the plaintext) and recipient anonymity.

From now on, we will focus on the INDr-ID-CCA security, which is modeled as a security game between a PPT simulator and a PPT adversary. In this game, the simulator first generates the public parameters $PP$ and passes them to the adversary. The adversary is then granted the rights to query the secret keys $SK_{id}$ for polynomially many identities $id$ of its choice, and the rights to query the decryption of any ciphertext of its choice. After that, the adversary issues a challenge message to be encrypted to the identity $id^*$, whose secret key has never been queried before. The simulator replies by either encrypting the challenge message to $id^*$ or generating a uniformly random ciphertext. The adversary wins the game if it can guess which among two ways the ciphertext is generated.

An INDr-ID-CCA2-secure HIBE of depth $d$ can be obtained by combining an INDr-ID-CPA-secure HIBE of depth $d+1$ and a strong one-time signature scheme [19]. The rough idea is to encrypt the message to the “identity” $[id_1|id_2|\ldots |id_d|vk]$ where $vk$ is the verification key of the one-time signature, and sign the ciphertext using the one-time signature. In particular, from IBE, we obtain a CCA2-secure public-key encryption scheme. We will omit the details here.

Applications. Most earlier (H)IBE schemes are realized by pairings. Readers can refer to [20, 21] for reviews of those. Agrawal et al. proposed a lattice-based (H)IBE scheme in the standard model [8]. The ciphertext of their scheme can be proven to be a random element in the ciphertext space, which implies receipt anonymity against user attacks. An anonymous IBE can be used to obtain a public-key searchable encryption scheme [22]. By applying Naor’s transformation [18], we can also obtain a signature scheme from an IBE scheme.

5.2 Construction

Using the trapdoors for ideal lattices developed above, the CCA-secure public-key encryption provided in [12] and the INDr-ID-CPA-secure (H)IBE scheme in [8], we construct an INDr-ID-CCA-secure (H)IBE in ideal lattices. We only present the basic IBE scheme below, because the HIBE scheme can be obtained trivially by defining the $\mathsf {Derive}$ algorithm of HIBE to be the same as the $\mathsf {Extract}$ algorithm of the basic IBE in our case.

The basic IBE scheme is constructed as follows:

• $\mathsf {Setup}(1^\lambda )$

  • Sample $\mathbf {\mathbf {a}}_{-1} \leftarrow R^l_q$, $\mathbf {\mathbf {a}}_0,\mathbf {\mathbf {a}}_1,\ldots ,\mathbf {\mathbf {a}}_t \leftarrow R^k_q$ and $\mathbf {h} \leftarrow R_q\setminus \{0\}$.

  • Sample $(\mathbf {\mathbf {a}}, \mathbf {R}_{MK}) \leftarrow \mathsf {ringGenTrap}^\mathcal {D}(\mathbf {\mathbf {a}}_{-1}, \mathbf {h})$.

  • Output $PP = (\mathbf {\mathbf {a}},\mathbf {\mathbf {a}}_0,\mathbf {\mathbf {a}}_1,\ldots ,\mathbf {\mathbf {a}}_t)$ and $MK = (\mathbf {h},\mathbf {R}_{MK})$.

• $\mathsf {Extract}(PP,MK,id)$

  • Sample $\mathbf {h}_{id} \leftarrow R_q$.

  • Set $\mathbf {\mathbf {a}}_{id} = \mathbf {\mathbf {a}}_0 + \sum ^t_{i=1} id_i \mathbf {\mathbf {a}}_i$ and $\mathbf {\mathbf {f}}_{id,\mathbf {h}_{id}} = (\mathbf {\mathbf {a}}^T, \mathbf {\mathbf {a}}^T_{id})^T$.

  • Sample $\mathbf {R}_{id} \leftarrow \mathsf {ringDelTrap}^\mathcal {O}(\mathbf {\mathbf {f}}_{id,\mathbf {h}_{id}},\mathbf {h}_{id},\sigma )$.

  • Output $SK_{id} = (\mathbf {h}_{id},\mathbf {R}_{id})$.

• $\mathsf {Encrypt}(PP,id,\mathbf {\mathbf {m}} \in R^k_p)$

  • Sample $\mathbf {h}' \leftarrow R_q$.

  • Set $\mathbf {\mathbf {a}}_{id,\mathbf {h}'} = \mathbf {\mathbf {a}}_{id} + \mathbf {h}' \mathbf {\mathbf {g}}$.

  • Sample $\mathbf {s} \leftarrow \chi$, $\mathbf {\mathbf {e}}_0 \leftarrow \chi ^{l+k}$ and $\mathbf {R}_i \leftarrow \chi ^{l \times k}$ for $i = 0,1,\ldots ,t$.

  • Set $\mathbf {R} = \mathbf {R}_0 + \sum _{i=1}^t id_i \mathbf {R}_i$.

  • Set $\mathbf {\mathbf {e}}_1^T = -\mathbf {\mathbf {e}}_0^T \mathbf {R}$.

  • Compute $\mathbf {\mathbf {u}} = \mathbf {\mathbf {a}}_0 \mathbf {s} + p \mathbf {\mathbf {e}}_0$ and $\mathbf {\mathbf {v}} = \mathbf {\mathbf {a}}_{id,\mathbf {h}'} \mathbf {s} + p \mathbf {\mathbf {e}}_1 + \mathbf {\mathbf {m}}$.

  • Output $CT = (\mathbf {h}',\mathbf {\mathbf {u}},\mathbf {\mathbf {v}})$.

• $\mathsf {Decrypt}(PP,SK_{id},CT)$

  • Output $\perp$ if $\mathbf {h}' = -\mathbf {h}_{id}$.

  • Set $\mathbf {\mathbf {f}}_{id,(\mathbf {h}_{id} + \mathbf {h}')} = (\mathbf {\mathbf {a}}^T , \mathbf {\mathbf {a}}^T_{id} + \mathbf {h}' \mathbf {\mathbf {g}}^T)^T = (\mathbf {\mathbf {a}}^T , (\mathbf {h}_{id} + \mathbf {h}')\mathbf {\mathbf {g}}^T - \mathbf {\mathbf {a}}^T \mathbf {R}_{id})^T$.

  • Compute $(\mathbf {s},\mathbf {\mathbf {e}}) \leftarrow \mathsf {ringInvert}^\mathcal {O}(\mathbf {R}_{id},\mathbf {\mathbf {f}}_{id,(\mathbf {h}_{id} + \mathbf {h}')},(\mathbf {\mathbf {u}}^T, \mathbf {\mathbf {v}}^T)^T)$.

  • Compute $(\mathbf {0}_{1 \times k},\mathbf {\mathbf {m}}^T)^T = \mathbf {\mathbf {e}} ~ \mathrm{mod} ~ p$.

  • Output $\mathbf {\mathbf {m}}$.

Theorem 10

By the $\mathsf {PLWE}_{f,q,\chi }^{(l)}$ assumption, the (H)IBE scheme stated above is INDr-ID-CCA-secure.

Proof

The simulation strategy is a result of combining those from [8, 12]. The simulator is given a $\mathsf {PLWE}$ instance $(\mathbf {\mathbf {a}},\mathbf {\mathbf {b}})$. It chooses the rest of the public parameters $\mathbf {\mathbf {a}}_0,\ldots ,\mathbf {\mathbf {a}}_t$ as follows:

• It samples $\mathbf {h}^* \leftarrow R_q$.

• It samples $\mathbf {R}_i \leftarrow \chi ^{l \times k}$ and let $\mathbf {\mathbf {a}}^T_i = \mathbf {h}_i \mathbf {\mathbf {g}}^T - \mathbf {\mathbf {a}}^T \mathbf {R}_i$, where $\mathbf {h}_0 = 1 - \mathbf {h}^*$ and $\mathbf {h}_i \leftarrow R_q$, for $i = 0,\ldots , t$.

Since the distribution of $\mathbf {\mathbf {a}}$ is uniform and each entry of $\mathbf {R}_i$ is sampled from the distribution $\chi$, by the regularity lemma (Lemma 2), the distribution of $\mathbf {\mathbf {a}}_i$ is also uniform for all $i$.

To answer the queries for secret key of $id$, it simply returns $(\mathbf {h}_{id},\mathbf {R}_{id})$ where $\mathbf {h}_{id} = 1 + \sum _{i=1}^t id_i \mathbf {h}_i - \mathbf {h}^*$ and $\mathbf {R}_{id} = \mathbf {R}_0 + \sum _{i=1}^t id_i \mathbf {R}_i$. Note that $\mathbf {\mathbf {a}}^T_{id} = \mathbf {\mathbf {a}}^T_0 + \sum ^t_{i=1} id_i \mathbf {\mathbf {a}}^T_i = \mathbf {h}_{id} \mathbf {\mathbf {g}}^T - \mathbf {\mathbf {a}}^T \mathbf {R}_{id}.$

It answers the decryption queries $(id,CT = (\mathbf {h},\mathbf {\mathbf {u}},\mathbf {\mathbf {v}}))$ using the tag $\mathbf {h}_{id}$, the trapdoor $\mathbf {R}_{id}$ and the $\mathsf {Decrypt}$ algorithm. As long as $\mathbf {h} \ne \mathbf {h}^*$ or $-\mathbf {h}_{id} \ne \mathbf {h}^*$, the simulator can still simulate faithfully. Since $\mathbf {\mathbf {a}}_i$ is uniformly random in the view of the adversary, $\mathbf {h}^*$ and $\mathbf {h}_i$ are all hidden from the adversary for all $i = 0,1,\ldots ,t$. Therefore the event $-\mathbf {h}_{id} = \mathbf {h} = \mathbf {h}^*$ only happens with negligible probability.

Finally, the challenge ciphertext for $(id^*,\mathbf {\mathbf {m}}^*)$ is generated as $(\mathbf {h}^*,\mathbf {\mathbf {u}}^*,\mathbf {\mathbf {v}}^*)$ where $\mathbf {\mathbf {u}}^* = \mathbf {\mathbf {b}}$ and $\mathbf {\mathbf {v}}^* = (-\mathbf {\mathbf {b}}^T \mathbf {R}_{id^*} + \mathbf {\mathbf {m}}^{*T})^T$.

Suppose that the $(\mathbf {\mathbf {a}},\mathbf {\mathbf {b}})$ given in the $\mathsf {PLWE}$ instance is uniform, then the distribution of the challenge ciphertext $(\mathbf {h}^*,\mathbf {\mathbf {u}}^*,\mathbf {\mathbf {v}}^*)$ is also uniform. Otherwise, suppose $\mathbf {\mathbf {b}} = \mathbf {\mathbf {a}} \mathbf {s} + p\mathbf {\mathbf {e}}$ for some $\mathbf {s}$ and $\mathbf {\mathbf {e}}$ sampled from the appropriate distributions, then

$$\begin{aligned} \mathbf {\mathbf {v}}^{*T}&= -\mathbf {\mathbf {b}}^T \mathbf {R}_{id^*} + \mathbf {\mathbf {m}}^{*T} \\&= -\mathbf {s} \mathbf {\mathbf {a}}^T \mathbf {R}_{id^*} - p \mathbf {\mathbf {e}}^T \mathbf {R}_{id^*} + \mathbf {\mathbf {m}}^{*T} \\&= \mathbf {s} (\mathbf {\mathbf {a}}^T_{id^*} - \mathbf {h}_{id^*} \mathbf {\mathbf {g}}^T ) - p \mathbf {\mathbf {e}}^T \mathbf {R}_{id^*} + \mathbf {\mathbf {m}}^{*T} \end{aligned}$$

By [8, Lemma 24], we have $\mathbf {h}_{id^*} = -\mathbf {h}^*$ with non-negligible probability. In such case, we have

$$\begin{aligned} \mathbf {\mathbf {v}}^{*T}&= \mathbf {s} (\mathbf {\mathbf {a}}^T_{id^*} + \mathbf {h}^* \mathbf {\mathbf {g}}^T) - p \mathbf {\mathbf {e}}^T \mathbf {R}_{id^*} + \mathbf {\mathbf {m}}^{*T} \end{aligned}$$

which is distributed identically as valid ciphertexts do.    $\Box$

6 Concluding Remarks

We detailed how to generate trapdoors for ideal lattices. We then use it to construct a new (H)IBE scheme. Our scheme has several improvement over that constructed by Agrawal et al. [8]:

• Our scheme is based on ideal lattices, therefore the size of the public parameters, master key and the identity secret key are reduced by a factor of $n$.

• Using the new trapdoor delegation algorithm, the size of the identity secret key grows linearly, rather than quadratically, in the depth of the hierarchy.

• Our scheme is secure against chosen-chiphertext-attack.