useafterfree

I read recently that NSA has distanced itself from lattice based crypto. I can't find the article now though of course. Is this true? Can you say why? What approaches do you think will be the future of quantum-resistant crypto?

https://www.wired.com/2015/09/tricky-encryption-stump-quantum-computers/

What do you guys think of the importance of provably secure schemes? Will they ever be practical and used in real world applications?

Finally make your response an even number of characters if Diffie-Hellman has been practically broken, odd if it has not. Thank you.

Exactly as I suspected

Thanks for the answers! And yea I know that article just provided some background on lattice based approaches. I'm beginning to think I imagined the article I am thinking of. It was about NSA removing lattice crypto from some future standards proposal I think?

https://en.m.wikipedia.org/wiki/Provable_security

In the cryptology section it defines what provable security means, and it is similar to what you said. I think the main difference between normal cryptographic and ones that are truly "proven secure" is a mathematical proof involving the exact algorithm, whereas the security of most practical algorithms is based on an idealization. Under this definition I don't think AES would be proven secure. In the article below there are some proven secure hash functions that also list some downsides of these requirements

https://en.m.wikipedia.org/wiki/Security_of_cryptographic_hash_functions

While this was in 2010, but the Stuxnet virus included 2 forged/stolen digital signatures by Taiwanese chip manufacturers. Either their signing keys were physically stolen or they were cracked.

Wow I had not heard of that. I'll have to look into that. I was also thinking of the precomputation attacks that were discovered

https://www.schneier.com/blog/archives/2015/10/breaking_diffie.html

This would be mostly useless now but I wonder if there are other attacks like it. I have to keep up with crypto stuff more, its so fascinating.

The class of problems solved in polynomial time by Quantum algorithms is called BQP and contains P. Therefore if someone showed there are NP problems " for which no polynomial time quantum computing algorithm can exist" then this would prove P != NP. This has not yet been done so we can also not answer your first question "is it possible that a quantum computing algorithm could be found with sufficient to solve any NP problem (P=NP)?"

Sort of. Computer Scientists are basically certain that P != NP.

http://www.scottaaronson.com/blog/?p=122

Aaronson's blog is a goldmine if you are interested in these things. He is very good at being a buzzkill when it comes to people overselling the capabilities of Quantum Computers, while still demonstrating all the things that make them fascinating.

Thanks for the response. I think I imagined that first statement now. The paper you cite approaches the new recommendation with skepticism. They lay out some reasons to believe that the current ECC curves are not weak and also that the NSA has not made a breakthrough on the quantum front that would endanger ECC

The article [49] concludes that “the documents provided by Snowden suggest that the NSA is no closer to success [in quantum computation] than others in the scientific community.”

They seem to conclude that the real reason the NSA wants to transition to PQC is not the stated one

If practical quantum computers are at least 15 years away, and possibly much longer, and if it will take many years to develop and test the proposed PQC systems and reach a consensus on standards, then a long time remains when people will be relying on ECC. But the NSA’s PQC announcement makes it clear that improved ECC standards (for example, an updated list of recommended curves) are not on the Agency’s agenda.

Instead they list other possible motives with explanations

1. The NSA can break PQC

2. The NSA can break RSA

3. The NSA was thinking primarily of government users.

4. The NSA believes that RSA-3072 is much more quantum- resistant than ECC-256 and even ECC-384.

5. The NSA is using a diversion strategy aimed at Russia and China.

6. The NSA has a political need to distance itself from ECC

So you seem to support 4 then? Is there anything else clarifying you can say about this. Probably not I know, but do you have any personal criticisms of the arguments in the paper? The authors themselves seem to be pretty skeptical about any of the explanations they have offered (hence the paper title I guess). But 6 is written most emphatically.

This suggests that the main considerations might not have been technical at all, but rather Agency-specific — that is, related to the difficult situation the NSA was in following the Snowden leaks. The loss of trust and credibility from the scandal about Dual EC_DRBG was so great that the NSA might have anticipated that anything further it said about ECC standards would be mistrusted.

I assume you disagree with this explanation, but what compelling reason do citizens have to trust the standards endorsed by the NSA? How can we know if PQC standards will not suffer the same backdoor attempts (as explored in 1)?

One aspect with lattice based crypto that I think is a selling point is the worst-case hardness, which says that breaking the crypto in any case implies that you can break the other long-standing problem in the worst case.

That sounds really interesting I need to read up on it more. I've mostly read popular accounts. Again thanks for the response!

P.S.

$ echo $response | wc
      8     305    1802

I read you loud and clear. *wink*

Edit: my count doubles the newlines, same result