Paper 2026/2706

Anamorphic Proofs of Knowledge from Prover Randomness

Abstract

Anamorphic encryption and signatures deliver a hidden message through a normal-looking ciphertext or signature. We move from hidden messages to hidden knowledge claims and introduce anamorphic proofs of knowledge, in which a single proof certifies its normal statement publicly while convincing a designated checker that the prover knows a witness for a separately registered anamorphic statement, such as a long-term credential. Our construction reuses a commitment the normal prover already makes to its own randomness. The prover adds a secret mask to the anamorphic witness and uses the sum as those coins, so the existing commitment carries the anamorphic statement while the public statement, proof format and length, and normal verifier remain unchanged. Two properties of the normal proof system suffice: its randomness commitment must be extractable, and the complete proof must be simulatable at a commitment that the checking key fixes in advance, which normal zero knowledge does not provide. The resulting normal and anamorphic modes are indistinguishable to an external observer, even given both witnesses and the normal prover's actual random coins. The same opening extractor gives anamorphic knowledge soundness and two guarantees against the checker: it cannot produce an accepting proof for a statement registered independently of its key, and it cannot produce a proof and witness for a statement of its own choice, in both cases at an unused label and after obtaining honest proofs at other labels. The checker learns neither witness. We instantiate the construction in random-base Compressed $\Sigma$ and in Bulletproofs with range aggregation in the random-oracle model. Finally, we show that three-move protocols with witness-assisted challenge transfer, including Schnorr and uncompressed representation protocols, cannot support the primitive in a local-checking model.