3 ms·

This article isn't focusing on why signatures are important, it's explaining why hash-based signatures are important. In other words it's not discussing the dif

by dsacco 9y ago

This article isn't focusing on why signatures are important, it's explaining why hash-based signatures are important. In other words it's not discussing the difference between message confidentiality and message authentication/nonrepudiation. The reason Green talks about quantum computers is because hash-based signatures are one of five or so primary research areas for developing quantum-resistant public-key cryptography. They cannot accommodate public-key encryption, but they are one of the oldest forms of digital signatures. In fact, blockchains and post-quantum resistance are the two major reasons for the renewed research interest in hash-based signatures.

taeric 9y ago
I was specifically reacting to the section "What are hash-based signatures good for?" I should have said I do like the article. The explanations were well done and appreciated.
DoctorOetker 9y ago
"They cannot accommodate public-key encryption" I take it you mean that there are no known hash-based public key encryption systems. I assume you don't intend to say they are provably impossible to construct? I remember when I first learned about hash-based cryptography I was amazed how hashing was the only cryptographic primitive used. Ever since I regularly (once or twice a year) try to google "hash-based public key" and other combinations in the hope that someday someone will have worked out how to found public key encryption on cryptographic hashing... It feels impossible but so felt hash-based signatures before learning how to sign a single bit and then generalize to more...
- akvadrako 9y ago
  I can't imagine how a hash-based encryption system could work and I wouldn't be surprised if one could prove it's impossible. But I'm not sure anyone has tried.
- Ar-Curunir 9y ago
  Impagliazzo and Rudich proved that one can't construct PKE from one way functions in a black box manner: https://www.researchgate.net/profile/Russell_Impagliazzo/publication/2477849_Limits_on_the_Provable_Consequences_of_One-way_Permutations/links/09e41511133b689298000000/Limits-on-the-Provable-Consequences-of-One-way-Permutations.pdf https://www.researchgate.net/profile/Russell_Impagliazzo/pub...
  - DoctorOetker 9y ago
    thanks a lot!
  - DoctorOetker 9y ago
    I am reading the paper now, and had a weird thought, but probably it is a brainfart: Keep in mind Monte Carlo algorithms versus Las Vegas algorithmms. Keep also in mind that since cryptographic one way permutations are available, both Alice and Bob can sign their messages on the public channel, and Eve can only read them (for injecting a message would require forging a signature). Consider the following (absurd) Las Vegas algorithm: both Alice and Bob seperately generate a random secret key. Then they sign the hash of the secret key and inform each other with this <Hash(secret),Signature(Hash(secret))> message. The Las Vegas secret key exchange protocol succesfully finishes if they read the same hash as they generated, and returns the bottom element or failure if they don't match. So provably with a (very) low probability they can establish a common secret in a Las Vegas protocol, which begs the question if a dual (necessarily interactive) Monte Carlo protocol can slowly grow an n-bit common secret. I suspect you can confirm that this is just a brainfart indeed?
    - Ar-Curunir 9y ago
      If by the hashing operation you mean application of the OWP, keep in mind that inverting the OWP is supposed to be hard, and furthermore, since it's a OWP, if Alice and Bob start with different secret keys, they won't hit the same "hash" as the output of the OWP. For this to work, they'd have to start off with the same secret key already, which makes the key exchange pointless. You mention using this approach to slowly grow a secret key, by performing many iterations of this protocol, but if you do it bit-by-bit, the adversary can easily brute force invert the OWP over {0, 1}, and thereby learn the secret key

by dsacco 9y ago

taeric 9y ago

I was specifically reacting to the section "What are hash-based signatures good for?" I should have said I do like the article. The explanations were well done and appreciated.

DoctorOetker 9y ago

"They cannot accommodate public-key encryption" I take it you mean that there are no known hash-based public key encryption systems. I assume you don't intend to say they are provably impossible to construct? I remember when I first learned about hash-based cryptography I was amazed how hashing was the only cryptographic primitive used. Ever since I regularly (once or twice a year) try to google "hash-based public key" and other combinations in the hope that someday someone will have worked out how to found public key encryption on cryptographic hashing... It feels impossible but so felt hash-based signatures before learning how to sign a single bit and then generalize to more...

akvadrako 9y ago
I can't imagine how a hash-based encryption system could work and I wouldn't be surprised if one could prove it's impossible. But I'm not sure anyone has tried.
Ar-Curunir 9y ago
Impagliazzo and Rudich proved that one can't construct PKE from one way functions in a black box manner: https://www.researchgate.net/profile/Russell_Impagliazzo/publication/2477849_Limits_on_the_Provable_Consequences_of_One-way_Permutations/links/09e41511133b689298000000/Limits-on-the-Provable-Consequences-of-One-way-Permutations.pdf https://www.researchgate.net/profile/Russell_Impagliazzo/pub...
- DoctorOetker 9y ago
  thanks a lot!
- DoctorOetker 9y ago
  I am reading the paper now, and had a weird thought, but probably it is a brainfart: Keep in mind Monte Carlo algorithms versus Las Vegas algorithmms. Keep also in mind that since cryptographic one way permutations are available, both Alice and Bob can sign their messages on the public channel, and Eve can only read them (for injecting a message would require forging a signature). Consider the following (absurd) Las Vegas algorithm: both Alice and Bob seperately generate a random secret key. Then they sign the hash of the secret key and inform each other with this <Hash(secret),Signature(Hash(secret))> message. The Las Vegas secret key exchange protocol succesfully finishes if they read the same hash as they generated, and returns the bottom element or failure if they don't match. So provably with a (very) low probability they can establish a common secret in a Las Vegas protocol, which begs the question if a dual (necessarily interactive) Monte Carlo protocol can slowly grow an n-bit common secret. I suspect you can confirm that this is just a brainfart indeed?
  - Ar-Curunir 9y ago
    If by the hashing operation you mean application of the OWP, keep in mind that inverting the OWP is supposed to be hard, and furthermore, since it's a OWP, if Alice and Bob start with different secret keys, they won't hit the same "hash" as the output of the OWP. For this to work, they'd have to start off with the same secret key already, which makes the key exchange pointless. You mention using this approach to slowly grow a secret key, by performing many iterations of this protocol, but if you do it bit-by-bit, the adversary can easily brute force invert the OWP over {0, 1}, and thereby learn the secret key