Paper 2025/2312 Original: eprint.iacr.org/2025/2312 ↗

Anamorphic Signatures With Dictator and Recipient Unforgeability for Long Messages

Abstract

Anamorphic signatures (Kutylowski {\it et al.}, Crypto'23) provide a way to covertly use encryption by hiding ciphertexts inside digital signatures without a dictator noticing. Recently (Asiacrypt'24), Jaeger and Stracovsky advocated stronger security notions for the primitive. Their notion of dictator unforgeability requires a dictator's inability to produce fresh signatures that decrypt to a meaningful covert message. The notion of recipient unforgeability requires that anamorphic receivers cannot forge signatures even after having observed anamorphic signatures on messages of their choice. To date, the known schemes satisfying all these properties simultaneously rely on the "randomness replacement" technique. As a result, they are restricted to short anamorphic messages either because their anamorphic decryption mechanism involves an exhaustive search step, or because they embed the anamorphic plaintext in a public random salt (which is typically short in compatible signature schemes like RSA-PSS). In this paper, we present anamorphic signatures that depart from the randomness replacement paradigm and make it possible to encrypt longer anamorphic plaintexts. We show that (generalized) Okamoto-Schnorr signatures, as well as GQ and $2^t$-root signatures all have anamorphic modes satisfying the three desired security properties. The ratio between the lengths of anamorphic plaintexts and signatures can even be very close to $1$ for appropriate parameters. We also discuss an extension to Lyubashevsky's lattice-based signatures.