Paper 2026/645
Toward Provable Security in Anamorphic Extension: New Constructions and Analysis
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
-
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}
}