6 ms·

Lattice-based public key schemes are designed to be quantum resistant. So this is a troubling development, because it might indicate that other lattice-based pu

by jamoes 12y ago

Lattice-based public key schemes are designed to be quantum resistant. So this is a troubling development, because it might indicate that other lattice-based public key schemes are vulnerable to similar attacks. It might be very difficult or even impossible to create quantum-proof public key schemes. Fortunately, though, a quantum-proof signature scheme (meaning no encryption or decryption, just signing) has already been developed: Lamport Signatures. These rely on the security if hash algorithms (such as SHA256), which are not weakened by the existence of quantum computing.

api 12y ago
If PKC turned out to be almost impossible post-QC, boy would that ever change the world of computing, networking, pretty much everything. It would mean everything would have to run on pre-shared secret keys. It would also be the absolute end of Bitcoin and derivatives, at least as far as I know.
- nightcracker 12y ago
  I don't think you read the post you replied to. Bitcoin requires secure signing and hashing, which are post-quantum secure (hash functions and Lamport/Merkle signatures).
  - api 12y ago
    I read it. Bitcoin also relies on elliptic curve crypto, which will fall to QC. Without a replacement, the entire concept of cryptocurrency as we currently know it falls.
- tptacek 12y ago
  Practical quantum cryptanalysis is already the end of Bitcoin, which relies on ECC algorithms that will fall to QC. (Maybe you're making the broader statement, that if QC turns out to make all forms of public key crypto insecure, regardless of the hard problem they're based on, then it won't even be possible to design a working alternative to Bitcoin.)
  - sysk 12y ago
    Public keys are only stored as a hash in the blockchain though (assuming no address re-use). Is RIPEMD-160 vulnerable to QC?
    - martinko 12y ago
      Addresses that have been sent from will be vulnerable because their public key will be displayed in the outgoing transaction. One-use addresses will not be vulnerable, as their public keys are indeed stored only as hashes in the blockchain, but the algorithm is not only RIPE, but something like SHA256(RIPEMD-160(SHA256(Public_Key))). I dont know about RIPE, but sha256 should be QC resistant. Thus if you do not reuse addresses you should be safe against QC.
- jamoes 12y ago
  > It would also be the absolute end of Bitcoin and derivatives, at least as far as I know. Not really, because bitcoin only relies on the signature aspect of PKC. So, bitcoin could move over to Lamport signatures, which are not affected by quantum computing. Lamport signatures are larger than ECDSA signatures, so blockchain bloat would be an issue. But presumably by then hard drives and all other computing specs would have increased substantially. Here's an interesting article by Vitalik Buterin which explains how the transition could take place: http://bitcoinmagazine.com/6021/bitcoin-is-not-quantum-safe-and-how-we-can-fix/ http://bitcoinmagazine.com/6021/bitcoin-is-not-quantum-safe-...
  - glomph 12y ago
    Could you describe how such a cross over could happen smoothly? Seems like there would be mass panic, all the mining rigs would have to re assemble etc.
    - api 12y ago
      That's really the problem I foresee. It'd be extremely hard to pull off without a bank run or a speculative frenzy. Financial markets are unbelievably skittish about uncertainties.
    - im3w1l 12y ago
      Announce a transition time a few years into the future so the miners don't get a capital loss. Code clients to switch over to the new algorithm at the transition time. When the transition finally comes, even those with slightly out of date client will switch over, since it was coded far in advance.
      - glomph 12y ago
        Wouldn't this require quantum computing to be developed relatively gradually and in the open? Seems likely that a gov or company will suddenly reveal it or have it exposed.
        12y ago
higherpurpose 12y ago
I guess it's a good thing that Dan Bernstein (one of the early evangelists for PQ crypto [1]) has been focusing on (pretty) fast code-based quantum-resistant cryptography lately, instead of lattice-based crypto: http://cr.yp.to/talks/2013.06.12/slides-djb-20130612-a4.pdf http://cr.yp.to/talks/2013.06.12/slides-djb-20130612-a4.pdf http://binary.cr.yp.to/mcbits-20130616.pdf http://binary.cr.yp.to/mcbits-20130616.pdf [1] http://pqcrypto.org/ http://pqcrypto.org/

by jamoes 12y ago

api 12y ago

If PKC turned out to be almost impossible post-QC, boy would that ever change the world of computing, networking, pretty much everything. It would mean everything would have to run on pre-shared secret keys. It would also be the absolute end of Bitcoin and derivatives, at least as far as I know.

nightcracker 12y ago
I don't think you read the post you replied to. Bitcoin requires secure signing and hashing, which are post-quantum secure (hash functions and Lamport/Merkle signatures).
- api 12y ago
  I read it. Bitcoin also relies on elliptic curve crypto, which will fall to QC. Without a replacement, the entire concept of cryptocurrency as we currently know it falls.
tptacek 12y ago
Practical quantum cryptanalysis is already the end of Bitcoin, which relies on ECC algorithms that will fall to QC. (Maybe you're making the broader statement, that if QC turns out to make all forms of public key crypto insecure, regardless of the hard problem they're based on, then it won't even be possible to design a working alternative to Bitcoin.)
- sysk 12y ago
  Public keys are only stored as a hash in the blockchain though (assuming no address re-use). Is RIPEMD-160 vulnerable to QC?
  - martinko 12y ago
    Addresses that have been sent from will be vulnerable because their public key will be displayed in the outgoing transaction. One-use addresses will not be vulnerable, as their public keys are indeed stored only as hashes in the blockchain, but the algorithm is not only RIPE, but something like SHA256(RIPEMD-160(SHA256(Public_Key))). I dont know about RIPE, but sha256 should be QC resistant. Thus if you do not reuse addresses you should be safe against QC.
jamoes 12y ago
> It would also be the absolute end of Bitcoin and derivatives, at least as far as I know. Not really, because bitcoin only relies on the signature aspect of PKC. So, bitcoin could move over to Lamport signatures, which are not affected by quantum computing. Lamport signatures are larger than ECDSA signatures, so blockchain bloat would be an issue. But presumably by then hard drives and all other computing specs would have increased substantially. Here's an interesting article by Vitalik Buterin which explains how the transition could take place: http://bitcoinmagazine.com/6021/bitcoin-is-not-quantum-safe-and-how-we-can-fix/ http://bitcoinmagazine.com/6021/bitcoin-is-not-quantum-safe-...
- glomph 12y ago
  Could you describe how such a cross over could happen smoothly? Seems like there would be mass panic, all the mining rigs would have to re assemble etc.
  - api 12y ago
    That's really the problem I foresee. It'd be extremely hard to pull off without a bank run or a speculative frenzy. Financial markets are unbelievably skittish about uncertainties.
  - im3w1l 12y ago
    Announce a transition time a few years into the future so the miners don't get a capital loss. Code clients to switch over to the new algorithm at the transition time. When the transition finally comes, even those with slightly out of date client will switch over, since it was coded far in advance.
    - glomph 12y ago
      Wouldn't this require quantum computing to be developed relatively gradually and in the open? Seems likely that a gov or company will suddenly reveal it or have it exposed.
      - 12y ago

higherpurpose 12y ago

I guess it's a good thing that Dan Bernstein (one of the early evangelists for PQ crypto [1]) has been focusing on (pretty) fast code-based quantum-resistant cryptography lately, instead of lattice-based crypto: http://cr.yp.to/talks/2013.06.12/slides-djb-20130612-a4.pdf http://cr.yp.to/talks/2013.06.12/slides-djb-20130612-a4.pdf http://binary.cr.yp.to/mcbits-20130616.pdf http://binary.cr.yp.to/mcbits-20130616.pdf [1] http://pqcrypto.org/ http://pqcrypto.org/