# Looking for a specific cryptosystem (encryption two times with two different keys and then decryption with another different key )

I am looking for a specific cryptosystem with the following properties:

Suppose a User (Say $User_1$) encrypts a message $M$ with the key $K_1$ (the resulted ciphertext is $C_1$). Another user, say $User_2$, encrypts the ciphertext $C_1$ with another key $K_2$ (the resulted ciphertext is $C_2$). Now, a third user (e.g., $User_3$) should be able to decrypt $C_2$ with the key $K_3$ to achieve the message $M$.

$C_1 = E_{K_1}(M)$

$C_2 = E_{K_2}(C_1)$

$M = D_{K_3}(C_2)$

Note: The keys may be related to each other, but they should be three different keys.

• You want him to be able to decrypt the result of double encryption but not decrypting either single encryption? Otherwise just give him both keys. You are assuming some trusted party generated the related keys, or need a process to produce such keys? Apr 6 '18 at 13:43
• Thanks @MeirMaor. Yes, I want the third user be able to decrypt the second ciphertext and achieve the original message without knowing the keys used for encryption of the message. Using either of a trusted third-party or a process is OK.
– star
Apr 6 '18 at 13:48

The standard answer to this is the Pollig-Hellman cipher.

Here's how it works; you have a large public prime $p$, and each key $k$ is a value relatively prime to $p-1$. Then, we have:

$$E_k(M) = M^k \bmod p$$

$$D_k(M) = M^{k^{-1} \bmod p-1} \bmod p$$

What this means is that we have:

$$E_{k_2}(E_{k_1}(M)) = E_{k_1 \cdot k_2 \bmod p-1}(M)$$

So, what you would do is have your TTP generate the three keys $k_1, k_2, k_3$ with $k_3 = k_1 \cdot k_2 \pmod {p-1}$, and you have the relation you're looking for.

• Thank you very much @poncho. Is it possible to have two completely different keys for encryption? In this solution, the second encrption is related to the first one. But, as these two times encryption are done by two different users, it is better to have two completely different keys. In your solution, the second user knows the key of the first user. Is the third user able to retrieve the first and second keys ($K_1$ and $K_2$) using the third key ($K_3$)? Note: He/she should not be able to retrieve $K_1$ and $K_2$ using $K_3$.
– star
Apr 6 '18 at 14:23
• @star: "In your solution, the second user knows the key of the first user."; no, he doesn't, all he knows is $k_2$; he has no information what $k_1$ might be. And, the third user (who knows $k_3$) cannot derive either $k_1$ or $k_2$; he knows what their product (modulo $p-1$) is, but nothing beyond that Apr 6 '18 at 14:33
• what does this mean: $D_k(M)=M^{k^{−1}mod p−1} mod p$. Is the $M$ the result of the first encryption?
– star
Apr 9 '18 at 10:15
• and also if a user encrypt a message $M$ as $C = E_{k_1.k_2 mod p-1}(M)$, then how the ciphertext $C$ can be decrypted?
– star
Apr 9 '18 at 10:20
• "Is the $M$ the result of the first encryption"; it's a free variable; it could be the result of the first encryption; or anything else you decide to apply the decryption operation to Apr 9 '18 at 11:35