Rafail Ostrovsky - Publications

On Input Indistinguishable Proof Systems

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti


We study input indistinguishable Communication (IIC), a security notion proposed by Micali, Pass, and Rosen in [ 14] and recently considered also by Garg, Goyal, Jain and Sahai in [19]· IIC aims at generalizing the notion of Witness Indistinguishable (WI) proof system to general two-party functionalities and in its concurrent version (cIIC&41;also considers security against man-in-the-middle(MiM) attacks·

In this paper, we focus on the proof system functionality and compare IIC with two other security notions for proof systems: WI and Non-Malleability (NM)· We address the following two questions·

1 Since IIC is a generalization of WI from proof systems to general 2 PC, are all WI proofs also IIC secure?

2 Are CIIC proofs also NM?

We show, somewhat surprisingly, that both answers to theabove questions are negative? Indeed, we show that there exists a WI proof system that is not IIC Secure? We then show that a large class of WI proof systems, including the classical Blum's proof system for NP, are concurrently secure in the IIC sense? This answers the second question in the negative, since Blum's proofs are known to be malleable·

The Consequence of our results is three-fold· 1) ICC isa too stringent notion and this leaves the possibility of security notions weaker than IIC with a satisfying level of Security· 2) For Important functionalities, such as the proof system functionality,classical constructions like Blum's protocol are cIIC secure·3&#CIIC security should be carefully evaluated when used as a security guarantee to model real-world concurrent attacks to protocols, as our results show that cIIC security does not guarantee non-malleability of proof systems· In contrast, standard simulation-based security[5,2] and Concurrent non-malleable WI( a game-based security notion introduced by [15,16]) are secure against MiM attacks (the latter even in constant rounds)·

comment: ICALP 2014 PP: 895-906

Fetch PDF file of the paper

Back to Publications List