Anamorphic Encryption with CCA Security: A Standard Model Construction Shujun Wang1 , Jianting Ning2 , Qinyi Li1 , and Leo Yu Zhang1 Griffith University, Australia {[email protected], [email protected], [email protected]} 2 Wuhan University, China [email protected]
arXiv:2604.07771v1 [cs.CR] 9 Apr 2026
1
Abstract. Anamorphic encryption serves as a vital tool for covert communication, maintaining secrecy even during post-compromise scenarios. Particularly in the receiver-anamorphic setting, a user can shield hidden messages even when coerced into surrendering their secret keys. However, a major bottleneck in existing research is the reliance on CPAsecurity, leaving the construction of a generic, CCA-secure anamorphic scheme in the standard model as a persistent open challenge. To bridge this gap, we formalize the Anamorphic Key Encapsulation Mechanism (AKEM), encompassing both Public-Key (PKAKEM) and SymmetricKey (SKAKEM) variants. We propose generic constructions for these primitives, which can be instantiated using any KEM that facilitates randomness recovery. Notably, our framework achieves strong IND-CCA (sIND-CCA) security for the covert channel. We provide a rigorous formal proof in the standard model, demonstrating resilience against a "dictator" who controls the decapsulation key. The security of our approach is anchored in the injective property of the base KEM, which ensures a unique mapping between ciphertexts and randomness. By integrating anamorphism into the KEM-DEM paradigm, our work significantly enhances the practical utility of covert channels within modern cryptographic infrastructures. Keywords: Anamorphic encryption · Key encapsulation mechanism · CCA security · Public key encryption.
1
Introduction
The "Crypto Wars" represent a pivotal political and technological conflict with significant implications for the global digital landscape [1]. At its core, the confrontation involves a vigorous debate between cryptographers and policymakers over the fundamental tension between "encryption restrictions" and "privacy protection." The role of cryptography in safeguarding privacy is fundamentally reliant on two key assumptions: Firstly, the sender-freedom assumption, which asserts that users can freely select their communication content without thirdparty interference; and secondly, the receiver-privacy assumption, which requires
2
S. Wang et al.
that the recipient’s private key remain strictly confidential. However, within the context of the Crypto Wars, dictator demands—such as those from powerful governments—are seeking to challenge these two foundational assumptions. To address the disruptive challenges posed to foundational cryptographic assumptions in environments with heavy censorship, Persiano et al. [2] introduced the paradigm of "Anamorphic Encryption (AME)." A core design principle of the paradigm acknowledges that deploying a new, dedicated encryption scheme for secret communication would readily arouse a dictator’s suspicion and be subsequently blocked. Consequently, AME is ingeniously built upon existing, widely deployed Public-Key Encryption (PKE) systems. The objective is to enable communicating parties to embed a covert channel, imperceptible to the dictator, within a seemingly conventional encrypted channel for the transmission of covert information. Specifically, AME is categorized into two types: SenderAME [3], which aims to counteract disruption of the sender-freedom assumption, and Receiver-AME [2], which focuses on scenarios where the receiver-privacy assumption is compromised. We focus on Receiver-AME, where parties supplement a standard (pk, sk) pair with a pre-shared double key. Under coercive scrutiny, the receiver strategically yields only sk as their purported sole secret; meanwhile, the undisclosed double key preserves the receiver’s ability to recover covert messages. From the dictator’s perspective, an anamorphic ciphertext that embeds a covert message must be computationally indistinguishable from a normal ciphertext generated with the public key pk. In prior works, the double key was conceived as a symmetric shared secret [2] [4] [5]. Subsequently, the concept of Public-Key Anamorphic Encryption was introduced, wherein Persiano et al. [6] proposed a variant where the double key is set to the empty string ϵ — a design that intriguingly obviates the necessity of privately transmitting the double key to the receiver. More recently, Catalano et al. [7] developed Fully Asymmetric Anamorphic Encryption, featuring a non-null double key structured as an asymmetric pair (dk, tk). However, regardless of whether the double key is symmetric or asymmetric, the vast majority of existing anamorphic schemes provide insufficient security guarantees for covert messages, predominantly settling for chosen-plaintext attack (CPA) security. Recent work by Banerjee et al. [8] achieved Replayable Chosen-Ciphertext Attack (RCCA) security [9] [10] for covert messages in the asymmetric setting. However, their approach, based on the Fujisaki-Okamoto (FO) transform [11] within the Random Oracle Model (ROM) [12] [13], suffers from limited generality and falls short of the ideal Chosen-Ciphertext Attack (CCA) security [14]. Choi et al. [15] pioneered the conceptual framework for CCA-security regarding covert messages, a significant contribution that addresses a theoretical void in anamorphic encryption. Despite its conceptual merits, the work provides neither a formalization of the construction nor a reductionbased security proof targeting that specific scheme. Furthermore, their methodology intrinsically relies on a monolithic PKE paradigm, which fundamentally diverges from modern cryptographic practice. In real-world deployments, publickey operations are almost exclusively instantiated via KEMs due to their effi-
Title Suppressed Due to Excessive Length
3
ciency and structural modularity in hybrid encryption. By treating the primitive as a traditional PKE, their design tightly couples the normal message m and the covert message m′ to derive the encryption randomness r. This design introduces a critical vulnerability: any modification of m by a dictator—even if m′ remains untouched—precludes the receiver from reconstructing r. This “all-ornothing” dependency renders the covert channel excessively fragile. Given these cumulative limitations, the following question arises: Is it possible to design a generic transformation for anamorphic encryption spanning both symmetric and asymmetric settings that achieves provable CCA security in the standard model without creating a fragile dependency between the normal and covert message spaces? 1.1
Our Contributions
In this work, we answer the question aforementioned in the affirmative sense. Our main contributions are summarized as follows: – We formalize the notions of Public-Key and Symmetric-Key Anamorphic Key Encapsulation Mechanism (PKAKEM and SKAKEM, respectively), which enable covert communication secure against a dictator holding the decapsulation key. By bridging the gap between anamorphism and the prevailing KEM-DEM paradigm, our work significantly improves the practical viability of anamorphic encryption for modern cryptographic ecosystems. – We present concrete constructions for PKAKEM and SKAKEM, which can be instantiated from any KEM that supports randomness recovery. We formally prove the anamorphic security of our constructions, which ensures that normal and anamorphic ciphertexts are computationally indistinguishable from the dictator. – We achieve strong Indistinguishability under Chosen-Ciphertext Attack (sINDCCA) security for covert messages, rigorously proven in the standard model. By decoupling the normal message from the covert message, thereby overcoming the “all-or-nothing” dependency of prior designs and rendering covert retrieval resilient to alterations of the normal ciphertext. 1.2
Technique Overview
The technical foundation of our paper lies in harmonizing the modern KEMDEM paradigm with anamorphic cryptography. By leveraging KEM primitive [16] [17] [18] [19] [20] as a building block, we develop PKAKEM and SKAKEM. The core technical challenge addressed in this work is the realization of strong Indistinguishability under Chosen-Ciphertext Attack (sIND-CCA) security within the standard model. In our context, "strong" security denotes that covert message confidentiality is preserved even against an adversary (e.g., a dictator) who possesses the legitimate decapsulation keys. Unlike prior attempts that suffer from an “all-or-nothing” dependency, our approach introduces a decoupling mechanism between the normal and covert message spaces. Such a design enables
4
S. Wang et al.
successful covert retrieval even when the normal message undergoes malicious alterations. The security of an anamorphic system is anchored in the notion of anamorphic security. While standard KEM encapsulation utilizes fresh randomness to generate ciphertexts and keys, our approach uses this entropy as a covert channel. Specifically, we substitute the original random coins with a pseudorandom value deterministically derived from the covert message. The substitution is undetectable to a polynomial-time dictator, as the pseudorandom values effectively mimic the uniform randomness of an honest encapsulation, ensuring that the two distributions are computationally indistinguishable. In our concrete constructions, the pseudorandomness for PKAKEM is sourced from the pseudorandom properties of both the covert message’s ciphertext and the accompanying Message Authentication Code (MAC), whereas SKAKEM relies on an Invertible Pseudorandom Function (IPF) to ensure the indistinguishability of its output. However, achieving anamorphic security is merely the preliminary requirement. The core technical challenge is ensuring sIND-CCA security for covert messages against an active, decapsulation-key-holding dictator. A naive strategy might attempt to leverage the Existential Unforgeability against Chosen-Message Attacks (EUF-CMA) security of a MAC to detect ciphertext tampering; yet, this approach fails to prevent a "many-to-one" mapping problem. Specifically, an adversary could craft a related ciphertext that maps to the same internal pseudorandom coins as the challenge, causing the decapsulation oracle to leak critical information and leading to a complete collapse of CCA security. To mitigate this, Choi et al. [15] proposed binding the normal message and the covert message within an authenticated encryption framework. However, such a rigid coupling introduces a critical fragility: any modification to the normal message by the dictator—even if the covert payload is untouched—precludes the reconstruction of the shared randomness, rendering the covert channel unusable. Our solution is to deploy the anamorphic transformation within a KEM framework that supports randomness recovery. The intrinsic structure of such KEMs ensures a stronger, typically injective, binding between the ciphertext and the randomness used for its generation. This structural property fundamentally decouples the normal message from the covert message, breaking the rigid ’all-or-nothing’ dependency that plagued prior designs. Beyond establishing a rigorous sIND-CCA security proof in the standard model, our construction achieves a seamless integration of anamorphism into mainstream cryptographic ecosystems. Such an alignment provides a novel and generalizable foundation for the eventual standardization and widespread deployment of anamorphic cryptography.
2
Preliminaries
2.1
Notation
Let Si denote the event that the adversary A succeeds in game Gi , and let | Pr[Si ]| be the probability of its occurrence. For a finite set X, the notation
Title Suppressed Due to Excessive Length
5
$
x ← − X denotes that x is sampled uniformly at random from X. Moreover, y ← AO1 ,O2 ,... indicates that y is the output of the probabilistic algorithm A that gives the oracle access to O1 , O2 and so on. 2.2
Pseudorandom Function
Let F (k, x) be a Pseudorandom Function (PRF) [21]. We say that F is a secure PRF if for every Probabilistic Polynomial-Time (PPT) distinguisher D, the advantage of D in distinguishing between the output of F (with a key k chosen uniformly at random) and the output of a truly random function f is negligible in the security parameter λ: F (k,·) λ (1 ) = 1] − Pr[Df (·) (1λ ) = 1] ≤ negl(λ). AdvPRF F,D (λ) = Pr[D
2.3
Message Authentication Code
A Message Authentication Code (MAC) [22] is a cryptographic primitive designed to ensure the integrity and authenticity of messages. Formally, a MAC scheme consists of the following three algorithms, defined over a key space K, a message space M and a tag space T : – k ← MAC.KGen(1λ ): The probabilistic key generation algorithm takes the security parameter 1λ as input and returns a secret key k ∈ K. – τ ← MAC.Tag(k, m): The probabilistic authentication algorithm takes a secret key k and a message m ∈ M to produce an authentication tag τ ∈ T . – b ← MAC.Verify(k, m, τ ): The deterministic verification algorithm takes a key k, a message m, and a tag τ as input, and outputs a bit b ∈ {0, 1}. Here, b = 1 indicates that the tag is valid, while b = 0 denotes invalidity. A MAC scheme is considered secure if it provides Strong Existential Unforgeability against Chosen-Message Attacks (SUF-CMA) [23]. Formally, for any PPT adversary A with access to the authentication oracle OMAC.Tag (k, ·) and the verification oracle OMAC.Verify (k, ·, ·), the advantage of A in forging a valid message-tag pair is negligible with respect to the security parameter λ. Specifically, A succeeds if it outputs a pair (m′ , τ ′ ) such that: – MAC.Verify(k, m′ , τ ′ ) = 1; – The specific pair (m′ , τ ′ ) was never returned by the authentication oracle OMAC.Tag (k, ·). The SUF-CMA advantage of A is defined as: k ← MAC.KGen(1λ ); OMAC.Tag (k,·),OMAC.Verify (k,·,·) λ ′ ′ AdvSUF-CMA (1 ) : ≤ negl(λ), MAC,A (λ) = Pr (m , τ ) ← A MAC.Verify(k, m′ , τ ′ ) = 1 ∧ (m′ , τ ′ ) ∈ /Q where Q denotes the set of all message-tag pairs (m, τ ) that were generated and returned by the authentication oracle OMAC.Tag during the game.
6
S. Wang et al.
Additionally, we define the pseudorandomness of a MAC scheme. For any PPT adversary A, there exists a negligible function negl(λ) such that for each security parameter λ ∈ N, the advantage of A satisfies: k ← MAC.KGen(1λ ); m ← A(1λ ); 1 τ0 ← MAC.Tag(k, m); pserand ′ :b=b− ≤ negl(λ). AdvMAC,A (λ) = 2 · Pr $ |τ0 | τ1 ← − {0, 1} ; 2 $ b← − {0, 1}; ′ b ← A(τb )
2.4
Public Key Encryption
A public key encryption (PKE) scheme [24] is formally defined by a tuple of three PPT algorithms (PKE.KGen, PKE.Enc, PKE.Dec): – (pk, sk) ← PKE.KGen(1λ ): The probabilistic key generation algorithm takes as input the security parameter 1λ and outputs a public/secret key pair (pk, sk). – C ← PKE.Enc(pk, m; r): The probabilistic encryption algorithm takes as input a public key pk, a message m and a randomness r to output a ciphertext C. – m ← PKE.Dec(sk, C): The deterministic decryption algorithm takes as input a secret key sk and a ciphertext C. Then it outputs the message m. Correctness. The PKE scheme satisfies correctness if for any key pair (pk, sk) generated by PKE.KGen(1λ ), any message m in the message space M, and any randomness r used during encryption, it holds that: PKE.Dec(sk, PKE.Enc(pk, m; r)) = m. Pseudorandomness. A PKE scheme provides ciphertext pseudorandomness [25] if, for any PPT adversary A, there exists a negligible function negl(λ) such that for each security parameter λ ∈ N, the advantage of A satisfies: (pk, sk) ← PKE.KGen(1λ ); m ← A(1λ , pk); C0 ← PKE.Enc(pk, m; r); 1 ′ Advpserand (λ) = 2 · Pr : b = b ≤ negl(λ). $ − |C | PKE,A C1 ← − {0, 1} 0 ; 2 $ b← − {0, 1}; ′ λ b ← A(1 , pk, Cb )
IND-CCA Security. A PKE scheme is IND-CCA secure if, for any PPT adversary A, there exists a negligible function negl(λ) such that for each security parameter λ ∈ N, the advantage of A satisfies:
Title Suppressed Due to Excessive Length
7
h i 1 IND-CCA AdvIND-CCA ≤ negl(λ), PKE,A (λ) = 2 · Pr ExptPKE,A (λ) = 1 − 2 where the security experiment ExptIND-CCA PKE,A (λ) is formally defined as follows. It is mandated that |m0 | = |m1 | and that A is strictly prohibited from querying the decryption oracle ODec (sk, ·) on the challenge ciphertext Cb . ExptIND-CCA PKE,A (λ) 1: (pk, sk) ← PKE.KGen(1λ ) 2: (m0 , m1 ) ← AODec (sk,·) (pk)
▷ Require |m0 | = |m1 |
$
3: b ← − {0, 1} 4: Cb ← PKE.Enc(pk, mb ) 5: b′ ← AODec (sk,·) (Cb ) ▷ Cannot query Cb to ODec 6: return 1 if b = b′ ; otherwise, return 0.
2.5
Randomness-Recoverable Key Encapsulation Mechanisms
A Randomness-Recoverable Key Encapsulation Mechanism (RR-KEM) is defined by a tuple of three polynomial-time algorithms over a session key space K, a ciphertext space C, and a randomness space R: – (ek, dk) ← KEMRR .KGen(1λ ): The probabilistic key generation algorithm takes the security parameter 1λ as input and outputs an encapsulation key ek and a decapsulation key dk. – (K, C) ← KEMRR .Encaps(ek, re ): The probabilistic encapsulation algorithm takes as input an encapsulation key ek and explicitly uses randomness re ∈ R. It outputs a session key K ∈ K and a ciphertext C ∈ C. – (K, re )/⊥ ← KEMRR .Decaps(dk, C): The deterministic decapsulation algorithm takes as input a decapsulation key dk and a ciphertext C. It outputs the recovered session key K and the underlying randomness re , or a rejection symbol ⊥ if decapsulation fails. Correctness. RR-KEM satisfies the correctness if, for any key pair (ek, dk) generated by KEMRR .KGen(1λ )and any randomness re ∈ R used during encapsulation, it holds that: Pr[KEMRR .Decaps(dk, C) = (K, re ) : (K, C) ← KEMRR .Encaps(ek, re )] = 1. 2.6
Invertible Pseudorandom Functions
An Invertible Pseudorandom Function (IPF) [26] Finv is defined over a key space KI , a domain XI and a range YI : KI × XI → YI . It comprises a probabilistic setup algorithm and two deterministic evaluation algorithms: – kI ← IPF.Setup(1λ ): Takes the security parameter 1λ as input and outputs a key kI ∈ KI .
8
S. Wang et al.
– y ← Finv (kI , x): Takes a key kI and an element x ∈ XI as input, and outputs an element y ∈ YI . −1 – x/⊥ ← Finv (kI , y): Takes a key kI and an element y ∈ YI as input, and outputs either an element x ∈ XI or a rejection symbol ⊥. Injectivity. For every security parameter λ and any key kI generated by IPF.Setup(1λ ), the function Finv (kI , ·) is strictly injective from XI to YI . Security. An IPF is considered secure if, for any PPT adversary A, its advantage in distinguishing Finv from a truly random injective function is negligible: h i −1 λ Finv (kI ,·),Finv (kI ,·) λ AdvIPF (1 ) = 1 Finv ,A (λ) = Pr kI ← IPF.Setup(1 ) : A h i −1 $ − Pr R ← − InjFuns[XI , YI ] : AR(·),R (·) (1λ ) = 1 ≤ negl(λ), where InjFuns[XI , YI ] denotes the set of all injective functions mapping from XI to YI . For any sampled random function R, its inverse R−1 is defined such that it maps elements from YI back to XI ∪{⊥}. Specifically, R−1 (y) = x if R(x) = y; otherwise, it returns ⊥. Furthermore, when the domain and range coincide (i.e., XI = YI ), InjFuns[XI , YI ] represents the set of all permutations over XI .
3
Anamorphic Key Encapsulation Mechanism
3.1
Public Key Anamorphic KEM
Definition 1 (Public Key Anamorphic KEM). A public key anamorphic KEM (PKAKEM) with a covert message space M′ is defined by a tuple of three algorithms: – (ek, dk, dk ′ , tk ′ ) ← PKAKEM.aGen(1λ ): The probabilistic anamorphic key generation algorithm takes the security parameter 1λ as input, and outputs a pair of standard encapsulation/decapsulation keys (ek, dk), along with a public/secret key pair (dk ′ , tk ′ ) for the receiver of the covert channel. – (K, act) ← PKAKEM.aEnc(1λ , ek, dk ′ , amsg): The probabilistic anamorphic encryption algorithm takes as input the security parameter 1λ , an encapsulation key ek, a covert receiver’s public key dk ′ and a covert message amsg ∈ M′ . It outputs a standard session key K and an anamorphic ciphertext act. – amsg/⊥ ← PKAKEM.aDec(dk, tk ′ , act): The deterministic anamorphic decryption algorithm takes as input a standard decapsulation key dk, a covert trapdoor key tk ′ , and an anamorphic ciphertext act. It outputs the recovered covert message amsg, or an error symbol ⊥ if extraction fails. Correctness. PKAKEM satisfies correctness if, for any covert message amsg ∈ M′ , the probability of decapsulation failure is negligible: (ek, dk, dk ′ , tk ′ ) ← PKAKEM.aGen(1λ ); Pr amsg ̸= PKAKEM.aDec(dk, tk ′ , act) : (K, act) ← PKAKEM.aEnc(1λ , ek, dk ′ , amsg)
Title Suppressed Due to Excessive Length
9
is negligible. Anamorphic security. PKAKEM achieves anamorphic security (i.e., indistinguishability between normal and anamorphic ciphertexts) if, for any PPT adversary A, the following advantage is negligible in λ: AdvAna-Security PKAKEM,A (λ) = |Pr[RealGPKAKEM (λ, A) = 1] − Pr[AnamorphicGPKAKEM (λ, A) = 1]| ≤ negl(λ), where the security games RealGPKAKEM and AnamorphicGPKAKEM are defined as follows: RealGPKAKEM (λ, A) $
(ek, dk) ← − KEMRR .KGen(1λ ) $
− R and returns KEMRR .Encaps(ek, re ) return AOe (ek,·) (ek, dk) where Oe (ek, amsg) computes re ←
AnamorphicGPKAKEM (λ, A) $
(ek, dk, dk ′ , tk ′ ) ← − PKAKEM.aGen(1λ ) ′
return AOa (ek,dk ,·) (ek, dk) where Oa (ek, dk ′ , amsg) returns PKAKEM.aEnc(1λ , ek, dk ′ , amsg) sIND-CCA security. PKAKEM achieves sIND-CCA security if, for any PPT adversary A, there exists a negligible function negl(λ) such that the advantage of A satisfies: sIND-CCA AdvsIND-CCA PKAKEM,A (λ) = 2 · Pr[ExptPKAKEM,A (λ) = 1] − 1/2 ≤ negl(λ),
where the security experiment ExptsIND-CCA PKAK,A (λ) is formally defined as follows: ExptsIND-CCA PKAKEM,A (λ) 1: (ek, dk, dk ′ , tk ′ ) ← PKAKEM.aGen(1λ ) ′ 2: (amsg0 , amsg1 ) ← APKAKEM.aDec(dk,tk ,·) (ek, dk, dk ′ )
▷ A knows dk
$
3: β ← − {0, 1} 4: actβ ← PKAKEM.aEnc(1λ , ek, dk ′ , amsgβ ) ′ 5: β ′ ← APKAKEM.aDec(dk,tk ,·) (actβ , ek, dk, dk ′ ) ′ 6: return 1 if β = β and actβ was never queried to aDec; otherwise 0.
Specific Construction. Let PKE denote a public key encryption scheme that provides ciphertext pseudorandomness and IND-CCA security. Let MAC be a message authentication code scheme that is pseudorandom and EUF-CMA secure. Let KEMRR be a randomness-recoverable KEM. The (Encode, Decode) pair constitutes an invertible transformation designed to preserve the statistical properties of its input. Specifically, for any input c′ , the encoded output re = Encode(c′ ) is computationally indistinguishable from a
10
S. Wang et al.
uniform random string in the randomness space R. Furthermore, the transformation is perfectly reversible, such that Decode(Encode(c′ )) = c′ holds for any valid input c′ . PKAKEM.aGen(1λ ) 1: (dk ′ , tk ′ ) ← PKE.Gen(1λ ) 2: (ek, dk) ← KEMRR .KGen(1λ ) 3: return (ek, dk, dk ′ , tk ′ )
PKAKEM.aEnc(1λ , ek, dk ′ , amsg) 1: mak ← MAC.KGen(1λ ) 2: c ← PKE. Enc(dk ′ , amsg ∥ mak) 3: τ ← MAC.Tag(mak, c) 4: c′ ← (c, τ ) 5: re ← Encode(c′ ) 6: (K, act) ← KEMRR .Encaps(ek; re ) 7: return (K, act)
PKAKEM.aDec(dk, tk ′ , act) 1: (K, re ) ← KEMRR .Decaps(dk, act) 2: c′ ← Decode(re ) 3: Parse c′ as (c, τ ) 4: amsg ∥ mak ← PKE.Dec(tk ′ , c) 5: if MAC.Verify(mak, c, τ ) = 0 then 6: return ⊥ 7: return amsg
3.2
Security Analysis of PKAKEM
Theorem 1. If PKE provides ciphertext pseudorandomness and MAC provides pseudorandomness, then the PKAKEM scheme achieves anamorphic security. Proof. We proceed via a sequence of computationally indistinguishable games G0 , G1 , and G2 . Let Si denote the event that the adversary A succeeds (i.e., outputs 1) in game Gi , and let Pr[Si ] be the probability of its occurrence. Game G0 : This game corresponds exactly to the AnamorphicGPKAKEM (λ, A) game. The challenger answers A’s oracle queries using the true anamorphic encryption algorithm. Thus: Pr[AnamorphicGPKAKEM (λ, A) = 1] = Pr[S0 ]. Game G1 : This game is identical to G0 , except that the oracle replaces the valid PKE ciphertext c with a uniformly random string. Specifically, upon receiving a query amsg, the oracle computes mak ← MAC.KGen(1λ ), samples $
c← − {0, 1}lc (where lc is the ciphertext length), computes τ ← MAC.Tag(mak, c), encodes re ← Encode(c ∥ τ ), and returns (K, act) ← KEMRR .Encaps(ek; re ).
Title Suppressed Due to Excessive Length
11
Lemma 1. For any PPT adversary A, there exists a PPT algorithm B1 such that: | Pr[S0 ] − Pr[S1 ]| = Advpserand PKE,B1 (λ). Proof. We construct a reduction algorithm B1 that plays the PKE pseudorandomness game against a challenger CPKE . Setup Phase: CPKE generates (pk, sk) ← PKE.KGen(1λ ) and sends pk to B1 . B1 implicitly sets the anamorphic public key dk ′ := pk. It generates the standard KEM keys (ek, dk) ← KEMRR .KGen(1λ ) and invokes AOa (·) (ek, dk, dk ′ ). Query Phase: When A submits a query amsg, B1 simulates the oracle Oa : 1. B1 generates mak ← MAC.KGen(1λ ). 2. B1 constructs the message m = amsg ∥ mak and submits it to CPKE . $
3. CPKE internally flips a coin b ← − {0, 1}. It computes C0 ← PKE.Enc(pk, m) $
and C1 ← − {0, 1}|C0 | , and returns the challenge Cb to B1 . 4. B1 receives Cb and computes τ ∗ ← MAC.Tag(mak, Cb ). 5. B1 computes re∗ ← Encode(Cb ∥ τ ∗ ) and returns (K, C) ← KEMRR .Encaps(ek; re∗ ) to A. Guess Phase: Eventually, A outputs a guess b′ . B1 outputs b′ as its guess for b. If CPKE chose b = 0, Cb is a valid ciphertext, and A’s view is perfectly identical to G0 . If CPKE chose b = 1, Cb is a uniformly random string, making A’s view perfectly identical to G1 . According to a standard cryptographic identity, the difference in A’s output probabilities between these two views is exactly the advantage function 2·| Pr[b = b′ ]−1/2| of B1 . Thus, the difference | Pr[S0 ]−Pr[S1 ]| is exactly bounded by Advpserand PKE,B1 (λ). Game G2 : This game modifies G1 by also replacing the MAC tag τ with a $ uniformly random string. Upon a query amsg, the oracle samples c ← − {0, 1}lc $
and τ ← − {0, 1}lτ (where lτ is the tag length), encodes re ← Encode(c ∥ τ ), and returns (K, act) ← KEMRR .Encaps(ek; re ). Lemma 2. For any PPT adversary A, there exists a PPT algorithm B2 such that: | Pr[S1 ] − Pr[S2 ]| = Advpserand MAC,B2 (λ). Proof. We construct B2 interacting with a MAC pseudorandomness challenger CMAC , which holds a hidden key k ← MAC.KGen(1λ ). Setup Phase: B2 independently generates (ek, dk) ← KEMRR .KGen(1λ ) and ′ (dk , tk ′ ) ← PKE.KGen(1λ ). It then invokes AOa (·) (ek, dk, dk ′ ). Query Phase: For each query amsg from A, B2 simulates the oracle: $
1. B2 samples a random string c∗ ← − {0, 1}lc and submits m = c∗ to CMAC . $
2. CMAC internally flips a coin b ← − {0, 1}. It computes τ0 ← MAC.Tag(k, m) $
and τ1 ← − {0, 1}|τ0 | , and returns the challenge τb to B2 .
12
S. Wang et al.
3. B2 receives τb , computes re∗ ← Encode(c∗ ∥ τb ), and returns (K, C) ← KEMRR .Encaps(ek; re∗ ) to A. Guess Phase: A outputs b′ . B2 outputs b′ as its guess for b. Analysis: If b = 0, τb is a valid MAC tag evaluated on the random string c∗ , which perfectly matches G1 . If b = 1, τb is drawn uniformly at random, which perfectly matches G2 . Therefore, the difference | Pr[S1 ] − Pr[S2 ]| is precisely bounded by B2 ’s advantage Advpserand MAC,B2 (λ). Conclusion: In G2 , the input to the encoding function is a bit-string (c ∥ τ ) $
where both components are sampled uniformly at random (c ← − {0, 1}lc and $
τ← − {0, 1}lτ ). By the implicit definition of Randomness-Recoverable KEMs, the mapping Encode deterministically transforms a uniformly distributed bit-string $ into uniformly distributed randomness re ← − R. Consequently, the simulated oracle in G2 is mathematically identical to an $ oracle that directly samples re ← − R and returns KEMRR .Encaps(ek; re ), which perfectly corresponds to the RealGPKAKEM (λ, A) game. Therefore: Pr[S2 ] = Pr[RealGPKAKEM (λ, A) = 1]. By summing the probability bounds across the sequence of games using the triangle inequality, the adversary’s total advantage is: AdvAna-Security PKAKEM,A (λ) = | Pr[S0 ] − Pr[S2 ]| ≤ | Pr[S0 ] − Pr[S1 ]| + | Pr[S1 ] − Pr[S2 ]| pserand = Advpserand PKE,B1 (λ) + AdvMAC,B2 (λ).
Since both the PKE and MAC schemes provide pseudorandomness, their respective advantage functions are negligible in λ. Therefore, the total distinguishing advantage is negligible, which completes the proof. Theorem 2. Assume PKE is an IND-CCA secure public-key encryption scheme, and MAC is a SUF-CMA message authentication code. Then the PKAKEM scheme achieves sIND-CCA security in the standard model. Proof. We proceed via a sequence of games. Let Si denote the event that the adversary A successfully guesses the challenge bit (i.e., β = β ′ ) in Game Gi . The advantage of A in Game Gi is defined as 2 · | Pr[Si ] − 1/2|. Game G0 : This is the original ExptsIND-CCA PKAKEM,A (λ) game. By definition, we have: AdvsIND-CCA PKAKEM,A (λ) = 2 · |Pr[S0 ] − 1/2| . Game G1 : This game is identical to G0 , except we modify how the challenger answers decryption queries in the second phase (after the challenge ciphertext act⋆ is issued). When A submits a query acti ̸= act⋆ , the challenger decodes it to (ci , τi ). If ci = c⋆ , the challenger immediately returns ⊥ without performing further decryption.
Title Suppressed Due to Excessive Length
13
Lemma 3. Let S0 and S1 be the events that the adversary A successfully guesses the challenge bit in Game G0 and Game G1 , respectively. We have: | Pr[S0 ] − Pr[S1 ]| ≤ AdvSUF-CMA MAC,B (λ). Proof. Let E be the event in Game G1 where the adversary A submits a decryption query acti such that acti ̸= act⋆ , but upon decoding, it yields (ci , τi ) with ci = c⋆ , and the MAC verification algorithm succeeds (i.e., MAC.Verify(mak ⋆ , c⋆ , τi ) = 1). Observe that Game G0 and Game G1 proceed perfectly identically unless event E occurs. In Game G0 , such a query would be processed and potentially decrypted, whereas in Game G1 , it is immediately rejected with ⊥. Conditional on E not occurring (¬E), the adversary’s view in both games is identical, meaning the probability of A winning is identical: Pr[S0 | ¬E] = Pr[S1 | ¬E]. Using the Law of Total Probability, we can expand Pr[S0 ] and Pr[S1 ]: Pr[S0 ] = Pr[S0 | E] Pr[E] + Pr[S0 | ¬E] Pr[¬E] Pr[S1 ] = Pr[S1 | E] Pr[E] + Pr[S1 | ¬E] Pr[¬E] Subtracting the two equations, the terms conditioned on ¬E perfectly cancel out: Pr[S0 ] − Pr[S1 ] = (Pr[S0 | E] − Pr[S1 | E]) · Pr[E] Taking the absolute value on both sides yields: | Pr[S0 ] − Pr[S1 ]| = | Pr[S0 | E] − Pr[S1 | E]| · Pr[E]. Since probabilities are strictly bounded by the interval [0, 1], the absolute difference | Pr[S0 | E] − Pr[S1 | E]| can be at most 1. Therefore, we derive the strict bound: | Pr[S0 ] − Pr[S1 ]| ≤ Pr[E]. We now bound Pr[E] by constructing an algorithm B that uses A to win the SUF-CMA game against the MAC scheme. B simulates the CCA game for A exactly as in G0 . B generates the key pairs (ek, dk) and (dk ′ , tk ′ ) by itself, allowing it to honestly answer all of A’s decryption queries. During the challenge phase, B generates a random MAC key mak ⋆ , encrypts amsgβ ∥ mak ⋆ to produce c⋆ , computes τ ⋆ ← MAC.Tag(mak ⋆ , c⋆ ), and constructs the challenge ciphertext act⋆ . If event E occurs during the subsequent decryption query phase, A has submitted a ciphertext acti ̸= act⋆ that decodes to (c⋆ , τi ) such that MAC.Verify(mak ⋆ , c⋆ , τi ) = 1. We analyze this submission:
14
S. Wang et al.
– By the definition of the scheme, the mappings provided by Encode and KEMRR are injective. Since acti ̸= act⋆ but ci = c⋆ , it is mathematically guaranteed that τi ̸= τ ⋆ . – The only valid MAC tag for the message c⋆ that A has ever witnessed under the key mak ⋆ is τ ⋆ . Since τi ̸= τ ⋆ and MAC.Verify(mak ⋆ , c⋆ , τi ) = 1, the pair (c⋆ , τi ) constitutes a fresh, valid message-tag pair that was never outputted by the MAC generation algorithm. When this occurs, B immediately halts the simulation and outputs (c⋆ , τi ) as its forgery. Because B’s simulation of G0 is perfect up until the moment E occurs, the probability that A triggers event E is exactly the probability that B produces a valid SUF-CMA forgery. Thus: Pr[E] ≤ AdvSUF-CMA MAC,B (λ). We conclude the proof of the lemma: | Pr[S0 ] − Pr[S1 ]| ≤ AdvSUF-CMA MAC,B (λ). Game G2 : This game alters the challenge encryption phase. Instead of encrypting amsgβ ∥ mak ⋆ , the challenger constructs a dummy message θ = ⋆ 0|amsgβ ∥mak | (a string of zeros of equal length) and encrypts θ to generate c⋆ . The rest of the encapsulation proceeds normally. Lemma 4. Let S1 and S2 be the events that the adversary A successfully guesses the challenge bit in Game G1 and Game G2 , respectively. We have: | Pr[S1 ] − Pr[S2 ]| ≤ AdvIND-CCA PKE,B (λ). Proof. Suppose there exists a polynomial-time adversary A that can distinguish Game G1 from Game G2 . We construct a reduction algorithm B that uses A as a subroutine to break the standard IND-CCA security of the underlying PKE scheme. Setup Phase: The IND-CCA challenger for PKE generates a key pair (pk, sk) and sends the public key pk to B. B embeds this public key into the anamorphic scheme by setting dk ′ = pk. Note that B does not know the corresponding secret key tk ′ (which equals sk). B then natively generates the randomness-recoverable KEM key pair (ek, dk) ← KEMRR .KGen(1λ ). B sends the public parameters (ek, dk, dk ′ ) to A. Pre-Challenge Decryption Queries: When A submits a decryption query for a ciphertext acti , B must simulate the OaDec oracle without knowing tk ′ . B proceeds as follows: 1. B uses its knowledge of dk to decapsulate acti : (Ki , re,i ) ← KEMRR .Decaps(dk, acti ).
Title Suppressed Due to Excessive Length
15
2. B decodes the randomness: (ci , τi ) ← Decode(re,i ). 3. Since B lacks tk ′ , it forwards ci to its own PKE IND-CCA decryption oracle. The oracle returns the underlying plaintext amsgi ∥ maki . 4. B verifies the MAC: if MAC.Verify(maki , ci , τi ) = 1, it returns amsgi to A; otherwise, it returns ⊥. This simulation is perfectly indistinguishable from the real game. Challenge Phase: A outputs two equal-length messages amsg0 and amsg1 . B generates a fresh $ MAC key mak ⋆ ← MAC.KGen(1λ ) and picks a random bit β ← − {0, 1}. B constructs two challenge plaintexts for its PKE challenger: M0 = amsgβ ∥ mak ⋆ M1 = θ
⋆
(where θ = 0|amsgβ ∥mak | )
B submits (M0 , M1 ) to its IND-CCA challenger. The challenger picks a random $
bit b ← − {0, 1}, encrypts Mb under dk ′ , and returns the challenge ciphertext ⋆ c . B computes τ ⋆ ← MAC.Tag(mak ⋆ , c⋆ ), sets c⋆⋆ = (c⋆ , τ ⋆ ), encodes re⋆ ← Encode(c⋆⋆ ), and encapsulates it: (act⋆ , K ⋆ ) ← KEMRR .Encaps(ek; re⋆ ). B sends act⋆ to A. Post-Challenge Decryption Queries: A may continue to make queries acti ̸= act⋆ . B processes them exactly as in the pre-challenge phase, with one crucial exception strictly following the rule introduced in Game G1 : if decoding acti yields ci = c⋆ , B immediately returns ⊥. This step is vital because B is prohibited from querying c⋆ to its own PKE decryption oracle. By leveraging the rule from G1 , B legally avoids illegal oracle queries while maintaining a perfect simulation. Guess: Eventually, A outputs a guess β ′ . B uses this to determine its own guess b′ for the PKE challenger: – If β ′ = β, B outputs b′ = 0. – If β ′ ̸= β, B outputs b′ = 1. We now formally map the probabilities. By definition, the IND-CCA advantage of B against PKE is: ′ ′ AdvIND-CCA PKE,B (λ) = |Pr[b = 0 | b = 0] − Pr[b = 0 | b = 1]| .
When the PKE challenger’s bit b = 0, the challenge ciphertext c⋆ is an encryption of M0 = amsgβ ∥ mak ⋆ . In this scenario, B provides A with a view that is perfectly distributed identically to Game G1 . Thus, the probability that A guesses correctly (β ′ = β) is exactly the probability of event S1 : Pr[b′ = 0 | b = 0] = Pr[β ′ = β | b = 0] = Pr[S1 ]. When the PKE challenger’s bit b = 1, c⋆ is an encryption of M1 = θ. Here, the view of A is perfectly distributed identically to Game G2 . Thus, the probability
16
S. Wang et al.
that A guesses correctly is exactly the probability of event S2 : Pr[b′ = 0 | b = 1] = Pr[β ′ = β | b = 1] = Pr[S2 ]. Substituting these into the advantage equation directly yields: AdvIND-CCA PKE,B (λ) = |Pr[S1 ] − Pr[S2 ]| . Conclusion: In Game G2 , the challenge ciphertext act⋆ encrypts the dummy string θ and is completely independent of the bit β. The adversary gains zero information about β from the challenge. Thus, Pr[S2 ] = 1/2. Combining the bounds from the sequence of games via the triangle inequality, we obtain: AdvsIND-CCA PKAKEM,A (λ) = 2 · |Pr[S0 ] − 1/2| ≤ 2 · |Pr[S0 ] − Pr[S1 ]| + 2 · |Pr[S1 ] − Pr[S2 ]| + 2 · |Pr[S2 ] − 1/2| IND-CCA ≤ 2 · AdvSUF-CMA MAC,B (λ) + 2 · AdvPKE,B (λ).
Since both terms on the right side are negligible, the advantage of any PPT adversary A is negligible. 3.3
Symmetric Key Anamorphic KEM
Definition 2 (Symmetric Key Anamorphic KEM). A Symmetric Key Anamorphic KEM (SKAKEM) with covert message space M′ is defined by a triple of polynomial-time algorithms: – (ek, dk, DK) ← SKAKEM.aGen(1λ ): The probabilistic anamorphic key generation algorithm inputs a security parameter 1λ and outputs a standard encapsulation key ek, a standard decapsulation key dk along with an anamorphic double key DK. – (K, act) ← SKAKEM.aEnc(ek, DK, amsg, ctr): The probabilistic anamorphic encryption algorithm takes as input the encapsulation key ek, the double key DK, a covert message amsg ∈ M′ , and a counter ctr. It outputs a session key K and an anamorphic ciphertext act. – amsg/⊥ ← SKAKEM.aDec(DK, dk, ctr, act): The deterministic anamorphic decryption algorithm inputs a double key DK, a decapsulation key dk, a matching counter ctr and an anamorphic ciphertext act. It outputs the covert message amsg or an error symbol ⊥. Correctness. SKAKEM satisfies correctness if for any anamorphic message amsg ∈ M′ , it holds that: (ek, dk, DK) ← SKAKEM.aGen(1λ ); Pr amsg ̸= SKAKEM.aDec(DK, dk, ctr, act) : (K, act) ← SKAKEM.aEnc(ek, DK, amsg, ctr) is negligible.
Title Suppressed Due to Excessive Length
17
Anamorphic security. SKAKEM achieves anamorphic security (i.e., indistinguishability between normal and anamorphic ciphertexts) if, for any PPT adversary A, the following advantage is negligible in λ: AdvAna-Security SKAKEM,A (λ) = |Pr[RealGSKAKEM (λ, A) = 1] − Pr[AnamorphicGSKAKEM (λ, A) = 1]| ≤ negl(λ), where the security games RealGSKAKEM and AnamorphicGSKAKEM are defined as follows: RealGSKAKEM (λ, A) $
(ek, dk) ← − KEMRR .KGen(1λ ) return AOe (ek,·,·) (ek, dk) $
where Oe (ek, amsg, ctr) computes re ← − R and returns KEMRR .Encaps(ek; re )
AnamorphicGSKAKEM (λ, A) $
(ek, dk, DK) ← − SKAKEM.aGen(1λ ) return AOa (ek,DK,·,·) (ek, dk) where Oa (ek, DK, amsg, ctr) returns SKAKEM.aEnc(ek, DK, amsg, ctr) sIND-CCA security. SKAKEM achieves sIND-CCA security if, for any PPT adversary A, there exists a negligible function negl(λ) such that the advantage of A satisfies: sIND-CCA AdvsIND-CCA SKAKEM,A (λ) = 2 · Pr[ExptSKAKEM,A (λ) = 1] − 1/2 ≤ negl(λ),
where the security experiment ExptsIND-CCA SKAKEM,A (λ) is formally defined as follows: ExptsIND-CCA SKAKEM,A (λ) $
1: (ek, dk, DK) ← − SKAKEM.aGen(1λ ) 2: (amsg0 , amsg1 , ctr∗ ) ← ASKAKEM.aEnc(ek,DK,·,·),SKAKEM.aDec(DK,dk,·,·) (ek, dk) $
3: β ← − {0, 1} 4: (K ∗ , act∗ ) ← SKAKEM.aEnc(ek, DK, amsgβ , ctr∗ ) 5: β ′ ← ASKAKEM.aEnc(ek,DK,·,·),SKAKEM.aDec(DK,dk,·,·) (act∗ , ek, dk) 6: return 1 if β = β ′ and the following conditions hold: (i) ctr∗ was never queried to SKAKEM.aEnc (ii) (ctr∗ , act∗ ) was never queried to SKAKEM.aDec otherwise return 0.
Specific Construction. Let F denote a secure pseudorandom function, and FInv be a secure IPF. Let ctr be a counter shared between the parties engaging
▷ A knows dk
18
S. Wang et al.
in covert communication. Let MAC be a scheme that is both pseudorandom and SUF-CMA secure. Let KEMRR be a randomness-recoverable KEM. SKAKEM.aGen(1λ ) $
1: k ← −K 2: (ek, dk) ← KEMRR .KGen(1λ ) 3: mak ← MAC.KGen(1λ ) 4: DK := (k, mak) 5: return (ek, dk, DK)
SKAKEM.aEnc(ek, DK, amsg, ctr) 1: Parse DK as (k, mak) 2: c := amsg ⊕ F (k, ctr) 3: τ ← MAC.Tag(mak, c) 4: c′ := (c, τ ) 5: re ← FInv (k, c′ ) 6: (K, act) ← KEMRR .Encaps(ek; re ) 7: return (K, act)
SKAKEM.aDec(DK, dk, ctr, act) 1: Parse DK as (k, mak) 2: (K, re ) ← KEMRR .Decaps(dk, act) −1 3: c′ := FInv (k, re ) 4: Parse c′ as (c, τ ) 5: if MAC.Verify(mak, c, τ ) = 0 then 6: return ⊥ 7: return c ⊕ F (k, ctr)
3.4
Security Analysis of SKAKEM
Theorem 3. Assume F is a secure pseudorandom function and FInv is a secure inverse pseudorandom function. Assuming F and FInv employ standard domain separation, the SKAKEM scheme achieves anamorphic security. Proof. We proceed via a sequence of computationally indistinguishable games, G0 and G1 . Let Si denote the event that a PPT adversary A outputs 1 in game Gi . Game G0 : This corresponds exactly to the AnamorphicGSKAKEM (λ, A) game. Pr[AnamorphicGSKAKEM (λ, A) = 1] = Pr[S0 ]. Game G1 : In this game, we replace the evaluation of the IPF FInv (k, ·) inside the encryption oracle with a truly random function R(·) : {0, 1}∗ → R.
Title Suppressed Due to Excessive Length
19
Specifically, upon receiving a query (amsg, ctr), the modified oracle computes c := amsg ⊕ F (k, ctr) and τ ← MAC.Tag(mak, c). It sets c′ := (c, τ ), samples the randomness as re ← R(c′ ), and returns KEMRR .Encaps(ek; re ). Lemma 5. If FInv is a secure PRF, there exists a PPT algorithm B such that: | Pr[S0 ] − Pr[S1 ]| = AdvIPF FInv ,B (λ). Proof. We construct a reduction B interacting with a PRF challenger CIP F . Since F and FInv employ domain separation, they behave as independent PRFs. Thus, $ B independently samples the masking key kenc ← − K and mak ← MAC.KGen(1λ ), while the challenger CIP F holds the hidden key for FInv . When A submits (amsg, ctr), B computes c := amsg ⊕ F (kenc , ctr) and τ ← MAC.Tag(mak, c). B sets c′ := (c, τ ) and submits c′ to its challenger CIP F , receiving a challenge response re∗ . B then returns KEMRR .Encaps(ek; re∗ ) to A. If CIP F instantiates the real FInv , A’s view is identical to G0 . If CIP F uses a truly random function R, A’s view perfectly matches G1 . Thus, B’s advantage bounds the difference perfectly. Analysis of Game G1 to RealG: In G1 , the randomness re is generated by a true random function R(c′ ). If the sequence of queried inputs c′ contains no duplicates, then R(c′ ) yields perfectly independent and uniformly distributed $
values in R, rendering G1 identical to the RealGSKAKEM game (where re ← − R is explicitly sampled). We bound the probability of a collision in c′ . A collision c′i = c′j (for i ̸= j) implies ci = cj . Recall that ci = amsgi ⊕ F (k, ctri ). Since A is nonce-respecting, ctri ̸= ctrj . Due to the PRF security of F (k, ·), the mask F (k, ctri ) is computationally unpredictable. Thus, A cannot adversarially choose amsgj to force cj = ci . The probability of an accidental collision is bounded by the PRF advantage plus the statistical collision bound qe2 /2|c| , where qe is the maximum number of queries. Therefore, G1 is statistically close to the real game: qe2 . 2|c| By summing the probability bounds across the games via the triangle inequality, we have: | Pr[S1 ] − Pr[RealGSKAKEM (λ, A) = 1]| ≤ AdvPRF F,A (λ) +
qe2 . 2|c| Since FInv and F are secure PRFs, their advantages are negligible. For a sufficiently large ciphertext length |c|, qe2 /2|c| is also negligible. Consequently, the total advantage is negligible, completing the proof. IPF PRF AdvAna-Security SKAKEM,A (λ) ≤ AdvFInv ,B (λ) + AdvF,A (λ) +
Theorem 4. Consider F as a secure PRF and assume that the MAC scheme is SUF-CMA secure. Additionally, let FInv be a secure IPF and KEMRR be a randomness-recoverable KEM. Then the SKAKEM scheme achieves sIND-CCA security.
20
S. Wang et al.
Proof. We proceed via a sequence of computationally indistinguishable games, G0 , G1 , and G2 . Let Si denote the event that a nonce-respecting PPT adversary A outputs β ′ = β in game Gi . Game G0 : This is the original ExptsIND-CCA SKAKEM,A (λ) game as defined in the security model. AdvsIND-CCA SKAKEM,A (λ) = 2 · |Pr[S0 ] − 1/2| . Game G1 : We modify the behavior of the decryption oracle. The challenger maintains a list Lenc recording all ciphertexts generated by the encryption oracle SKAKEM.aEnc. When A submits a query (ctr, act) to the SKAKEM.aDec oracle, the challenger first checks if act ∈ Lenc . If act ∈ / Lenc , the oracle immediately returns ⊥ without performing any decryption operations. If act ∈ Lenc , it returns the corresponding amsg from its internal records. Lemma 6. | Pr[S0 ] − Pr[S1 ]| ≤ AdvSUF-CMA MAC,B1 (λ). Proof. Let F orge be the event that A queries SKAKEM.aDec with a valid ciphertext act ∈ / Lenc that successfully passes the internal MAC.Verify check in G0 . Games G0 and G1 proceed identically until F orge occurs. Thus, | Pr[S0 ] − Pr[S1 ]| ≤ Pr[F orge]. We construct a reduction B1 to bound Pr[F orge]. B1 interacts with a SUF-CMA challenger, gaining access to MAC.Tag and MAC.Verify oracles under a hidden $ key mak ∗ . B1 independently generates k ← − K and (ek, dk) ← KEMRR .KGen(1λ ), implicitly setting DK = (k, mak ∗ , ek), and invokes A. For queries (amsg, ctr) to SKAKEM.aEnc, B1 computes c := amsg⊕F (k, ctr), queries its MAC.Tag oracle to get τ , computes re ← FInv (k, (c, τ )), and encapsulates it to act, which is added to Lenc . For queries (ctr, act) to SKAKEM.aDec, B1 decapsulates act to retrieve re −1 and inverses it via FInv to get (c, τ ). It then queries the MAC.Verify oracle with (c, τ ). Since KEMRR and FInv mathematically establish an injective mapping from act to (c, τ ), any queried act ∈ / Lenc implies a novel pair (c, τ ) that was never generated by the MAC.Tag oracle. If MAC.Verify returns 1, B1 has successfully forged a strong MAC and outputs (c, τ ) as its winning forgery. Therefore, Pr[F orge] is exactly bounded by B1 ’s SUF-CMA advantage. Game G2 : In this game, we modify the computation of the challenge ciphertext. We replace the evaluation of the PRF F (k, ctr∗ ) with a uniformly $
random string R∗ ← − {0, 1}|amsg| . The challenge ciphertext is constructed using c∗ := amsgβ ⊕ R∗ . Lemma 7. | Pr[S1 ] − Pr[S2 ]| ≤ AdvPRF F,B2 (λ). Proof. We construct B2 interacting with a PRF challenger. B2 holds a freshly generated mak and (ek, dk), but queries the PRF challenger for evaluations of F (k, ·). During SKAKEM.aEnc queries, B2 queries the PRF challenger with ctr to obtain the mask, and honestly simulates the rest of the encryption. Crucially,
Title Suppressed Due to Excessive Length
21
because we are in G1 , the SKAKEM.aDec oracle automatically rejects any act ∈ / Lenc . For act ∈ Lenc , B2 simply looks up the associated amsg from its encryption history. Thus, B2 never needs to evaluate F (k, ctr) to answer decryption queries, completely avoiding any circular dependency with its challenger. For the challenge query (amsg0 , amsg1 , ctr∗ ), B2 queries the PRF challenger with ctr∗ to get a string Y ∗ , and sets c∗ := amsgβ ⊕ Y ∗ . It computes the tag τ ∗ and encapsulates the challenge ciphertext (K ∗ , act∗ ) normally. If the PRF challenger uses the real function F , this perfectly simulates G1 . If the challenger returns a truly random string, it perfectly simulates G2 . Therefore, the distinguishing advantage is bounded by AdvPRF F,B2 (λ). Conclusion: In G2 , the challenge ciphertext incorporates c∗ = amsgβ ⊕ R . Since A is required to be nonce-respecting, the specific challenge counter ctr∗ is never queried to the SKAKEM.aEnc oracle, meaning R∗ is a completely fresh, uniformly random string. Consequently, R∗ acts as a perfect one-time pad, information-theoretically hiding the bit β. The adversary’s probability of guessing β is exactly 1/2, meaning Pr[S2 ] = 1/2. Summing the bounds across the sequence of games yields: PRF SUF-CMA AdvsIND-CCA SKAKEM,A (λ) ≤ 2 · AdvMAC,B1 (λ) + AdvF,B2 (λ) ≤ negl(λ). ∗
4
Discussion on RR-KEMs
The anamorphic cryptographic framework proposed in this work inherently relies on the underlying Key Encapsulation Mechanism possessing the RandomnessRecoverable property. To demonstrate the broad applicability and practical impact of our design, we discuss various concrete instantiations of KEMRR . As summarized in Table 1, we categorize these instantiations across two crucial dimensions: the underlying security model (Random Oracle Model vs. Standard Model) and the foundational hardness assumptions (Factoring/RSA, Discrete Logarithm, and Lattices/LPN). Table 1. Instantiations of RR-KEMs across different models and cryptographic assumptions. Model
Discrete Logarithm (DL)
Lattices / LPN
RSA-OAEP (PKCS#1)[34] PSEC-KEM (ISO/IEC 18033-2)[38] ML-KEM (FIPS 203) [39]
ROM Standard
4.1
Factoring / RSA
ATF-based schemes[40]
LTF-based schemes[41]
Hybrid Encryption [27]
Instantiations in the Random Oracle Model (ROM)
In the ROM, IND-CCA secure KEMs are typically constructed by applying the FO transformation [11] or its modern variants to a weakly secure PKE scheme. A
22
S. Wang et al.
core feature of modern FO transforms is derandomization during encapsulation, which naturally yields the randomness-recoverability property. RSA and Factoring-based Schemes. RR-KEMs represent a foundational component in applied cryptography, their functionality often embedded within widely adopted standards without being explicitly designated as such. A canonical illustration of this principle is the key transport mechanism in legacy versions of the Transport Layer Security (TLS) [28] [29] [30] protocol. In versions such as TLS 1.2 [31] and its predecessors, RSA-based key exchange cipher suites (e.g., TLS_RSA_WITH_AES_256_GCM_SHA384) were predominant. The protocol dictates that the client generates a random Pre-Master Secret, encrypts it using the server’s public RSA key, and transmits the resulting ciphertext. The server then decrypts this ciphertext to retrieve the original Pre-Master Secret. This entire process is essentially an instance of a KEM, where the Pre-Master Secret serves as the recoverable randomness. The canonical cryptographic formalization of an RR-KEM is RSA-OAEP[32] [33], standardized in PKCS#1 [34]. Its underlying encapsulation phase can be rigorously described by the following sequential steps: 1. Generation of Randomness: The encapsulator generates a random byte string r, which constitutes the core randomness intended to be recovered by the recipient. 2. Key Derivation: A standard Key Derivation Function [35], such as HKDF [36] [37], is applied to the randomness to derive the session key K = KDF(r). 3. OAEP Padding: Within the OAEP padding network, the message payload m and the randomness r are mutually masked via a Feistel-like structure using two hash functions (modeled as random oracles G and H). Specifically, the network computes s = m ⊕ G(r) and t = r ⊕ H(s). These components are then concatenated to form a highly structured message block X = s ∥ t, whose length is matched to the RSA modulus. 4. RSA Encryption: Finally, the encapsulator encrypts the formatted message block X using the recipient’s public RSA key (N, e), yielding the final ciphertext C = X e (mod N ). During decapsulation, after the receiver utilizes the RSA trapdoor (private key d) to decrypt the ciphertext and recover the padded payload (s, t), it not only recovers the underlying message but, crucially, can deterministically extract the original masking randomness by computing r = t ⊕ H(s). Because this exact decoding mechanism guarantees flawless recovery of r, our anamorphic design can be directly integrated into legacy industrial systems deploying RSA-OAEP without requiring any modifications to the underlying cryptographic libraries. Discrete Logarithm (DL) based Schemes. Standard randomized DL-based schemes, such as textbook ElGamal is fundamentally non-randomness-recoverable. In these schemes, the ephemeral public key is computed as R = g r using a uniformly sampled randomness r. Extracting r from R requires solving the intractable Discrete Logarithm Problem (DLP).
Title Suppressed Due to Excessive Length
23
However, DL-based KEMs inherently achieve the RR property when instantiated via modern FO transformations. A prominent standardized example is PSEC-KEM [38], which is included in the ISO/IEC 18033-2 standard. In PSECKEM, the encapsulator derandomizes the process by deriving the ephemeral randomness deterministically from a hashed payload seed, i.e., r = H(seed ∥ pk). During decapsulation, the receiver recovers the seed using the DH shared secret and simply re-evaluates the hash to deterministically recover the exact randomness r. By bypassing the DLP bottleneck via FO-derandomization, schemes like PSEC-KEM serve as perfect KEMRR substrates for our anamorphic design. Lattice-based Schemes (NIST Post-Quantum Standard). Following the NIST Post-Quantum Cryptography standardization, modern lattice-based KEMs, most notably ML-KEM (formerly CRYSTALS-Kyber, standardized as FIPS 203 [39]), explicitly utilize post-2017 FO transformations with implicit rejection (FO̸⊥ ). In ML-KEM, the randomness vector r used in the underlying LWE/MLWE encryption is deterministically derived via a random oracle query (SHAKE-256) taking the plaintext seed m and the public key pk as inputs: r = G(m ∥ pk). During decapsulation, the decryptor recovers m′ and must re-evaluate the hash to recover the exact randomness r′ for ciphertext verification via re-encryption. This mandatory re-encryption mechanism makes the FIPS 203 standard inherently randomness-recoverable, ensuring our framework is perfectly post-quantum ready without modifying the underlying encapsulation algorithms. 4.2
Instantiations in the Standard Model
While relying on random oracles is highly efficient in practice, constructing RR-KEMs strictly in the standard model is crucial for theoretical soundness. Fortunately, our framework can be robustly instantiated from well-established standard-model assumptions. ATF and LTF-based Constructions. IND-CCA secure schemes constructed from Adaptive Trapdoor Functions (ATFs) [40] and Lossy Trapdoor Functions (LTFs) [41] generally support explicit randomness recovery. In these constructions, the evaluation function c = fpk (x) takes an input x that typically concatenates the message and the injected randomness (i.e., x = m ∥ r). The secret trapdoor −1 allows the legitimate receiver to compute the strict inverse fsk (c) and recover the complete pre-image x. Consequently, the decapsulation algorithm naturally extracts and outputs the exact randomness r alongside the session key. Lattices and LPN-based Constructions. In the post-quantum setting without random oracles, constructing CCA-secure schemes with extractable randomness is notoriously challenging. However, advancements in Lattices and Learning Parity with Noise (LPN) provide precise mathematical mechanisms for this. Notably, the standard-model CCA-secure schemes proposed in [27] explicitly support randomness recovery. By leveraging specific trapdoor generation techniques or extractable hash proofs, these mechanisms can securely invert the LWE/LPN
24
S. Wang et al.
instances to recover the short error vectors, which serve as the encryption randomness r. By adopting these standard-model LPN/Lattice constructions, our anamorphic framework achieves robust post-quantum security entirely free from ROM heuristics.
5
Conclusion
In this paper, we formalized Public-Key and Symmetric-Key Anamorphic Key Encapsulation Mechanisms (PKAKEM and SKAKEM) and proposed generic constructions instantiable from any randomness-recoverable KEM. We rigorously proved their anamorphic security, ensuring that covert ciphertexts successfully bypass dictator detection. Crucially, our work achieves the realization of strong IND-CCA (sIND-CCA) security for covert messages within anamorphic systems. This guarantees strict confidentiality against chosen-ciphertext attacks, even if the dictator possesses the standard decapsulation key. With all security guaranties tightly proven in the standard model and demonstrating seamless compatibility with deployed standards such as RSA-OAEP and ML-KEM, our framework bridges the gap between provable security and real-world deployment.
References 1. Rogaway, P.: The moral character of cryptographic work. Cryptology ePrint Archive (2015) 2. Persiano, G., Phan, D.H., Yung, M.: Anamorphic encryption: Private communication against a dictator. In: Advances in Cryptology–EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II. pp. 34–63. Springer (2022) 3. Wang, Y., Chen, R., Huang, X., Yang, G., Yung, M.: Sender-anamorphic encryption reformulated: Achieving robust and generic constructions. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 135-167. Springer (2023) 4. Banfi, F., Gegier, K., Hirt, M., Maurer, U., Rito, G.: Anamorphic encryption, revisited. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 3-32. Springer (2024) 5. Kutylowski, M., Persiano, G., Phan, D.H., Yung, M., Zawada, M.: The self-anticensorship nature of encryption: On the prevalence of anamorphic cryptography. Proceedings on Privacy Enhancing Technologies 2023(4), 170–183 (2023) 6. Persiano, G., Phan, D.H., Yung, M.: Public-key anamorphism in (CCA-secure) public-key encryption and beyond. In: Annual International Cryptology Conference. pp. 422–455. Springer (2024) 7. Catalano, D., Giunta, E., Migliaro, F.: Anamorphic encryption: New constructions and homomorphic realizations. In: Advances in Cryptology–EUROCRYPT 2024: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II. pp. 33–62. Springer (2024) 8. Banerjee, S., Pal, T., Rupp, A., Slamanig, D.: Simple Public Key Anamorphic Encryption and Signature using Multi-Message Extensions. Cryptology ePrint Archive (2025)
Title Suppressed Due to Excessive Length
25
9. Canetti, R., Krawczyk, H., Nielsen, J.B.: Relaxing chosen-ciphertext security. In: Advances in Cryptology–CRYPTO 2003: 23rd Annual International Cryptology Conference, Proceedings. pp. 565–582. Springer (2003) 10. Faonio, A., Fiore, D.: Improving the efficiency of re-randomizable and replayable CCA secure public key encryption. In: International Conference on Applied Cryptography and Network Security. pp. 271–291. Springer (2020) 11. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Annual International Cryptology Conference. pp. 537–554. Springer (1999) 12. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM (JACM) 51(4), 557–594 (2004) 13. Don, J., Fehr, S., Majenz, C., Schaffner, C.: Security of the Fiat-Shamir transformation in the quantum random-oracle model. In: Annual International Cryptology Conference. pp. 356–383. Springer (2019) 14. Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 207-222. Springer (2004) 15. Choi, W., Collins, D., Liu, X., Zikas, V.: A unified treatment of anamorphic encryption. Cryptology ePrint Archive (2025) 16. Abe, M., Gennaro, R., Kurosawa, K., Shoup, V.: Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 128–146. Springer (2005) 17. Nagao, W., Manabe, Y., Okamoto, T.: A universally composable secure channel based on the KEM-DEM framework. In: Theory of Cryptography Conference. pp. 426–444. Springer (2005) 18. Chen, R., Huang, X., Yung, M.: Subvert KEM to break DEM: practical algorithmsubstitution attacks on public-key encryption. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 98–128. Springer (2020) 19. Dent, A.W.: A designer’s guide to KEMs. In: IMA International Conference on Cryptography and Coding. pp. 133–151. Springer (2003) 20. Saito, T., Xagawa, K., Yamakawa, T.: Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 520–551. Springer (2018) 21. Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing 17(2), 373–386 (1988) 22. Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining message authentication code. Journal of Computer and System Sciences 61(3), 362– 399 (2000) 23. Dodis, Y., Kiltz, E., Pietrzak, K., Wichs, D.: Message authentication, revisited. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 355–374. Springer (2012) 24. Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: International Conference on the Theory and Applications of Cryptographic Techniques. pp. 255–271. Springer (2003) 25. Möller, B.: A public-key encryption scheme with pseudo-random ciphertexts. In: European Symposium on Research in Computer Security. pp. 335–351. Springer (2004) 26. Boneh, D., Kim, S., Wu, D.J.: Constrained keys for invertible pseudorandom functions. Theory of Cryptography Conference. pp. 237–263. Springer (2017)
26
S. Wang et al.
27. Boyen, X., Izabachène, M., Li, Q.: Secure Hybrid Encryption in the Standard Model from Hard Learning. In: Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings. pp. 399–418. Springer (2021) 28. Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.3. RFC 8446 (2018) 29. Blake-Wilson, S., Nystrom, M., Hopwood, D., Mikkelsen, J., Wright, T.: Transport Layer Security (TLS) Extensions. RFC 4366 (2006) 30. Eastlake, D.: Transport Layer Security (TLS) Extensions: Extension Definitions. RFC 6066 (2011) 31. Dierks, T., Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246 (2008) 32. Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP is secure under the RSA assumption. In: Annual International Cryptology Conference. pp. 260–274. Springer (2001) 33. Kiltz, E., O’Neill, A., Smith, A.: Instantiability of RSA-OAEP under chosenplaintext attack. Journal of Cryptology 30(3), 889-919 (2017) 34. Jonsson, J., Kaliski, B.: Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1. RFC 3447, RFC Editor (2003) 35. Yao, F.F., Yin, Y.L.: Design and analysis of password-based key derivation functions. In: Cryptographers’ Track at the RSA Conference. pp. 245-261. Springer (2005) 36. Krawczyk, H., Eronen, P.: HMAC-based Extract-and-Expand Key Derivation Function (HKDF). RFC 5869 (2010) 37. Krawczyk, H.: Cryptographic extraction and key derivation: The HKDF scheme. In: Annual Cryptology Conference. pp. 631–648. Springer (2010) 38. ISO/IEC: ISO/IEC 18033-2:2006: Information technology – Security techniques – Encryption algorithms – Part 2: Asymmetric ciphers. International Organization for Standardization, Geneva, Switzerland (2006) 39. National Institute of Standards and Technology: Module-Lattice-Based KeyEncapsulation Mechanism Standard. Federal Information Processing Standards Publication (FIPS) 203, U.S. Department of Commerce (2024) 40. Kiltz, E., Mohassel, P., O’Neill, A.: Adaptive trapdoor functions and chosenciphertext security. In: Advances in Cryptology–EUROCRYPT 2010. pp. 673–692. Springer (2010) 41. Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Proceedings of the 40th annual ACM symposium on Theory of computing (STOC). pp. 120–129. ACM (2008)