Efficient and non-malleable proofs of plaintext knowledge and applications

TitleEfficient and non-malleable proofs of plaintext knowledge and applications
Publication TypeConference Papers
Year of Publication2003
AuthorsKatz J
Conference NameProceedings of the 22nd international conference on Theory and applications of cryptographic techniques
Date Published2003///
PublisherSpringer-Verlag
Conference LocationBerlin, Heidelberg
ISBN Number3-540-14039-5
Abstract

We describe efficient protocols for non-malleable (interactive) proofs of plaintext knowledge for the RSA, Rabin, Paillier, and El Gamal encryption schemes. We also highlight some important applications of these protocols: - Chosen-ciphertext-secure, interactive encryption. In settings where both parties are on-line, an interactive encryption protocol may be used. We construct chosen-ciphertext-secure interactive encryption schemes based on any of the schemes above. In each case, the improved scheme requires only a small overhead beyond the original, semantically-secure scheme. - Password-based authenticated key exchange. We derive efficient protocols for password-based key exchange in the public-key model [28, 5] whose security may be based on any of the cryptosystems mentioned above. - Deniable authentication. Our techniques give the first efficient constructions of deniable authentication protocols based on, e.g., the RSA or computational Diffie-Hellman assumption. Of independent interest, we consider the concurrent composition of proofs of knowledge; this is essential to prove security of our protocols when run in an asynchronous, concurrent environment.

URLhttp://dl.acm.org/citation.cfm?id=1766171.1766189