Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Efficient and Non-malleable Proofs of Plaintext Knowledge and Applications

Jonathan I. Katz

Published Jan 1, 2003• 41 citations
Publisher
DOI
10.1007/3-540-39200-9_13

Related papers

Efficient and Non-malleable Proofs of Plaintext Knowledge and Applications (Extended Abstract)

Jonathan I. Katz

•Jan 1, 2003•1 citation

Concurrent Non-Malleable Zero Knowledge Proofs

Huijia Lin, Rafael Pass, Wei-Lung Dustin Tseng +1 more

Lecture notes in computer science•Jan 1, 2010•37 citations

Zero-Knowledge Protocols for NTRU: Application to Identification and Proof of Plaintext Knowledge

Keita Xagawa, Keisuke Tanaka

Lecture notes in computer science•Jan 1, 2009•13 citations

Black-Box Proof of Knowledge of Plaintext and Multiparty Computation with Low Communication Overhead

Steven Myers, Mona Sergi, Abhi A. Shelat

Lecture notes in computer science•Jan 1, 2013•3 citations

Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem

Shafi Goldwasser, Dmitriy Kharchenko

Lecture notes in computer science•Jan 1, 2005•20 citations

Constant-Round Concurrent NMWI and its relation to NMZK

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: • We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions).

•Jan 1, 2006•7 citations
One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: • We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions).