Anamorphic encryption
An anamorphic extension of a PKE scheme lets a sender and a receiver who share a double key embed a covert message in ciphertexts of that scheme, such that an adversary holding the receiver’s secret key and choosing every message — the dictator — cannot distinguish these ciphertexts from regular encryptions — PPY22.
Syntax
An anamorphic extension of , with message space and covert message space , is a triple of efficient algorithms :
- , a randomized algorithm outputting a key pair for and a double key ,
- , a randomized, possibly stateful, algorithm taking a regular message and a covert message , outputting a ciphertext ,
- , a deterministic algorithm outputting a covert message.
denotes together with an anamorphic extension; this is the receiver-anamorphic syntax of PPY22. It is an anamorphic encryption scheme if it meets the requirements of § Anamorphic encryption schemes.
Properties
Correctness
For , is -correct if for all , , and ,
over and the randomness of . For a stateful , the bound holds for every with and in place of and , where are the outputs of successive calls on any pairs .
Security against the dictator
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{anam}}_{\mathsf{AME},\calA}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$
\State $(\pk_0, \sk_0) \gets \KeyGen(1^\secpar)$; $(\pk_1, \sk_1, \mathsf{dk}) \gets \mathsf{aGen}(1^\secpar)$
\State $\calO_0(m, \hat m) := \Enc(\pk_0, m)$ \Comment{Ignores $\hat m$}
\State $\calO_1(m, \hat m) := \mathsf{aEnc}(\pk_1, \mathsf{dk}, m, \hat m)$
\State $b' \gets \calA^{\calO_b}(\pk_b, \sk_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
is anamorphically secure if for all efficient ,
is negligible — PPY22.
The world-0 oracle ignores , so the dictator’s view in world 1 is computationally independent of the covert messages. A dictator that checks on each answer shows that recovers from anamorphic ciphertexts except with probability at most the decryption error of plus — standard.
Anamorphic encryption schemes
is an anamorphic encryption scheme if is IND-CPA-secure, for all , and is -correct for a negligible and anamorphically secure. Anamorphic security does not give IND-CPA security of , since its adversary holds .
Robustness
Robustness widens the range of to , with . An anamorphic encryption scheme is robust if for all and ,
over and the randomness of : covert decryption of a regular ciphertext reports that it carries no covert message — BGHMR24. In the model of PPY22 a receiver cannot tell whether a ciphertext carries a covert message — BGHMR24. The model of BGHMR24 also allows several double keys to be associated with a key pair after its deployment, which enables deniability when a double key depends only on the public key.
Variations
Sender-anamorphic encryption
Sender-anamorphic encryption, introduced in PPY22, targets a dictator that breaks the sender’s freedom to choose the messages it encrypts, as receiver-anamorphic encryption targets one that breaks the receiver’s privacy — WCHY23. The sender embeds a covert message in a ciphertext of the regular message the dictator dictates, and the sender and the covert receiver share no secret, whereas in receiver-anamorphic encryption they share the double key — WCHY23. The absence of a shared secret separates the two notions; the dictator of already chooses every regular message.
TODO: the syntax and security game, stated from PPY22 or from the reformulation of WCHY23, naming which: the keys of the sender, the covert receiver and the receiver of the regular message, and whether the dictator chooses the key pair of the receiver of the regular message or only holds it.
WCHY23 reformulate the notion as -sender-anamorphic encryption with (strong) security and robustness, and show that a strongly secure -sender-anamorphic scheme implies a reformulated receiver-anamorphic scheme, a public-key stegosystem in the sense of vAH04, and a generalized algorithm-substitution attack on PKE.
Fully asymmetric anamorphic encryption
CGM24a split the double key into an encryption component , which uses, and a decryption component , which also needs, so that a receiver can set up several independent covert channels for a single covert key. A fully asymmetric anamorphic extension of is a triple of efficient algorithms:
- , a randomized algorithm outputting a key pair for , a covert encryption key and a covert decryption key ,
- , a randomized algorithm taking and ,
- , a deterministic algorithm.
These are the algorithms of CGM24a, who write for . It is -correct if for all , and , over and the randomness of . Anamorphic security is with and , the dictator holding but neither covert key. Asymmetry is a separate game, in which the adversary holds the covert encryption key:
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{fa}}_{\mathsf{AME},\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk, \mathsf{dk}, \mathsf{tk}) \gets \mathsf{aGen}(1^\secpar)$; $b \getsr \bits$
\State $(m_0, m_1, \hat m_0, \hat m_1, \stA) \gets \calA(1^\secpar, \pk, \mathsf{dk})$
\State $c^* \gets \mathsf{aEnc}(\pk, \mathsf{dk}, m_b, \hat m_b)$
\State $b' \gets \calA(c^*, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
The adversary gets no oracle and not ; holding , it can compute itself. The extension is a fully asymmetric anamorphic encryption scheme if is IND-CPA-secure, , it is -correct for a negligible and anamorphically secure, and for all efficient
is negligible — CGM24a (Definition 10). An extension whose contains , and whose does not need , can be anamorphically secure and still fail this game: with and , the adversary decrypts — standard.
In this setting, called fully asymmetric in DL25 and CGM25 and asymmetric in CGM24b, a party able to send covert messages need not be able to read them — DL25.
Public-key anamorphic encryption
In public-key anamorphic encryption, a sender that has not coordinated with the receiver in any way, so that no secret is shared between them, can send the receiver a covert message that is hidden from a dictator controlling the receiver’s private key — PPY24.
TODO: the syntax and security game of PPY24: which keys the sender’s covert encryption takes ( alone or also a public anamorphic key), which key the receiver decrypts covert messages with, and whether the dictator, holding , must be unable only to learn or also to tell anamorphic ciphertexts from regular ones.
Anamorphic-resistant encryption
An IND-CPA-secure is anamorphic-resistant if every efficient anamorphic extension of it that is -correct for a negligible and anamorphically secure, in the sense of , has a covert message space of size for some polynomial , that is, covert bits per ciphertext — ABGMM25. ABGMM25 grade anamorphic resistance against several levels of anamorphic security; this section’s notion is resistance against extensions secure in the sense of .
DG25 introduced anamorphic-resistant encryption, with definitions under which covert communication over the scheme is either impossible or very slow, and by designing such schemes challenge the folklore belief that semantic security always enables some form of steganography. CCGM25 give IND-CPA-secure schemes that provably cannot be turned anamorphic; both use extremely lossy functions in the construction itself. The first is in the public-parameters model and also uses iO; the second, in the random-oracle model without public parameters or iO, uses robust extremely lossy functions with group structure, which CCGM25 define and realize.
Anamorphic signatures
In an anamorphic signature scheme a signer embeds a covert message in signatures for a party holding a double key, against a dictator that holds the signing key — KPPYZ23a. JS24 break and repair the unforgeability definitions of the anamorphic signature literature.
Other results
Constructions
- Receiver-anamorphic extensions exist for established schemes, among them the Naor–Yung CCA-secure construction (CPA-secure PKE + NIZK ⇒ CCA1-secure PKE), and a black-box rejection-sampling method embeds a small covert message in ciphertexts of a PKE scheme — PPY22. The rejection-sampling method is not secure for every IND-CPA-secure scheme — CGM25.
- Many existing encryption schemes admit anamorphic extensions — KPPYZ23b.
- ElGamal and Cramer–Shoup encryption satisfy selective randomness recoverability, which gives each a robust anamorphic extension, and RSA-OAEP has a robust anamorphic extension — BGHMR24.
- Hybrid encryption (KEM + SKE ⇒ PKE) and the IBE-to-CCA transform of CHK04 admit anamorphic extensions; some homomorphic schemes, among them the fully homomorphic scheme of GSW13, can be made anamorphic while keeping their homomorphism with respect to both the regular and the covert message — CGM24a.
- The CCA-secure scheme of KW19b is public-key anamorphic — PPY24. PPY24 also identify a sufficient condition under which a CCA-secure scheme black-box reduced from a CPA-secure scheme gives rise to an anamorphic encryption scheme, and one further property of the reduction under which it yields a public-key anamorphic scheme.
- From iO, every IND-CPA-secure PKE scheme with sufficiently high min-entropy ciphertexts has a fully asymmetric anamorphic extension with a small covert message space — CGM25. Fully asymmetric anamorphic homomorphic encryption exists under LWE — DL25.
- The Dual Regev scheme of GPV08 has an anamorphic broadcast mode, in which one ciphertext for a single public key carries a separate covert message to each of several anonymous groups of receivers — DPPY25.
Limits
- An anamorphic extension that uses only as an oracle, and works for every IND-CPA-secure , has a covert message space of size at most ; no such black-box extension is asymmetric, whatever the size of its covert message space. With further assumptions on , generic extensions reach exponential-size covert message spaces — CGM24b.
- Some contrived IND-CPA-secure scheme makes the rejection-sampling method of PPY22 insecure, and stateless black-box anamorphic extensions of every IND-CPA-secure scheme do not exist unless the target notion is weakened or satisfies further assumptions; the impossibility persists for extensions that resort to non-black-box techniques such as NIZKs, iO or garbling — CGM25.
- Under conditions identified by CCGM25, anamorphic encryption is equivalent to an algorithm-substitution attack, so their anamorphic-resistant schemes are IND-CPA-secure schemes provably resistant to subversion — CCGM25. Anamorphic-resistant encryption follows from PKE and extremely lossy functions, both known from exponential DDH, without random oracles — ABGMM25.