5
$\begingroup$

Over the years, new discoveries have weakened some of the mathematical primitives used in cryptography, like the broken Knapsack cryptosystem, Shor's algorithm, etc. What we believe to be hard problems today, can become simpler tomorrow. We need to trust the judgement of mathematicians that certain algebraic problems remain hard to solve in the future, and no secret agency has found a shortcut in the meantime.

That is why I love the beauty of hash-based digital signatures (e.g. Lamport, Merkle, XMSS, Sphincs+). It is all just basic logic and bookkeeping. It is not relying on math puzzles, and only requires that the hash function is not broken. But you could even mitigate that by combining multiple different hash functions if you are truly paranoid. Even without any math background you can simply understand why hash-based signatures are secure.

Next to digital signatures, you could also create a simple hash-based symmetric cipher. For example by hashing a shared secret with a counter and XOR-ing the plain text.

I was wondering whether public-key encryption can also be based on hashes. I was unable to find anything in literature, so my guess is that you will unfortunately need some sort of algebraic problem to construct a parameterized trap-door function (as opposed to a fixed hash function like SHA256).

Any suggestions or pointers to literature?

$\endgroup$
8
  • 2
    $\begingroup$ Check out Merkle's puzzles $\endgroup$ Commented Jun 26 at 5:49
  • $\begingroup$ @DanielS, Thanks, that is an interesting idea! Too bad the difference in complexity for the adversary is only quadratic. At the bottom of the page it links to an article by Barak and Mahmoody-Ghidary showing that this quadratic bound cannot be improved upon. $\endgroup$ Commented Jun 26 at 19:15
  • $\begingroup$ It's possible if you assume indistinguishability obfuscation (IO). See Wikipedia page for IO (en.wikipedia.org/wiki/Indistinguishability_obfuscation): Concretely, an indistinguishability obfuscator (with the additional assumption of the existence of one-way functions) could be used to construct the following kinds of cryptography: ... IND-CCA-secure public-key cryptography. $\endgroup$ Commented Jun 26 at 21:33
  • 3
    $\begingroup$ "Even without any math background you can simply understand why hash-based signatures are secure." That's called delusion. $\endgroup$ Commented Jun 27 at 7:23
  • 1
    $\begingroup$ @JasonSmith If you don't care about tightness of reduction then you can model everything as random oracle. In that sense you can probably say hash-based signature is "simple." The non-trivial part is computing the exact probability that these schemes fail, which is critical to choosing good parameters for these schemes. See, e.g. eprint.iacr.org/2023/408.pdf $\endgroup$ Commented Jun 27 at 17:03

1 Answer 1

3
$\begingroup$

The short answer is no, this is known to be impossible. See below for some caveats.

The impossibility. Impagliazzo and Rudich showed already in 1988 that key agreement in the random oracle model is impossible. Key agreement captures any interactive protocol that allows two parties (say, Alice and Bob) to establish a secret that looks random to an eavesdropper. Public key encryption (PKE) is a special form of key agreement where Alice sends one message (the public key) and Bob replies with one message (the ciphertext encrypting a random shared key). Thus, this result rules out PKE in the random oracle model.

Since the random oracle model is an idealized hash function, this result rules out key agreement that makes only black-box use of a hash function. Informally speaking, a black-box construction is a construction that only uses the interface of a hash function and does not need to know how it works internally, see here for a precise definition. The vast majority of constructions in cryptography is black-box and non-black-box constructions tend to be extremely inefficient.

I recommend Section 4.1 in this paper for a simpler proof of the result by Impagliazzo and Rudich for the special case of perfectly correct key agreement.

Non-black-box constructions. This result leaves the possibility of a non-black-box construction from hash functions, however we currently do not know of a non-black-box construction of key agreement from hash functions. At least a variant of this question, to build key agreement from one-way functions in a non-black-box way, is a very fundamental question and has received a lot of attention since the work by Impagliazzo and Rudich. So I think it is fair to say that this approach seems very difficult.

I think the best approach we have so far for a non-black-box construction is the PKE by Sahai and Waters that uses indistinguishability obfuscation (iO) and one-way functions. However, iO is an extremely powerful primitive and to get a construction from hash functions, we would have to build iO from hash functions. Most of the current attempts to build iO combine several algebraic assumptions e.g. from lattice and code-based cryptography (and we know how to build PKE from these assumptions directly). Thus, these constructions will not be suitable to solve this question. But there are a few exceptions, like this idea.

Fine-grained PKE. Another approach to circumvent this impossibility result is to relax the security requirement. The standard definition of security for PKE (or any cryptographic primitive) says that there should be a super-polynomial gap in the runtime of honest users and an adversary. If we allow a polynomial gap instead, PKE from hash function becomes possible. This was already explored in 1974 by Ralph Merkle. His protocol, known as Merkle’s puzzle, is a non-interactive key exchange (NIKE) with a quadratic gap between honest users and the adversary’s runtime. A NIKE can be trivially transformed in a PKE.

The quadratic gap is known to be optimal, as shown by Barak and Mahmoody.

This approach will likely not yield a practical scheme anytime soon. To protect against an adversary that makes $2^{128}$ hash function evaluations, both generation of a public key and a ciphertext would each take $2^{64}$ hash evaluations. This is infeasible for consumer hardware and even a state-of the art bitcoin miner like this one would need ~620 years (and an incredible amount of electricity) to generate one public key or ciphertext. Also ciphertexts and public keys would be 512 EiB in size!

Simplicity of hash-based constructions. Finally, I want to add that I disagree with your view that hash-based constructions are “simpler” or “more secure”, as you suggest in your post. Hash-based constructions can indeed be explained without any background in fields like number theory or algebraic geometry. However these explanations typically sweep the following two points under the rug:

  1. The design and especially the analysis of hash functions is quite complicated and cumbersome.

  2. Many cryptographic primitives use the hash function as a random oracle. However, this is an idealization and often very little is known about the security without this idealization.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.