I know hashes can be used to construct symmetric encryption schemes (HMAC running in counter mode), signature schemes (SPHINCS), pseudorandom generators, etc.

One thing that's missing is public key encryption. Is it possible to create a hash based public-key encryption scheme?

My intuition says no. But it would be nice if there is a proof that it can't be done.

  • 1
    $\begingroup$ The closest approximation I've seen is one of the very first proposals, Merkle puzzles. en.wikipedia.org/wiki/Merkle%27s_Puzzles - the merely quadratic work factor advantage is wildly insufficient in real world settings, and I don't think anybody ever managed to improve over it. Actually, just found that it's proven optimal (no better option can exist) arxiv.org/abs/0801.3669 $\endgroup$ – Natanael Aug 19 '19 at 8:18
  • $\begingroup$ @Natanael Feel free to post that as an answer. We cannot disprove that other schemes may exist, after all. At least, I expect that to be true, math is weird :) $\endgroup$ – Maarten Bodewes Aug 20 '19 at 17:42
  • $\begingroup$ @MaartenBodewes sure, probabilistic workarounds occasionally shows up and surprise us. But in this case I doubt a symmetric-only scheme will beat quadratic advantage. Although I wouldn't be very surprised by some hybrid scheme with a very lightweight asymmetric component that rely on symmetric for achieving practical security. As for posting as an answer, will do that soon (don't mind if somebody else goes first and explain the paper) $\endgroup$ – Natanael Aug 20 '19 at 18:31
  • $\begingroup$ I don't mind either, but usually it is wishful thinking :) I'll destroy the comments if / when an answer is posted. $\endgroup$ – Maarten Bodewes Aug 20 '19 at 18:45

Browse other questions tagged or ask your own question.