7 ms·
Chapter 16 focuses on post-quantum crypto, including lattices. I see that it (and chapter 17) remains unfinished. Boneh certainly knows lattice tools; it's int
by chrispeel 7y ago
Chapter 16 focuses on post-quantum crypto, including lattices. I see that it (and chapter 17) remains unfinished. Boneh certainly knows lattice tools; it's interesting to me that he nor his students do not seem to be in a hurry to work on lattice-based crypto. Perhaps this is a signal that they aren't worried that a quantum computer capable of cracking current systems will arrive anytime soon.
- nabla9 7y agoGoogle's new quantum supremacy device has 1,113 single-qubit gates and 430 two-qubit gates. Article "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749 shows how to significantly reduce the cost of factoring integers and computing discrete logarithms. Implementation of the efficient device mentioned in the article requires 2.7 billion Toffoli gates for 2048 bit input. It could factor one key in 8 hours. Microprocessors reached that high MOS transistor count less than 10 years ago. For example, 8-core Core i7 Haswell-E has 2.6 billion transistors (2014). If quantum computers follow Moore's law like conventional IC, it will take 40-years before they can factor 2048 bit RSA.
- archgoon 7y ago> Microprocessors reached that high MOS transistor count less than 10 years ago. Note however that quantum computers can potentially benefit from existing lithography processes, so it may not take as long to scale up as we have already developed processes for very small highly integrated circuits.
- adtac 7y agoWe don't need quantum computers to be at microprocessor scale to make 2048-bit RSA factoring groundbreaking. If a quantum computer the size of a car can do it in 8 hours, it's sufficient.
- nabla9 7y agoIt's extremely hard to maintain car sized superposition for 8 hours. The devise itself can be huge, mostly because it's cooled, but the actual quantum state inside is just tiny chip.
- hailwren 7y agoI think, generally, the concern with quantum resistant cryptography is that, like homomorphic encryption schemes, it’s unworkably slow right now.
- jason13579 7y agoNo, it’s not. Some implementations do even perform better than current public key crypto schemes.
- throwawaymath 7y agoWhich post-quantum cryptosystems are more efficient than RSA?
- jason13579 7y agoI did not claim that they outperform RSA in particular and I would not call RSA a state of the art public key cryptosystem. Actually, I would strongly suggest against using RSA without first having a deep dive into the field of number theory. However, for extreme RSA key sizes (e.g. 4096 bit) NewHope does actually outperform RSA and definitely outperforms some ECC counterparts.
- hailwren 7y agoNewHope has not been proven to be quantum resistant. I think researchers generally believe that NewHope will be proven to be quantum resistant, but there is the problem of adapting Micciancio's regular lattice proof to ideal lattices.
- jason13579 7y agoThat’s right, it hasn’t. Just as almost every other candidate in the NIST competition. However, none of the currently employed public key crypto systems has even been proven to be secure against standard computers and they can definitely be broken by a (powerful) quantum computer. So I would still favor taking a scheme that most likely is secure against quantum computing over one that can definitely be broken by it, especially if their performance does not differ too much anymore.