There exists a function $f$ such that if one-way functions exist then $f$ is a one-way function. Such a function is called a universal one-way function.

Now the public-key encryption schemes that I’ve come across use functions for which it is an open problem whether they are one-way functions even under the assumption that one-way functions exist. My question is, has anyone implemented a public-key encryption scheme based on a universal one-way function?

If not, what makes a universal one-way function impractical to use?

  • 3
    $\begingroup$ Public key encryption requires trapdoor one-way functions (it is in "cryptomania" instead of "minicrypt"). Are universal trapdoor one-way functions known to exist? Anyway even if they are universal constructions such as these are typically highly inefficient, so nobody would want to use one in practice (although you could of course implement one for fun if you want to). $\endgroup$ – Mark Sep 13 '20 at 4:10
  • 1
    $\begingroup$ @Mark We don't know that "Public key encryption requires trapdoor one-way functions". It's a reasonable conjecture, but non-relativizing constructions of PKE from OWF have never been ruled out. It's a reasonable conjecture. $\endgroup$ – Maeher Sep 13 '20 at 10:52
  • $\begingroup$ @Maeher Regardless, is there an encryption scheme which if PKE exists then it is guaranteed to be a PKE? $\endgroup$ – Keshav Srinivasan Sep 13 '20 at 14:19
  • $\begingroup$ @Maeher Sorry, one should replace what I said with "There are no known constructions of public key encryption from one way functions" $\endgroup$ – Mark Sep 13 '20 at 15:08
  • $\begingroup$ To be precise, public-key encryption requires trapdoor predicates -- trapdoor functions are sufficient but not necessary. $\endgroup$ – Occams_Trimmer Sep 14 '20 at 14:14

We don't know of any construction of PKE based on a universal OWF. Actually, we do not even have any plausible candidate PKE that would be based on an arbitrary OWF. Obtaining such constructions is a major open problem. We know that there is no black-box construction of PKE from any OWF by a seminal result of Impagliazzo and Rudich. Of course, we cannot rule out all possible constructions: since we believe that both PKE and OWF exist, a valid construction of PKE from any OWF is: ignore the OWF and take a PKE which exists.

In any case, universal OWFs are too inefficient to be really useful in practice. Levin's initial construction is really, really super-duper inefficient. Levin also gave a more combinatorial construction based on tiling in this paper, but that would still be way to inefficient for any practical purpose (though perhaps "implementable in theory", unlike his first candidate).

There are constructions of universal PKE (that are secure if any PKE exists), see for example the pointers in this paper, paragraph "Brief history of combiners and universal cryptographic primitives" in the introduction.

EDIT: answering the question in the comment

Universal cryptographic primitives are closely related to cryptographic combiners. A $(1,n)$-cryptographic combiner takes $n$ candidate cryptographic primitives, where one of them is guaranteed to be correct and secure (but we do not know which one), and produces a single combined correct and secure primitive.

Combiners and universal constructions have been formally studied in this work. The authors formally prove that the existence of a $(1,n)$-combiner for a primitive implies a universal construction of the primitive.

Then, their paper also provides a $(1,n)$-combiner for key agreement protocols; by their previous result, this implies a construction of universal key agreement. Furthermore, their construction is round-preserving: the final key agreement has the same round complexity as the candidate which had the highest round complexity in the combination.

This is actually more general than the result you are looking for, because a PKE is just a 2-round key agreement. Indeed, take a 2-round key agreement protocol between Alice and Bob, where Alice speaks first. Define the first flow of Alice to be the public key, and the secret state that she keeps to be the secret key. Given this first flow, Bob can compute his output, i.e., the shared key (since he will not receive any further message). An encryption of a message $m$ can then simply be defined as (second flow of the protocol, $K \oplus m$) (where $\oplus$ denotes the bitwise XOR): given the second flow and her secret state, Alice can recover $K$ (by the correctness of the key agreement), from which she can unmask $K \oplus m$ and retrieve $m$. Security of the encryption scheme follows from the unpredictability of the key in the KA protocol.

Furthermore, this is actually a 2-way equivalence: given a PKE, it is straightforward to build a 2-round KA protocol (I'll let you check it).

Summing up: there is a $(1,n)$-combiner for two-round key agreements (hence in particular for PKE) by the result of the work I pointed to above, where the result of the combination is still a 2 round KA. By their other result, this implies a universal construction of two-round key agreement. By the simple reduction I gave above (which is a standard exercise), this implies a universal PKE.

  • $\begingroup$ Can you elaborate on universal PKE's? That's what my question was really about, I had just incorrectly assumed that a PKE based on a universal one-way function was universal. In any case, I looked at that paragraph in the paper, but which of its citations describes the construction of a universal PKE? $\endgroup$ – Keshav Srinivasan Sep 14 '20 at 20:29
  • $\begingroup$ Ok, added a paragraph on universal PKE :) $\endgroup$ – Geoffroy Couteau Sep 15 '20 at 8:02
  • $\begingroup$ So is this universal PKE impractical to use in real-world applications? $\endgroup$ – Keshav Srinivasan Sep 15 '20 at 11:24
  • $\begingroup$ Yes. Completely impractical :) $\endgroup$ – Geoffroy Couteau Sep 15 '20 at 11:26
  • $\begingroup$ Why is it impractical? $\endgroup$ – Keshav Srinivasan Sep 15 '20 at 11:27

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.