Paper 2026/645

Toward Provable Security in Anamorphic Extension: New Constructions and Analysis

Nabanita Chakraborty, Indian Institute of Technology Kharagpur
Ratna Dutta, Indian Institute of Technology Kharagpur
Abstract

Anamorphic encryption (AE) enables covert communication in adversarial settings where the receiver’s secret key may be exposed to a coercive adversary. Although existing AE constructions demonstrate the feasibility of this paradigm, their covert bandwidth rates are severely limited, particularly when built from conventional public-key encryption (PKE) schemes. This work develops a systematic approach to constructing bandwidth-efficient anamorphic extensions of residuosity-based PKEs. We first present a robust bit-wise anamorphic extension of the Goldwasser-Micali cryptosystem and a block variant that substantially improves covert throughput. We then construct an anamorphic extension of the Benaloh cryptosystem using an explicit, uniquely decodable embedding of covert messages together with a redundancy tag for robustness. Beyond individual constructions, we introduce a general Δ-structured public-key encryption framework that captures the common algebraic structure enabling anamorphic extensions and instantiate it with block Goldwasser-Micali, Paillier and Damgård-Jurik encryption. We further provide a formal analysis of key deniability, robustness, message loss and windowed decryption, counter-reuse attacks and forward security against subsequent sender coercion. The security of our constructions is established through IND-NA reductions to pseudorandom-function security. At the 128-bit security level, our Benaloh, block Goldwasser-Micali and Paillier constructions achieve approximately 0.46-0.48 covert bits per ciphertext bit under the comparison metric considered, demonstrating a substantial bandwidth improvement over the representative prior approaches. Overall, the proposed framework provides a unified foundation for designing efficient anamorphic extensions of structured public-key encryption schemes.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Anamorphic extensionGoldwasser-Micali PKEBenaloh PKEPaillier PKEDamg˚ard-Jurik PKEIND-NA securityRobustness
Contact author(s)
nabanita @ kgpian iitkgp ac in
ratna @ maths iitkgp ac in
History
2026-11-03: revised
2026-04-02: received
See all versions
Short URL
https://ia.cr/2026/645
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/645,
      author = {Nabanita Chakraborty and Ratna Dutta},
      title = {Toward Provable Security in Anamorphic Extension: New Constructions and Analysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/645},
      year = {2026},
      url = {https://eprint.iacr.org/2026/645}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.