# Is there an asymmetric algorithm that can perform double encryption?

I'm looking for any asymmetric algorithm can perform the serial encryption, by serial I mean double or more encryption with different key (same key size). RSA can not do it since the cipher of the first encryption is to long to perform an other encryption with the same key length.

For example (from Yao, Yang & Xiong 2015):

We use $C = {\{ m\} _y}$ to denote encryption of a plaintext $m$ with a public key $y$. In addition, we use ${\{ m\} _{{y_{1}}:{y_{N}}}}$ to denote a serial of encryptions under multiple public keys, i.e., $${\{ m\} _{{y_1}:{y_{N}}}} = {\{ \ldots{\{ {\{ m\} _{{y_N}}}\} _{{y_{N - 1}}}}\ldots\} _{{y_1}}}.$$

• If you have a sequence of RSA moduli that are strictly increasing and you have plaintext materials seperated into blocks of a constant size that is smaller than the least modulus, you could evidently do that multiple RSA encryption in the ordering of the sequence of the moduli.. – Mok-Kong Shen Mar 15 '16 at 13:25
• @Mok-KongShen thanks, I agree with you. i taught i can find other ideas for the same key size. since increasing size is not very suitable and i tested it. must every time increase at least by 88 bit. – Achille ishak Mar 15 '16 at 14:53
• I wonder how you got the value 88. If the block size of the plaintext material is mb bits (mb even), It is practically easy to obtain an RSA modulus n (n > 2**mb) that has mb + 2 bits. See Example 2 in Appendix of s13.zetaboards.com/Crypto/topic/7234475/1/ This implies that the differences between the bit sizes of successive elements in the sequence of RSA moduli could be as small as 2. – Mok-Kong Shen Mar 16 '16 at 12:09

No. ​ For semantic security, the encryption of a known plaintext with a given key must be overwhelmingly likely to have high entropy so for most plaintexts and keys, there must be lots of possible encryptions of the plaintext with the key.

So for most keys, the ciphertext space must be significantly larger than the plaintext space.

You might be interested in trapdoor permutations. The only candidates I'm aware of for [such permutations with domain not depending on the public key] come from multi-variate crypto.

On the other hand, it's easy for symmetric schemes to satisfy the deterministic version of CCA-security.

• You are genius. i also wonder if there is a semantically secure algorithm can do that. i will wait for others answers. if no answer i will set your is the one. – Achille ishak Mar 15 '16 at 11:45
• I just edited my answer to address that. ​ ​ – user991 Mar 15 '16 at 11:54
• the problem some research they use is it in theory and i wonder how they did their evaluation and experiment. sending emails, I get no answers. – Achille ishak Mar 15 '16 at 11:59
• Well, one could use RSA permutations with non-decreasing moduli. ​ ​ – user991 Mar 15 '16 at 12:02