7 ms·

How To Make A Mint: The Cryptography Of Anonymous Electronic Cash (1996)

45 points by ferdo 13y ago

dcc1 13y ago
tl:dr NSA invented Bitcoin?
- arh68 13y ago
  It doesn't solve the decentralization problem. > Without a trusted certification authority and a secure infrastructure, the above four security features cannot be achieved, and electronic commerce becomes impossible over an untrusted transmission medium.
  - dcc1 13y ago
    You right, no proof of work either
- ferdo 13y ago
  Not necessarily, but they were out in front of the idea in the 90's.
- Scaevolus 13y ago
  Their proposal requires a central bank. They discuss how to do "offline" transactions without contacting this central authority, but double-spending would only be detected when money is "deposited" back into the central bank.
  - betterunix 13y ago
    It is worth pointing out that the double spending is not merely detected in these systems; the bank is able to compute a proof, that anyone can verify, of a particular party's guilt. This allows the bank to create a blacklist, or to use a legal system, etc.
  - nly 13y ago
    It doesn't necessarily require a central bank, which everyone must be compelled to use, it just requires a banking system. If someone wishes to pay you, and happens to use a different bank to yourself, then your bank (whom you, admittedly, have to trust) can work on your behalf, directly with the sourcing bank, to claim the funds. There's quite good reason to trust in this system because our bank knows that the sourcing bank can identify double-spenders. The plus side of such a system is honest bank customers still get complete anonymity, even if the banks conspire against you. The downside is you can never know if your bank is conspiring against their customers as a whole i.e. by not operating in line with their inflation/reserve policy... which of course is one of Bitcoins best features.
- betterunix 13y ago
  1. They are describing the invention of David Chaum 2. What they are describing has a security definition and can be proved secure. Bitcoin has no security definition, no proof of security, and is vulnerable to polynomial time attacks.
  - maaku 13y ago
    > Bitcoin has no security definition, no proof of security, and is vulnerable to polynomial time attacks. Cite?
    - betterunix 13y ago
      It is pretty hard to cite the lack of a security definition and the lack of a security proof. As for the polynomial time attack, it is describe in the original Bitcoin paper, at the end of Section 4: http://bitcoin.org/bitcoin.pdf http://bitcoin.org/bitcoin.pdf It is also described here: https://en.bitcoin.it/wiki/Weaknesses#Attacker_has_a_lot_of_computing_power https://en.bitcoin.it/wiki/Weaknesses#Attacker_has_a_lot_of_... And in this criticism by Ben Laurie: http://www.links.org/files/decentralised-currencies.pdf http://www.links.org/files/decentralised-currencies.pdf
      - maaku 13y ago
        Ok, that's not an attack against the cryptography of the system, which you're original post implied. E.g, you can't use a polynomial-time algorithm to spend coins which belong to me.
        betterunix 13y ago
        "that's not an attack against the cryptography of the system" I am not sure what you mean. What do you think this is an attack against? "you can't use a polynomial-time algorithm to spend coins which belong to me." In some situations I can. If, for example, you received your money from me, I can take the money from you and transfer it to someone else. The attacker can also stop you from completing transactions and stop you from receiving rewards for mining.
- gwern 13y ago
  No; Bitcoin sacrifices some of the nice features of the known possible digital cash systems in 1996 in exchange for an ad hoc sort of decentralization. Arguably, that's why it's succeeding - decentralization turned out to be more important than either high-powered security proofs or efficiency (my essay on the topic: http://www.gwern.net/Bitcoin%20is%20Worse%20is%20Better http://www.gwern.net/Bitcoin%20is%20Worse%20is%20Better ).
  - ferdo 13y ago
    Tatsuaki Okamoto has quite the crypto and coding chops: https://www.google.com/#sclient=psy-ab&q="Tatsuaki+Okamoto"+c%2B%2B+Visual https://www.google.com/#sclient=psy-ab&q="Tatsuaki+Okamoto"+... http://academic.research.microsoft.com/Author/1002804/tatsuaki-okamoto http://academic.research.microsoft.com/Author/1002804/tatsua... http://www.informatik.uni-trier.de/%7Eley/pers/hd/o/Okamoto:Tatsuaki.html http://www.informatik.uni-trier.de/%7Eley/pers/hd/o/Okamoto:...
- vy8vWJlco 13y ago
  With their records, if they didn't make it, they should at least know who did (who posted the paper, who was mining during the early days, etc...).
A1kmm 13y ago
But I don't think the blinding scheme presented in section 3.2 can be trusted if the bank logs all coins it signs and all coins it verifies. When signing a coin to make a withdrawal, the bank is given (r^v · M (mod N)) - N and v is publicly known, M and r are only known to Alice. The bank computes r · M^s (mod N) (using s, which only the bank knows). Later, Bob supplies the bank with M', a message, and (r · M^s (mod N)) / r, and the bank is not supposed to be able to link M' back to M. But the bank can enumerate all (r_i^v · M_i (mod N)) that it signed, and divide by M'; if M=M', the result is of the form r_i^v (mod N). The bank knows the prime factorisation N = pq, so they can test r_i^v (mod p) and r_i^v (mod q); for a prime modulus, computing a power residue is efficient, and for a large enough p and q (as you want in cryptography) and a moderately high v, this gives a high level of confidence that M=M'.
- betterunix 13y ago
  Indeed; this is why provable security is so important: http://www1.icsi.berkeley.edu/~luby/PAPERS/blind.ps http://www1.icsi.berkeley.edu/~luby/PAPERS/blind.ps http://eprint.iacr.org/2011/316.pdf http://eprint.iacr.org/2011/316.pdf http://www.cs.umd.edu/~jkatz/papers/blind_sigs-proc.pdf http://www.cs.umd.edu/~jkatz/papers/blind_sigs-proc.pdf
IvyMike 13y ago
In 1995(?) I went to a talk by Chaum, and was convinced that e-cash was the way of the future. It was awesome. Then, in 1996(ish) I went to a talk by Simson Garfinkel, and asked him about e-cash. This dashed my hopes for e-cash. He specifically raised an important objection to all the e-cash schemes of the time: the "risk" of the system was essentially essentially infinite. An e-cash mint could, if subverted by hook or crook, print an infinite amount of e-cash, thus disrupting the entire system. (Imagine terrorists with guns going into an e-cash mint and saying "Print us one quadrillion dollars of money". In the e-cash systems of the time, a few minutes later, they would say "here ya gone, one quadrillion dollars of untraceable unrevokable money".) I think the genius of the bitcoin system is that there is no central mint, and the "proof-of-work" system eliminates the possibility of someone minting an infinite amount of cash. P.S. It's Saturday night and I'm not entirely sober. If you want to call me an idiot based on the above, well, that seems fair. On the other hand, if you want to argue with either Chaum or Garfinkel, please research and read what they actually wrote rather than rely on my drunken recollection.

45 points by ferdo 13y ago

dcc1 13y ago

tl:dr NSA invented Bitcoin?

arh68 13y ago
It doesn't solve the decentralization problem. > Without a trusted certification authority and a secure infrastructure, the above four security features cannot be achieved, and electronic commerce becomes impossible over an untrusted transmission medium.
- dcc1 13y ago
  You right, no proof of work either
ferdo 13y ago
Not necessarily, but they were out in front of the idea in the 90's.
Scaevolus 13y ago
Their proposal requires a central bank. They discuss how to do "offline" transactions without contacting this central authority, but double-spending would only be detected when money is "deposited" back into the central bank.
- betterunix 13y ago
  It is worth pointing out that the double spending is not merely detected in these systems; the bank is able to compute a proof, that anyone can verify, of a particular party's guilt. This allows the bank to create a blacklist, or to use a legal system, etc.
- nly 13y ago
  It doesn't necessarily require a central bank, which everyone must be compelled to use, it just requires a banking system. If someone wishes to pay you, and happens to use a different bank to yourself, then your bank (whom you, admittedly, have to trust) can work on your behalf, directly with the sourcing bank, to claim the funds. There's quite good reason to trust in this system because our bank knows that the sourcing bank can identify double-spenders. The plus side of such a system is honest bank customers still get complete anonymity, even if the banks conspire against you. The downside is you can never know if your bank is conspiring against their customers as a whole i.e. by not operating in line with their inflation/reserve policy... which of course is one of Bitcoins best features.
betterunix 13y ago
1. They are describing the invention of David Chaum 2. What they are describing has a security definition and can be proved secure. Bitcoin has no security definition, no proof of security, and is vulnerable to polynomial time attacks.
- maaku 13y ago
  > Bitcoin has no security definition, no proof of security, and is vulnerable to polynomial time attacks. Cite?
  - betterunix 13y ago
    It is pretty hard to cite the lack of a security definition and the lack of a security proof. As for the polynomial time attack, it is describe in the original Bitcoin paper, at the end of Section 4: http://bitcoin.org/bitcoin.pdf http://bitcoin.org/bitcoin.pdf It is also described here: https://en.bitcoin.it/wiki/Weaknesses#Attacker_has_a_lot_of_computing_power https://en.bitcoin.it/wiki/Weaknesses#Attacker_has_a_lot_of_... And in this criticism by Ben Laurie: http://www.links.org/files/decentralised-currencies.pdf http://www.links.org/files/decentralised-currencies.pdf
    - maaku 13y ago
      Ok, that's not an attack against the cryptography of the system, which you're original post implied. E.g, you can't use a polynomial-time algorithm to spend coins which belong to me.
      - betterunix 13y ago
        "that's not an attack against the cryptography of the system" I am not sure what you mean. What do you think this is an attack against? "you can't use a polynomial-time algorithm to spend coins which belong to me." In some situations I can. If, for example, you received your money from me, I can take the money from you and transfer it to someone else. The attacker can also stop you from completing transactions and stop you from receiving rewards for mining.
gwern 13y ago
No; Bitcoin sacrifices some of the nice features of the known possible digital cash systems in 1996 in exchange for an ad hoc sort of decentralization. Arguably, that's why it's succeeding - decentralization turned out to be more important than either high-powered security proofs or efficiency (my essay on the topic: http://www.gwern.net/Bitcoin%20is%20Worse%20is%20Better http://www.gwern.net/Bitcoin%20is%20Worse%20is%20Better ).
- ferdo 13y ago
  Tatsuaki Okamoto has quite the crypto and coding chops: https://www.google.com/#sclient=psy-ab&q="Tatsuaki+Okamoto"+c%2B%2B+Visual https://www.google.com/#sclient=psy-ab&q="Tatsuaki+Okamoto"+... http://academic.research.microsoft.com/Author/1002804/tatsuaki-okamoto http://academic.research.microsoft.com/Author/1002804/tatsua... http://www.informatik.uni-trier.de/%7Eley/pers/hd/o/Okamoto:Tatsuaki.html http://www.informatik.uni-trier.de/%7Eley/pers/hd/o/Okamoto:...
vy8vWJlco 13y ago
With their records, if they didn't make it, they should at least know who did (who posted the paper, who was mining during the early days, etc...).

A1kmm 13y ago

But I don't think the blinding scheme presented in section 3.2 can be trusted if the bank logs all coins it signs and all coins it verifies. When signing a coin to make a withdrawal, the bank is given (r^v · M (mod N)) - N and v is publicly known, M and r are only known to Alice. The bank computes r · M^s (mod N) (using s, which only the bank knows). Later, Bob supplies the bank with M', a message, and (r · M^s (mod N)) / r, and the bank is not supposed to be able to link M' back to M. But the bank can enumerate all (r_i^v · M_i (mod N)) that it signed, and divide by M'; if M=M', the result is of the form r_i^v (mod N). The bank knows the prime factorisation N = pq, so they can test r_i^v (mod p) and r_i^v (mod q); for a prime modulus, computing a power residue is efficient, and for a large enough p and q (as you want in cryptography) and a moderately high v, this gives a high level of confidence that M=M'.

betterunix 13y ago
Indeed; this is why provable security is so important: http://www1.icsi.berkeley.edu/~luby/PAPERS/blind.ps http://www1.icsi.berkeley.edu/~luby/PAPERS/blind.ps http://eprint.iacr.org/2011/316.pdf http://eprint.iacr.org/2011/316.pdf http://www.cs.umd.edu/~jkatz/papers/blind_sigs-proc.pdf http://www.cs.umd.edu/~jkatz/papers/blind_sigs-proc.pdf

IvyMike 13y ago

In 1995(?) I went to a talk by Chaum, and was convinced that e-cash was the way of the future. It was awesome. Then, in 1996(ish) I went to a talk by Simson Garfinkel, and asked him about e-cash. This dashed my hopes for e-cash. He specifically raised an important objection to all the e-cash schemes of the time: the "risk" of the system was essentially essentially infinite. An e-cash mint could, if subverted by hook or crook, print an infinite amount of e-cash, thus disrupting the entire system. (Imagine terrorists with guns going into an e-cash mint and saying "Print us one quadrillion dollars of money". In the e-cash systems of the time, a few minutes later, they would say "here ya gone, one quadrillion dollars of untraceable unrevokable money".) I think the genius of the bitcoin system is that there is no central mint, and the "proof-of-work" system eliminates the possibility of someone minting an infinite amount of cash. P.S. It's Saturday night and I'm not entirely sober. If you want to call me an idiot based on the above, well, that seems fair. On the other hand, if you want to argue with either Chaum or Garfinkel, please research and read what they actually wrote rather than rely on my drunken recollection.