Rafail Ostrovsky - Publications

Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model.

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti


One of the central questions in Cryptography is the design of round-efficient protocols that are secure under concurrent man-in-the-middle attacks. In this paper we present the first constant-round concurrent non-malleable zero-knowledge argument system for NP in the Bare Public-Key model [Canetti et al. STOC 2000], resolving one of the major open problems in this area. To achieve our result, we introduce and study the notion of non-malleable witness indistinguishability, which is of independent interest. Previous results either achieved relaxed forms of concurrency/security or needed stronger setup assumptions or required a non-constant round complexity.

comment: ICALP (2) 2008: 548-559

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List