10
$\begingroup$

A recent (29 Mar 2021) article "Ring-LWE over two-to-power cyclotomics is not hard" by Hao Chen is available in pre-print here: https://eprint.iacr.org/2021/418

I'm not a cryptographer. Does this article mean that Ring-LWE is unsuitable for post-quantum asymmetric cryptography? Does this means that others algorithms might be similarly affected? Or is the author somehow wrong?

$\endgroup$
4
  • 4
    $\begingroup$ The belief I've seen expressed among cryprographers on Twitter is that this sounds highly suspicious (read: wrong). As I said on a similar thread, for such amazing claims, having a proof of concept implementation seems absolutely necessary (especially when the author is not a world-renowned researcher, and thus less likely to attract strong cryprographers willing to take the time to dig deeply in the paper). But if it was true, however, yes it would "destroyes ring LWE" (to use a now famous expression). $\endgroup$ – Geoffroy Couteau Apr 1 at 11:31
  • 4
    $\begingroup$ The paper suggests an algorithm in section 8. It should be relatively straightforward to test this in Sage (the amount of time it takes may scale with the user's competency with Sage of course). The fact that the paper does not include experimental validation of the result using an implementation of this algorithm is somewhat odd, as it would make the paper much more convincing for relatively little effort on the part of the author. $\endgroup$ – Mark Apr 1 at 17:18
  • 1
    $\begingroup$ Leo Ducas has mentioned on twitter that he has reached out to the author in the past about assisting in implementing his algorithms (this is roughly the third paper making increasingly strong claims), but the conversation went nowhere. As a result, it looks like he isn't looking to do something similar that he did to Schnorr's recent RSA claims. $\endgroup$ – Mark Apr 2 at 20:15
  • 8
    $\begingroup$ I took a close look at the paper and found that its approach cannot possibly work against the targeted Ring-LWE parameters. I wrote up the reasons and other notes here: twitter.com/ChrisPeikert/status/1378079417726029824 . (If anyone would like to convert that into an official answer here, please feel free.) $\endgroup$ – Chris Peikert Apr 2 at 20:23
10
$\begingroup$

Update: 20210403

TL;DR

  • If correct, the paper would affect the security of a wide range of RLWE systems, including all of the most commonly used variants.
  • However, the paper violates a "no go" theorem of a reviewed and established paper by Peikert.

Putting to the side the question of whether the paper is correct or not, there are RLWE instances that do not take place in power of two cyclotomic rings (although it is by far the most popular choice). For the NIST process it is worth noting that both CRYSTALS submissions (KYBER and DILITHIUM), FALCON and SABER all do use power of two cyclotomic rings. NTRU however uses $x^{509}-1$, $x^{677}-1$ and $x^{821}-1$, NTRUPrime does not even use a cyclotomic ring.

Thus even if the claims are met, they do not break all ring lattice systems, nor even all NIST ring lattice candidates.

(Technically the NTRU and LWE problems are distinct, though both are solved in practice by solving SVP/CVP instances, so I'll abusively elide the difference between RLWE and ring lattice instances).

The paper claims to break decisional RLWE (distinguishing $(\mathbf a, \mathbf {as}+\mathbf e)$ from $(\mathbf a, \mathbf b)$ as opposed to recovering $\mathbf s$ and $\mathbf e$) in power of 2 cyclotomic rings. It then claims a quantum attack on a short sub-basis question. By section 5 of the LPR paper a decisional RLWE method would convert to a search RLWE method on cyclotomic rings (thanks to Mark and Chris Peikert for pointing out this reduction). This observation is not made in section 3.4 of Hao Chen's paper.

In terms of the distinguishing attack, the nub of the idea seems to be that we can find a sublattice $\mathbf L_2$ which contains both an ideal lattice $\mathbf Q$ that is dense enough that quite a few random elements end up in there and another sublattice $\mathbf L_1$ where error vectors have an elevated chance of appearing (e.g. the chance of an error vector appearing in $\mathbf L_1$ is twice the chance of a random vector appearing in $\mathbf L_2$). Then, if given a large collection of $(\mathbf a,\mathbf b)$ pairs from which we must guess the ones where $\mathbf b$ was generated from $\mathbf b=\mathbf{as}+\mathbf e$ we specialise to the subset where $\mathbf a\in \mathbf Q$. If generated via RLWE then $\mathbf{as}\in \mathbf Q\subset \mathbf L_2$ by the ideal property and $\mathbf e\in \mathbf L_1\subset \mathbf L_2$ with elevated probability, thus $\mathbf{as}+\mathbf e\in \mathbf L_2$ with elevated probability. If we therefore pick the $(\mathbf a,\mathbf b)$ pairs where $\mathbf a\in Q$ and $\mathbf b\in L_2$ and declare these to be RLWE instances, we would be more likely to be correct. Cyclotomic lattices do lend themselves to a wide choice of $\mathbf Q$.

However, lattices such as $L_2$ cannot exist for worst case error distributions. Section 5 of the Peikert paper linked in the TL;DR shows that if $\mathbf Q$ is dense enough to contain many $\mathbf a$, then the distribution of errors for worst case error distributions is smooth (i.e. does not have elevated probability) in $\mathbf Q$ and hence $\mathbf L_2$. Provably-hard ring LWE instances will usually have some reduction to worst case error distribution.

The "no go" observation is due to Chris Peikert and is largely taken from his twitter feed as linked in the paragraph above. Any errors and misrepresentations are due to me.

$\endgroup$
4
  • 3
    $\begingroup$ Aren't search and decision for RLWE equivalent? I thought section 5 of this essentially says that if you can solve "prime-ideal decision RLWE", $q$ completely splits, and the number field is Galois, you can combine that to solve search RLWE. I would imagine that decision RLWE implies prime-ideal decision RLWE by essentially working mod all the other prime ideals, but I do not work with RLWE much. $\endgroup$ – Mark Apr 1 at 17:24
  • 1
    $\begingroup$ @Mark Short answer: dunno guv. I'm not an expert on the directed graph of hardness of lattice problems and will happily defer to your good self and Chris Peikert. OTOH that paper is referenced by our hero and he did not seem to make the connection. It also looks like section 5 also specialises to cyclotomic fields and so perhaps NTRUPrime is about to have its day in the sun :-)? $\endgroup$ – Daniel Shiu Apr 1 at 18:58
  • 3
    $\begingroup$ Mark is correct: breaking decision-RLWE in cyclotomics for fully splitting, poly-bounded $q$ efficiently translates to breaking search-RLWE for the same parameters. I don’t know whether the paper is correct or not, but if it really can break decision then all the rest of the claims should follow. $\endgroup$ – Chris Peikert Apr 1 at 19:54
  • $\begingroup$ Thanks for writing this up! $\endgroup$ – Chris Peikert Apr 3 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.