Anamorphic signatures allow covert communication through signatures in environments where encryption is restricted. They enable trusted recipients with a double-key to extract hidden messages while the signature remains indistinguishable from a regular one. However, the traditional notion of anamorphic signatures suffers from vulnerabilities, particularly when a single recipient or sender is compromised, exposing all hidden messages and providing undeniable proof that citizens are part of the anamorphic exchange. To address these limitations, we explore a threshold-based approach to distribute trust among multiple recipients, preventing adversaries from decrypting anamorphic messages even if some recipients are compromised. Our first contribution is the formalization of the notion of threshold-recipient anamorphic signatures, where decryption is possible only through collaboration among a subset of recipients. We then explore a stronger model in which the dictator controls the key-generation process through which it learns all secret keys, as well as how citizens store cryptographic keys. A particular example of this model in the real world is a dictator providing citizens with electronic identity documents (eIDs) and blocking all other usage of cryptography. We demonstrate that anamorphic communication is still possible even in such a scenario. Our construction is secure against quantum adversaries and does not rely on any computational assumptions beyond the random-oracle model. Finally, we present an impossibility result for encoding anamorphic messages with a threshold-sender model when using many existing threshold signature schemes, even when the adversary is part of the signing group. Our work outlines both the possibilities and limitations of extending anamorphic signatures with threshold cryptography, offering new insights into improving the security and privacy of individuals under authoritarian regimes.
Anamorphic signatures allow covert communication through signatures in environments where encryption is restricted. They enable trusted recipients with a double-key to extract hidden messages while the signature remains indistinguishable from a regular one. However, the traditional notion of anamorphic signatures suffers from vulnerabilities, particularly when a single recipient or sender is compromised, exposing all hidden messages and providing undeniable proof that citizens are part of the anamorphic exchange. To address these limitations, we explore a threshold-based approach to distribute trust among multiple recipients, preventing adversaries from decrypting anamorphic messages even if some recipients are compromised. Our first contribution is the formalization of the notion of threshold-recipient anamorphic signatures, where decryption is possible only through collaboration among a subset of recipients. We then explore a stronger model in which the dictator controls the key-generation process through which it learns all secret keys, as well as how citizens store cryptographic keys. A particular example of this model in the real world is a dictator providing citizens with electronic identity documents (eIDs) and blocking all other usage of cryptography. We demonstrate that anamorphic communication is still possible even in such a scenario. Our construction is secure against quantum adversaries and does not rely on any computational assumptions beyond the random-oracle model. Finally, we present an impossibility result for encoding anamorphic messages with a threshold-sender model when using many existing threshold signature schemes, even when the adversary is part of the signing group. Our work outlines both the possibilities and limitations of extending anamorphic signatures with threshold cryptography, offering new insights into improving the security and privacy of individuals under authoritarian regimes.
The concept of anamorphic encryption, first formally introduced by Persiano et al. in their influential 2022 paper titled ``Anamorphic Encryption: Private Communication Against a Dictator,'' enables embedding covert messages within ciphertexts. One of the key distinctions between a ciphertext embedding a covert message and an original ciphertext, compared to an anamorphic ciphertext, lies in the indistinguishability between the original ciphertext and the anamorphic ciphertext. This encryption procedure has been defined based on a public-key cryptosystem. Initially, we present a quantum analogue of the classical anamorphic encryption definition that is based on public-key encryption. Additionally, we introduce a definition of quantum anamorphic encryption that relies on symmetric key encryption. Furthermore, we provide a detailed generalized construction of quantum anamorphic symmetric key encryption within a general framework, which involves taking any two quantum density matrices of any different dimensions and constructing a single quantum density matrix, which is the quantum anamorphic ciphertext containing ciphertexts of both of them. Subsequently, we introduce a definition of computational anamorphic secret-sharing and extend the work of Çakan et al. on computational quantum secret-sharing to computational quantum anamorphic secret-sharing, specifically addressing scenarios with multiple messages, multiple keys, and a single share function. This proposed secret-sharing scheme demonstrates impeccable security measures against quantum adversaries.
Anamorphic encryption is a cryptographic paradigm that allows covert messages to be hidden inside ordinary ciphertexts of a public-key encryption scheme. The covert channel is enabled by a secret double-key shared between the sender and an authorized receiver. Even if an adversary coerces the receiver into revealing the secret-key, the hidden communication remains undetectable without the double-key. Existing formulations of asymmetric anamorphic encryption suffer from two limitations. First, key pairs of a public-key encryption scheme and double-keys are tightly coupled: once a public-key is deployed, it is no longer possible to associate fresh double-keys with it. Second, existing constructions of asymmetric anamorphic encryption either rely on additional cryptographic primitives or on stronger structural assumptions, or they are scheme-specific.In this work, we refine the syntax of asymmetric anamorphic encryption so that double-key generation is separated from key deployment, allowing multiple double-keys to be registered with the same public-key after setup. We then construct an asymmetric anamorphic encryption scheme from the group-action-based public-key encryption scheme $ \mathsf{gaPKE} $, which is built from a regular effective group action over a commutative group. The resulting scheme is secure in the standard model. Our construction combines a hybrid encryption scheme, built under the $ \textsf{GA-DDH}$ assumption and entropy smoothing of hash functions, with a second independent group-action instance that carries the covert message. The resulting scheme satisfies anamorphic security, sender indistinguishability under chosen-plaintext attack security and colluder indistinguishability under chosen-plaintext attack security. We instantiate our framework in both post-quantum and classical settings. Using $ \textsf{CSIDH}$ group actions, we obtain the first isogeny-based asymmetric anamorphic encryption scheme. Using $ \textsf{DDH}$-hard groups, we obtain a classical anamorphic encryption scheme based on hashed ElGamal.
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 CPA-security, 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 Symmetric-Key (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.
A novel post-quantum threshold oblivious signature scheme is presented. Oblivious signatures enable a requester to obtain a signature on a single selected message from a set of candidates without revealing the selection to the signer. Unlike blind signatures, the signer may be aware of the candidate set. To mitigate single-point failures the scheme employs Shamir’s secret sharing to distribute signing authority among multiple participants. To address quantum threats, it leverages isogeny-based cryptography founded on the Group Action Inverse Problem for post-quantum resilience. The construction adapts an existing isogeny-based oblivious signature by introducing a trusted dealer. The signing protocol is multi-party; verification confirms signature validity on the selected message without revealing secret information. Security reduces to the hardness of Group Action Inverse Problem and the security of the secret-sharing scheme in the semi-honest model, covering corrupted dealers, users, and coalitions of fewer than the threshold number of signers. The threshold design eliminates dependence on a single signer, preventing unauthorized signatures after key compromise. Theoretical contributions advance threshold cryptography with post-quantum primitives; practical applications include anonymous voting, secure transactions, and privacy-preserving distributed systems. Future directions include malicious adversary models and integrations with other post-quantum primitives.
Signature schemes, proposed in 1976 by Diffie and Hellman, have become ubiquitous across modern communications. They allow for the exchange of messages from one sender to multiple recipients, with the guarantees that messages cannot be forged or tampered with and that messages also can be forwarded from one recipient to another without compromising their validity. Signatures are different from, but no less important than encryption, which ensures the privacy of a message. Commonly used signature protocols—signatures based on the Rivest–Adleman–Shamir (RSA) algorithm, the digital signature algorithm (DSA), and the elliptic curve digital signature algorithm (ECDSA)—are only computationally secure, similar to public key encryption methods. In fact, since these rely on the difficulty of finding discrete logarithms or factoring large primes, it is known that they will become completely insecure with the emergence of quantum computers. We may therefore see a shift towards signature protocols that will remain secure even in a post-quantum world. Ideally, such schemes would provide unconditional or information-theoretic security. In this paper, we aim to provide an accessible and comprehensive review of existing unconditionally securesecure signature schemes for signing classical messages, with a focus on unconditionally secure quantum signature schemes.
Modern cryptography encompasses much more than encryption of secret messages. Signature schemes are widely used to guarantee that messages cannot be forged or tampered with, for example in e-mail, software updates and electronic commerce. Messages are also transferrable, which distinguishes digital signatures from message authentication. Transferability means that messages can be forwarded; in other words, that a sender is unlikely to be able to make one recipient accept a message which is subsequently rejected by another recipient if the message is forwarded. Similar to public-key encryption, the security of commonly used signature schemes relies on the assumed computational difficulty of problems such as finding discrete logarithms or factoring large primes. With quantum computers, such assumptions would no longer be valid. Partly for this reason, it is desirable to develop signature schemes with unconditional or information-theoretic security. Quantum signature schemes are one possible solution. Similar to quantum key distribution (QKD), their unconditional security relies only on the laws of quantum mechanics. Quantum signatures can be realized with the same system components as QKD, but are so far less investigated. This talk aims to provide an introduction to quantum signatures and to review theoretical and experimental progress so far.