Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum Algorithms for Lattice Problems

eprint.iacr.org

Post reply on HN
Print view View original

21–30 of 127 posts

Re: Quantum Algorithms for Lattice Problems

#21

Post by tptacek »

tux3 wrote: post #18
kyoji wrote: post #10

Earlier quoted context omitted.

Not entirely true, there are other PKE and DSA algorithms that were/are a part of the competition that used problems not related to lattices. However, the lattice-based options were often among the fastest and smallest.

Isogenies vindicated? :)

I know you're kidding but for the benefit of the class isogeny schemes were pulled when their best candidate design turned out to be breakable with a Python script owing to obscure non-cryptographic mathematic research from the 1990s.

I'd expect we're not getting isogenies back. :)

Re: Quantum Algorithms for Lattice Problems

#22

Post by anonymousDan »

j2kun wrote: post #17
troq13 wrote: post #9

Just a bit more improvement and they might be able to use a computer that doesn't exist to break an encrypting scheme nobody uses. Alarming.

Major systems and big companies like Google are already mid-transition to PQC. So it is alarming.

Furthermore this could have implications for fully homomorphic encryption schemes based on lattices. But nonetheless I laughed :)

Re: Quantum Algorithms for Lattice Problems

#23

Post by AnthonyMouse »

j2kun wrote: post #17
troq13 wrote: post #9

Just a bit more improvement and they might be able to use a computer that doesn't exist to break an encrypting scheme nobody uses. Alarming.

Major systems and big companies like Google are already mid-transition to PQC. So it is alarming.

More to the point, the purpose of the encrypting system nobody uses is to have something to use if anybody ever makes the computer that doesn't exist. Now if that happens, what?

Re: Quantum Algorithms for Lattice Problems

#24

Post by rhaps0dy »

ghostway wrote: post #3
ghostway wrote: post #2

From the paper: > Let us remark that the modulus-noise ratio achieved by our quantum algorithm is still too large to break the public-key encryption schemes based on (Ring)LWE used in practice. In particular, we have not broken the NIST PQC standardization candidates. For example, for CRYSTALS-Kyber [BDK+18], the error term is chosen from a small constant range, the modulus is q = 3329, the dimension is n = 256 · k w…

(of course, this doesn't mean we are in the clear -- a polynomial-time algorithm is alarming)

I don't understand your comment in the context of the previous comment you posted. AIUI, the excerpt says "our algorithm only applies when the modulus q is larger than n^2" where n is 2563 or 2566 (I guess?). So the excerpt would be saying that the algorithm does not apply in this case, because 3000 << (256*3)^2. Right?

Re: Quantum Algorithms for Lattice Problems

#25

Post by j2kun »

tptacek wrote: post #21
tux3 wrote: post #18

Earlier quoted context omitted.

Isogenies vindicated? :)

I know you're kidding but for the benefit of the class isogeny schemes were pulled when their best candidate design turned out to be breakable with a Python script owing to obscure non-cryptographic mathematic research from the 1990s. I'd expect we're not getting isogenies back. :)

I was at a conference with some of these folks recently and they stated some glimmer of hope remains for repairing isogeny-based crypto. I guess we'll see.

Re: Quantum Algorithms for Lattice Problems

#27

Post by adgjlsfhk1 »

doomrobo wrote: post #11
tromp wrote: post #8

How does this affect these statements on Wikipedia [1] > some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently. and [2] ? > One class of quantum resistant cryptographic algorithms is bas…

The idea of "appear to be resistant to attack" is an empirical one. When someone says that, they are saying that we simply have not found a good attack against this problem. That can change any day, in principle. Unfortunately, "we don't know of an attack" is about as strong a statement you can make in cryptography, when talking about a fundamental hardness assumption. More verbosely, you'd say "the best known attack…

imo, this isn't quite true. there are a lot of areas where we can say "this looks sufficiently secure for now, but given the rate of advancement in this area in the last decade, we expect it will probably lose a few bits of security in the next decade"

Re: Quantum Algorithms for Lattice Problems

#28

Post by abdullahkhalids »

rhaps0dy wrote: post #24
ghostway wrote: post #3

Earlier quoted context omitted.

(of course, this doesn't mean we are in the clear -- a polynomial-time algorithm is alarming)

I don't understand your comment in the context of the previous comment you posted. AIUI, the excerpt says "our algorithm only applies when the modulus q is larger than n^2" where n is 256 3 or 256 6 (I guess?). So the excerpt would be saying that the algorithm does not apply in this case, because 3000 << (256*3)^2. Right?

If the history of cryptography is any guide, even though this result doesn't break LWE crypto-protocols, it's much more likely now that someone will come up an improvement that will break LWE crypto-protocols. First constructions of algorithms are rarely optimal.

Even though the opposite is possible as well, now that a concrete algorithm has been made. Someone could very well prove that LWE crypto-protocols are secure against some class of algorithms this algorithm belongs to.

Of course, right now, we should just wait for the experts to read the paper and check if there are any problems.

Re: Quantum Algorithms for Lattice Problems

#29

Post by tempaway4785751 »

AnthonyMouse wrote: post #23
j2kun wrote: post #17

Earlier quoted context omitted.

Major systems and big companies like Google are already mid-transition to PQC. So it is alarming.

More to the point, the purpose of the encrypting system nobody uses is to have something to use if anybody ever makes the computer that doesn't exist. Now if that happens, what?

We really need to get people to take really complicated risks that might never come to pass much more seriously. Perhaps someone smart can explain the really complicated risks that might never come to pass to the government that doesn't really look beyond the three year time horizon and get them to allocate some of their money that doesn't really exist to help.

Re: Quantum Algorithms for Lattice Problems

#30

Post by pvg »

tptacek wrote: post #21
tux3 wrote: post #18

Earlier quoted context omitted.

Isogenies vindicated? :)

I know you're kidding but for the benefit of the class isogeny schemes were pulled when their best candidate design turned out to be breakable with a Python script owing to obscure non-cryptographic mathematic research from the 1990s. I'd expect we're not getting isogenies back. :)

breakable with a Python script

The traditional, elegant method of a more civilized age:

Last on the program were Len Adleman and his computer, which had accepted a challenge on the first night of the conference. The hour passed; various techniques for attacking knapsack systems with different characteristics were heard; and the Apple II sat on the table waiting to reveal the results of its labors. At last Adleman rose to speak mumbling something self-deprecatingly about “the theory first, the public humiliation later” and beginning to explain his work. All the while the figure of Carl Nicolai moved silently in the background setting up the computer and copying a sequence of numbers from its screen onto a transparency. At last another transparency was drawn from a sealed envelope and the results placed side by side on the projector. They were identical. The public humiliation was not Adleman‘s, it was knapsack’s.

W. Diffie, The first ten years of public-key cryptography, Proceedings of the IEEE, vol. 76, no. 5, pp. 560-577, May 1988

Post reply on HN