Is it possible to derive an asymmetric algorithm from a symmetric one?

Given the advancements in quantum computing, there's a lot of incentive to move away from the usual asymmetric cryptography. Is there a way to turn a symmetric algorithm (e.g. AES) into an asymmetric one?

• You can build an asymmetric signature algorithm from a hash. But it's impossible to build asymmetric encryption from symmetric primitives. – CodesInChaos May 19 '17 at 22:17

Besides the hash based signature constructions mentioned by @CodesInChaos in the comments, it is entirely possible to build an asymmetric cryptosystem from a secret key one. Granted, the secret key ciphers in question are not typical, such as AES, but ones that support homomorphic operations on ciphertexts.

Homomorphic Encryption

A cipher supports a homomorphic operation on ciphertexts if $D(E(m1) * E(m2)) \equiv m1 * m2$, where $*$ is some operation such as addition or multiplication.

• Note that the operation performed on the ciphertexts does not necessarily have to be the "plaintext" operation: For example, the Paillier cryptosystem utilizes multiplication on ciphertexts to compute the addition of plaintexts.

Additionally, some such ciphers also offer the following property: $D(E(m1) + m2) \equiv m1 + m2$.

These properties can be used to create public key encryption systems.

An example

One example is provided in Fully Homomorphic Encryption Over The Integers:

• A public key consists of many secret-key encryptions of 0
• Random elements of the public key are summed together to form a ciphertext, and the message is added to the ciphertext
• $ciphertext := pb_{r_0} + pb_{r1} + pb_{r2} + ... + pb_{rn} + m$
• Decryption applies the decryption operation of the secret key cipher to obtain the plaintext message

In the above example, inverting a public key ciphertext without the private key is equivalent to solving a subset sum problem.

Acquiring the private key from the public key requires analyzing the secret key cipher that is used to instantiate the scheme. In the above design, they base the hardness of their secret key cipher on the Approximate Greatest Common Divisor problem.

However, you can instantiate such a scheme with any cipher that can perform the specified operations.

Now, the security of the constructed schemes is another question. But the mechanisms can be constructed. Additionally, many such schemes are not nearly as efficient as they would need to be in order to be utilized in practice: The ciphertexts and public keys can get huge.

More examples

1. Merkle's original knapsack cryptosystem can be deconstructed similarly.

2. Aside from encryptions of 0, you can also release encryptions of $1, 2, 3, ... N$ and sum elements randomly, with a final adjustment to set the message equal to your plaintext. (This requires a modular reduction step in order to function)

3. Or, there is another encoding still: release encryptions of powers of 2, as well as some 0s. Then, sum together some 0s randomly, then combine appropriate powers-of-2 such that the plaintext equivalent is equal to the message. (Powers of 2 are weight-1 words; They consist of a single set bit)

4. The last scheme that I know of is to release some encryptions of 0. Then, to encrypt, multiply each element of the public key by a large random (plaintext) integer, sum the results, then add the message to the ciphertext. This one seems to offer the prospect of smaller public keys then the alternatives.

• $pb_0 r_0 + pb_1 r_1 + pb_2 r_2 + ... + m$

I have yet to encounter such a scheme that is built using multiplication as the homomorphic operation; All of the above require only addition. By that I do not mean such schemes do not exist, I just don't know of any.

(Note: multiplication by plaintext is supported when ciphertexts support addition: $E(m) + E(m) \equiv E(m) * 2$

Why doesn't AES work with any of these?

"Normal" symmetric primitives are designed to destroy any semblance of structure. It's just a lot easier and faster to drown the information in impossibly complicated equations then it is to formulate something simple enough to provide the required properties while still providing security. Since the constructions need to be simple, it usually means the numbers need to be big, and this comes with a cost.

• Actually the definition of homomorphic encryption is a bit wider: $D(E(m1) + E(m2)) \equiv m1 \cdot m2$, i.e. the kind of operation done on the encrypted messages need not be the same to the one on the messages in plaintext. For example the sum of two ciphertexts could end up producing the product of the plaintext messages (or viceversa). – Bakuriu May 20 '17 at 6:29
• @Bakuriu That is a good point; I will edit the answer to include that. Thank you! – Ella Rose May 20 '17 at 16:24