Let's imagine that we have some symmetrical encryption algorithm, that has only two functions: Encrypt(Data, Key) and Decrypt(Data, Key). Let's say that the algorithm is strong and quick, but we don't know how it works. Is it possible only using those two functions to create a usable asymmetrical encryption algorithm? If not, is there any way to add anything that will help us create one?


1 Answer 1


It is not known whether it is possible to construct secure public-key encryption schemes from private-key ones (and by extension, from one-way functions). From Barak's recent survey:

One could ask if there really is an inherent difference between public-key and private-key cryptography or maybe this is simply a reflection of our ignorance. That is, is it is not possible to build a public-key cryptosystem out of an arbitrary one-way function and hence base it on the same assumptions as private-key encryption? The answer is that we do not know

In fact, this is one of the most important open questions in cryptography, along with the question of whether one-way functions exist. So, in practice you can consider that it is not possible, and consult the above for a survey of the known methods to construct public-key cryptosystems.

See also Impagliazzo's "Five Worlds"; your question can be reworded as: is it possible that we live in Minicrypt, the world where one-way functions exist but public-key cryptography does not?

  • $\begingroup$ We can build signature schemes out of arbitrary one-way functions. $\endgroup$
    – forest
    Commented Jul 16, 2018 at 23:04
  • $\begingroup$ @forest It could be argued that signature schemes are related to public-key cryptosystems only in a superficial way, and that they fundamentally belong to private-key cryptography, precisely because they can be constructed from OWFs. $\endgroup$
    – fkraiem
    Commented Jul 16, 2018 at 23:58

Your Answer

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

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