9 ms·

Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets

196 points by icedicedavid 13y ago

Groxx 13y ago
Page isn't loading for me :/ cache for anyone else hitting this: http://webcache.googleusercontent.com/search?q=cache:WsX8NCwh8nkJ:bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-which-bitcoin-dodged-some-cryptographic-bullet/+&cd=1&hl=en&ct=clnk&gl=us&client=firefox-a http://webcache.googleusercontent.com/search?q=cache:WsX8NCw... -- edit: tl;dr of it all is: 1) addresses are hashes of public keys, not public keys themselves, so you can't really figure out the private key even with magic / quantum computing. 2) 21 million BTC * 100 million divisions = 2.1 quadrillion < maximum integer uniquely representable by a (double-precision) float (~2^50.9 < 2^53), handy for simpler programming. 3) elliptic curve chosen wasn't one of the dubious NIST ones. The article is pretty well written, IMO, and does a reasonable job explaining why these are issues in the first place, and how it avoids them. Probably worth a read unless you grok it all from the tl;dr, and even then since it might help you explain things to others.
- raverbashing 13y ago
  In essence, apart from 2, which wouldn't take too much hindsight to calculate, both items seem to be the work of a real expert in crypto. Not the ones that go for the "proven" way "because NIST said so" or the "internet specialists" that cry wolf more often than not (and miss or even suggest security holes)
  - maaku 13y ago
    Not really. The original bitcoin client did what was called direct-to-IP transactions, which didn't use hashed pubkeys, and which was vulnerable to man-in-the-middle attacks (oops). Bitcoin's ECDSA curve was chosen because it was one of the faster ones, not because of any NIST connection (a "real" cryptographer of the day would have probably advised against the secp256k1 curve used in bitcoin in favor of one of the NIST curves, or DJB's curve which is superior in just about every way.
    - celticninja 13y ago
      unless the "real" cryptographer knew about the NIST/NSA weakening of secp256r1
      - maaku 13y ago
        My point, perhaps too subtle, was that in 2009 there was not sufficient public evidence to suggest such weakening. Rather, the reigning opinion (supported by historical evidence) was that NIST/NSA routinely strengthened standards by selecting parameters so as to make the algorithm secure against publicly unknown mathematical attacks. That is, after all, their stated purpose and what they did with the DES S-boxes. Turns out, the NSA is a shadow of its former self. But you'd have to have had non-public insider information to have known that with confidence in 2009.
      - pbsd 13y ago
        What weakening, may I ask?
  - geofft 13y ago
    1 is a little hokey because in the common case, the hash is just a weakness -- it doesn't add any security against classical computers, for which ECDSA is already hard enough, and it opens the possibility of hash collisions. I say "common case" because it only really is a win if _both_ quantum computers are in use _and_ you've never spent from the wallet and never will (except possibly to cash out entirely).
sillysaurus2 13y ago
Who created Bitcoin? This comment seems to offer many clues: https://news.ycombinator.com/item?id=5547590 https://news.ycombinator.com/item?id=5547590 There are two groups that are on the suspects list for having engendered bitcoin, one group centers around Trinity College, another is a bunch of loosely affiliated international collaborators. Both groups are on the record with precursors to bitcoin (papers, software), neither has admitted openly that they were the ones. Along with https://news.ycombinator.com/item?id=5548093 https://news.ycombinator.com/item?id=5548093 Investigations into the real identity of Satoshi Nakamoto have been attempted by The New Yorker and Fast Company. Fast Company's investigation brought up circumstantial evidence that indicated a link between an encryption patent application filed by Neal King, Vladimir Oksman and Charles Bry on 15 August 2008, and the bitcoin.org domain name which was registered 72 hours later. The patent application (#20100042841) contained networking and encryption technologies similar to bitcoin's. After textual analysis, the phrase "...computationally impractical to reverse" was found in both the patent application and bitcoin's whitepaper. All three inventors explicitly denied being Satoshi Nakamoto. Anyone care to speculate whether it's more likely the creators were based in Trinity College rather than being international collaborators? It's interesting that the controller of the Satoshi persona managed to stay anonymous for so long. I wonder if they were careful to only write forum posts via Tor? Otherwise their IP address might've been logged. An IP address would be enough for an ISP to unmask them (or at least narrow down the suspect list quite a lot). Satoshi also made a lot of source code commits, which seems like another way their IP address could leak.
- Afforess 13y ago
  >All three inventors explicitly denied being Satoshi Nakamoto Obviously if the inventor was not a single person, but the result of a group effort, one could truthfully reply that they were not the inventor.
  - canttestthis 13y ago
    Why would you even assume that they replied truthfully?
terabytest 13y ago
This is the first article I've ever read that managed to explain cryptographical stuff in simple terms without making my head spin.
- jawr 13y ago
  Seems like there is a cryptographic explanation every few days. It's a popular topic to write about at the moment. This was well written however.
simondlr 13y ago
Besides dodging bullets, it amazes me that Satoshi had the foresight to include a scripting language into the outputs of transactions, envisioning a future where contracts could be built onto the blockchain. For a proof-of-concept, Bitcoin didn't need it. It could've just supported the ability for owners of addresses to claim outputs (in a hard-coded manner).
- nhaehnle 13y ago
  The irony, of course, is that last time I checked, large parts of this scripting language were disabled in the official client due to security concerns.
- rtpg 13y ago
  apparently originally he wanted to make a capability for a bunch of different transactions but realized that it would be easier to just stick q scripting language in there. Another data point for the "lazy programmers are the best programmers" thesis
- applecore 13y ago
  Pretty good explanation of the motivation behind scripts: https://bitcointalk.org/index.php?topic=195.msg1611#msg1611 https://bitcointalk.org/index.php?topic=195.msg1611#msg1611
ploureiro 13y ago
"my own BitcoinJS fork (which also adds other improvements) does use plain numbers to store the number of satoshis." Why wouldn't I feel tempted to use his fork?..
- enimodas 13y ago
  my thoughts exactly. For those who don't know, never ever use floats for things like money. Try in windows calculator for example sqrt(4) - 2 and see why. Strangely enough he talks about floating point rounding errors in one of the next paragraphs?
  - vbuterin 13y ago
    > For those who don't know, never ever use floats for things like money. This is normally a very good rule to follow. The reason is that floating point is binary, whereas cash is decimal, so even an innocent number like 0.4 has no exact representation in binary (it's actually an infinite tail: 0.011001100110011...). Here, however, I'm using floats NOT to store decimals; every single value that I store is an integer. There is absolutely no danger in using floating point numbers to store relatively small integers like 1253251126; the issue only arises in the context of very large numbers (specifically, those above 2^53) and decimals. If anyone can come up with a remotely realistic series of integer manipulations that will cause an inaccuracy in Javascript where all values always stay below 2^50.9, I will certainly abandon my choice of moving to integers at once; otherwise, I see no problem.
    - shalmanese 13y ago
      Still seems risky to me. There are some numeric calculations where input and output values are small but intermediate representations might be many times larger. It's not certain that all the people working after you are going to be aware of the assumptions intrinsic in your code.
  - Luc 13y ago
    It's explained rather well in the article, over several paragraphs, why it's okay to use floating point in this case. The first thing we did in the programming class at university was to learn how the IEEE floating point standard works...
foxylad 13y ago
Interesting... 2.1 quadrillion satoshis divided by 20 trillion dollars is about 100, so eventually there will be about the same number of satoshis as there are normal money cents in the world. Very nice symmetry!
nly 13y ago
Regarding the choice of the secp256k1 curve: ECDSA signature verification is fairly slow and sipa, one of the Bitcoin developers, has been developing a faster implementation[1]. If anyone has any crypto expertise and can review the code, or otherwuse can provide further optimisations or patches, I'm sure it'd be appreciated. https://github.com/sipa/secp256k1 https://github.com/sipa/secp256k1
daniel-levin 13y ago
> As a result, most of the decisions that Satoshi Nakamoto made in 2008 we are essentially stuck with. Every single time I read something about what 'Satoshi Nakamoto' did in designing, implementing and securing Bitcoin, I grow more skeptical that one person, or even a small group of people, created Bitcoin. It is very difficult to believe that something this sophisticated was developed by anyone other than a well financed, possibly nation-state backed organisation. This article suggests that Bitcoin was made difficult or impossible to fork by-design, which implies that the creator doesn't want to allow anyone to seize control of Bitcoin. Paradoxically, the more you learn about Bitcoin, the more mysterious it becomes. Who would go through all that trouble to create it? What can they gain from Bitcoin's existence?
- mrb 13y ago
  I think Bitcoin has been designed by a single person. The source code alone of version 0.1.0 was not very complex, see my post https://news.ycombinator.com/item?id=6561079 https://news.ycombinator.com/item?id=6561079 And most of the crytographic choices are logical and could have been taken by a person reasonably well-educated in computer security and cryptography who pays attention to details. This is my opinion as a pentester / IT security researcher / developer with experience in cryptography. "This article suggests that Bitcoin was made difficult or impossible to fork by-design, which implies that the creator doesn't want to allow anyone to seize control of Bitcoin." Well, source code is easy to change and fork. But because this would create a fork in the block chain, you would end up with a different Bitcoin network that does not recognize transactions of the original Bitcoin network. "Who would go through all that trouble to create it?" Version 0.1.0 is only 13k lines of code. "What can they gain from Bitcoin's existence?" Someone wanted to experiment with his ideas about a revolutionary peer-to-peer currency/payment network, and maybe hoped to inspire others with his creation? Some people enjoy experimenting with cool ideas just for the heck of it. What was Linus Torvalds thinking he would gain from writing the first version of Linux? Anyway, the success of Bitcoin so far is probably beyond what Satoshi envisioned as probable (although he may have seen it as possible).
  - throwhalloween 13y ago
brainburn 13y ago
> Thus, if your Bitcoin funds are stored in an address that you have not spent from (so the public key is unknown), they are safe against a quantum computer – at least until you try to spend them. Uhm, no such thing? Every mined bitcoin is instantly sent to an address
- yafujifide 13y ago
  No, freshly mined bitcoins are never 'sent' anywhere - they just appear in the mining address. Thus, the public key is not revealed until they are sent.
misiti3780 13y ago
I'm not a crypto expert at all but I do have one question: If there is a concept of "quantum-safe" (which I did not know until reading this article), why hasn't the broader internet (HTTPS) adopted them? Is there any plans for there adoption in the future?
- HNaTTY 13y ago
  Quantum-safe in the same respect that an md5sum of an ISO cannot reveal the contents of the ISO.
- JeremyBanks 13y ago
  http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography My understanding is that schemes that would be resistant to quantum attacks are much less efficient, and have more negative tradeoffs, than the systems in use today. Speed is an important property for a most cryptography, so few people would adopt such a system until the threat seems more pressing.
- frezik 13y ago
  Block ciphers can be easily made quantum-safe by doubling the key size (see "Grover's Algorithm"). We might have to update everyone's browser to support extending AES to 512 bits, but it's doable. The real problem is public key ciphers that rely on prime number factorization. Eliptic curves are one solution, but the only people who seem to have in-depth knowledge about them are in the NSA.
- KMag 13y ago
  The mathematics are less well researched, and at least for some algorithms the keys are quite large. (For instance, a pretty standard sized Niederreiter key and a single Niederreiter signature put the minimum size for a certificate over 1 MB, which is a lot less onerous than it used to be, but a bit big for doing a lot of copying on cellular networks.) I haven't heard this expressed anywhere, but it could also be that the McEliece and Niederreiter algorithms have a bit of a feel to them like the Merkle-Hellman knapsack algorithm that was thought for a long time to be secure. Though, if you're being paranoid and can spare the cycles, it wouldn't hurt to take Elliptic Curve Diffie-Hellman (or ECIES) exchange, encrypt that using RSA (or ElGamal), and then Encrypt that using Niederreiter (or McEliece), like a bunch of Russian dolls nested by key/message size. All three crypto systems would need to be broken in order to recover the key.
tptacek 13y ago
Matthew Green and Paulo Barreto were making fun of this on Twitter. No, the use of a hash does not mean bitcoin will survive quantum cryptanalysis. As Green --- not a stranger to the workings of bitcoin --- puts it, "if the elliptic curve discrete log problem is solved, bitcoin is toast". Further, the "smart" curve choice bitcoin made was simply not using the NIST P-curves. But lots of stuff chose not to use the NIST curves; that's why we have Certicom's curves and the Brainpool curves. Unfortunately, bitcoin didn't do that much better than the NIST P-curves; the Koblitz curves they use also have problems that researchers are exploring.
- gigq 13y ago
  The point in the article was that if you sent the coins to an address that never spent any coins (like the reference client does where it will always create a new "change" address for left over coins from a transaction) then the public key of the address that holds your coins will never be seen on the network.
- Perseids 13y ago
  For everyone who was also looking for the tweets: https://twitter.com/pbarreto/status/395378161631784960 https://twitter.com/pbarreto/status/395378161631784960
mkramlich 13y ago
my takeaway from this article just reinforces the perception of Bitcoin I already had, namely: which do I trust more? a monetary system run by engineers & mathematicians. or a monetary system run by politicians/lawyers, government bureaucrats, and an old-money banking aristocracy? Choices, choices...
- pilom 13y ago
  I've worked with a lot of engineers. Most of us aren't really that smart and usually we make problems much more complicated than they need to be. I'd trust a unique and fairly original monetary system run by good engineers. But most engineers are really not that good.
  - mkramlich 13y ago
    I've seen evidence that suggests the leading engineers behind Bitcoin are good. In contrast, I've seen repeated evidence over decades that the folks leading the US government are dangerously incompetent on things which are incredibly important to get right for all the rest of us, namely the economy, the environment/ecosystem and health care.
Glyptodon 13y ago
This is the first time I've seen information addressing quantum computers and bitcoin in a meaningful way (between the linked text and the additional info it links). As a relative layperson when it comes to such things it's nice to finally have some notion of Bitcoin's ability to cope with the quantum world.

196 points by icedicedavid 13y ago

Groxx 13y ago

Page isn't loading for me :/ cache for anyone else hitting this: http://webcache.googleusercontent.com/search?q=cache:WsX8NCwh8nkJ:bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-which-bitcoin-dodged-some-cryptographic-bullet/+&cd=1&hl=en&ct=clnk&gl=us&client=firefox-a http://webcache.googleusercontent.com/search?q=cache:WsX8NCw... -- edit: tl;dr of it all is: 1) addresses are hashes of public keys, not public keys themselves, so you can't really figure out the private key even with magic / quantum computing. 2) 21 million BTC * 100 million divisions = 2.1 quadrillion < maximum integer uniquely representable by a (double-precision) float (~2^50.9 < 2^53), handy for simpler programming. 3) elliptic curve chosen wasn't one of the dubious NIST ones. The article is pretty well written, IMO, and does a reasonable job explaining why these are issues in the first place, and how it avoids them. Probably worth a read unless you grok it all from the tl;dr, and even then since it might help you explain things to others.

raverbashing 13y ago
In essence, apart from 2, which wouldn't take too much hindsight to calculate, both items seem to be the work of a real expert in crypto. Not the ones that go for the "proven" way "because NIST said so" or the "internet specialists" that cry wolf more often than not (and miss or even suggest security holes)
- maaku 13y ago
  Not really. The original bitcoin client did what was called direct-to-IP transactions, which didn't use hashed pubkeys, and which was vulnerable to man-in-the-middle attacks (oops). Bitcoin's ECDSA curve was chosen because it was one of the faster ones, not because of any NIST connection (a "real" cryptographer of the day would have probably advised against the secp256k1 curve used in bitcoin in favor of one of the NIST curves, or DJB's curve which is superior in just about every way.
  - celticninja 13y ago
    unless the "real" cryptographer knew about the NIST/NSA weakening of secp256r1
    - maaku 13y ago
      My point, perhaps too subtle, was that in 2009 there was not sufficient public evidence to suggest such weakening. Rather, the reigning opinion (supported by historical evidence) was that NIST/NSA routinely strengthened standards by selecting parameters so as to make the algorithm secure against publicly unknown mathematical attacks. That is, after all, their stated purpose and what they did with the DES S-boxes. Turns out, the NSA is a shadow of its former self. But you'd have to have had non-public insider information to have known that with confidence in 2009.
    - pbsd 13y ago
      What weakening, may I ask?
- geofft 13y ago
  1 is a little hokey because in the common case, the hash is just a weakness -- it doesn't add any security against classical computers, for which ECDSA is already hard enough, and it opens the possibility of hash collisions. I say "common case" because it only really is a win if _both_ quantum computers are in use _and_ you've never spent from the wallet and never will (except possibly to cash out entirely).

sillysaurus2 13y ago

Who created Bitcoin? This comment seems to offer many clues: https://news.ycombinator.com/item?id=5547590 https://news.ycombinator.com/item?id=5547590 There are two groups that are on the suspects list for having engendered bitcoin, one group centers around Trinity College, another is a bunch of loosely affiliated international collaborators. Both groups are on the record with precursors to bitcoin (papers, software), neither has admitted openly that they were the ones. Along with https://news.ycombinator.com/item?id=5548093 https://news.ycombinator.com/item?id=5548093 Investigations into the real identity of Satoshi Nakamoto have been attempted by The New Yorker and Fast Company. Fast Company's investigation brought up circumstantial evidence that indicated a link between an encryption patent application filed by Neal King, Vladimir Oksman and Charles Bry on 15 August 2008, and the bitcoin.org domain name which was registered 72 hours later. The patent application (#20100042841) contained networking and encryption technologies similar to bitcoin's. After textual analysis, the phrase "...computationally impractical to reverse" was found in both the patent application and bitcoin's whitepaper. All three inventors explicitly denied being Satoshi Nakamoto. Anyone care to speculate whether it's more likely the creators were based in Trinity College rather than being international collaborators? It's interesting that the controller of the Satoshi persona managed to stay anonymous for so long. I wonder if they were careful to only write forum posts via Tor? Otherwise their IP address might've been logged. An IP address would be enough for an ISP to unmask them (or at least narrow down the suspect list quite a lot). Satoshi also made a lot of source code commits, which seems like another way their IP address could leak.

Afforess 13y ago
>All three inventors explicitly denied being Satoshi Nakamoto Obviously if the inventor was not a single person, but the result of a group effort, one could truthfully reply that they were not the inventor.
- canttestthis 13y ago
  Why would you even assume that they replied truthfully?

terabytest 13y ago

This is the first article I've ever read that managed to explain cryptographical stuff in simple terms without making my head spin.

jawr 13y ago
Seems like there is a cryptographic explanation every few days. It's a popular topic to write about at the moment. This was well written however.

simondlr 13y ago

Besides dodging bullets, it amazes me that Satoshi had the foresight to include a scripting language into the outputs of transactions, envisioning a future where contracts could be built onto the blockchain. For a proof-of-concept, Bitcoin didn't need it. It could've just supported the ability for owners of addresses to claim outputs (in a hard-coded manner).

nhaehnle 13y ago
The irony, of course, is that last time I checked, large parts of this scripting language were disabled in the official client due to security concerns.
rtpg 13y ago
apparently originally he wanted to make a capability for a bunch of different transactions but realized that it would be easier to just stick q scripting language in there. Another data point for the "lazy programmers are the best programmers" thesis
applecore 13y ago
Pretty good explanation of the motivation behind scripts: https://bitcointalk.org/index.php?topic=195.msg1611#msg1611 https://bitcointalk.org/index.php?topic=195.msg1611#msg1611

ploureiro 13y ago

"my own BitcoinJS fork (which also adds other improvements) does use plain numbers to store the number of satoshis." Why wouldn't I feel tempted to use his fork?..

enimodas 13y ago
my thoughts exactly. For those who don't know, never ever use floats for things like money. Try in windows calculator for example sqrt(4) - 2 and see why. Strangely enough he talks about floating point rounding errors in one of the next paragraphs?
- vbuterin 13y ago
  > For those who don't know, never ever use floats for things like money. This is normally a very good rule to follow. The reason is that floating point is binary, whereas cash is decimal, so even an innocent number like 0.4 has no exact representation in binary (it's actually an infinite tail: 0.011001100110011...). Here, however, I'm using floats NOT to store decimals; every single value that I store is an integer. There is absolutely no danger in using floating point numbers to store relatively small integers like 1253251126; the issue only arises in the context of very large numbers (specifically, those above 2^53) and decimals. If anyone can come up with a remotely realistic series of integer manipulations that will cause an inaccuracy in Javascript where all values always stay below 2^50.9, I will certainly abandon my choice of moving to integers at once; otherwise, I see no problem.
  - shalmanese 13y ago
    Still seems risky to me. There are some numeric calculations where input and output values are small but intermediate representations might be many times larger. It's not certain that all the people working after you are going to be aware of the assumptions intrinsic in your code.
- Luc 13y ago
  It's explained rather well in the article, over several paragraphs, why it's okay to use floating point in this case. The first thing we did in the programming class at university was to learn how the IEEE floating point standard works...

foxylad 13y ago

Interesting... 2.1 quadrillion satoshis divided by 20 trillion dollars is about 100, so eventually there will be about the same number of satoshis as there are normal money cents in the world. Very nice symmetry!

nly 13y ago

Regarding the choice of the secp256k1 curve: ECDSA signature verification is fairly slow and sipa, one of the Bitcoin developers, has been developing a faster implementation[1]. If anyone has any crypto expertise and can review the code, or otherwuse can provide further optimisations or patches, I'm sure it'd be appreciated. https://github.com/sipa/secp256k1 https://github.com/sipa/secp256k1

daniel-levin 13y ago

> As a result, most of the decisions that Satoshi Nakamoto made in 2008 we are essentially stuck with. Every single time I read something about what 'Satoshi Nakamoto' did in designing, implementing and securing Bitcoin, I grow more skeptical that one person, or even a small group of people, created Bitcoin. It is very difficult to believe that something this sophisticated was developed by anyone other than a well financed, possibly nation-state backed organisation. This article suggests that Bitcoin was made difficult or impossible to fork by-design, which implies that the creator doesn't want to allow anyone to seize control of Bitcoin. Paradoxically, the more you learn about Bitcoin, the more mysterious it becomes. Who would go through all that trouble to create it? What can they gain from Bitcoin's existence?

mrb 13y ago
I think Bitcoin has been designed by a single person. The source code alone of version 0.1.0 was not very complex, see my post https://news.ycombinator.com/item?id=6561079 https://news.ycombinator.com/item?id=6561079 And most of the crytographic choices are logical and could have been taken by a person reasonably well-educated in computer security and cryptography who pays attention to details. This is my opinion as a pentester / IT security researcher / developer with experience in cryptography. "This article suggests that Bitcoin was made difficult or impossible to fork by-design, which implies that the creator doesn't want to allow anyone to seize control of Bitcoin." Well, source code is easy to change and fork. But because this would create a fork in the block chain, you would end up with a different Bitcoin network that does not recognize transactions of the original Bitcoin network. "Who would go through all that trouble to create it?" Version 0.1.0 is only 13k lines of code. "What can they gain from Bitcoin's existence?" Someone wanted to experiment with his ideas about a revolutionary peer-to-peer currency/payment network, and maybe hoped to inspire others with his creation? Some people enjoy experimenting with cool ideas just for the heck of it. What was Linus Torvalds thinking he would gain from writing the first version of Linux? Anyway, the success of Bitcoin so far is probably beyond what Satoshi envisioned as probable (although he may have seen it as possible).
- throwhalloween 13y ago

brainburn 13y ago

> Thus, if your Bitcoin funds are stored in an address that you have not spent from (so the public key is unknown), they are safe against a quantum computer – at least until you try to spend them. Uhm, no such thing? Every mined bitcoin is instantly sent to an address

yafujifide 13y ago
No, freshly mined bitcoins are never 'sent' anywhere - they just appear in the mining address. Thus, the public key is not revealed until they are sent.

misiti3780 13y ago

I'm not a crypto expert at all but I do have one question: If there is a concept of "quantum-safe" (which I did not know until reading this article), why hasn't the broader internet (HTTPS) adopted them? Is there any plans for there adoption in the future?

HNaTTY 13y ago
Quantum-safe in the same respect that an md5sum of an ISO cannot reveal the contents of the ISO.
JeremyBanks 13y ago
http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography My understanding is that schemes that would be resistant to quantum attacks are much less efficient, and have more negative tradeoffs, than the systems in use today. Speed is an important property for a most cryptography, so few people would adopt such a system until the threat seems more pressing.
frezik 13y ago
Block ciphers can be easily made quantum-safe by doubling the key size (see "Grover's Algorithm"). We might have to update everyone's browser to support extending AES to 512 bits, but it's doable. The real problem is public key ciphers that rely on prime number factorization. Eliptic curves are one solution, but the only people who seem to have in-depth knowledge about them are in the NSA.
KMag 13y ago
The mathematics are less well researched, and at least for some algorithms the keys are quite large. (For instance, a pretty standard sized Niederreiter key and a single Niederreiter signature put the minimum size for a certificate over 1 MB, which is a lot less onerous than it used to be, but a bit big for doing a lot of copying on cellular networks.) I haven't heard this expressed anywhere, but it could also be that the McEliece and Niederreiter algorithms have a bit of a feel to them like the Merkle-Hellman knapsack algorithm that was thought for a long time to be secure. Though, if you're being paranoid and can spare the cycles, it wouldn't hurt to take Elliptic Curve Diffie-Hellman (or ECIES) exchange, encrypt that using RSA (or ElGamal), and then Encrypt that using Niederreiter (or McEliece), like a bunch of Russian dolls nested by key/message size. All three crypto systems would need to be broken in order to recover the key.

tptacek 13y ago

Matthew Green and Paulo Barreto were making fun of this on Twitter. No, the use of a hash does not mean bitcoin will survive quantum cryptanalysis. As Green --- not a stranger to the workings of bitcoin --- puts it, "if the elliptic curve discrete log problem is solved, bitcoin is toast". Further, the "smart" curve choice bitcoin made was simply not using the NIST P-curves. But lots of stuff chose not to use the NIST curves; that's why we have Certicom's curves and the Brainpool curves. Unfortunately, bitcoin didn't do that much better than the NIST P-curves; the Koblitz curves they use also have problems that researchers are exploring.

gigq 13y ago
The point in the article was that if you sent the coins to an address that never spent any coins (like the reference client does where it will always create a new "change" address for left over coins from a transaction) then the public key of the address that holds your coins will never be seen on the network.
Perseids 13y ago
For everyone who was also looking for the tweets: https://twitter.com/pbarreto/status/395378161631784960 https://twitter.com/pbarreto/status/395378161631784960

mkramlich 13y ago

my takeaway from this article just reinforces the perception of Bitcoin I already had, namely: which do I trust more? a monetary system run by engineers & mathematicians. or a monetary system run by politicians/lawyers, government bureaucrats, and an old-money banking aristocracy? Choices, choices...

pilom 13y ago
I've worked with a lot of engineers. Most of us aren't really that smart and usually we make problems much more complicated than they need to be. I'd trust a unique and fairly original monetary system run by good engineers. But most engineers are really not that good.
- mkramlich 13y ago
  I've seen evidence that suggests the leading engineers behind Bitcoin are good. In contrast, I've seen repeated evidence over decades that the folks leading the US government are dangerously incompetent on things which are incredibly important to get right for all the rest of us, namely the economy, the environment/ecosystem and health care.

Glyptodon 13y ago

This is the first time I've seen information addressing quantum computers and bitcoin in a meaningful way (between the linked text and the additional info it links). As a relative layperson when it comes to such things it's nice to finally have some notion of Bitcoin's ability to cope with the quantum world.