About Anamorphic Cryptography

30 Apr, 2025

I recently discovered the excellent work of Giuseppe Persiano, Duong Hieu Phan and Moti Yung about Anamorphic cryptography.

IRL, Anamorphosis is a concept where an image changes depending on the viewer's perspective or POV. Meaning that, in cryptography, we can create ciphertexts that reveal different messages depending on the recipients, even though they use the same encrypted data.

The Idea

In a scenario where you are under the surveillance of a dictator that, because he's a dictator, can and will read all encrypted messages, forbid all trusted encryption schemes and impose you to give him your private keys.

In this senario, traditional encryption methods will fail, and won't help. You'd be required to use tricks and decoys to delay or deceive your opponent. Anamorphic cryptography tries to address this issue by creating two meaningfull cleartexts from one ciphertext, depending on the used secret key.

You have

$s k_{0}$ : a private key given to the dictator
$s k_{1}$ : another private key, now given to your desired recipient
$m_{0}$ : A decoy message, such as I love the Dictator.
$m_{1}$ : The actual secret message, such as I hate the Dictator.

You then encrypts the two messages with the public key:

$C = E n c (p k, m s g_{0}, m s g_{1})$

The Dictator will then decrypt with his private key $s k_{0}$ , and reveal the first message:

$D e c (s k_{0}, C) \to m_{0}$

Your recipient will also decrypt the same ciphertext with his key $s k_{1}$ , and reveal the second message:

$D e c (s k_{1}, C) \to m_{1}$

This way, the dictator is misled into thinking they have full control, while the actual secret message remains hidden. As far as the dictator knows, he has the ONLY real key needed for the ciphertext.

Implementation

Anamorphic cryptography may and can be implemented with various encryption schemes. You can use RSA-OAEP, Paillier, Goldwasser-Micali, ElGamal, Cramer-Shoup, or Smooth Projective Hash-based systems but, by far, ElGamal method is particularly well-suited for this purpose.

The ElGamal encryption scheme is based on the difficulty of the discrete logarithm problem just like Diffie-Hellman . Here's a quick recap of how it works:

Key Generation:
- Choose a large prime number $p$ .
- Choose a base $g$ for the discrete logarithm.
- Generate a secret key $s k$ .
- Compute the public key $p k = g^{s k} \mod p$ .
Encryption:
- For a message $m$ , generate a random value $r$ .
- Compute the ciphertext $(c_{1}, c_{2})$ where:
  $c_{1} = m \cdot p k^{r} \mod p$
  $c_{2} = g^{r} \mod p$
Decryption:
- To decrypt the ciphertext $(c_{1}, c_{2})$ :
  $m = c_{1} \cdot c_{2}^{- s k} \mod p$

ElGamal for Anamorphic Cryptography

We can modify the ElGamal method for anamorphic cryptography where, Alice and Bob needs to correspond, spied by the dictator Eve. Alice creates a secret key $s k_{a}$ and a public key $p k$ as usual. However, the random value $r$ is generated in a specific way to embed a secret message $h m$ to Bob.

Key Generation

Secret Key Generation:
- Choose a large prime number $p$ .
- Choose a base $g$ for the discrete logarithm.
- Generate a secret key $s k_{a}$ .
- Compute the public key $p k = g^{s k_{a}} \mod p$ .
Bob's Key Generation:
- generate a second secret key $s k_{b}$ for Bob.

Encryption

Message Preparation:
- Alice has two messages: $m$ (the decoy message for the dictator) and $h m$ (the secret message for Bob).
Random Value Generation:
- Instead of generating a random $r$ , Alice computes $r$ as:
  $r = (h m + s k_{b}) \mod p$
Ciphertext Generation:
- Alice can then compute the ciphertext as usual $(c_{1}, c_{2})$ where:
  $c_{1} = m \cdot p k^{r} \mod p$
  $c_{2} = g^{r} \mod p$

Decryption

Eves's Decryption:
- The dictator decrypts the ciphertext $(c_{1}, c_{2})$ using Alice's secret key (She knows it remember, she's a dictator), $s k_{a}$ :
  $m = c 1 \cdot c_{2}^{- s k} \mod p$
- Eve sees the decoy message $m$ .
Bob's Decryption:
- Bob decrypts the ciphertext $(c_{1}, c_{2})$ using his own secret key $s k_{b}$ :
  $v a l = c_{2} \cdot g^{- s k_{b}} \mod p$
- Wich simplifies to:
  $v a l = g^{r} \cdot g^{- s k_{b}} \mod p = g^{(h m + s k_{b}) - s k_{b}} \mod p = g^{h m} \mod p$
- Bob then solves the discrete logarithm problem to find $h m$ by searching for the value of $h m$ that satisfies $g^{h m} \mod p = v a l$ . Since $h m$ has a smaller range than $p$ , this search is practially feasible.

In summary, this approach allows Alice to send a secret message to Bob while deceiving the dictator Eve with a decoy message. Some people might not see how nice it is, but I plan to leverage this for a secret path routing system. Hope you found and you'll find it interesting,

See you,

https://eprint.iacr.org/2022/639.pdf
https://asecuritysite.com/principles_pub/ana

#anamorphic #cryptography #infosec