Paper 2002/027

Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications

Jonathan Katz


We describe very efficient protocols for non-malleable (interactive) proofs of plaintext knowledge for the RSA, Rabin, Paillier, and El-Gamal encryption schemes whose security can be proven in the standard model. We also highlight some important applications of these protocols, where we take care to ensure that our protocols remain secure when run in an asynchronous, concurrent environment: --- Chosen-ciphertext-secure, interactive encryption: In some settings where both parties are on-line (e.g., SSL), 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 provide efficient protocols for password-based authenticated key exchange in the public- key model \cite{HK98,B99}. Security of our protocols may be based on any of the cryptosystems mentioned above. --- Deniable authentication: We demonstrate deniable authentication protocols satisfying the strongest notion of security. These are the first efficient constructions based on, e.g., the RSA or computational Diffie-Hellman assumptions. Our techniques provide a general methodology for constructing efficient \emph{non-malleable} (zero-knowledge) proofs of knowledge when shared parameters are available (for our intended applications, these parameters can simply be included as part of users' public keys). Thus, non-malleable proofs of knowledge are easy to achieve ``in practice''.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
non-malleableproofs of knowledge
Contact author(s)
jkatz @ cs columbia edu
2002-03-10: revised
2002-03-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Katz},
      title = {Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2002/027},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.