Secure Digital Signature Scheme against Chosen Message Attacks

Digital signature scheme based on the computational difficulty of integer factorization. The scheme possesses secure against an adaptive chosen-message attack: Receiver who receives signatures for messages of his choice (where each message may be chosen in a way that depends on the signatures of previously chosen messages) cannot later forge the signature. This is surprising, since the properties of having forgery being equivalent to factoring and being invulnerable to an adaptive chosen-message attack were considered in the folklore to be contradictory. More commonly, we show how to construct a signature scheme with such properties based on the existence of a claw-free pair of permutations a potentially weaker assumption than the intractability of integer factorization. The new scheme is potentially realistic: signing and verifying signatures are practically fast, and signatures are compact.