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.

  • 1
    $\begingroup$ 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? $\endgroup$
    – Meir Maor
    Apr 6 '18 at 13:43
  • $\begingroup$ 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. $\endgroup$
    – 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.

  • $\begingroup$ 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$. $\endgroup$
    – star
    Apr 6 '18 at 14:23
  • $\begingroup$ @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 $\endgroup$
    – poncho
    Apr 6 '18 at 14:33
  • $\begingroup$ what does this mean: $D_k(M)=M^{k^{−1}mod p−1} mod p$. Is the $M$ the result of the first encryption? $\endgroup$
    – star
    Apr 9 '18 at 10:15
  • $\begingroup$ 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? $\endgroup$
    – star
    Apr 9 '18 at 10:20
  • $\begingroup$ "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 $\endgroup$
    – poncho
    Apr 9 '18 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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