1 Introduction
Multilinear maps are very powerful tools in cryptography. Following their use in constructing two interesting applications: a one-round non-interactive multiparty key exchange protocol and a broadcast encryption scheme with short keys [
7], multilinear maps have yielded many remarkable cryptographic applications. However, without the realization of multilinear maps, the promising applications would have been only ambiguous implementations. As a first breakthrough in the generation of multilinear maps, Garg, Gentry, and Halevi introduced the concept of graded encoding schemes as a variant of multilinear maps and described a candidate approximate construction (GGH13) using ideal lattices. Shortly after this, Coron, Lepoint, and Tibouchi [
15] proposed another potential graded encoding scheme (CLT13) over integers. These graded encoding schemes expanded their applications such as general-purpose obfuscation, functional encryption, and others [
1,
3,
5,
6,
22,
24‐
26,
30,
36,
37].
The security of the applications based on the graded encoding schemes relies on the presumed hardness of the problems such as the graded decision Diffie–Hellman (GDDH), subgroup membership (SubM), decision linear (DLIN), and graded external-decision Diffie–Hellman (GXDH) problems. However, it was showed that when instantiated in the GGH13 scheme with some distinct encodings termed as low-level encodings of zero, the SubM, DLIN, and GXDH problems could be solved in polynomial time by the so-called
zeroizing attack [
20, Sec. 6] (also called the weak discrete logarithm attack). Subsequently, this approach became potentially more powerful: Hu and Jia extended it and proved that the GDDH problem could also be solved in polynomial time [
28].
In contrast, the CLT13 scheme was not apparently susceptible to the zeroizing attack. It was believed that the problems, including SubM, DLIN, GXDH, and GDDH, were hard problems in the CLT13 scheme. Thus, the CLT13 scheme is considered as the only candidate for implementing applications that require the presumed hardness of the problems as the security basis. Such applications include key-homomorphic pseudorandom functions and a one-round group password-based authenticated key exchange [
1,
3,
5,
6,
15,
22,
30,
36]: The widespread use of the CLT13 scheme has raised concerns about its security because its presumed hardness has not been proven for standard assumptions.
Our Contributions In this paper, we describe a polynomial time cryptanalysis of the CLT13 scheme. This algorithm employs low-level encodings of zero. Our algorithm is applicable until such encodings of zero are used for the “rerandomization procedure” in the CLT13 scheme. We then show that this algorithm allows the recovery of all the secret parameters. Using these secret parameters, we can eventually solve the SubM, DLIN, GXDH, and GDDH problems.
Apart from an indirect attack, we also provide polynomial time algorithms for analyzing three related problems in the CLT13 scheme: the SubM, DLIN, and GXDH problems. Although these polynomial time algorithms are not as efficient as the previous ones because of their computational complexity, they are of significance in that they can be directly applied to the problems.
Consequently, there is no direct construction of secure multilinear maps, for which any of the GDDH, SubM, DLIN, and GXDH problems are hard.
1 Several cryptographic applications are impacted,e.g., all the constructions of [
3,
22,
30,
36], GPAKE construction in [
1] for more than three users, one of the two constructions of password hashing in [
5], and one of the key-homomorphic PRF constructions in [
6].
Technical Overview We describe two independent methods for solving the problems associated with the CLT13 scheme. The first method allows for determining all the secret elements of the CLT13 scheme, and the second one solves each problem directly. We name these two techniques as the eigenvalue technique and determinant technique, respectively, because the main part of each algorithm is the computation of the eigenvalues and determinants, respectively.
Let \(p_i\) be the secret distinct primes for \(1\le i\le n\), and \(x_0\) equal \(\prod _{i=1}^n p_i\). We denote \({\hat{p}}_i=x_0/p_i\) for each i and \({\hat{P}}=\sum _{i=1}^n {\hat{p}}_i\). For integer vector \(\mathbf {r}=(r_i)\in {\mathbb {Z}}^n\) with \(r_i \ll p_i\), a Chinese remainder encoding of \(\mathbf {r}\) (referred as CRT-encoding) is defined as an integer, denoted by \(\mathsf{CRT}_{(p_i)} (r_i)\in (x_0/2, x_0/2]\). This is congruent to integer \(r_i\) in each modulo \(p_i\). Informally, the setting of the CLT13 scheme is reduced to the following problem: when we are given \(x_0\), \({\hat{P}}\), and polynomially many CRT-encodings of the integer vectors, recover all the secret primes.
In [
19], Galbraith, Gebregiyorgis, and Murphy introduced a CRT-approximate greatest common divisor problem (
CRT-ACD) problem. Herein, when given a multiple of
\(x_0\), written as
\(x_0\cdot q_0\), and variants of CRT-encodings,
\(x_0\cdot q_j + \mathsf{CRT}_{(p_i)} (r_{ij}),\) for polynomially many
\(j\ge 1\), find the secret primes, for which integers
\(q_j\) are sampled from some distribution. Compared to the
CRT-ACD problem, we consider
\(q_0=1\) and
\(q_j=0\) for all
\(j\ge 1\). In addition, integer
\({\hat{P}}\) is given. Therefore, we call this problem as
CRT-ACD with an auxiliary input.
(1) Eigenvalue Technique Our main technique is to construct a diagonalizable matrix in \({\mathbb {Q}}\) whose eigenvalues are \(r_{i}\) for some CRT-encoding, \(\mathsf{CRT}_{(p_i)}(r_{i})\). Then, by computing the greatest common divisor (gcd) between \(x_0\) and \((\mathsf{CRT}_{(p_i)}(r_{i}) - r_{i})\), we recover \(p_i\).
More precisely, under the condition that the magnitude of
\(r_{i}\) is sufficiently small, we observe that
$$\begin{aligned}{}[{\hat{P}} \cdot \mathsf{CRT}_{(p_i)} (r_{i})]_{x_0}= & {} \sum _{i=1}^{n} {r_{i}} \cdot {{\hat{p}}}_i . \end{aligned}$$
The equality holds over integers. According to the Chinese remainder theorem, the product of the CRT-encodings yields a CRT-encoding in which the corresponding message vectors are multiplied componentwise. Therefore, we can extend the observation to the product of the CRT-encodings until each component of the message vector is much smaller than
\(p_i\).
For several CRT-encodings
\(\mathsf{CRT}_{(p_i)} (r_{i,j})\), let
\(w_{j,k}\) and
\(w_{j,k}'\) be integers
\([\mathsf{CRT}_{(p_i)} (r_{i,j}) \cdot \mathsf{CRT}_{(p_i)} (r_{i,1})\cdot \mathsf{CRT}_{(p_i)} (r_{i,k}) \cdot {\hat{P}}]_{x_0}\) and
\([\mathsf{CRT}_{(p_i)} (r_{i,j}) \cdot \mathsf{CRT}_{(p_i)} (r_{i,k}) \cdot {\hat{P}}]_{x_0}\), respectively. Then, by spanning indices
\(j, k\in \{1,\ldots ,n\}\), we can construct matrices
\(\mathbf{W}=(w_{j,k})_{j,k}\) and
\(\mathbf{W}'=(w'_{j,k})_{j,k}\), which can be written as
$$\begin{aligned} \mathbf{W} = \mathbf{R} \cdot \mathsf{diag}(r_{i,1})\cdot \mathbf{R}'~~~~\text {and}~~~~\mathbf{W}' = \mathbf{R} \cdot \mathbf{R}' \end{aligned}$$
for
\(\mathbf{R}=(r_{i,j})_{i,j}\),
\(\mathbf{R}'=({\hat{p}}_i\cdot r_{i,k})_{i,k}^T\) and diagonal matrix
\(\mathsf{diag}(r_{i,1})\), whose
i-th diagonal entry is
\(r_{i,1}\). By assuming that matrices
\(\mathbf{R}\) and
\(\mathbf{R}'\) are invertible, we obtain matrix
\(\mathbf{Y}\) in the following form:
$$\begin{aligned} \mathbf{Y} =\mathbf{W} \cdot (\mathbf{W}')^{-1}=\mathbf{R} \cdot \mathsf{diag}(r_{i,1}) \cdot (\mathbf{R})^{-1}, \end{aligned}$$
whose eigenvalues are exactly the set, {
\(r_{1,1}, \ldots , r_{n,1}\)}. Hence, we can compute the eigenvalues in polynomial time from
\(\mathbf Y\). As mentioned above, by computing
\(\gcd (x_0, \mathsf{CRT}_{(p_i)}(r_{i,1})-r_{i,1})\), we can recover secret prime
\(p_i\) for each
i. We refer to Sect.
3 for the application of this strategy in the CLT13 scheme.
(2) Determinant Technique For the SubM, DLIN, and GXDH problems, the determinant technique could be directly used to analyze the problems instead of performing the eigenvalue-based analysis. For example, we consider a simplified SubM problem: given two CRT-encodings \(A=\mathsf{CRT}_{(p_i)} (r_i )\) and \(B=\mathsf{CRT}_{(p_i)} ( r_{i}')\), where \(r_i\) and \(r_i'\) are \(\rho \)-bit integers much smaller than \(p_i\). We need to distinguish whether \(r_i\) and \(r_i'\) are co-prime for all i.
Given two CRT-encodings \(A=\mathsf{CRT}_{(p_i)} (r_i )\) and \(B=\mathsf{CRT}_{(p_i)} ( r'_{i})\), our goal is to construct two matrices over \({\mathbb {Z}}\) whose determinants are multiples of \(\prod _{i=1}^n r_i\) and \(\prod _{i=1}^n r_i'\), respectively. Then, one can solve this problem by computing the gcd.
More precisely, in the construction of
\(\mathbf{W}\), we can build two matrices
\(\mathbf{W}_A\) and
\(\mathbf{W}_B\) by replacing
\(\mathsf{CRT}_{(p_i)} (r_{i,1})\) with
A and
B, respectively. Therefore, the determinants of these matrices are
\(\det (\mathbf{W}_A)=\det (\mathbf{R})\cdot \det (\mathbf{R}')\cdot \prod _{i=1}^n r_i\) and
\(\det (\mathbf{W}_B)=\det (\mathbf{R})\cdot \det (\mathbf{R}')\cdot \prod _{i=1}^n r'_i\), respectively. Next, we consider the value of
\(\det (\mathbf{W}_A) / \gcd ( \mathbf{W}_A,~\mathbf{W}_B)\). If
\(r_i\) and
\(r'_i\) have a common factor for all
i, then this term is smaller than
\(2^{n\cdot (\rho -1)}\). Otherwise, this value is not smaller than
\(2^{n\cdot (\rho -1)}\), and thus, we can solve the simplified SubM problem. This method can also be applied to the DLIN and GXDH problems. We refer to Sect.
4 for more details.
Related and Follow-up Works After the preliminary investigations of this work were published in the IACR Cryptology ePrint Archive and the proceedings of the Eurocrypt’15 conference, the attack was extended and the CLT13 scheme was transformed to prevent the attack. Our attack strongly relies on the fact that the low-level encodings of 0 are published. In [
8], Boneh, Wu, and Zimmerman first extended our attack without giving the encoding of 0. Moreover, they described a modification of the CLT13 scheme to prevent the extended attack. Additionally, an independent approach to immunize the CLT13 scheme against our attack was proposed by Garg, Gentry, Halevi, and Zhandry [
23].
2 Since then, Coron
et al. [
13] have extended the attack by using the so-called
orthogonal encodings. This work showed that the two immunizations were insecure. Apart from these immunization works, a further modification of CLT13 was proposed by Coron, Lepoint, and Tibouchi in Crypto’15 [
17]. They claimed that our attack and the extended attack were prevented because the modified scheme maintained underlying modulus
\(x_0\) a secret, such that the zero-testing procedure depended on the secret values nonlinearly. However, it was also shown to be insecure by Cheon, Fouque, Lee, Minaud, and Ryu in [
10], who demonstrated the recovery of
\(x_0\).
Nonetheless, for the security of the general-purpose obfuscation schemes in the CLT13 scheme, one of the promising applications still remains an open problem because the schemes are neither given the encodings of zero nor are subjected to the extended attacks. Thereafter, Coron, Lepoint, and Tibouchi provided a new analysis result [
14] that could enable one to break the polynomial time for several CLT13-based candidate obfuscations with a distinct property called input partitionability in the CLT13 scheme [
2,
4,
21,
32,
33]. However, this property of input partitionability is not typically satisfied. It was also suggested to convert any input-partitionable obfuscation scheme in the CLT13 scheme to a non-input-partitionable scheme [
18]. In summary, the security of the general obfuscations in the CLT13 scheme has not yet been clarified.
Notation. We use \(a\leftarrow A\) to denote the operation of uniformly choosing element a from finite set A. We define \([n] = \{1,2,\ldots ,n\}\). We let \({\mathbb {Z}}_q\) denote ring \({\mathbb {Z}}/(q{\mathbb {Z}})\). For pairwise co-prime integers \(p_1,p_2,\ldots ,p_n\) and integers \(r_1,r_2,\ldots ,r_n\), we define \(\mathsf{CRT}_{(p_1,p_2,\ldots ,p_n)}(r_1,r_2,\ldots ,r_n)\) (abbreviated as \(\mathsf{CRT}_{(p_i)} (r_i)\)) as the unique integer in \(\left( -\frac{1}{2} \prod _{i=1}^n p_{i},\frac{1}{2}\prod _{i=1}^n p_{i}\right] \) which is congruent to \(r_i \mod p_i\) for all \(i\in [n]\). We use notation \([t]_p\) for integers t and p to denote the reduction of t modulo p in the interval \((-p/2,p/2]\).
We use lower-case bold letters to denote the vectors, whereas we use the upper-case bold letters to denote matrices. For matrix \(\mathbf{S}\), we denote the transpose of \(\mathbf{S}\) by \({\mathbf{S}}^T\). We define \(\Vert {\mathbf{S}}\Vert _{\infty } = \max _i \sum _{j \in [n]} |s_{ij}| \), where \(s_{ij}\) is the (i, j) component of \(\mathbf{S}\). Finally, we denote \(\mathsf{diag}(a_1,\ldots ,a_n)\) or \(\mathsf{diag}(a_i)\) in the diagonal matrix with diagonal coefficients equal to \(a_1,\ldots ,a_n\).
Organization In Sect.
2, we define the
CRT-ACD problem and its analysis. In Sect.
3, we recall the CLT13 scheme and adapt the analysis to it. In Sect.
4, we introduce three related problems on the CLT13 scheme and their cryptanalyses. We conclude this paper in Sect.
5.
2 CRT-ACD with an Auxiliary Input
In this section, we introduce and analyze the CRT-ACD problem using an auxiliary input. The approximate greatest common divisor problem (ACD) was initially introduced by Howgrave-Graham [
27] as was the problem of finding secret prime
p given many near-multiples of
p. One of the promising applications of this problem is a homomorphic encryption scheme [
35]. The scheme offers conceptual simplicity compared to other homomorphic encryption schemes based on lattice problems.
The ACD problem is naturally extended by using multiple primes rather than a single one. Galbraith, Gebregiyorgis, and Murphy provided an informal definition of an extended ACD problem, which is called the
CRT-ACD problem [
19]. An instance of the problem is an integer of the form
\(p_i q_i + r_i\) for several primes
\(p_i\). Therefore, it can be defined by using the CRT. Cheon
et al. provided a batch-homomorphic encryption [
9] based on the
CRT-ACD problem. For appropriate parameters, Galbraith
et al. argued that “it is an open problem to give an algorithm to solve the CRT-ACD problem that exploits the CRT structure” [
19].
In this section, however, we show that when some integer, called the auxiliary input, is given, the CRT-ACD problem can be solved in polynomial time. Now, we define the precise variant of the CRT-ACD we consider.
Auxiliary input \({\hat{P}}\) needs the distinct feature that it can be written as a summation of its CRT components in \(\mathbb Z_{x_0}\). A key observation is that the equation holds over the integers when \(n+\log n < \eta -1\). Extending this property, we obtain the following lemma.
This lemma transforms the modulus equation to an integer equation of \(r_1,\ldots , r_n\) with unknown coefficients \({{\hat{p}}}_1, \ldots , {{\hat{p}}}_n\).
Our algorithm for solving CRT-ACD with an auxiliary input consists of two steps. The first step is to construct a diagonalizable matrix in \({\mathbb {Q}}\), whose eigenvalues are set \(\{r_{i}\}\) of some CRT-ACD sample \(\mathsf{CRT}_{(p_i)}(r_{i})\). The next step is to recover \(r_i\) by computing the eigenvalues. Then, by computing the common divisor of \(\mathsf{CRT}_{(p_i)}(r_{i}) - r_{i}\) and \(x_0\), we can obtain all \(p_i\).
We now describe the complete details of solving CRT-ACD with an auxiliary input.
2.1 Constructing Matrix Equations in \({\mathbb {Q}}\)
Suppose we are given
\(2n+1\) samples from distribution
\({\mathcal {D}}_{\chi _\varepsilon , \eta }(p_1,\ldots ,p_n)\) as follows:
$$\begin{aligned} a_j = \textsf {CRT}_{(p_i)}(a_{i,j}), b = \textsf {CRT}_{(p_i)}(b_i), c_k=\textsf {CRT}_{(p_i)}(c_{i,k}) \text { for } 1 \le j, k \le n. \end{aligned}$$
For simplicity, we denote
\(w_{j,k}\) and
\(w_{j,k}'\) by
\(a_j \cdot b\cdot c_k \mod x_0\) and
\(a_j\cdot c_k \mod x_0\), respectively.
To adapt Lemma
1 to
\(w_{j,k}\) and
\(w_{j,k}'\) under the condition
\(3\varepsilon + n+\log {n} + 1 < \eta \), we have
$$\begin{aligned} w_{j,k}= & {} \sum _{i=1}^{n} a_{i,j} \cdot b_i \hat{p_i} \cdot c_{i,k} = \begin{pmatrix} a_{1, j}&a_{2, j}&\cdots&a_{n, j} \end{pmatrix} \begin{pmatrix} b_1 \hat{p}_1&{} 0 &{} \cdots &{} 0 \\ 0 &{} b_2 \hat{p}_2&{} \cdots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \cdots &{} b_n \hat{p}_n\\ \end{pmatrix} \begin{pmatrix} c_{1,k}\\ c_{2,k}\\ \vdots \\ c_{n,k}\\ \end{pmatrix}\\ w'_{j,k}= & {} \sum _{i=1}^{n} a_{i,j}\cdot \hat{p_i}\cdot c_{i,k} = \begin{pmatrix} a_{1, j}&a_{2, j}&\cdots&a_{n, j} \end{pmatrix} \begin{pmatrix} \hat{p}_1&{} 0 &{} \cdots &{} 0 \\ 0 &{} \hat{p}_2&{} \cdots &{} 0 \\ 0 &{} 0 &{} \ddots &{} 0 \\ 0 &{} 0 &{} \cdots &{} \hat{p}_n\\ \end{pmatrix} \begin{pmatrix} c_{1,k}\\ c_{2,k}\\ \vdots \\ c_{n,k}\\ \end{pmatrix} \end{aligned}$$
By collecting these values, we can construct two matrices
\(\mathbf{W} = (w_{j,k})\) and
\(\mathbf{W}' = (w'_{j,k})\in {\mathbb {Z}}^{n \times n}\), which can be written as
$$\begin{aligned} \mathbf{W}= & {} \mathbf{A}^T \cdot \textsf {diag}(b_1\hat{p}_1,\ldots ,b_n\hat{p}_n) \cdot \mathbf{C},\\ \mathbf{W}'= & {} \mathbf{A}^T \cdot \textsf {diag}(\hat{p}_1,\ldots ,\hat{p}_n) \cdot \mathbf{C} \end{aligned}$$
for
\(\mathbf{A}^T=(a_{i,j})\) and
\(\mathbf{C}=(c_{i,k}) \in {\mathbb {Z}}^{n \times n}\). Suppose matrices
\(\mathbf{A}\) and
\(\mathbf{C}\) are invertible in
\({\mathbb {Q}}\). We compute
\((\mathbf{W}')^{-1}\) over
\(\mathbb {Q}\) and the following matrix:
$$\begin{aligned} \mathbf{V} =\mathbf{W} \cdot (\mathbf{W}')^{-1} =\mathbf{A}^T \cdot \textsf {diag}(b_1,\ldots ,b_n) \cdot (\mathbf{A}^T)^{-1}. \end{aligned}$$
2.2 Disclosing all the Secret Quantities
The eigenvalues of matrix
\(\mathbf V\) discussed in Sect.
2.1 are exactly those in
\(B=\{ b_1, \ldots , b_n\}\). Set
B can be computed in polynomial time in
\(\eta ,n,\) and
\(\varepsilon \) from
\(\mathbf V\) by computing the roots of the characteristic polynomial.
Prime \(p_i\) is a common factor to both \((b - b_i)\) and \(x_0\), which have other common factors if and only if \(b_j = b_i\) for some \(j \in \{1,\ldots ,n\}\). Hence, if \(b_i\)s are distinct, we can obtain all secret integers \(p_1,\ldots ,p_n\).
Remark Two conditions are required for our algorithm to work appropriately. The first is that matrices
\(\mathbf A\) and
\(\mathbf C\) are invertible, and the other is that
\(b_i \ne b_j\) for all
\( 1\le i< j\le n\). The probability that each condition is satisfied depends on distribution
\(\chi _\varepsilon \) and matrix size
n. Because the two conditions are independent and as they depend on different variables, our attack succeeds in obtaining the probability of the product of the two probabilities. For example, let
\(\chi _\varepsilon \) be a uniform distribution in
\((-2^\varepsilon ,2^\varepsilon )\), and let
n be asymptotically a polynomial of
\(\varepsilon \), i.e.,
\(n=poly(\varepsilon )\). The first probability is overwhelming with respect to
\(\varepsilon \) [
31, Lem. 1], whereas the second probability is equal to
\(\frac{n!\cdot \left( {\begin{array}{c}2\cdot 2^\varepsilon -1\\ n\end{array}}\right) }{{(2\cdot 2^\varepsilon -1)}^n}\), where ! is the factorial operator and
\(\left( {\begin{array}{c}2\cdot 2^\varepsilon +1\\ n\end{array}}\right) \) is the binomial coefficient. The latter probability is also overwhelming with respect to
\(\varepsilon \), where
\(n=poly(\varepsilon )\).
Let
\(f_\mathbf{V}\) be a characteristic polynomial of matrix
\(\mathbf{V}\). Because each root
\(b_i\) is less than
\(2^\rho \), we consider prime
\(p_0\) that is larger than
\(2^\rho \) and find roots
x such that
\(f_\mathbf{V}(x) \bmod p_0\). This reveals the original roots of
\(f_\mathbf{V}\) in
\(O(M(n(\rho +\log n))\cdot (\rho +\log n)\cdot \log n) = \widetilde{{\mathcal {O}}} (n\cdot \rho ^2)\) by Rabin’s algorithm [
34], where
M(
t) is an upper bound to the number of bit operations required to multiply two
t-bit numbers.
Because our attack consists of a matrix multiplication, computing a characteristic polynomial and finding the roots of the polynomial, the complexity of the first two algorithms is bounded by
\(\widetilde{{\mathcal {O}}} (n^{\omega }\cdot \log x_0)=\widetilde{{\mathcal {O}}} (n^{\omega }\cdot n\cdot \eta )\) and that of the last one is bounded by
\(\widetilde{{\mathcal {O}}} (n\cdot \rho ^2)\) with
\(\omega \le 2.38\). This implies that the overall cost is bounded by
\( \widetilde{{\mathcal {O}}} (n^{\omega +1}\cdot \eta )\), with
\(\omega \le 2.38\).
3 Hence, we obtain the following result:
4 Subgroup Membership, Decision Linear, and Graded External Diffie–Hellman Problems
We start by defining the SubM, DLIN, and GXDH problems associated with the CLT13 scheme. We then describe how to solve these problems in polynomial time. The attack procedure consists of two steps. First, in Sect.
4.1, we discuss how to recover
\(\prod _i g_i\), which is an order of the message space. This is a common procedure for solving the SubM and DLIN problems. Next, in Sects.
4.2,
4.3 and
4.4, we present the value for solving the SubM, DLIN, and GXDH problems.
We recall primes
\(\{g_i\}\) described in Sect.
3.1. Let
\(G = {\mathbb {Z}}_{g_1} \times \ldots \times {\mathbb {Z}}_{g_n}\) and its subgroup
\(G' = \{0\} \times {\mathbb {Z}}_{g_2}\times \ldots \times {\mathbb {Z}}_{g_n}\). We let
\(\mathsf{enc}_1(m)\) denote a level-1 encoding of
\( m=(m_1,\ldots ,m_n) \in G\) generated by the procedure in Sect.
3.1. Then, it can be written as
\(\mathsf{CRT}_{(p_i)}(\frac{r_i\cdot g_i + m_i}{z})\) for some integer
\(r_i\). For integers
\(L>0\), we let
\(\mathsf{Rk}_j(G^{L\times L})\) denote the set of
\(L\times L\) matrices over
G of rank
j. Here, we define rank of matrix
\((m^{(u,v)})_{u,v}\in G^{L\times L}\) as the maximum of the ranks of matrices
\((m_i^{(u,v)})_{u,v}\), where
\(m_i^{(u,v)}\) is the
i-th entry of
\(m^{(u,v)}\in G\). Then, the SubM and DLIN problems are defined as follows.
In the constructions in [
1], the authors considered the following particular case of the
L-DLIN problem. The problem was defined for
\(\mathsf{params}\) and
\(\mathbf{p}_{zt}\) as well as
\(\{\mathsf{enc}_1(a_i)\}_{i \in [L]}\) and
\(\{\mathsf{enc}_1(a_i b_i)\}_{i \in [L]}\) for some uniform and independent
\(a_1, \ldots , a_L, b_1, \ldots , b_L \in G\). Given an encoding of
\(\mathsf{enc}_1(m)\), the goal was to distinguish whether
m was uniformly sampled from
G or
\(m = b_1 + \ldots + b_{L}\). This can be restated as a distinct case of Definition
3, as it requests to assess whether the matrix below is full rank.
$$\begin{aligned} \begin{pmatrix} {a_1b_1}&{}{a_1}&{}0&{}\ldots &{}0\\ {a_2b_2}&{}0&{}{a_2}&{}\ldots &{}0\\ &{}\vdots &{}&{}&{}\\ {a_Lb_L}&{}0&{}0&{}\ldots &{}{a_L}\\ {m}&{}1&{}1&{}\ldots &{}1 \end{pmatrix} \end{aligned}$$
Next, to describe the GXDH problem, we briefly recall the asymmetric multilinear map variant of CLT13 [
26, App. B.3].
Instance generation
. The parameter settings of
\(p_i, g_i\),
\(x_0, \{x'_j\},\) and
H are as in the original scheme. Let
\(\mathbf{\Pi }^{(t)}=(\pi _{ij}^{(t)})_{i,j} \in {\mathbb {Z}}^{n \times n}\) with
\(\pi ^{(t)}_{ij}\)\(\leftarrow \)\((n2^{\rho },(n+1)2^{\rho }) \cap \mathbb {Z}\) if
\(i=j\), otherwise
\(\pi ^{(t)}_{ij}\)\(\leftarrow \)\((-2^{\rho },2^{\rho }) \cap \mathbb {Z}\) for
\(t\in [\kappa ]\). For
\(1 \le t \le \kappa \),
\(z_t\) is uniformly sampled in
\({\mathbb {Z}}_{x_0}\). Then define, for all
\(1 \le t \le \kappa \):
$$\begin{aligned} y^{(t)}= & {} \mathsf{CRT}_{(p_i)}\left( \dfrac{r^{(t)}_{i}\cdot g_i + 1}{z_t}\right) , \text { where } r^{(t)}_{i} \leftarrow (-2^{\rho },2^{\rho }) \cap \mathbb {Z}, \text { for } 1 \le i \le n, \\ x^{(t)}_j= & {} \mathsf{CRT}_{(p_i)}\left( \dfrac{r^{(t)}_{ij}\cdot g_i }{z_t}\right) , \text { for } 1 \le j \le \tau ,\\ \Pi _j^{(t)}= & {} \mathsf{CRT}_{(p_i)}\left( \dfrac{\pi ^{(t)}_{ij} \cdot g_i }{z}\right) \text { for } j \in [n]. \end{aligned}$$
Further, we define:
$$\begin{aligned} (\mathbf{p}_{zt})_j=\sum \limits _{i=1}^{n} h_{ij} \cdot \left( \prod _{1 \le t \le \kappa } z_t \cdot g_i^{-1} \bmod p_i \right) \cdot {\hat{p}}_{i} \bmod x_0, \text { for } 1 \le j \le n. \end{aligned}$$
Output
\(\textsf {params}=(n,\eta , \alpha , \rho , \beta , \tau , \ell , \nu , \lbrace y^{(t)} \rbrace , \lbrace x^{(t)}_j \rbrace , \lbrace x'_j \rbrace , \lbrace \Pi ^{(t)}_j \rbrace , s)\) and
\(\mathbf{p}_{zt}\). From now on, we use
\( \mathsf{enc}_{t}(m)\) to denote encoding
\(\mathsf{CRT}_{(p_i)} (\frac{r_i\cdot g_i+m_i}{z_t})\). We now define the GXDH problem in the CLT13 scheme.
This can be regarded as a variant of the 2-DLIN problems by distinguishing the following distributions:
$$\begin{aligned} \left\{ \begin{pmatrix} \mathsf{enc}_t(c)&{} \mathsf{enc}_t(a) \\ \mathsf{enc}_t(b)&{} \mathsf{enc}_t(1) \end{pmatrix}\right\} \ \text { and~ } \ \left\{ \begin{pmatrix} \mathsf{enc}_t(ab)&{} \mathsf{enc}_t(a) \\ \mathsf{enc}_t(b)&{} \mathsf{enc}_t(1) \end{pmatrix}\right\} , \text {where~}{c \leftarrow G}. \end{aligned}$$
Throughout this section, as in Sect.
3.2, we only use one zero-testing parameter; we denote
\((\mathbf{p}_{zt})_1\) as
\({p}_{zt}\).
Our main strategy to solve the three related problems in the CLT13 scheme is as follows: For a given level-1 encoding \(\mathsf{enc}_1(m)= \mathsf{CRT}_{(p_i)}(r_i\cdot g_i + m_i)\) (or \(\mathsf{enc}_t(m)\) of the asymmetric multilinear map), we first suggest an approach for constructing integral matrix \(\mathbf{W}_m\in {\mathbb {Z}}^{n\times n} \), such that \(\mathbf{W}_m = \mathbf{X} \cdot \mathsf{diag}(r_1\cdot g_1+m_1,\ldots ,r_n\cdot g_n+m_n)\cdot \mathbf{R}\) for some invertible matrices \(\mathbf{X}\) and \(\mathbf{R}\in {\mathbb {Z}}^{n\times n}\). Then, by using matrix \(\mathbf{W}_m\), we construct a matrix whose determinant is related to an order of the message space, \(\prod _i g_i\). Hence, by computing the determinant of the matrix, we can solve each problem.
More precisely, the related problems can be seen as follows:
-
SubM: Given encoding \(\mathsf{enc}_1(m)\), it is determined whether \(m \leftarrow G'\) or not.
-
L-DLIN: Given \(L\times L\) matrix of level-1 encodings of \(({m}^{(i,j)})_{i,j}\), we determine whether the message matrix is of full rank or not.
-
GXDH: Given a \(2\times 2\) matrix of level-1 encodings of \(\begin{pmatrix} c &{} a \\ b &{} 1 \\ \end{pmatrix}\), we determine whether the matrix is of full rank or not.
In the case of the SubM problem, if
m is sampled from
\(G'\), the value of
\(\det (\mathbf{W}_m)\) has a non-trivial factor of
\(\prod g_i\). Otherwise, the value does not have a common factor. In the case of the L-DLIN problem, the determinant of
\((\mathbf{W}_{m^{(i,j)}})_{i,j}\) is a multiple of
\(\prod _i g_i\) if middle term matrix
\(\mathbf{M}\) does not have a full rank. In other cases, the determinant of
\(\mathbf{M}\) is not a multiple of
\(\prod _i g_i\) with a high probability. In the case of the GXDH problem, we can apply the same argument as for the DLIN problem. Hence, if one can recover the
\(\prod \limits g_i\), one can solve the related problems.
Remark. The important difference between the cryptanalysis of these related problems and that of the CLT13 scheme is the form of the middle matrix of
\(\mathbf{W}\). The previous attack discussed in Sect.
3.2 is based on the fact that the middle matrix is diagonal. For example, in [
8], the authors chose the middle matrix as a block diagonal matrix.
6 However, the attack on the related problems in this section does not depend on it.
4.1 Computing \(\prod _i g_i\) from the CLT13 Instances
Here, we are given
\(\mathsf{params}\) and one zero-testing parameter
\({p}_{zt}\), as described in Sect.
3.1. Let us consider
\(w_{uv}{:=}\left[ \Pi _u\cdot y\cdot \Pi _v \cdot y^{\kappa -3} \cdot {p}_{zt}\right] _{x_0}\),
\(w_{uv}^{(i)}{:=}\left[ \Pi _u\cdot \Pi _i\cdot \Pi _v^{} \cdot y^{\kappa -3} \cdot {p}_{zt}\right] _{x_0}\), where
\(\Pi _j = \mathsf{CRT}_{(p_i)}(\pi _{ij}\cdot g_i/z)\), and
\(y = \mathsf{CRT}_{(p_i)}((r_i\cdot g_i+1)/z)\). Our concept of obtaining
\(\prod _i g_i\) is that determinant of matrix
\((w_{uv}^{(i)})_{u,v}\) is typically a multiple of
\({\prod _i g_i}\). To this end, we deal with the following matrices.
$$\begin{aligned} \mathbf{W}_y= & {} (w_{uv})_{u,v}=\mathbf{\Pi }^T \cdot \mathsf{diag}(r_1\cdot g_1 +1, \ldots , r_n\cdot g_n + 1) \cdot \mathbf{\Pi '}.\\ \mathbf{W}_i= & {} (w_{uv}^{(i)})_{u,v}=\mathbf{\Pi }^T \cdot \mathsf{diag}(\pi _{i1}\cdot g_1 , \ldots , \pi _{in}\cdot g_n) \cdot \mathbf{\Pi '}, \end{aligned}$$
where
\(\mathbf{\Pi }=(\pi _{ij})_{i,j}\),
\(\mathbf{\Pi }'=(h_i\cdot g_i \cdot (r_i\cdot g_i +1)^{\kappa -3}\cdot \pi _{ik})_{i,k}\). Because
\(\mathbf{W}_y\) is not a multiple of
\(\prod _i g_i\), we can obtain multiple
\(\prod _i g_i\) by taking a ratio of the gcd’s of the determinants of The appropriate subsets of
\(\{\mathbf{W}_1,\ldots , \mathbf{W}_\tau , \mathbf{W}_y\}\):
$$\begin{aligned}&\dfrac{\gcd (\det \mathbf{W}_1,\ldots ,\det \mathbf{W}_n)}{\gcd (\det \mathbf{W}_1,\ldots ,\det \mathbf{W}_n, \det \mathbf{W}_y)}\\&\quad = \dfrac{ \gcd (\prod _i \pi _{i1}, \ldots ,\prod _i {\pi _{i\tau } } )}{ \gcd (\prod _i {\pi _{i1} g_i},\ldots , \prod _i {\pi _{i\tau } g_i}, \prod _i (r_i g_i+1) )} \cdot \prod _i g_i \\&\quad = \Delta \cdot \prod _i g_i, \end{aligned}$$
for some integer
\(\Delta \). We expect that
\(\Delta \) consists of only small factors because it is a common divisor of many random variables. Based on the setting, variables
\(\prod _i r_{ij}\) are the products of
\(r_{ij}\) sampled from each uniform distribution. Here, we assume that the probability that a multiple of
p is sampled according to a uniform distribution is
\(\le 1/p\). Under this assumption, integer
\(\Delta \) is (2
n-)smooth (i.e., all its divisors are
\(\le 2n\)) with probability
\(\ge 0.9\), as we explain below. More general results can be found in [
12].
By Lemma
2, integer
\(\Delta \) is (2
n)-smooth with probability
\(>0.9\). We eliminate it by exhaustive division by all the integers, i.e.,
\(\le 2n\). This costs
\(\widetilde{\mathcal {O}}(n\log x_0)=\widetilde{\mathcal {O}}(\kappa ^3\lambda ^5)\) bit operations. This is dominated by the cost of the operations described in Sect.
3.2, which is
\(\widetilde{\mathcal {O}}(\kappa ^{\omega +2} \lambda ^{2\omega +3})\).
4.2 Solving the SubM Problem Over the CLT13
We explain how to solve the SubM problem using the result of the previous section. As mentioned in Sect.
4.1, we consider
\(w_{u,v}=\left[ \Pi _u\cdot \mathsf{enc}_1 (m)\cdot \Pi _v \cdot y^{\kappa -3} \cdot \mathbf{p}_{zt}\right] _{x_0}\) and a matrix
\(\mathbf{W}=(w_{u,v})_{u,v}\), where
\(\mathsf{enc}_1 (m)\) is a level-1 encoding,
\([\mathsf{CRT}_{(p_i)}(r_i\cdot g_i' + m_i)/z]_{x_0}\), which we need to distinguish. Then, matrix
\(\mathbf{W}\) can be written as
$$\begin{aligned} \mathbf{W} = \mathbf{\Pi }^T \cdot \mathsf{diag}(r_1 \cdot g_1' + m_1, \ldots , r_n \cdot g_n' + m_n) \cdot \mathbf{\Pi '}, \end{aligned}$$
where
\(\mathbf{\Pi }^T=(\pi _{ij})_{i,j}\),
\(\mathbf{\Pi }'=(h_i\cdot g_i\cdot (r_i\cdot g_i +1)^{\kappa -3}\cdot r_{ik})_{i,k}\). The attack only consists of computing
\(\gcd (\det \mathbf{W}, \prod _i g_i)\).
If m is uniformly sampled in G, then we expect the probability that \(m_i\) is zero for some i is at most \(n / 2^{\alpha }\), where \(\alpha \) is \(\log (g_i)\). Hence, in that case, we have \(\alpha n / 2^{\alpha }\) as an expected value of \(\log (\gcd (\det \mathbf{W}, \prod _i g_i))\). For the original setting of \(\alpha = \lambda \), this is negligible.
If m is uniformly sampled in \(G'\), then \(m_1\) is zero, and we expect the probability that the others are zero is \((n-1)/2^{\alpha }\). Hence, in that case, we have \(\log (\gcd (\det \mathbf{W}, \prod _i g_i)) \approx \alpha + \alpha (n-|I|) / 2^{\alpha }\), which is at least larger than \(\alpha -1\). Hence, this value is distinguished from the previous one.
4.3 Solving the DLIN Problem in CLT13
As we have seen, we assume that
\(\prod _i g_i\) is known. In the DLIN problem, we are given a matrix of level-1 encodings
\(\mathbf{E} = (\mathsf{enc}_1(m^{(i,j)}))_{i,j}\) for
\(1\le i,j\le L\). We write
\(\mathsf{enc}_1(m^{(i,j)}) = \mathsf{CRT}(\frac{r^{(i,j)}_{k}\cdot g_{k}+m_k^{(i,j)}}{ z})\). Using the same method as above, we compute matrices
\(\mathbf{W}_{{i,j}}=\mathbf{X'} \cdot \mathsf{diag}(r^{(i,j)}_1 \cdot g_1 + m^{(i,j)}_1, \ldots , r^{(i,j)}_n \cdot g_n + m^{(i,j)}_n) \cdot \mathbf{\Pi '} \in {\mathbb {Z}}^{n \times n}\) for all
\(1\le i,j\le L\). We define
$$\begin{aligned} \mathbf{W}=\begin{pmatrix} \mathbf{W}_{{11}} &{} \mathbf{W}_{{12}} &{} \ldots &{} \mathbf{W}_{{1L}}\\ \mathbf{W}_{{21}} &{} \mathbf{W}_{{22}} &{} \ldots &{} \mathbf{W}_{{2L}}\\ \vdots &{}&{}\ddots \\ \mathbf{W}_{{L1}} &{} \mathbf{W}_{{L2}} &{} \ldots &{} \mathbf{W}_{{LL}} \end{pmatrix}~~\in \mathbb {Z}^{nL\times nL}. \end{aligned}$$
Next, we evaluate the determinant of
\(\mathbf{W}\). It satisfies the following equation:
$$\begin{aligned} \det (\mathbf{W})=\det (\mathbf{\Pi })^{L}\cdot \det (\mathbf{\Pi '})^{L}\cdot \det \begin{pmatrix} \mathbf{D}_{1,1} &{} \mathbf{D}_{1,2} &{} \ldots &{} \mathbf{D}_{1,L}\\ \mathbf{D}_{2,1} &{} \mathbf{D}_{2,2} &{} \ldots &{} \mathbf{D}_{2,L}\\ \vdots &{}&{}\ddots \\ \mathbf{D}_{L,1} &{} \mathbf{D}_{L,2} &{} \ldots &{} \mathbf{D}_{L,L} \end{pmatrix}, \end{aligned}$$
where
\(\mathbf{D}_{i,j}=\mathsf{diag}(r^{(i,j)}_{1}\cdot g_{1}+m^{(i,j)}_1,\ldots , r^{(i,j)}_{n}\cdot g_{n}+m^{(i,j)}_n)\) for all
i,
j. For simplicity, let
\(\Delta = \det (\mathbf{\Pi })^{L}\cdot \det (\mathbf{\Pi '})^{L}\),
\(\mathbf{Q}_k = (r^{(i,j)}_{k}\cdot g_{k}+m^{(i,j)}_k)_{i,j}\), and
\(\mathbf{P}_k = (m^{(i,j)}_k)_{i,j}\). Then,
\(\det \mathbf{W}\) can be written as
\(\Delta \cdot \prod _{k} \det \mathbf{Q}_k\).
To distinguish between the instances of DLIN, we compute \(\det \mathbf{W}\) and check whether it is divisible by \(\prod _k g_k\). If \(\mathbf{E}\) is sampled from a full-rank matrix, the determinant of \({\mathbf{P}}_k\) is nonzero for some k. Hence, \(\det \mathbf{W}\) cannot be a multiple of \(\prod _k g_k\). In the other case, then \(\det \mathbf{P}_i = 0\) for all i. Hence, \(\det \mathbf {W}\) is a multiple of \(\prod _k g_k\) because \(\mathbf{Q}_k\) is congruent to \(\mathbf{P}_k\) in modulo \(g_k\). The total bit-complexity of the attack is \(\widetilde{\mathcal {O}}(\kappa ^{\omega +2} \lambda ^{2\omega +3} + L^{\omega }\kappa ^{2} \lambda ^{3})\).
4.4 Solving the GXDH Problem in CLT13
Without the loss of generality, we assume that
\(t=1\) in the GXDH problem. The first step in the attack is to obtain
\(\prod _i g_i\) from
\((\mathsf params\),
\({p}_{zt})\). Similar to Sect.
4.1, we compute
\(\mathbf{W}_{y^{(1)}}\) and
\(\mathbf{W}_i\) by using
\((\mathsf params)\) as follows (for
\(1 \le i \le n\)):
$$\begin{aligned} \begin{array}{ccl} \mathbf{W}_{y^{(1)}}&{}=&{}([y^{(1)} \cdot \Pi ^{(2)}_u\cdot \Pi ^{(3)}_v \cdot y^{(4)}\ldots y^{(\kappa )} \cdot { p}_{zt}]_{x_0})_{u,v}\\ &{}=&{}(\mathbf{\Pi }^{(2)})^T \cdot \mathsf{diag}(r^{(1)}_1\cdot g_1+1,\ldots ,r^{(1)}_n\cdot g_n+1) \cdot \mathsf{diag}(h'_1,\ldots ,h'_n)\cdot \mathbf{\Pi }^{(3)}, \\ \mathbf{W}_{i}&{}=&{}([\Pi _i^{(1)} \cdot \Pi ^{(2)}_u \cdot \Pi ^{(3)}_v \cdot y^{(4)}\ldots y^{(\kappa )} \cdot {p}_{zt}]_{x_0})_{u,v}\\ &{}=&{}(\mathbf{\Pi }^{(2)})^T\cdot \mathsf{diag}(\pi ^{(1)}_{i1}\cdot g_1,\ldots ,\pi ^{(1)}_{in}\cdot g_n) \cdot \mathsf{diag}(h'_1,\ldots ,h'_n)\cdot \mathbf{\Pi }^{(3)}, \end{array} \end{aligned}$$
where
\(\mathbf{\Pi }^{(2)} = (\pi ^{(2)}_{ui})_{u,i}\),
\({\tilde{h}}_i=h_i\cdot g_i\cdot \prod _{k=4}^\kappa (r^{(k)}_i\cdot g_i+1)\cdot {\hat{p}}_i\), and
\(\mathbf{\Pi }^{(3)} = (\pi _{iv}^{(3)})_{i,v}\).
Similar to Sect.
4.1, we obtain a multiple of
\(\prod _i g_i\) by taking a ratio of the gcds of the determinants of the appropriate subsets of
\(\{\mathbf{W}_1,\ldots , \mathbf{W}_n, \mathbf{W}_{y^{(1)}}\}\):
$$\begin{aligned} \dfrac{\gcd (\det \mathbf{W}_1,\ldots ,\det \mathbf{W}_n)}{\gcd (\det \mathbf{W}_1,\ldots ,\det \mathbf{W}_n, \det \mathbf{W}_{y^{(1)}})}= & {} \Delta \cdot \prod _i g_i, \end{aligned}$$
for some integer
\(\Delta \). By Lemma
2, integer
\(\Delta \) is (2
n)-smooth with probability
\(\ge 0.9\). We eliminate it by trial division by all the integers
\(\le 2n\). Thus, we can obtain
\(\prod _i g_i\) in complexity time
\(\widetilde{\mathcal {O}}(\kappa ^{\omega +3} \lambda ^{2\omega +6})\).
The rest is similar to the DLIN attack in Sect.
4.3. In the GXDH problem, we are given three encodings
\(\mathsf{enc}_{1}(a)=\mathsf{CRT}(\frac{r_{ak}\cdot g_{k}+a_k}{ z_1}), \mathsf{enc}_{1}(b)=\mathsf{CRT}(\frac{r_{bk}\cdot g_{k}+b_k}{ z_1})\), and
\(\mathsf{enc}_{1}(c)=\mathsf{CRT}(\frac{r_{ck}\cdot g_{k}+c_k}{ z_1})\). Next, we repeat the procedure for the construction of
\(\mathbf{W}_{y^{(1)}}\) by replacing
\(y^{(1)}\) with
\(\mathsf{enc}_{1}(a),\)\(\mathsf{enc}_{1}(b)\), and
\(\mathsf{enc}_{1}(c)\), respectively. Then, we obtain:
$$\begin{aligned} \begin{array}{ccl} \mathbf{W}_{a}&{}=&{}(\mathbf{\Pi }^{(2)})^T\cdot \mathsf{diag}(r_{a1}\cdot g_1+a_1,\ldots ,r_{an}\cdot g_n+a_n) \cdot \mathsf{diag}(h'_1,\ldots ,h'_n)\cdot \mathbf{\Pi }^{(3)}, \\ \mathbf{W}_{b}&{}=&{}(\mathbf{\Pi }^{(2)})^T\cdot \mathsf{diag}(r_{b1}\cdot g_1+b_1,\ldots ,r_{bn}\cdot g_n+b_n) \cdot \mathsf{diag}(h'_1,\ldots ,h'_n)\cdot \mathbf{\Pi }^{(3)}, \\ \mathbf{W}_{c}&{}=&{}(\mathbf{\Pi }^{(2)})^T\cdot \mathsf{diag}(r_{c1}\cdot g_1+c_1,\ldots ,r_{cn}\cdot g_n+c_n) \cdot \mathsf{diag}(h'_1,\ldots ,h'_n)\cdot \mathbf{\Pi }^{(3)}. \end{array} \end{aligned}$$
As the last step, we compute:
$$\begin{aligned} \mathbf{W}= & {} \begin{pmatrix} \mathbf{W}_{c} &{} \mathbf{W}_{a} \\ \mathbf{W}_{b} &{} \mathbf{W}_{y^{(1)}} \end{pmatrix}~~\in \mathbb {Z}^{2n\times 2n}~~\text {and}~~\\ \det \mathbf{W}= & {} \Delta '\cdot \prod _i \left( (r_{ai}\cdot g_i+a_i)\cdot (r_{bi}\cdot g_i+b_i)-(r_{ci}\cdot g_i+c_i)\cdot (r^{(1)}_i\cdot g_i+1) \right) , \end{aligned}$$
where
\(\Delta '=\det (\mathbf{\Pi }^{(2)})^2\cdot \det (\mathbf{\Pi }^{(3)})^2\cdot (\prod _i h_i')^2\). If
c is equal to
\(a\cdot b\), then the quantity above has
\(\prod _i g_i\) as a large factor. If
c is uniformly and independently sampled in
G, then the quantity above is independent of
\(\prod _i g_i\). The cost of the attack is also bounded by
\(\widetilde{\mathcal {O}}(\kappa ^{\omega +2}\lambda ^{2\omega +3})\).