# Could ANY cipher serve as the foundation for a public key cryptosystem?

My reasoning goes like this:

• In principle, any trapdoor function can serve as the foundation for an asymmetric encryption scheme.

• All ciphers are trapdoor functions, since it's easier to encrypt plaintext than it is to crack ciphertext. Put another way, it's easier to use key and plaintext to produce ciphertext, than it is to go backwards and use ciphertext to produce key and plaintext.

• Therefore, one could (at least in theory) devise a public key cryptosystem derived from any cipher, whether it be Caesar or AES.

This has the interesting implication that one could devise an asymmetric encryption scheme based on an existing asymmetric scheme + key + plaintext combo, and then derive another from that one, etc. etc.

I found this interesting quote which seems to confirm my hunch:

every problem X in NP has a naturally associated public-key cryptosystem (warning: it's a .PDF file)

• There is an impossibility proof for constructing asymmetric encryption for symmetric crypto in a blackbox fashion: Hash-based asymmetrical encryption (not digital signature) schemes? – CodesInChaos Oct 8 '18 at 8:21
• Since you can construct symmetric encryption schemes using hashes, this is sufficient. For example H(key || counter) xor plaintext is a stream cipher. You can use a four round feistel network to construct a block-cipher (see Luby-Rackoff), etc. – CodesInChaos Oct 8 '18 at 8:26
• You can construct symmetric encryption using hashes. So if you could construct asymmetric encryption from symmetric encryption, you could indirectly construct asymmetric encryption from hashes, which contradicts the impossibility proof. – CodesInChaos Oct 8 '18 at 8:50
• @MelerLawler No, first of all, the Caesar cipher is a classical cipher; it doesn't adhere to modern cryptographic principles. Second, Codes only has to show that he can construct a symmetric (block) cipher, there is no need to create a particular cipher scheme: note the "blackbox fashion" part of the first comment. – Maarten Bodewes Oct 8 '18 at 21:10
• You're the one stating that all ciphers are trapdoor functions. Codes has shown you a cipher that conclusively isn't a trapdoor function, because if it was it would be possible to construct asymmetric encryption. Therefore your statement has been proven to be false. – Maarten Bodewes Oct 8 '18 at 21:50

Let's take a look at the trapdoor function definition here (Wikipedia):

Here the public key operation is function $$f$$ (the black line).

What you've produced is a $$\text{Gen}$$ function that produces a public value $$ct$$ and a private key value $$(pt, k)$$. But you haven't supplied us a function $$f$$ - based on $$ct$$ - which is hard to inverse without the private key $$t$$ - consisting of the set $$(pt, k)$$ in your reasoning.

So you actually haven't produced a trapdoor function, and therefore your reasoning is flawed.

Image created by IkamusumeFan CC BY-SA 4.0, from Wikimedia Commons

Your reasoning is flawed. Producing a cipher text for a given key from plaintext without the key is no easier than the reverse for symmetric ciphers. Without the key k, producing ciphertext $$Enc_k(x)$$ is every bit as hard as $$Dec_k(x)$$ for many ciphers it is the same operation entirely (e.g anything in CTR mode). And even for common block ciphers there is great similarity between encrypt and decrypt.

For a public key system I need some operation which can be done without the private key. AES etc. do not supply one. If you have the key both operations are easy, without the key they are darn near impossible.

• To clarify, I was not suggesting that producing a ciphertext for a key, without actually having the key, is easy. I meant, given a key and plaintext, it's easy to create the corresponding ciphertext, but harder to work backwards from the ciphertext to the key and plaintext. In other words, I'm asking if one could use the plaintext + key as private key, and ciphertext as public key. – Meler Lawler Oct 8 '18 at 7:02

Public key cryptosystem implies that there is also a private key somewhere. You can't have two different keys for symmetric encryption like AES. What key would you publish if you use AES? If you publish the only key you used for encryption you also publish they key for decryption!

• As I explained in my other comment, I think I should have clarified I'm talking about using the plaintext + key combo as private key, and the corresponding ciphertext as public key. – Meler Lawler Oct 8 '18 at 7:04
• Ok I think I get you now. But what algorithm or mathematical formula would you use to encrypt (using cipher text) and decrypt (using plaintext-key combo)? Don't we need some sort of mathematical formula like RSA and elliptic curves? – daygoor Oct 8 '18 at 9:08
• Yes we would, and I have no idea what it would be. I presume it would depend on the symmetric cipher used as a base. I have read people say that in principle any trapdoor function can be used for this purpose, and it sounds like a really big claim. That's why I made this thread, to verify whether it is actually true. – Meler Lawler Oct 8 '18 at 9:10
• The problem is that cipher text (in symmetric encryption) is not unique to a specific plain text and key. You can get the same cipher text from different plain text and key combinations! While RSA has a public key that corresponds to one and only one private key. – daygoor Oct 8 '18 at 9:31
• Oh, that is a good point. Thanks for pointing that out. – Meler Lawler Oct 8 '18 at 19:28