International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications

Jonathan Katz
Search ePrint
Search Google
Abstract: 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''.
  title={Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / non-malleable, proofs of knowledge,},
  note={ 11756 received 4 Mar 2002, last revised 10 Mar 2002},
  author={Jonathan Katz},