(In)Security of Ring-LWE Under Partial Key Exposure

1.1 Leaky RLWE Assumptions–Search and Decision Versions

We next briefly introduce the search and decision versions of the Leaky RLWE assumptions. For p∈Rq:= ℤq[x]/(xn+1), we denote p^:=NTT(p):=(p(ω1),p(ω3),…,p(ω2n−1)), where ω is a primitive 2n-th root of unity modulo q, and is guaranteed to exist by choice of prime q, s.t. q ≡ 1 mod 2n. Note that p^ is indexed by the set ℤ2n*.

The search version of the RLWE problem with leakage, denoted Leaky R-SLWE, is parametrized by (n′∈ {1,2,4,8,…n},S⊆ℤ2n′⋆ ). The goal is to recover the RLWE secret s=NTT−1(s^), given samples from the distribution Dreal,n′,Ss which outputs (a^,a^⋅s^+e^,[ s^i ]i≡α mod 2n′∣∀α∈S), where a, s, and e are as in the standard RLWE assumption (see Appendix A.2 and [26] for the precise definition).

The decision version of the RLWE problem with leakage, denoted Leaky R-DLWE is parametrized by (n′∈{1,2,4,8,…n},S⊆ℤ2n′⋆). The goal is to distinguish the distributions Dreal,n′,Ss and Dsim,n′,Ss, where Dreal,n′,Ss is as above and Dsim,n′,Ss outputs a^,u^,[ si^ ]i≡α mod 2n′∣∀α∈S ) ss, where u^i=ai^⋅si^+ei^ for i≡α  mod  2n′, α∈S and ui^ is chosen uniformly at random from ℤq, otherwise. Note that only the coordinates of u^ corresponding to unleaked positions are required to be indistinguishable from random.

When S={α} consists of a single element, we sometimes abuse notation and write the Leaky-RLWE parameters as (n′,α) Leaky-RLWE with parameters (n′,S) where S={ α1,α2,…,αt }, is equivalent to Leaky-RLWE with parameters (n′,S′), where S′=α1−1. · S (multiply every element of S by α1−1 ). It is also not hard to see that leaky search and decision are equally hard when secret s is uniform random from R_q versus drawn from the error distribution (the same reduction for standard RLWE works in our case).

1.2 Our Results

Partial key exposure attacks.

We present attacks on Leaky R-SLWE and test them on various practical parameter settings, such as the NewHope [7] parameter settings as well as the RLWE challenges of Crockett and Peikert [12]. Our attacks demonstrate that Leaky R-SLWE is easy for leakage parameters (n′=4,α=1),(n′=8,S={1,7}) and (n′=8,S={1,15}), under (1) NewHope parameter settings of n = 1024, q = 12289, and x = Ψ 16 (centered binomial distribution of parameter 16); (2) The same parameters above, but with χ=D8 (discrete Gaussian with standard deviation of 8, which has the same standard deviation as Ψ 16), since this is the recommended setting in the case where the adversary gets to see many RLWE samples [3]; (3) For parameters of several of the Crockett and Peikert challenges, including those classified as “very hard.” In all the above cases, we fully recover the RLWE secret with high probability, given the corresponding 1/4-fraction of the positions in the NTT transform of the RLWE secret. See Section 3.2 for details on the experimental results.

A search-to-decision reduction.

Define Tn′(n) to be the time required to solve Leaky R-SLWE for dimension n, given positions [ s^i ]i≡α mod 2_n′ . Assuming search R-LWE without leakage is subexponentially 2Ω(nϵ) -hard for some constant ϵ ≤ 1 and polynomial modulus q, then Tn(n)∈2Ω(nϵ),1 ^[1] i.e. there is a constant c such that, for sufficiently large n, Tn(n)≥2c(nϵ). Also, T1(n)∈poly(n), since the entire s is leaked. So there is some constant c′ such that, for sufficiently large n, there exists n⋆=n⋆(n)∈{2,4,8,16,…,n} such that Tn⋆(n)≥2c′(nϵ) and Tn⋆(n)Tn⋆/2(n)≥n. ^[2]

Applications.

The Leaky R-DLWE assumption is a useful tool for analyzing the security of RLWE-based cryptosystems subject to partial key exposure, and guaranteeing a graceful degradation in security. In particular, the Leaky R-DLWE assumption was used to analyze the NewHope protocol of [7] in the ePrint version of this paper [14]. The assumption is applicable to schemes in which the RLWE assumption is used to guarantee that a certain outcome is high-entropy (as opposed to uniform random), such as NewHope without reconciliation [6].

Practicality of our attack.

We note that an attack on Leaky R-SLWE yields an attack on standard search R-LWE by guessing each possible leakage outcome, running the Leaky R-SLWE attack and checking correctness of the recovered secret. Therefore, we believe this line of research is interesting beyond the context of leakage resilience, since if the attack can be made to work successfully for sufficiently low leakage rate (far lower than the 1 /4-leakage rate of our attacks), then one could potentially obtain an improved attack on standard search R-LWE.

We chose to consider partial exposure of the NTT transform of the R- LWEsecret, since in practical schemes the secret key is often stored in the NTT domain and certain types of side-channel attacks allow recovering large portions of the secret key stored in memory. E.g., in their analysis of “cold boot attacks” on NTT cryp-tosystems, Albrecht et al. [4] considered bit-flip rates as low as 0.2%. However, the highly structured leakage required for our attack is unlikely to occur in a practical leakage setting such as a “cold boot attack,” where one expects to recover the values of random locations in memory. We leave open the question of reducing the structure of the leakage in our attack. Specifically, as a starting point it will be interesting to see if our attack can extend to leakage patterns of n′ = 16, |S| = 4 or n′ = 32, |S| = 8, etc. While the leakage rate remains the same (1/4) in each case, these patterns capture leakage that is less and less structured, since at the extreme, one can view leakage of a random 1 /4-fraction of the NTT coordinates as an instance of Leaky R-SLWE with parameters n′ = n and |S| = n/4. ^[3]

1.3 Comparison with Concurrent Work of Bolboceanu et al. [9]

One of the settings considered by [9] is sampling the RLWE secret from an ideal I ⊆ qR. It is straightforward to see that sampling the RLWE secret uniformly at random from Rq and then leaking the NTT coordinates i such that i = α mod 2n′ is equivalent to sampling the RLWE secret from the ideal I that contains those elements whose NTT transform is 0 in positions i such that i = α mod 2n′.

Nevertheless, our decisional assumption is weaker than the assumption of [9], since [9] require that the entire vector u be indistinguishable from uniform random, whereas we only require that the NTT transform of u is indistinguishable from uniform random at the positions i that are not leaked. Our assumption lends itself to a search-to-decision reduction while the assumption of [9] does not. While [9] do provide a direct security reduction for their decisional assumption, the required standard deviation of the error (in polynomial basis, tweaked and scaled by q) is , ω(q1/n′⋅n3/2), which would be far higher than the noise considered in the NewHope and RLWE Challenges settings. In contrast, our assumption can be applied in practical parameter regimes and is sufficient to argue the security of several practical cryptosystems under partial key exposure.

Finally, we compare our attack to that of [9]. For fixed n, q, our attack works for noise regimes that are not covered by the attack of [9]. For example, for NewHope settings of n = 1024, q = 12289, the attack of [9] has success rate at most 1/1000 when the standard deviation of noise distribution is less than 0.00562. ^[4] In contrast, our attack works (with success ranging from 82/200 to 2/1000) when the standard deviation of the noise is 8≈2.83. ^[5] Our attack applies only for certain leakage patterns corresponding to certain ideals I, whereas the attack of [9]works for any ideal. The techniques of the two attacks are entirely different. [9] obtain a “good” basis for the ideal via non-uniform advice, perform a change of basis and then use Babai’s roundoff algorithm to solve the resulting BDD instance.We use the algebraic structure of the problem to convert RLWE instances over high dimension into CVP instances over constant dimension n′.We then exactly solve the CVP instances over constant dimension and determine the “high confidence” solutions that are likely to be the correct values of the RLWE error. Assuming all high confidence solutions are correct, we obtain a noiseless system of linear equations w.r.t. the RLWE secret, allowing efficient recovery of the secret.

1.4 Related Work

Leakage-resilient cryptography.

The study of provably secure, leakage-resilient cryptography was introduced by the work of Dziembowski and Pietrzak in [19]. Pietrzak [29] also constructed a leakage-resilient stream-cipher. Brakerski et al. [11] showed how to construct a scheme secure against an attacker who leaks at each time period. There are other works as well considering continual leakage [17, 22]. There are also work on leakage-resilient signature scheme [10, 21, 27].

Leakage-resilience and Lattice-based Cryptography.

Goldwasser et al. [20], and subsequently [2, 16, 18] studied the leakage resilience of standard LWE based cryptosystems in the symmetric and public key settings.

Leakage Resilience of Ring-LWE.

Dachman-Soled et al. [13] considered the leakage resilience of a RLWE-based public key encryption scheme for specific leakage profiles. This was followed by Albrecht et al. [4], they investigated cold boot attacks and compared the number of operations for implementing the attack when the secret key is stored as polynomial coefficients versus when encoding of the secret key using a number theoretic transform (NTT) is stored in memory. Recently, [30] showed that given multiple samples of RLWE instances such that the public key for every instance lies in some specific subring, one can reduce the original RLWE problem to multiple independent RLWE problems over the subring. In this work we do not place any such restriction on the RLWE samples required to mount partial key exposure attack.

3.1 Reconstructing the secret given (α mod 8) leakage

Recall that for p∈ℤq[x]/(xn+1), the NTT transform, p^, is obtained by evaluating p(x) mod q at the powers ωi for i∈ℤ2n⋆, where ω is a 2n-th primitive root in ℤq. For n′∈{1,2,4,8,…,n}, let u=n/n′. For α∈ℤ2n′⋆, consider puα(x) be the degree u − 1 polynomial that is obtained by taking p(x) modulo (xu−(ωα)u) We may assume WLOG that α = 1. We abbreviate notation and write p^u, instead of pu1.

We consider attacks in which the adversary learns all coordinates i of s^ such that i ≡ 1 mod 2n′ where n′∈{1,2,4,8,…,n}, and aims to recover the RLWE secret s. First, we note that in NTT transform notation the equation a^⋅s^+e^=u^ holds component-wise. Therefore, given leakage on certain coordinates of s^, we can solve for the corresponding coordinates of  e^.  We also get to see multiple RLWE samples (which we write in matrix notation–where the Aj matrices are the circulant matrices corresponding to the ring element aj, s)  as (A1,A1s+e1=u1),…,(Aℓ,Aℓs+eℓ=uℓ). Thus, for the j-th RLWE sample we learn all the coordinates e^ij, for i ≡ 1 mod 2n′. Note that the leaked coordinates are the evaluation of the polynomial eu(x) at the ωi for i ≡ 1 mod 2n′. We can then reconstruct the polynomial eu(x) using Lagrange Interpolation.

For i∈{0,…,u−1}, the (i + 1)-st coefficient of eu(x), i.e. eu,i is equal to

The coefficients of e can be partitioned into u groups of size n′, forming independent linear systems, each with n′ variables and one equation. Given only the leakage, the set of feasible secret keys is a cartesian product S1×⋯×Su, where for i ∈ [u], the set Si is the set of vectors e¯i:={ ei,ei+u,ei+2u,…,ei+(n′−1)u } that satisfy the i-th linear system:

Since each coordinate of e is drawn independently from χ and since each linear system above has small dimension n′, we can use a brute-force-search to find the most likely solution and calculate its probability.

Given this information, we will carefully choose the solutions ej e¯ij (from all possible sets of solutions [ e¯ij ]j∈[ℓ],i∈[u] ) that have a high chance of being the correct values of the RLWE error. To obtain a full key recovery attack,we require the following: (1) In total,we must guess at least u number of n′-dimensional solutions, e¯ij, from all the obtained solutions [j [ e¯ij ]j∈[ℓ],i∈[u]  ;  (2) With high probability all our guesses are correct. Observe that if our guess of some e¯ij is correct, we learn the following linear system of n′ equations and n variables (Aj,i⋅s=uj,i−ej,i), where Aj,i is the submatrix of Aj consisting of the n′ rows i,i+u,i+2⋅u,…,i+(n′−1)⋅u, and u^j,ⁱ , e^j,ⁱ are vectors consisting of the i,i+u,i+2⋅u,…,i+(n′−1)⋅u coordinates of u^j and e^j. So assuming (1) and (2) hold, we learn u noiseless systems of n′ linear equations, each with n = u · n′ number of variables.We then construct a linear system of n variables and n equations, which can be solved to obtain the candidate s.

In order to ensure that (2) holds, we only keep the guess ^jfor e¯ij when we have “high confidence” that it is the correct solution. The probability of a particular solution e¯ij:=(eij,ei+uj,…,ei+(n′−1)uj), is the ratio of the probability of e¯ij ibeing drawn from the error distribution (which is coordinate-wise independent) over the sum of the probabilities of all solutions. For small dimension n′, this can be computed via a brute-force method. In our case, we keep the highest probability solution when it has probability at least, say 0.98. The probability that all guesses are correct is therefore 0.98u=0.98n/n′.

Since computing the exact probability as above is computationally intensive, we develop a heuristic that performs nearly as well and is much faster. Note that finding the “most likely” solution is equivalent to solving a CVP problem over an appropriate n′-dimensional lattice. We then calculate the probability of the solution under the discrete Gaussian and set some threshold . If the probability of the solution is above the threshold we keep it, if not we discard it. Experimentally, we show that by setting the threshold correctly, we can still achieve high confidence. See Figure 1 for the exact settings of the threshold for each setting of parameters. Our experiments also show that (1) also holds given a reasonable number of RLWE samples. See Section 3.2 for a presentation of our experimental results. We describe our attack in cases where the leakage is on all coordinates i such that i≡α1 mod 2n′ or i≡α2 mod 2n′ in Appendix B.1.

Figure 1

Performance of attack against RLWE Challenges [12] and NewHope [7] parameter settings. For each parameter setting, we report the following: min/max and average number of RLWE samples required for successful break, total number of broken instances, and max run-time (in seconds) for successful break. Threshold is set such that the minimal weight solutions to the linear systems given in Section 3 have high confidence with sufficiently high probability.

Complexity of the attack.

We provide the pseudocode for the attack in Appendix D, Figure 3. While our attack works well in practice, we do not provide a formal proof that our attack is polynomial time for a given setting of parameters. Within the loop beginning on line 5, all the steps (or subroutines) shown in Figure 3 can be computed in polynomial time. Note that even step 12 (CVP.closest_vector), which requires solving a CVP instance, can be computed in polynomial time because for the leakage patterns we consider, the dimension of the CVP instance will always be either 4 or 8–a constant, independent of n. However, our analysis does not bound the number of iterations of the loop beginning on line 5. Specifically,we do not analyze how large the variable RLWESamples must be set in order to guarantee that the attack is successful with high probability. Bounding this variable corresponds to bounding the number of RLWE samples needed in order to obtain a sufficient number of “high confidence” solutions. In practice, the number of RLWE samples was always fewer than 200 for all parameter settings. In future work,we plan to compute the expected number of RLWE samples needed to obtain a sufficient number of high confidence solutions for a given parameter setting. Assuming this expected number of samples is polynomial in n, we obtain an expected polynomial time attack.

Figure 2

Description of Attack 1.

Figure 3

Description of Partial Key Exposure Attack from Section 3

3.2 Experimental Results

We first assess the performance of our attack on the RLWE challenges published by Crockett and Peikert [12], with various parameters, ranging from “toy” to “very hard” security levels. For each parameter setting, a cut-and-choose protocol was used by [12] to prove correctness of the challenges: They committed to some number (e.g. N = 32) of independent RLWE instances, a random index i was chosen, and the secret key for all except the i-th instance was revealed. For each of the 31 opened challenges,we simulate the Leaky RLWE experiment and attempt to recover the full secret s using our attack. We next measure the performance of our attack on RLWE instances generated using the dimension, modulus and noise distribution proposed in the original NewHope scheme [7]. These parameters are more conservative than the ones chosen for the later submission to the NIST competition [5]. When multiple RLWE samples are released, bounded error distributions are less secure [3]. We therefore tested our attack in the more difficult setting of Gaussian error, in addition to the original binomial error distribution of [7].

The experiments were run using server with AMD Opteron 6274 processor, with a python script using all the cores with Sage version 8.1.We used fplll [15] library for CVP solver and the source code of all the attacks are available online at [1]. The results of our attacks are summarized in Figure 1.We report the total number of instances we broke and the average number of RLWE samples needed for those instances. To decide whether a solution is kept or discarded, its probability mass under the error distribution χ is calculated and compared to the threshold. The threshold for each parameter setting is set heuristically so that minimal weight solutions passing the threshold are correct with high confidence (see Figure 1 for the exact threshold settings). We tested leakage patterns of (n′=4,S={1}),(n′=8,S={1,7}) and (n′=8,δ={1,15}) –all corresponding to 1/4-fraction leakage—for each parameter setting and were able to break multiple Leaky RLWE instances for every parameter setting/leakage pattern shown in Figure 1. We also report the maximum time it took to break a single instance for each parameter setting in Figure 1. Overall, the maximum amount of time to break a single instance was 6 hours for the hardest instance, i.e. Challenge ID 89.We attempted to launch our attack given only 1/8-fraction of leakage (leakage pattern (n′ = 8, α = 1)), but were only successful for the easiest case, i.e. Challenge ID 1. For, e.g. Challenge ID 89, the attack failed since for 5000 number of linear systems, the maximum confidence of any solution was 0.28, meaning that we expect to recover the secret key with probability at most 0.282048/8≈2−470, which is well beyond feasible.