Paper 2026/275

PhantomCrypt: Composing Existence and Content Deniability with Post-Quantum Security

Abstract

Traditional deniable encryption denies the $content$ of secret communications by allowing plausible alternative plaintexts under coercion. But the recognizable use of a deniable-encryption tool can itself defeat the purpose: a revealed plaintext becomes suspicious once a coercer detects that a non-standard tool was used, and fully encrypted, format-anomalous traffic is already detected and acted upon by deployed censorship systems. This motivates a second axis of deniability, the deniability of the mechanism's $use$, which we call $second-order deniability$ (2OD) and treat as a design goal rather than a single achievable primitive. We decompose 2OD into two formally separate properties: $content deniability$ (CD), that a coercer holding all disclosed keys cannot identify the true message among decoys, and $existence deniability$ (ED), that the transmitted ciphertext is indistinguishable from the output of a fixed, standard reference protocol. We give game-based definitions of CD and ED, prove that the two are logically independent, and present PhantomCrypt, a construction that composes False-Bottom Encryption (CD) with Invisible Encryption (ED) under a post-quantum hybrid KEM/AEAD envelope. We are deliberate about what each guarantee buys. ED, as we define and prove it, is the indistinguishability of the transmitted ciphertext $object$ from a single, explicitly specified reference distribution (a standard hybrid KEM/AEAD wrapper over an unmodified cover string); it reduces to KEM and AEAD security. It is $not$ a claim of traffic-analysis resistance, and it is conditional on an assumption we make explicit rather than prove: that the chosen cover string is itself unremarkable to the observer. CD we prove negligible in the random-oracle model, conditioned on the secrecy of a pre-shared seed, with the residual advantage controlled by the seed's entropy relative to the field size. We further show that this coupling is sharp: a feasibility threshold separates a regime where strong deniability holds from one where it is information-theoretically impossible, governed by the seed-entropy margin relative to the plausible-message entropy. We are explicit about the boundary throughout: ED is object-level indistinguishability, not a defense against traffic analysis or device-side software forensics, and we state where full 2OD does and does not hold. A proof-of-concept implementation encrypts a 32-byte message with three decoys in under 10\,ms on commodity hardware, with scaling measured across cover-text length and decoy count.

Note: PhantomCrypt v4: 30.06.2026