8 ms·

Bitcoin’s race to outrun the quantum computer

73 points by benmunster1 7y ago

dnprock 7y ago
I get that quantum computer can run faster with more states. But can someone with quantum computing experience explain how quantum computer can address exponential computation? Does it reduce exponential computation into polynomial? My answer to the above question is no. Assuming a quantum computer has 10 states. Its running time for exponential algorithms is still exponential. A simple example: 2^10 is about 10^3. Still exponential.
newbrict 7y ago
Problem includes far more than bitcoin.. Your bank for example
- zazagura 7y ago
  Not really. Your bank (and the whole web) can easily switch to a quantum resistant encryption algo when time comes. For Bitcoin this is much harder.
  - rolltiide 7y ago
    Its not much harder for bitcoin... The community will just do a blockchain snapshot of balances at an agreed upon block and start a new distributed ledger with quantum resistant encryption Snapshots have been done hundreds of times
    - xiphias2 7y ago
      It's easy to add a quantum resistant algorithm, but as it's much more expensive to verify and takes more block space, the transaction fees will be much higher. Transitioning is a huge political problem as well.
      - londons_explore 7y ago
        It'll be politically easy. Nobody wants someone else able to steal their money.
    - zazagura 7y ago
      Everybody will need new private keys. What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? Do you set a threshold day, after which all unclaimed coins are just marked destroyed forever? If not, how do you know someone claiming some coins didn't use a quantum computer to get the key?
      - gruez 7y ago
        >Do you set a threshold day yeah pretty much. >What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? If those coins hasn't been touched for decades, despite widespread announcements of pre-quantum cryptography (presumably it wouldn't happen overnight), it's safe to say that nobody is going to claim them.
        rolltiide 7y ago
        Dont treat any address differently
      - rolltiide 7y ago
        You wont know that, you will provide the tools and also new accounts will have assurance and regenerate confidence in the system So we have moved from concluding that bitcoin use is an irreparably flawed concept to a method of maintaining viability of the concept
    - sroussey 7y ago
      > The community will just do ... This is the funny thing about decentralized services. They require centralized action. Not saying it is good or bad, but it is... different.
      - rolltiide 7y ago
        It requires community consensus thats the opposite of centralized Anyone can make a snapshot, assigning value to it is not centralized
        sroussey 7y ago
        I said centralized action. Community consensus sounds nicer, but simultaneous action is required. I don’t imagine this is other settings... “I only do breaking changes on my api so let’s have everyone change their client at midnight”. Imagine if we all changed implementations of SQL at once! Actually, we changed the meaning of the $() function inside the devtools console across all browsers at the same time. That was fun. :)
        rolltiide 7y ago
        No thats not necessary. People just add flags in their mining protocol that only trigger when a threshold is reached. The last Segwit changes needed a percent change of closer to 90% just to trigger the next change. We are only assuming that consensus would be reached quickly given the scenario presented. It would be irresponsible to design it to need simultaneous action. People would have to considering to stop using the bitcoin network for X,000 blocks while consensus is being reached, and only until it is reached.
rtempaccount1 7y ago
Whilst Quantum computing is an interesting topic, gotta say I think bitcoin's challenges are far more mundane and pressing that that. No.1 challenge is how to stop centralized exchanges from extensive market manipulation. Decentralized crypto currencies are never going to achieve their goals, whilst players like Bitfinex and Tether are in a position to "print" unlimited amounts of money and use them to purchase coins like BTC.
krastanov 7y ago
Just to be clear, this has barely anything to do with any crypto-currency organization. It is a really regrettable framing for an event that should be of great interest to anyone dealing with cryptography, not just the fairly restricted group of crypto-currentcy enthusiasts. If scalable quantum computers can be built (which seems probable, as we are progressing fast in the number of qubits we can keep together), then certain restricted types of public key encryption will be broken by quantum hardware (all currently used public key encryption actually). We know other public key encryption algorithms exist that can run on classical computers and still not be broken by quantum computers. In many ways they are less tested and less practical, so for a while NIST has been sponsoring the development of such quantum-resistant running-on-classical-computers public-key algorithms. The usual name for this is post-quantum encryption.
- olliej 7y ago
  That list is still going though I don’t have it handy (I’ll try to update with the mailing list). There are a number of problems that are well established with strong security proofs vs classical and quantum algorithms - the problem is that the key and message sizes are fairly terrible for practice currently. On the plus side all the current symmetric ciphers are still pretty solid against quantum machines (Grover’s search is a sqrt improvement so would simply require a doubling in key size, but I suspect in practice not necessary)
- Causality1 7y ago
  We seem to be getting better at using quantum computers for hard math. What I'm curious about is when we'll be able to use them for easy math. How many qubits do we need to run Doom Quantum?
  - krastanov 7y ago
    Quantum computers are (conjectured to) outperform classical computers in a very restricted set of problems. These problems happen to be extremely important (e.g. protein folding and some forms of linear algebra), but for tasks that are already efficiently solved by classical computers you probably will never use a quantum computer (maybe in many decades this will change, when it becomes as "trivial" to construct quantum CPUs as it is to construct classical CPUs)
lixtra 7y ago
> Take the Bitcoin blockchain: an unencrypted public key is sent along with every bitcoin transaction, and left unencrypted during the time it takes for the network to confirm the block, around ten minutes. My understanding is that it remains unencrypted forever. That’s why it is a public key. As long as the coins are not moved to another account that public key stays a valuable target. Edit: As DennisP pointed out my understanding was wrong and indeed only the hash of the target is published until you make an transaction from an account.
- esotericn 7y ago
  Nitpick: What people like to call "Satoshi's coins" were actually mined in transactions to pubkeys rather than to pubkey hashes. Early Bitcoin transactions did not use addresses. Example from block 1: https://www.blockchain.com/btc/tx/0e3e2357e806b6cdb1f70b54c3.. https://www.blockchain.com/btc/tx/0e3e2357e806b6cdb1f70b54c3.... You'll see at the bottom that the opcode is a PUSH / CHECKSIG rather than the later DUP / HASH160 / PUSH / EQUALVERIFY / CHECKSIG format. So this isn't true. (blockchain.info derives an address but actually the pubkeys are right there in plain sight. Have at it!) Most transactions are indeed made to pubkey hashes though, yes.
- RandomBacon 7y ago
  So then if Satoshi destroyed the private keys instead holding on to them just in case for an event like this, it's possible that someone might take the million or so BTC just sitting around? Depending on how easy it is, all those addresses that were abandoned containing 50 BTC are also up for grabs. Would a coin without public addresses be better suited against such future?
  - DennisP 7y ago
    Not if Satoshi's coins have never moved. A bitcoin address is a hash of a public key. The public key isn't revealed until the first time funds are transferred out of that address.
    - RandomBacon 7y ago
EGreg 7y ago
This is a general problem with public keys, not just Bitcoin!! One of the problems with current PKI is weakness in the face of quantum computers, leading to a new crop of algorithms being submitted to NIST, etc. I wanted to ask whether the following simple scheme, based just on cryptographic hashes, can be used CONFIDENTLY, SECURELY and RELIABLY in many situations where Assymetric Key cryptography is used today, and in many others too, such as providing provably random polling etc. It is very similar to a One Time Pad but uses a cryptographic hash function to generate the OTP codes. Here is the scheme: Everyone generates a random private key K[p] and store it just like any assymetric private key (encrypted with some non-stored derived key). They use any cryptographic hash function that hasn’t had a serious preimage attack (perhaps even MD5?), hash it n (eg 10,000,000) times to get h[p][n], and publicly commit to that number. This is like a public key. The hashes are long enough that it’s infeasible to reverse them. Key strengthening can be achieved by jumping a few onion layers between transactions. If you start running out then you post a new public key, signed with one of your remaining onion layer codes. Any verifiers store the original public key per participant, and then can replace them with the new public key if it was properly signed by the old one, etc. Use case: generating provably random numbers by mutually distrusting parties Participants they gradually reveal their hashes, one onion layer per transaction. Each provably random seed is a function of the alphabetically smallest/largest three of those hashes at the next onion layer. If not all of them reveal the hashes in time, they gossip, verify and agree on which ones are the smallest/largest three before some cutoff point like “most reported that most reported”. That leaves tons of bits of entropy coming from everyone! Use case: Authenticator Apps The hash h[p][n+1] would be a hash of some substring of h[p][n] with enough bits that finding all chosen preimages (by an eavesdropper of the previous code) would be infeasible in advance. Perhaps 10 alphanumeric characters is enough. Also when displaying the code to enter, the authenticator app can tell the user a number from 1-100 indicating to the verifier how many onion layers to peel, making it harder to precompute the preimages. Or the user would have to enter the entire hash via the network-connected computer scanning a QR code, NFC or something. From a security standpoint, this method seems superior to the HOTP and TOTP schemes used in authenticator apps today, since there is no need to trust the verifier with any secret keys (https://www.ietf.org/rfc/rfc4226.txt https://www.ietf.org/rfc/rfc4226.txt) Also there is no need to sychronize clocks, since the client simply lets the server know how many times to run the hash, and increments that number every time. Use case: Signing Payloads Participants reveal a payload and commit to an HMAC signature by using cryptographic key at the next onion level, which at that point would be known only to them. All these signatures are collected into a blockchain block / merkle tree timestamp / similar thing, and it is sent to the participant before they reveal the onion key they used to sign it. Use case: Off the Record Messaging The Blockchain or Merkle tree is private between a few parties only, so once the next onion level is revealed, no participant can prove the payload was generated by a given participant, since all the onion hashes were known, any of them could generate a new valid tree with any payload history. They can only prove it to each other, or given enough “witnesses” attest to that tree, people might trust then on the basis of consensus of (presumably) mutually distrusting parties, but that’s not the same thing as cryptographic proof. But that is true of any OTR conversation. Use case: Restoring Access This can be used instead of Shamir Secret Key sharing. The server would have to store keys for every participant, and M of N participants would just sign that they approve authorization of some new session, some new key, or whatever. These signatures could be easily checked by anyone who has the public keys of the M participants who signed it. Use case: Decrypting payloads Not sure how one would do this one, to be honest. With PKI, someone could encrypt a payload that can only be decrypted by a private key holder. I see how to do signatures and HMAC, but not the other way.
jchanimal 7y ago
Finally a good use-case for bitcoin: a bounty for the first quantum computer to crack it.
- anaolykarpov 7y ago
  That bounty is currently at 185 billion USD. Of course, it would be pretty difficult to sell all the bitcoins without slippage, but I guess one could cash in at least several tens of millions.
- travisoneill1 7y ago
  Not really. BTC has no value other than its ability to be exchanged for USD. If BTC is cracked no one will trade their USD for it anymore and it will be worthless.
  - rolltiide 7y ago
    The first person to assume custody of a large amount of bitcoin will sell and be incredibly rich They can siphon off a lot before other people catch on to people’s complaints and realize the best practices were followed
  - toss1 7y ago
    Yes, but anyone smart enough to run a quantum computer to solve the private keys and steal bitcoin is also likely to be smart enough to first examine the blockchain for balances that would not get complained about. Apparently, something like 20% of all BTC is just stranded inadvertently lost or destroyed keys -- starting with 'accounts' after the closely watched genesis block, but which have seen no transactions for maybe 5-8 years should net a lot of funds without being noticed.
ddtaylor 7y ago
It's worth mentioning that Bitcoin addresses aren't exposed on the blockchain as public keys, but hashes of the public keys. If you want to steal the coins you'll need to turn ripemd160(sha256(sha256(publicKey))) into a private key. Good luck.
- DennisP 7y ago
  Yes, but the public key is exposed when you send from that address. If a quantum computer is quick enough, it could get your private key and issue its own transaction, racing you to get into a block.
  - gruez 7y ago
    Cracking a public key in 10 minutes is much harder than cracking a public key (at all). Considering we haven't cracked anything yet, I wouldn't be worried about that. Also, if you're transferring thousands of bitcoin and want to be safe, you could always privately send it to a miner rather than broadcasting it. In that case the tx would have 1 confirmation before the the public knows about it, requiring them to also pull off a 50% attack.
    - deleted 7y ago
      [deleted]
    - DennisP 7y ago
      A QC factors the current public key algorithms in constant time. More qubits just means you can factor bigger keys. How big that constant is will depend on how the QC works. Sending privately to a miner would help, but you'd end up with a very centralized system since you would want to send to the biggest miner, to minimize the time until that miner produces a block. You can't have miners sharing the transaction, even privately among themselves, since if they did that then one of them could have a QC and you wouldn't have any way to know who stole your money.
  - sroussey 7y ago
    It doesn't need to be quick if you still have coins at that address.
anm89 7y ago
"The amount of time the universe itself has left—around 0.65 billion billion years." Is this true?? I've never heard this claimed before.
- Mtinie 7y ago
  I’ve never seen it framed that way, but they may be referencing the estimated timeframe for the “heat death” of the universe: https://en.m.wikipedia.org/wiki/Heat_death_of_the_universe https://en.m.wikipedia.org/wiki/Heat_death_of_the_universe
  - anm89 7y ago
    Yeah that was my assumption but I've never seen that specific time frame proposed and it just seems like the kind of thing I would have heard of if it was a know fact.
- mensetmanusman 7y ago
  You can estimate this because there is a known amount of energy around in the visible universe (energy, mass, etc.). We know from inflation that this number changes at a given rate. We also know that time and entropy are connected, so when entropy of the known universe is at the maximum, it would be essentially meaningless to say time could continue, i.e ‘the end of time.’
johnwheeler 7y ago
What a deceptive article. They take a crypto conference happening at a prestigious institution and sprinkle in some bitcoin punditry to make them seem related.
bhouston 7y ago
Will breaking classic computer public key encryption reveal any secrets that were encoded prior to them being obsolete? Should we be recording encrypted streams and saving them for a few years until we can break them? Is there any value in that?
- sroussey 7y ago
  What do you think the NSA is doing? The public blockchains make all this more feasible since they have the community keep the data around in original state for them! So much cheaper than recording SSL/TLS traffic, for example. Also that is why they would find it important to exfiltrate the data from a company (or government) before it can be re-encrypted with something better.
- tialaramex 7y ago
  Yes, if this ever works and is affordable. Suppose our adversaries have a machine which can do Shor's algorithm at the scale needed to break modern public keys for say $1M and an hour, and they have been recording encrypted sessions. For sessions encrypted using RSA key exchange, it is enough for them to spend $1M and wait one hour and then they can decrypt everything that they've recorded, using one particular key. So e.g. a typical HTTPS site only has one key for months or even years, if they've recorded the encrypted data they can read all of it for $1M. Where Forward Secrecy (e.g. ECDHE) was used, the cost is $1M (and an hour) for each session, because the keys change each time so each fresh session needs the expensive algorithm.
jeromebaek 7y ago
> Ah, but with the right quantum computer, able to process information at speeds exponentially faster than today’s supercomputers? Suddenly, what seems uncrackable becomes child’s play, able to be broken in under 10 minutes. Cringe. Quantum computers are not "able to process information at speeds exponentially faster than today's supercomputers". They're able to solve a very specific subset of problems which are hard for classical computers. A very specific subset, called BQP, mostly having to do with finding prime factors. NP hard problems are probably uncrackable with quantum computers.

73 points by benmunster1 7y ago

I get that quantum computer can run faster with more states. But can someone with quantum computing experience explain how quantum computer can address exponential computation? Does it reduce exponential computation into polynomial? My answer to the above question is no. Assuming a quantum computer has 10 states. Its running time for exponential algorithms is still exponential. A simple example: 2^10 is about 10^3. Still exponential.

newbrict 7y ago

Problem includes far more than bitcoin.. Your bank for example

zazagura 7y ago
Not really. Your bank (and the whole web) can easily switch to a quantum resistant encryption algo when time comes. For Bitcoin this is much harder.
- rolltiide 7y ago
  Its not much harder for bitcoin... The community will just do a blockchain snapshot of balances at an agreed upon block and start a new distributed ledger with quantum resistant encryption Snapshots have been done hundreds of times
  - xiphias2 7y ago
    It's easy to add a quantum resistant algorithm, but as it's much more expensive to verify and takes more block space, the transaction fees will be much higher. Transitioning is a huge political problem as well.
    - londons_explore 7y ago
      It'll be politically easy. Nobody wants someone else able to steal their money.
  - zazagura 7y ago
    Everybody will need new private keys. What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? Do you set a threshold day, after which all unclaimed coins are just marked destroyed forever? If not, how do you know someone claiming some coins didn't use a quantum computer to get the key?
    - gruez 7y ago
      >Do you set a threshold day yeah pretty much. >What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? If those coins hasn't been touched for decades, despite widespread announcements of pre-quantum cryptography (presumably it wouldn't happen overnight), it's safe to say that nobody is going to claim them.
      - rolltiide 7y ago
        Dont treat any address differently
    - rolltiide 7y ago
      You wont know that, you will provide the tools and also new accounts will have assurance and regenerate confidence in the system So we have moved from concluding that bitcoin use is an irreparably flawed concept to a method of maintaining viability of the concept
  - sroussey 7y ago
    > The community will just do ... This is the funny thing about decentralized services. They require centralized action. Not saying it is good or bad, but it is... different.
    - rolltiide 7y ago
      It requires community consensus thats the opposite of centralized Anyone can make a snapshot, assigning value to it is not centralized
      - sroussey 7y ago
        I said centralized action. Community consensus sounds nicer, but simultaneous action is required. I don’t imagine this is other settings... “I only do breaking changes on my api so let’s have everyone change their client at midnight”. Imagine if we all changed implementations of SQL at once! Actually, we changed the meaning of the $() function inside the devtools console across all browsers at the same time. That was fun. :)
        rolltiide 7y ago
        No thats not necessary. People just add flags in their mining protocol that only trigger when a threshold is reached. The last Segwit changes needed a percent change of closer to 90% just to trigger the next change. We are only assuming that consensus would be reached quickly given the scenario presented. It would be irresponsible to design it to need simultaneous action. People would have to considering to stop using the bitcoin network for X,000 blocks while consensus is being reached, and only until it is reached.

rtempaccount1 7y ago

Whilst Quantum computing is an interesting topic, gotta say I think bitcoin's challenges are far more mundane and pressing that that. No.1 challenge is how to stop centralized exchanges from extensive market manipulation. Decentralized crypto currencies are never going to achieve their goals, whilst players like Bitfinex and Tether are in a position to "print" unlimited amounts of money and use them to purchase coins like BTC.

krastanov 7y ago

Just to be clear, this has barely anything to do with any crypto-currency organization. It is a really regrettable framing for an event that should be of great interest to anyone dealing with cryptography, not just the fairly restricted group of crypto-currentcy enthusiasts. If scalable quantum computers can be built (which seems probable, as we are progressing fast in the number of qubits we can keep together), then certain restricted types of public key encryption will be broken by quantum hardware (all currently used public key encryption actually). We know other public key encryption algorithms exist that can run on classical computers and still not be broken by quantum computers. In many ways they are less tested and less practical, so for a while NIST has been sponsoring the development of such quantum-resistant running-on-classical-computers public-key algorithms. The usual name for this is post-quantum encryption.

olliej 7y ago
That list is still going though I don’t have it handy (I’ll try to update with the mailing list). There are a number of problems that are well established with strong security proofs vs classical and quantum algorithms - the problem is that the key and message sizes are fairly terrible for practice currently. On the plus side all the current symmetric ciphers are still pretty solid against quantum machines (Grover’s search is a sqrt improvement so would simply require a doubling in key size, but I suspect in practice not necessary)
Causality1 7y ago
We seem to be getting better at using quantum computers for hard math. What I'm curious about is when we'll be able to use them for easy math. How many qubits do we need to run Doom Quantum?
- krastanov 7y ago
  Quantum computers are (conjectured to) outperform classical computers in a very restricted set of problems. These problems happen to be extremely important (e.g. protein folding and some forms of linear algebra), but for tasks that are already efficiently solved by classical computers you probably will never use a quantum computer (maybe in many decades this will change, when it becomes as "trivial" to construct quantum CPUs as it is to construct classical CPUs)

lixtra 7y ago

> Take the Bitcoin blockchain: an unencrypted public key is sent along with every bitcoin transaction, and left unencrypted during the time it takes for the network to confirm the block, around ten minutes. My understanding is that it remains unencrypted forever. That’s why it is a public key. As long as the coins are not moved to another account that public key stays a valuable target. Edit: As DennisP pointed out my understanding was wrong and indeed only the hash of the target is published until you make an transaction from an account.

esotericn 7y ago
Nitpick: What people like to call "Satoshi's coins" were actually mined in transactions to pubkeys rather than to pubkey hashes. Early Bitcoin transactions did not use addresses. Example from block 1: https://www.blockchain.com/btc/tx/0e3e2357e806b6cdb1f70b54c3.. https://www.blockchain.com/btc/tx/0e3e2357e806b6cdb1f70b54c3.... You'll see at the bottom that the opcode is a PUSH / CHECKSIG rather than the later DUP / HASH160 / PUSH / EQUALVERIFY / CHECKSIG format. So this isn't true. (blockchain.info derives an address but actually the pubkeys are right there in plain sight. Have at it!) Most transactions are indeed made to pubkey hashes though, yes.
RandomBacon 7y ago
So then if Satoshi destroyed the private keys instead holding on to them just in case for an event like this, it's possible that someone might take the million or so BTC just sitting around? Depending on how easy it is, all those addresses that were abandoned containing 50 BTC are also up for grabs. Would a coin without public addresses be better suited against such future?
- DennisP 7y ago
  Not if Satoshi's coins have never moved. A bitcoin address is a hash of a public key. The public key isn't revealed until the first time funds are transferred out of that address.
  - RandomBacon 7y ago

EGreg 7y ago

This is a general problem with public keys, not just Bitcoin!! One of the problems with current PKI is weakness in the face of quantum computers, leading to a new crop of algorithms being submitted to NIST, etc. I wanted to ask whether the following simple scheme, based just on cryptographic hashes, can be used CONFIDENTLY, SECURELY and RELIABLY in many situations where Assymetric Key cryptography is used today, and in many others too, such as providing provably random polling etc. It is very similar to a One Time Pad but uses a cryptographic hash function to generate the OTP codes. Here is the scheme: Everyone generates a random private key K[p] and store it just like any assymetric private key (encrypted with some non-stored derived key). They use any cryptographic hash function that hasn’t had a serious preimage attack (perhaps even MD5?), hash it n (eg 10,000,000) times to get h[p][n], and publicly commit to that number. This is like a public key. The hashes are long enough that it’s infeasible to reverse them. Key strengthening can be achieved by jumping a few onion layers between transactions. If you start running out then you post a new public key, signed with one of your remaining onion layer codes. Any verifiers store the original public key per participant, and then can replace them with the new public key if it was properly signed by the old one, etc. Use case: generating provably random numbers by mutually distrusting parties Participants they gradually reveal their hashes, one onion layer per transaction. Each provably random seed is a function of the alphabetically smallest/largest three of those hashes at the next onion layer. If not all of them reveal the hashes in time, they gossip, verify and agree on which ones are the smallest/largest three before some cutoff point like “most reported that most reported”. That leaves tons of bits of entropy coming from everyone! Use case: Authenticator Apps The hash h[p][n+1] would be a hash of some substring of h[p][n] with enough bits that finding all chosen preimages (by an eavesdropper of the previous code) would be infeasible in advance. Perhaps 10 alphanumeric characters is enough. Also when displaying the code to enter, the authenticator app can tell the user a number from 1-100 indicating to the verifier how many onion layers to peel, making it harder to precompute the preimages. Or the user would have to enter the entire hash via the network-connected computer scanning a QR code, NFC or something. From a security standpoint, this method seems superior to the HOTP and TOTP schemes used in authenticator apps today, since there is no need to trust the verifier with any secret keys (https://www.ietf.org/rfc/rfc4226.txt https://www.ietf.org/rfc/rfc4226.txt) Also there is no need to sychronize clocks, since the client simply lets the server know how many times to run the hash, and increments that number every time. Use case: Signing Payloads Participants reveal a payload and commit to an HMAC signature by using cryptographic key at the next onion level, which at that point would be known only to them. All these signatures are collected into a blockchain block / merkle tree timestamp / similar thing, and it is sent to the participant before they reveal the onion key they used to sign it. Use case: Off the Record Messaging The Blockchain or Merkle tree is private between a few parties only, so once the next onion level is revealed, no participant can prove the payload was generated by a given participant, since all the onion hashes were known, any of them could generate a new valid tree with any payload history. They can only prove it to each other, or given enough “witnesses” attest to that tree, people might trust then on the basis of consensus of (presumably) mutually distrusting parties, but that’s not the same thing as cryptographic proof. But that is true of any OTR conversation. Use case: Restoring Access This can be used instead of Shamir Secret Key sharing. The server would have to store keys for every participant, and M of N participants would just sign that they approve authorization of some new session, some new key, or whatever. These signatures could be easily checked by anyone who has the public keys of the M participants who signed it. Use case: Decrypting payloads Not sure how one would do this one, to be honest. With PKI, someone could encrypt a payload that can only be decrypted by a private key holder. I see how to do signatures and HMAC, but not the other way.

jchanimal 7y ago

Finally a good use-case for bitcoin: a bounty for the first quantum computer to crack it.

anaolykarpov 7y ago
That bounty is currently at 185 billion USD. Of course, it would be pretty difficult to sell all the bitcoins without slippage, but I guess one could cash in at least several tens of millions.
travisoneill1 7y ago
Not really. BTC has no value other than its ability to be exchanged for USD. If BTC is cracked no one will trade their USD for it anymore and it will be worthless.
- rolltiide 7y ago
  The first person to assume custody of a large amount of bitcoin will sell and be incredibly rich They can siphon off a lot before other people catch on to people’s complaints and realize the best practices were followed
- toss1 7y ago
  Yes, but anyone smart enough to run a quantum computer to solve the private keys and steal bitcoin is also likely to be smart enough to first examine the blockchain for balances that would not get complained about. Apparently, something like 20% of all BTC is just stranded inadvertently lost or destroyed keys -- starting with 'accounts' after the closely watched genesis block, but which have seen no transactions for maybe 5-8 years should net a lot of funds without being noticed.

ddtaylor 7y ago

It's worth mentioning that Bitcoin addresses aren't exposed on the blockchain as public keys, but hashes of the public keys. If you want to steal the coins you'll need to turn ripemd160(sha256(sha256(publicKey))) into a private key. Good luck.

DennisP 7y ago
Yes, but the public key is exposed when you send from that address. If a quantum computer is quick enough, it could get your private key and issue its own transaction, racing you to get into a block.
- gruez 7y ago
  Cracking a public key in 10 minutes is much harder than cracking a public key (at all). Considering we haven't cracked anything yet, I wouldn't be worried about that. Also, if you're transferring thousands of bitcoin and want to be safe, you could always privately send it to a miner rather than broadcasting it. In that case the tx would have 1 confirmation before the the public knows about it, requiring them to also pull off a 50% attack.
  - deleted 7y ago
    [deleted]
  - DennisP 7y ago
    A QC factors the current public key algorithms in constant time. More qubits just means you can factor bigger keys. How big that constant is will depend on how the QC works. Sending privately to a miner would help, but you'd end up with a very centralized system since you would want to send to the biggest miner, to minimize the time until that miner produces a block. You can't have miners sharing the transaction, even privately among themselves, since if they did that then one of them could have a QC and you wouldn't have any way to know who stole your money.
- sroussey 7y ago
  It doesn't need to be quick if you still have coins at that address.

anm89 7y ago

"The amount of time the universe itself has left—around 0.65 billion billion years." Is this true?? I've never heard this claimed before.

Mtinie 7y ago
I’ve never seen it framed that way, but they may be referencing the estimated timeframe for the “heat death” of the universe: https://en.m.wikipedia.org/wiki/Heat_death_of_the_universe https://en.m.wikipedia.org/wiki/Heat_death_of_the_universe
- anm89 7y ago
  Yeah that was my assumption but I've never seen that specific time frame proposed and it just seems like the kind of thing I would have heard of if it was a know fact.
mensetmanusman 7y ago
You can estimate this because there is a known amount of energy around in the visible universe (energy, mass, etc.). We know from inflation that this number changes at a given rate. We also know that time and entropy are connected, so when entropy of the known universe is at the maximum, it would be essentially meaningless to say time could continue, i.e ‘the end of time.’

johnwheeler 7y ago

What a deceptive article. They take a crypto conference happening at a prestigious institution and sprinkle in some bitcoin punditry to make them seem related.

bhouston 7y ago

Will breaking classic computer public key encryption reveal any secrets that were encoded prior to them being obsolete? Should we be recording encrypted streams and saving them for a few years until we can break them? Is there any value in that?

sroussey 7y ago
What do you think the NSA is doing? The public blockchains make all this more feasible since they have the community keep the data around in original state for them! So much cheaper than recording SSL/TLS traffic, for example. Also that is why they would find it important to exfiltrate the data from a company (or government) before it can be re-encrypted with something better.
tialaramex 7y ago
Yes, if this ever works and is affordable. Suppose our adversaries have a machine which can do Shor's algorithm at the scale needed to break modern public keys for say $1M and an hour, and they have been recording encrypted sessions. For sessions encrypted using RSA key exchange, it is enough for them to spend $1M and wait one hour and then they can decrypt everything that they've recorded, using one particular key. So e.g. a typical HTTPS site only has one key for months or even years, if they've recorded the encrypted data they can read all of it for $1M. Where Forward Secrecy (e.g. ECDHE) was used, the cost is $1M (and an hour) for each session, because the keys change each time so each fresh session needs the expensive algorithm.

jeromebaek 7y ago

> Ah, but with the right quantum computer, able to process information at speeds exponentially faster than today’s supercomputers? Suddenly, what seems uncrackable becomes child’s play, able to be broken in under 10 minutes. Cringe. Quantum computers are not "able to process information at speeds exponentially faster than today's supercomputers". They're able to solve a very specific subset of problems which are hard for classical computers. A very specific subset, called BQP, mostly having to do with finding prime factors. NP hard problems are probably uncrackable with quantum computers.