Paper 2026/2866

Anamorphic NIZK: Definition, Construction and More

Abstract

Anamorphic encryption enables covert communication despite disclosure of ordinary decryption keys~\cite{PersianoPY22}. Work on anamorphic signatures extends this capability to settings permitting only authentication and shows that Fiat-Shamir preserves anamorphism~\cite{kutylowski2023anamorphicSignatures,fiat1986prove}. However, this result assumes an already anamorphic protocol and does not by itself ensure witness privacy against the recipient, motivating anamorphism directly in non-interactive zero-knowledge proofs (NIZKs). We introduce anamorphic NIZK (ANIZK), in which publicly verifiable proofs carry covert messages recoverable with a double key. The framework formalizes anamorphic security, strong robustness, and recipient anamorphic zero knowledge and simulation extractability. A generic construction in the random oracle model combines suitable Sigma protocols with authenticated encryption with associated data through a salted Fiat-Shamir transform. Applying ANIZK within the Naor-Yung paradigm \cite{NaorYung90} yields recipient anamorphic encryption satisfying STE-xCCA1, SIND-aCCA1, and SIND-nCCA security under the notions of~\cite{choi2026unified}. Finally, an asymmetric variant of ANIZK, termed ASY-ANIZK, combines a labeled NIZK with public-key encryption satisfying ciphertext pseudorandomness and random ciphertext rejection. It separates public embedding from secret recovery and achieves weak robustness, as public embedding precludes strong robustness.