LWE based PQC algorithm can be broken?

[BongHo Kang]

Dear PQC Forum,

Recently, I have found a paper that the LWE based PQC algorithms can be broken when applying the divide-and-conquer strategy with the help of quantum computers according to the paper.

"Quantum solvability of noisy linear problems by divide-and-conquer strategy"

http://arxiv-export-lb.library.cornell.edu/pdf/1908.06229

Could you somebody can answer whether there is a possibility of being broken regarding the lattice based algorithms such as NTRU (Ring-LWE), Kyber(LWE), and SABER (LWR)?

If there is a possibility, what would be the resolution?

Regards,

BongHo Kang.

[Christopher J Peikert]

Hello,

On Tue, May 3, 2022 at 4:02 AM BongHo Kang <bongh...@gmail.com> wrote:

Dear PQC Forum,

Recently, I have found a paper that the LWE based PQC algorithms can be broken when applying the divide-and-conquer strategy with the help of quantum computers according to the paper.

This paper does not claim anything about breaking LWE or PQC algorithms.

The problem considered in the paper is not LWE; instead, it is one where “noisy linear samples” are given in *quantum superposition* (by contrast, LWE samples are purely classical). It has been known for several years that such problems can be easy for quantum computers; see references [7,8] in the paper (and there might be even earlier results).

Sincerely yours in cryptography,

Chris

[BongHo Kang]

Dear Professor Chris,

I really appreciate your quick response and clear explanation.

I see it is known issue and not related to LWE or PQC algorithms.

Regards,

BongHo Kang.