12
$\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?

Improve this question
$\endgroup$
4
  • 5
    $\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, 2021 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, 2021 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, 2021 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, 2021 at 20:23

2 Answers 2

Reset to default
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.

Improve this answer
$\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, 2021 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 S
    Apr 1, 2021 at 18:58
  • 4
    $\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, 2021 at 19:54
  • $\begingroup$ Thanks for writing this up! $\endgroup$
    – Chris Peikert
    Apr 3, 2021 at 12:24
-1
$\begingroup$

I think we should keep a watchful eye on this since the background of the author.

He is actually a contributive Chinese mathematician and recently goes back to the world of cryptography. The information about him on the Internet is too limited.

Back? Because, several years ago, he published some papers on Crypto and Eurocrypt.

The author's information, according to my knowledge:

Recent papers: https://www.researchgate.net/scientific-contributions/Hao-Chen-2075500377

Earlier papers: https://www.x-mol.com/university/faculty/113222

The iacr list:

Crypto09, Ignacio Cascudo, Hao Chen, Ronald Cramer, Chaoping Xing, Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Fixed Finite Field

Eurocrypt08, Hao Chen, Ronald Cramer, Robbert de Haan, Ignacio Cascudo, Strongly Multiplicative Ramp Schemes from High Degree Rational Points on Curves

Eurocrypt07, Hao Chen, Ronald Cramer, Shafi Goldwasser, Robbert de Haan, Vinod Vaikuntanathan Secure Computation from Random Error Correcting Codes

Crypto06, Hao Chen, Ronald Cramer, Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Chris Peikert is one of the leading experts on lattice cryptography, so I'd tend to believe his judgement of the attacks given his comments to the question. $\endgroup$
    – j.p.
    Sep 6, 2021 at 6:54
  • $\begingroup$ Reputation is not proof. See: en.wikipedia.org/wiki/Nobel_disease $\endgroup$
    – A. Hersean
    Sep 6, 2021 at 10:01
  • $\begingroup$ Of course, it is. I'm not saying that we should convince the result by somewhat reputation. I just want to add some information about the author as of its vacancy. At least, we should not take it as the conclusion from a nobody. $\endgroup$
    – apxf
    Sep 7, 2021 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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