4 ms·

The article mentions this problem, and there seems to be a concept emerging that is called "volume": Basically, how complex the algorithm can be you can run on

The article mentions this problem, and there seems to be a concept emerging that is called "volume": Basically, how complex the algorithm can be you can run on a quantum computer, taking into account the number of qubits, their error rate, the stability, ...

blattimwind 9y ago
I hope that we see some analysis done on this subject in the near future, because the rising uncertainty regarding current public-key tech is starting to get difficult for certain businesses.
- anfilt 9y ago
  There is a Public crypto system based off error correcting codes that is quantumly secure. It's the McEliece cryptosystem, it's about as old as RSA. However, the key sizes are in 10's of thousands to 100's of thousands of bits. From my reading most crytographers think it's is secure. So if you need it now. You could probably get away with using it. However, one should have a decent explanation to why use a less well known algorithm. It's probably had less eyes looking at so a major flaw/attack could exists, but it's not if one does exist.
  - dsacco 9y ago
    McEliece has had significant cryptanalytic attention since the 70s, when it was first invented. In fact, it’s probably the most well studied post-quantum proposal, and it’s not really waiting on any further cryptanalysis. It’s currently considered secure (with binary Goppa codes) and has modes for both encryption and digital signatures via Neiderreiter, but it doesn’t support key exchange. The real issue, as you touched on, is key size. There are production deployments of the cryptosystem, but it’s actually a bit worse than your numbers if you’re looking for post-quantum resistance. In the post-quantum secure setting, McEliece uses public keys that have an upper bound of over 1MB (around 8.5 million bites specifically) in order to achieve 128-bit security. Fortunatly McEliece is not the only proposal we have, and error correcting codes aren’t the only computational problem being studied. We also have credible proposals from lattices, hashes, multivariate polynomial equations and (most recently) supersingular elliptic curve isogenies.
    - blattimwind 9y ago
      From my research so far it looks like SIDH is the most promising candidate to upgrade existing protocols (relatively congruent to ECDH; "small" key sizes). For proprietary protocols the "newiness" of pq-crypto doesn't seem to be a big problem per se, just use curve hardening (kdf(ECDH || pq-kex)) in case the pq-crypto is broken (either due to implementation defects or cryptanalysis).
      - dsacco 9y ago
        It depends on the application. SIDH is attractive because it doesn’t throw out decades of elliptic curve mathematics because of the spectre of quantum computers. The mathematics is a bit more familiar if you squint at it, though working with isogenies themselves is still very different from normal elliptic curve cryptography. But more importantly, a codebase that implements elliptic curve arithmetic can port much of that functionality to implement SIDH. And yes - SIDH is also attractive because of the small key sizes. But it’s also significantly slower than lattice-based key exchange using something like Learning With Errors (LWE). In practice the decision comes down to time versus space constraints: if your application is space-poor and time-rich, SIDH is a good proposal for key exchange. This looks especially nice in the context of IoT devices. But if your application is space-rich and time-poor, SIDH looks less attractive in favor of other options.
- dsacco 9y ago
  This is a very active area of research in theoretical cryptography, and has been for over a decade. It’s an area that I myself work in. The uncertainty is not quite what you think: researchers more or less know what will happen to public-key cryptography, and to which cryptosystems. We also have credible proposals for encryption, key exchange and digital signatures. The uncertainty is when quantum computers will be practical, not what will happen when they are. Contemporary research is predominantly concerned with improving computability efficiency or security proofs for underlying complexity characteristics.
  - blattimwind 9y ago
    > The uncertainty is when quantum computers will be practical, not what will happen when they are. That's what I meant above; I apologize for I should have been more clear in my wording.
    - dsacco 9y ago
      Ah, no worries. Post-quantum cryptography has a reputation for being somewhat excessively theoretical (which to be fair is a reasonable argument). But there are benefits other than post-quantum security. For example, lattice problems can provide security according to worst-case hardness, whereas factoring problems can only provide average-case hardness. In other words, for some lattice problems, we can prove that breaking the cryptosystem is equivalent to breaking every instance of the lattice problem, but factoring problems only guarantee that breaking the cryptosystem is equivalent to breaking a subset of problems from some distibution. The former is a much stronger security assumption (though in practice this comes with its own set of challenges). It’s an exciting area of research.

blattimwind 9y ago

I hope that we see some analysis done on this subject in the near future, because the rising uncertainty regarding current public-key tech is starting to get difficult for certain businesses.

anfilt 9y ago
There is a Public crypto system based off error correcting codes that is quantumly secure. It's the McEliece cryptosystem, it's about as old as RSA. However, the key sizes are in 10's of thousands to 100's of thousands of bits. From my reading most crytographers think it's is secure. So if you need it now. You could probably get away with using it. However, one should have a decent explanation to why use a less well known algorithm. It's probably had less eyes looking at so a major flaw/attack could exists, but it's not if one does exist.
- dsacco 9y ago
  McEliece has had significant cryptanalytic attention since the 70s, when it was first invented. In fact, it’s probably the most well studied post-quantum proposal, and it’s not really waiting on any further cryptanalysis. It’s currently considered secure (with binary Goppa codes) and has modes for both encryption and digital signatures via Neiderreiter, but it doesn’t support key exchange. The real issue, as you touched on, is key size. There are production deployments of the cryptosystem, but it’s actually a bit worse than your numbers if you’re looking for post-quantum resistance. In the post-quantum secure setting, McEliece uses public keys that have an upper bound of over 1MB (around 8.5 million bites specifically) in order to achieve 128-bit security. Fortunatly McEliece is not the only proposal we have, and error correcting codes aren’t the only computational problem being studied. We also have credible proposals from lattices, hashes, multivariate polynomial equations and (most recently) supersingular elliptic curve isogenies.
  - blattimwind 9y ago
    From my research so far it looks like SIDH is the most promising candidate to upgrade existing protocols (relatively congruent to ECDH; "small" key sizes). For proprietary protocols the "newiness" of pq-crypto doesn't seem to be a big problem per se, just use curve hardening (kdf(ECDH || pq-kex)) in case the pq-crypto is broken (either due to implementation defects or cryptanalysis).
    - dsacco 9y ago
      It depends on the application. SIDH is attractive because it doesn’t throw out decades of elliptic curve mathematics because of the spectre of quantum computers. The mathematics is a bit more familiar if you squint at it, though working with isogenies themselves is still very different from normal elliptic curve cryptography. But more importantly, a codebase that implements elliptic curve arithmetic can port much of that functionality to implement SIDH. And yes - SIDH is also attractive because of the small key sizes. But it’s also significantly slower than lattice-based key exchange using something like Learning With Errors (LWE). In practice the decision comes down to time versus space constraints: if your application is space-poor and time-rich, SIDH is a good proposal for key exchange. This looks especially nice in the context of IoT devices. But if your application is space-rich and time-poor, SIDH looks less attractive in favor of other options.
dsacco 9y ago
This is a very active area of research in theoretical cryptography, and has been for over a decade. It’s an area that I myself work in. The uncertainty is not quite what you think: researchers more or less know what will happen to public-key cryptography, and to which cryptosystems. We also have credible proposals for encryption, key exchange and digital signatures. The uncertainty is when quantum computers will be practical, not what will happen when they are. Contemporary research is predominantly concerned with improving computability efficiency or security proofs for underlying complexity characteristics.
- blattimwind 9y ago
  > The uncertainty is when quantum computers will be practical, not what will happen when they are. That's what I meant above; I apologize for I should have been more clear in my wording.
  - dsacco 9y ago
    Ah, no worries. Post-quantum cryptography has a reputation for being somewhat excessively theoretical (which to be fair is a reasonable argument). But there are benefits other than post-quantum security. For example, lattice problems can provide security according to worst-case hardness, whereas factoring problems can only provide average-case hardness. In other words, for some lattice problems, we can prove that breaking the cryptosystem is equivalent to breaking every instance of the lattice problem, but factoring problems only guarantee that breaking the cryptosystem is equivalent to breaking a subset of problems from some distibution. The former is a much stronger security assumption (though in practice this comes with its own set of challenges). It’s an exciting area of research.