Cryptographically Strong Undeniable Signatures, Unconditionally Secure for the Signer

We present the first undeniable signature schemes where signers are unconditionally secure. In the efficient variants, the security for the recipients relies on a discrete logarithm assumption or on factoring; and in a theoretical version, on claw-free permutation pairs.Besides, on the one hand, the efficient variants are the first practical cryptographically strong undeniable signature schemes at all. On the other hand, in many cases they are more efficient than previous signature schemes unconditionally secure for the signer.Interesting new subprotocols are efficient collision-free hash functions based on a discrete logarithm assumption, efficient perfectly hiding commitments for elements of ℤ_p (p prime), and fairly practical perfect zero-knowledge proofs for arithmetic formulas in ℤ_p or ℤ_2σ.