10
$\begingroup$

In the Wikipedia article or another article about post-quantum crypto there's a plenty of information about hash-based signatures. But where are hash-based ecryption with pubkey?

But, over the long-term, it's generally confidentiality (i.e. encryption) that you need to maintain and I haven't talked about post-quantum encryption at all in this post. (Maybe in the future.)

Why articles about hash-based asymmetric encryption are more hard to come by?

Possible reasons:

  • It is impossible and the proof is basic enough that it not deserves an article (or a question here)
  • It is even more impractical than hash-based signatures
  • It is secret and classified
  • It is somehow not interesting and nobody cared to research it
  • It is called by some other term, using which articles get found easily.
  • Linked articles actually do speak about them, but I don't read attentively and missed it.
Improve this question
$\endgroup$
4
  • $\begingroup$ I've never heard of a hash-based public-key encryption scheme. $\endgroup$
    – Squeamish Ossifrage
    Dec 29, 2017 at 23:47
  • 4
    $\begingroup$ A little more to the point: It is not the case that there is any sort of duality between public-key encryption and public-key signature that implies a scheme for one leads to a corresponding scheme for the other. There are some encryption and signature schemes built out of a common primitive, like a trapdoor permutation, but that's because the primitive turns out to be versatile, not because there's a generic way to fashion encryption out of signature or vice versa. $\endgroup$
    – Squeamish Ossifrage
    Dec 30, 2017 at 0:19
  • $\begingroup$ Related: Can Winternitz be easily converted to a many-time encryption scheme? $\endgroup$
    – CodesInChaos
    Dec 30, 2017 at 10:01
  • 1
    $\begingroup$ @SqueamishOssifrage There are Merkle's puzzles, but the work the attacker has to do is only quadratic in the work the defender does, which makes it infeasible to achieve the security levels expected of modern cryptography. $\endgroup$
    – CodesInChaos
    Dec 30, 2017 at 10:06

1 Answer 1

Reset to default
11
$\begingroup$

It's impossible to construct a strong asymmetric encryption algorithm that relies only on the security of a hash function:

We prove that every key exchange protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary making O(n^2) queries to the oracle.

Boaz Barak, Mohammad Mahmoody-Ghidary - Merkle Puzzles are Optimal

(The proof assumes the attacker is only limited by the number of hash computations and has unlimited computational power otherwise)

The quadratic advantage of Merkle Puzzles is not sufficient to achieve the security and performance levels expected of modern cryptography. For example at a security level of 80 bits (Breaking it is equivalent to about one day of bitcoin mining), the defenders would need to exchange terabytes of information and need an hour or so of computation.

And against quantum computers you don't even get that quadratic advantage.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ $O(n^2)$ is an asymptotic bound. Theoretically there could be a system that is secure enough with practical parameter sizes, due to large enough constants preventing attacks. I doubt it, but the proof does not rule it out. $\endgroup$
    – otus
    Dec 30, 2017 at 14:23
  • 2
    $\begingroup$ Someone missed an opportunity to submit another proposal with a quadratic separation between attacker and defender costs to NIST PQCRYPTO, alongside the post-quantum RSA proposals! $\endgroup$
    – Squeamish Ossifrage
    Dec 30, 2017 at 21:16
  • $\begingroup$ @SqueamishOssifrage It looks like merkle puzzles are totally broken against QCs. And the quantum analogs have an even small separation between attacker and defender than classical merkle puzzles. $\endgroup$
    – CodesInChaos
    Dec 30, 2017 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.