Cryptanalysis of the CLT13 Multilinear Map

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.

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.¹ 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].

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 thatThe 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 asfor \(\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: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].² 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.

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 first recall the CLT13 multilinear map and then describe the attack. We refer to the original paper [15] for a complete description.

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.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 \):Further, we define: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: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: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.⁶ However, the attack on the related problems in this section does not depend on it.

This study exhibits a method to recover in polynomial time all the secret values in the CLT13 scheme with a low-level encoding of zero. In addition, we propose a direct algorithm to solve the problems associated with the CLT13 scheme. Consequently, several applications of the CLT13 scheme are impacted.

Because the security of the general-purpose obfuscation schemes in the CLT13 scheme has not been yet clarified, a natural line of research is to extend the range of the attackable graded encoding schemes for the application.

In addition, as a main technique for solving the CLT13 scheme, we introduce a new problem CRT-ACD with an auxiliary input. Independently, solving the CRT-ACD problem is still an open problem. Hence, studying the relation between the two problems will also be an interesting topic.