You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
ACES depends on the generation of an arithmetic channel, defined as a quadruple $\mathsf{C} = (p, q, \omega, u)$, where $p$, $q$, and $\omega$ are positive integers, and $u$ is a polynomial in $\mathbb{Z}[X]$ satisfying the equation $u(\omega) = q$ in $\mathbb{Z}$. While the integer $\omega$ remains fixed at $1$ and the ACES library automatically generates the polynomial $u$, the user is still required to manually select the values for $p$ and $q$.
Importantly, the security of ACES relies on two consecutive modulus operations, specifically involving the positive integers $q$ and $p$. We will review the corresponding security principles pertaining to these two integers in the subsequent subsections.
ACES encryption
The ACES framework encrypts a message $m \in \mathbb{Z}_p$ as a ciphertext $(c,c')$ according to the following procedure:
The first component $c$ is an $n$-vector over $\mathbb{Z}_q[X]_u$ given by $c = f_0^Tb$, where:
$f_0$ is an $n \times N$ matrix over $\mathbb{Z}_q[X]_u$ (chosen during key generation).
$b = (b_i)_i$ is an $N$-vector over $\mathbb{Z}_q[X]_u$ such that $b_i(\omega) \in \lbrace 0,1,\dots,p \rbrace$ (selected by the sender).
The second component $c'$ is an element of $\mathbb{Z}_q[X]$ defined as $c' = r_m + c^Tx + e$, where:
$r_m$ is an element over $\mathbb{Z}_q[X]_u$ chosen such that its evaluation in $\mathbb{Z}_q$ at the integer $\omega$ equals $m$ (chosen by the sender).
$x$ is an $n$-vector over $\mathbb{Z}_q[X]_u$ (considered the private key).
$e$ is a scalar product in the form of $b^Te'$, where $e'= (e_i')_i$ is an $N$-vector over $\mathbb{Z}_q[X]_u$ such that the evaluation of $e_i'$ in $\mathbb{Z}_q$ at the integer $\omega$ is equal to a product $p \ell$ where $\ell \in \lbrace 0,1\rbrace$.
ACES Security
Protecting the public key
Given that the public key takes the form $(f_0, f_1)$ with $f_1 = f_0^Tx + e'$, it is reasonable to assume that an attacker's objective might involve deducing the value of $x$ by analyzing the distribution of $f_1$.
First, let us establish that the polynomial $e' = (e_1',\dots,e_N')$ is determined by the sender $\mathsf{Bob}$ through the selection of a random $N \times n$-matrix $(a_{i,j})_{i,j}$ in $\mathbb{Z}_q$, a random $N$-vector $s=(s_1,s_2,\dots,s_N)$ of non-negative integers $s_i < n$ and a random $N$-vector
If the attacker found an element $x'$ such that $f_0^Tx = f_0^Tx'$, the previous distribution would appear random since the distribution of the coefficients $a_{i,j}$
is uniform. More specifically, in this scenario, the polynomials are examined coefficient by coefficient, which means that the attacker would only perceive the randomness of each coefficient and not their overall relationships. We reach a similar conclusion for any other element $x'$, as the summand $\mathsf{row}_i(f_0)^T(x-x')$ would merely shift the random behavior by a constant value. As a result, ACES benefits from the hardness of the RLWE problem.
Note
The paper "Provably Weak Instances of Ring-LWE Revisited" provides examples where an attack on the presented version of RLWE (PLWE) is feasible due to the condition $u(1) = 0$ in $\mathbb{Z}_q$. It is crucial to note that this vulnerability is observed in cases where $q$ is small, and the error term $e'$ tends to exhibit a distribution closer to Gaussian than uniform. It is important to emphasize that this scenario is distinct from the context considered in ACES.
Attacks in $\mathbb{Z}$ with evaluations at $\omega$
An attacker may want to take advantage of the form of the image of $e'$ in $\mathbb{Z}_q$ when evaluated at $\omega=1$. Specifically, the attacker is likely to exploit the existence of a non-negative integer $k_i$ satisfying the equation:
$$e_{i}'(\omega) - qk_i = p \epsilon_{i}$$
It is worth noting that the probability of $k_i$ being non-zero is high, given that the coefficients $a_{i,j}$ are as likely to be small as they are to be large in the interval $\mathbb{Z}_q$. Because the attacker is not assumed to know the value of each $e_i'(\omega)$ they may likely to attack the public key using some search/decision algorithm. Specifically, given a $n$-vector $x'$ over $\mathbb{Z}_q[X]_u$, an attacker may want to analyze the distribution of the integers
The previous integer can be calculated as a difference of the form $\chi_i = f_{1,i}(\omega)- \mathsf{row}_i(f_0(\omega))^Tx'(\omega)-qk_i'$ for some positive integer $k_i'$. This means that the attacker has access to a distribution of the following form:
$$\chi_{i} = \mathsf{row}_{i}(f_0(\omega))^{T}(x(\omega)-x'(\omega)) + p \epsilon_i+q(k_i-k_i')$$
The previous formula means that if $f_0^Tx = f_0^Tx'$, then the distribution of the data points is restricted to elements of the form $qk + p \epsilon$ with $\epsilon \in \lbrace 0,1 \rbrace$ and $k \in \mathbb{N}$. Without any assumption on $f_0$, this may give a way for an attacker to search for elements $x'$ capturing the values of $x$ when evaluated at the element $\omega$.
However, if we sample $f_0 = (f_{0,i,j})_{i,j}$ according to the formula
where $s_{i,j}$ is a random integer from the interval $[0,n-1]$, and $k_{i,j}^{\prime\prime}$ and $v_{i,j,k}$ are random integers from $[0,q-1]$, then we have the property that $f_{0,i,j}(\omega)$ is a non-trivial multiple $p k_{i,k}$ of $p$ in $\mathbb{Z}_q$.
In other words, the distribution of the data points $\chi_i$ looks more like a random sample of elements from $p\mathbb{N} + q\mathbb{Z}$. If we choose $p$ and $q$ to be coprime, then the set $p\mathbb{N} + q\mathbb{Z}$ is equal to $\mathbb{N}$, which means that that the distribution of our data points $\chi_i$ would just look uniform in $\mathbb{Z}_q$. Indeed, suppose that we can find $x'$ such that there are $\eta_i \in \lbrace 0,1\rbrace$ and $\kappa_i \in \mathbb{N}$ for which the following equation holds.
$$\chi_i = p \eta_i + q \kappa_i$$
In this context, we have the following relation, where $k_i^{\prime\prime}$ denotes the vector $(k_{i,1}^{\prime\prime},\dots,k_{i,N}^{\prime\prime})$.
The equation displayed on the right says that the vector $(k_i^{\prime\prime})^Tx'(\omega)$ in $\mathbb{Z}_q$ is of the form
$$(k_i^{\prime\prime})^Tx(\omega) + \eta_i'$$
for some $\eta_i' \in \lbrace -1,0,1 \rbrace$. In other words, the attacker is only given a vector very close to the lattice generated by the vector $k_i^{\prime\prime}$. Since finding vectors of a lattice that are close to some given vector is considered a difficult, it follows that the attacker will face the challenge of solving a Closest Vector Problem.
Protecting your ciphertext
Recall that a general ciphertext $(c,c')$ consists of an $n$-vector $c$ over $\mathbb{Z}_q[X]_u$ and an element $c$ in $\mathbb{Z}_q[X]_u$ such that the equation
$$c' = r_m + c^Tx + e$$
holds and where the folloiwng conditions are satisfied:
$r_m$ is an element of $\mathbb{Z}_q[X]_u$ such that the value $r_m(\omega)$ is equal to the value of a message $m$ in $\mathbb{Z}_q$;
$e$ is an element of $\mathbb{Z}_q[X]_u$ such that the value $e(\omega)$ is a multiple of $p$ in $\mathbb{Z}_q$.
Here, it is reasonable to assume that an attacker's objective might involve deducing the value of $r_m$ by analyzing the distribution of $c'$. To discuss this scenario, let us establish that the polynomial $r_m$ is determined by the sender $\mathsf{Bob}$ through the selection of $n$ random coefficients $m_0, m_1, \dots, m_{n-1}$ in $\mathbb{Z}_q$ and a random non-negative integer $s < n$. This encoding follows the formula:
While the previous structure can already suggest various attack models on the ciphertext, it is important to note that the encryption of a given message $m$ by ACES is even more specific as $e = b^Te'$ and $c = b^Tf_1$.
In our implementation, the polynomial $b$ is determined by $\mathsf{Bob}$ through the selection of $n$ random coefficients $b_0, b_1, \dots, b_{n-1}$ in $\mathbb{Z}_q$, a random non-negative integer $s' < n$ and a random element $\delta_1 \in \lbrace 0,1,\dots,p\rbrace$ with the formula:
While $b$ is generated randomly, it still has the property that $b(\omega) \in \lbrace 0,1,\dots,p \rbrace$, which may give some advantage to an attacker as the evaluation $(be')(\omega)$ would still be small in $\mathbb{Z}_q$.
To prevent an attacker to take advantage of the previous properties, the encrypter is recommanded to apply a random identity operation on the encrypted data to convert it into a ciphetext $(c,c')$ with a general as defined above.
For example, the ciphertext resulting from the following operations on the encrypted data $\mathsf{E}(m)$ can still be decoded as $m$, but it does not have the same form as if it had just been produced by ACES:
However, since every general ciphertext should be assumed to result from a homomorphic operation on ciphertexts generated by ACES, general ciphertexts still have some structure that can be exploited if the matrix
$$f_0 = (f_{0,i,j})_{i,j}$$
satisfies certain properties. For example, if the evaluations $f_{0,i,j}(\omega)$ are all multiples of $p$ in $\mathbb{Z}$, then so do the coefficients of the vectors $c$ associated with any ciphertext $(c,c')$. These considerations are taken into account in the following two sections.
Attacks in $\mathbb{Z}_q[X]_u$
Given a $n$-vector $x'$ over $\mathbb{Z}_q[X]_u$, an attacker may want to analyze the distribution of the coefficients making the polynomial $c' - c^Tx'$. Specifically, the sample associated with this distribution is given by the following set, where $\rho_i$ returns the $i$-th coefficient of its input.
If the attacker found an element $x'$ such that $c^Tx = c^Tx'$, the previous distribution would appear random because the polynomial $e$ can be expressed as products and sums of polynomials whose coefficients are randomly picked in $\mathbb{Z}_q$.
Note that, in our scenario, the polynomials are examined coefficient by coefficient, which means that the attacker would only perceive the randomness of each coefficient and not their overall relationships. For example, the $s$-th coefficient of $r_m$, which is of the form
would still look random. Indeed, during the generation of $r_m$, $\mathsf{Bob}$ has the freedom to select $a_0, a_1, \dots, a_{n-1}$ such that the inequality
Furthermore, because each coefficient $m_i$ is taken randomly in the interval $[0, q-1]$, the sum
$$m - \sum_{i=0}^{n-1}m_i + m_s$$
varies within the interval $[-(n-1)q,p]$. Consequently, the element $k_0$ should reasonably be inferred within the interval $[0,n]$. This calculation also suggests that the value of $k_0$ is mainly determined by the coeffcients $m_i$ as the value $m$ is less than $p$, which can be considered much smaller than $q$ (since $p^2 < q$).
Selecting coprime $p$ and $q$ would then ensure that the "randomness" of the term $qk_0$ is entirely determined by the randomness of the elements $m_0, m_1, \dots, m_{n-1}$.
Finally, because the same principles as those listed above hold even when $c^Tx \neq c^Tx'$, it follows that ACES benefits from the hardness of the LWE/RLWE problem in all cases.
Attacks in $\mathbb{Z}$ with evaluations at $\omega$
An attacker may want to take advantage of the properties satisfied by the images of $e$ and $r_m$ in $\mathbb{Z}_q$ when evaluated at $\omega=1$. Specifically, the attacker is likely to exploit the existence of two non-negative integers $k_0$ and $k_1$ satisfying the following equations for some non-negative integer $\lambda$
It is worth noting that the probability of $k_0$ and $k_1$ being non-zero is high, given that the coefficients of $e$ and $r_m$ are as likely to be small as they are to be large in $\mathbb{Z}_q$. Because the attacker is not assumed to know the values of $e(\omega)$ and $r_m(\omega)$, they may likely to attack the public key using some search/decision algorithm.
Specifically, given a $n$-vector $x'$ over $\mathbb{Z}_q[X]_u$ and an integer $m' \in \mathbb{Z}_p$, an attacker may want to decompose the following quantity:
The previous integer can be calculated as a difference of the form $\chi = c'(\omega) - c(\omega)^Tx'(\omega) - m'-qk_2$ for some positive integer $k_2$. This means that the attacker has access to a quantity of the following form:
$$\chi = m-m' + p \lambda + q(k_0+k_1-k_2) + c(\omega)^T(x(\omega)-x'(\omega))$$
As explained in previous sections, we have a certain interest in making the image $f_{0,i,j}(\omega)$ to be multiples of $p$. As a result, given that we can assume that the ciphertext $(c,c')$ is the result of a homomorphic calculation using encrypted data as produced by ACES, it is reasonable to assume that the attacker will deal with a ciphertext $(c,c')$ such that the coefficients of $c(\omega)^T$ are multiples of $p$ in $\mathbb{Z}_q$. As a result, we can supposed that there exists a $n$-vector
$$k_3 = (k_{3,1},k_{3,2},\dots,k_{3,n})$$
of non-negative integers such that $c(\omega)^T(x(\omega)-x'(\omega)) = pk_3^T(x(\omega)-x'(\omega))$. This means that we now have the following equation:
If we choose $p$ and $q$ to be coprime, then usual theorems on Diophantine equations imply that the number of solutions for the previous equation is significant. Indeed, suppose that we can find $x'$ and $m'$ such that there are $\eta \in \mathbb{Z}$ and $\kappa \in \mathbb{N}$ for which the following equation holds.
Assuming that the attacker can easily find a soluton $(h_0,h_1)$ to the Diophantine equation $qh_0 + ph_2 = 1$, the attacker will have to find an integer $v$ such that we have:
still have to be inferred. These considerations show that attacking ciphertexts in the way described above will likely be equivalent to searching the space of solutions of a system of two quadratic equations with $n+6$ unknown variables. This means that there is a large number of solutions to try for the attacker.
Alternatively, we can look at the previous problem as a Diophatine equation of $n+2$ variables as follows:
are as close as possible to 0 (if not equal to 0) so that we can have a situation where $m' = m$, and $x' = x$. This can add to the difficulty of finding the right solution. To corborate this intuition further, we can mention that, in general, solving Diophantine equations for vectors with small norms is hard, and is closely related to solving a Short Integer Solution probolem or a Shortest Vector Problem.
Homomorphism and why it works
While the decryption in ACES operates within the ring $\mathbb{Z}$, it is essential to recognize that the homomorphic structure is established within the polynomial ring $\mathbb{Z}_q[X]_u$. In drawing a parallel, consider this process akin to employing complex numbers for computations that might pose greater challenges when exclusively using real numbers, such as solving polynomials or analyzing signals.
Specifically, if we let $x = (x_1,\dots,x_n)$ denote the private key for ACES, then the homomorphism property relies on a 3-tensor $\lambda = (\lambda_{i,j}^k)_{i,j,k}$ satisfying the following relation for every triple $(i,j,k)$ of elements in $\lbrace 0,1,2,\dots,n\rbrace$.
If we tried to imagine what this equation would amount to in the context of complex numbers, we would be faced with the challenge of finding real numbers $\lambda_1$ and $\lambda_2$ for which equations of the following form holds.
By uniqueness of the complex and real parts, we would then obtain:
$\lambda_1 a_1 + \lambda_2 a_2 = a_1a_2-b_1b_2$
$\lambda_1 b_1 + \lambda_2 b_2 = a_1b_2+a_2b_1$
Note that without the complex structure, deducing the values of $\lambda_1$ and $\lambda_2$ would be challenging. This underscores how $\mathbb{C}$ introduces a mathematical structure that cannot be recovered by $\mathbb{R}$. In a parallel manner, we leverage the polynomial ring $\mathbb{Z}[X]$ to encapsulate the homomorphic properties of ACES. After performing arithmetic operations on polynomials to compute homomorphic sums and products, we can seamlessly revert to $\mathbb{Z}$ for decrypting the encrypted data.
Remark on security
The conditions that define the coefficients of the 3-tensor $\lambda = (\lambda_{i,j}^k)_{i,j,k}$ are essentially equivalent to solving a system of quadratic polynomial equations in a finite field ring. In theory, the task of recovering the private key $x$ from the 3-tensor $\lambda$ is safeguarded by the Polynomial System Solving Problem. Specifically, if we express
there exists a tuple $(a_0',a_1',\dots,a_{n-1}')$ of integers in the range $[0, q-1]$ such that, for every $r \in \lbrace 0,1,2,\dots,n-1\rbrace$, the coefficients of $\lambda$ satisfy the following equations in $\mathbb{Z}_q$:
$$\sum_{s+t = r } a_{i,s} a_{j,t} - \sum_{s+t = r } \mu_{s} a_{t}' = \sum_{k=0}^{n-1}\lambda_{i,j}^{k} a_{k,r}.$$
Solving this set of equations involves finding a specific solution $(a_{1,0},\dots,a_{n,n-1},a_0',\dots,a_{n-1}')$ for a system of $n^3$ quadratic polynomial equations
$$f_{i,j,1}(w_1,\dots,w_{n(n+1)}) = 0,$$
$$\vdots$$
$$f_{i,j,n}(w_1,\dots,w_{n(n+1)}) = 0,$$
in the finite ring $\mathbb{Z}_q$. According to research (source and source), embarking on an exhaustive search for the solution would result in a computational complexity of $O(q^{n(n+1)})$. Opting for a sufficiently large value of $q$ would force an attacker to turn to a formal calculus algorithm, such as the F5 algorithm, designed for solving polynomial equations with Gröbner basis. However, note that in our specific scenario, employing Gröbner basis techniques on our set of polynomial equations would prove ineffective since the equations characterizing $\lambda$ are already reduced.
Indeed, observe that the monomial $a_{i,s}a_{j,t}$ can only appear in the equations $f_{i,j,s+t}(w_1,\dots,w_{n(n+1)}) = 0$ and $f_{j,i,t+s}(w_1,\dots,w_{n(n+1)}) = 0$, which in our implementation are given by the same equation. This means that this monomial cannot be further reduced by uisng the other equations. Consequently, an attacker attempting to compromise the private key using the equations defining the 3-tensor $\lambda$ would likely have to resort to either an exhaustive search or a hybrid method, which would still be computationally expensive, especially if $q$ is chosen to be large.
Cost of homomorphism
ACES is a fully homomorphic encryption scheme that initially relies on a leveled FHE framework. This framework is then equipped with a refresh operation $\mathsf{refr}$ designed to mitigate the level increase resulting from arithmetic operations. In this section, we explore the conditions that must be satisfied by the parameters $p$ and $q$ to leverage the homomorphism property.
For two ciphertexts $(c_1, c_1') \in S_{\mathsf{C},k_1}(m_1)$ and $(c_2, c_2') \in S_{\mathsf{C},k_2}(m_2)$ with respective levels $k_1$ and $k_2$, the homomorphic sum of these ciphertexts can be computed if the inequality shown below on the left holds:
Similarly, for a suited parameter $\lambda$ (refer to the paper in section 5.2), the homomorphic product of the ciphertexts $(c_1, c_1')$ and $(c_2, c_2')$ is achievable if the inequality shown below on the left holds:
While this does not affect the estimation of levels significantly, it is important to note that the current version of the research paper contains an inacurate formula for the previous inequality (namely, the formula $k_1 k_2 p< q/p$). The reader can check in Theorem 5.22 that the noise for the multiplication is given by a formula $e_3 = e_1r_2(m_2) + e_2 r_1(m_1)+e_1e_2$ where the polynomial $e_1r_2(m_2)$ has a level $\leq k_1p$, the polynomial $e_1r_2(m_2)$ has a level $\leq k_2p$ and the polynomial $e_1e_2$ has level $k_1k_2p$. This means that the level of $e_3$ varies between $k_1k_2p$ and $(k_1 k_2 +k_1+k_2)p$.
Given that the level of any encryption $(c, c')$ produced through ACES is constrained by an upper bound equal to $Np$, we can derive an estimate for $q$ in terms of $p$ and $N$ to ensure the system's capability to be decrypted after homomorphic additions and multiplications. To elaborate further, starting with ciphertexts generated by ACES, a multiplication operation results in a level of $2Np^2+N^2p^3$, whereas an addition operation yields a level of $2Np$. Consequently, a combination of additions and multiplications in the form:
Considering our desire for this level to be significantly less than $q/p$, the following inequality should be satisfied for the use of around $K$ layers of additions and multiplications:
$$q \gg (K_0Np)^{2^{K+1}}$$
Protection against the Chinese Remainder Theorem
The existence of the 3-tensor $\lambda$ facilitating homomorphic multiplications in ciphertexts stems from the quotient of the ring $\mathbb{Z}_q[X]$ by the polynomial ideal generated by $u$. Consequently, the parameter $u$ plays a crucial role in our system. However, this parameter introduces a potential vulnerability, as an attacker might attempt to glean information about the private key through it.
First, recall that the polynomial $u$ is taken in $\mathbb{Z}[X] \subseteq \mathbb{R}[X]$ such that $u(\omega) = q$. Let the sequence
$$\omega_1, \omega_2, \dots, \omega_{\rho}$$
denote the distinct roots of $u$ in $\mathbb{C}$ when $u$ is treated as a polynomial in $\mathbb{R}[X]$. Given the equation $u(\omega_i) = 0$ for all $i \in \lbrace 1,2,\dots,\rho \rbrace$, we have the following expression in $\mathbb{C}$:
Given that $\rho \leq \mathsf{degree}(u) = n < n + 2n + 1$, deducing the values of $a_i$ and $a_i'$ through this approach could become particularly challenging. This difficulty becomes more pronounced when the value of $n$ exceeds $4$, introducing the possibility of some roots $\omega_k$ being complex numbers and non-expressible by radicals. This intricacy adds complexity to the task of precisely determining the approximate values of the coefficients of $c^T(\omega_k)$.
Take away on parameters
Throughout the preceding sections, we showed that users should adhere to the following requirements when selecting values for $p$, $q$, $n$ and $N$:
we should have $p^2 < q$
$p$ and $q$ should be coprime
to process at least $K$ layers of operations, we should have $q \gg (K_0Np)^{2^{K+1}}$ for some constant $K_0$.