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.
$\endgroup$
  • $\begingroup$ I've never heard of a hash-based public-key encryption scheme. $\endgroup$ – Squeamish Ossifrage Dec 29 '17 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 '17 at 0:19
  • $\begingroup$ Related: Can Winternitz be easily converted to a many-time encryption scheme? $\endgroup$ – CodesInChaos Dec 30 '17 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 '17 at 10:06
10
$\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.

$\endgroup$
  • 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 '17 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 '17 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 '17 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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