Abstract
We study Input Indistinguishable Computation (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 a Witness Indistinguishable (WI) proof system to general two-party functionalities and in its concurrent version (cIIC) 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 2PC, are all WI proofs also IIC secure?
-
2
Are cIIC proofs also NM?
We show, somewhat surprisingly, that both answers to the above 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) IIC is a 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).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, S., Goyal, V., Jain, A., Prabhakaran, M., Sahai, A.: New impossibility results for concurrent composition and a non-interactive completeness theorem for secure computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 443–460. Springer, Heidelberg (2012)
Barak, B., Prabhakaran, M., Sahai, A.: Concurrent non-malleable zero knowledge. In: 47th FOCS. IEEE Computer Society Press (2006)
Blum, M.: How to Prove a Theorem So No One Else Can Claim It. In: Proceedings of the International Congress of Mathematicians, pp. 1444–1451 (1986)
Cao, Z., Visconti, I., Zhang, Z.: On constant-round concurrent non-malleable proof systems. Inf. Process. Lett. 111(18), 883–890 (2011)
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. In: 23rd ACM STOC, pp. 542–552. ACM Press (1991)
Dwork, C., Naor, M.: ZAPs and their applications. In: 41st FOCS, pp. 283–293. IEEE Computer Society Press (2000)
Dwork, C., Naor, M., Sahai, A.: Concurrent zero-knowledge. In: 30th ACM STOC, pp. 409–418. ACM Press (1998)
Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: 22nd ACM STOC, pp. 416–426. ACM Press (1990)
Garg, S., Goyal, V., Jain, A., Sahai, A.: Concurrently secure computation in constant rounds. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 99–116. Springer, Heidelberg (2012)
Garg, S., Goyal, V., Jain, A., Sahai, A.: Concurrently secure computation in constant rounds (full version) (2012), http://goo.gl/iPXSbe
Garg, S., Kumarasubramanian, A., Ostrovsky, R., Visconti, I.: Impossibility results for static input secure computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 424–442. Springer, Heidelberg (2012)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186–208 (1989)
Lindell, Y.: Lower Bounds for Concurrent Self Composition. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 203–222. Springer, Heidelberg (2004)
Micali, S., Pass, R., Rosen, A.: Input-indistinguishable computation. In: 47th FOCS, pp. 136–145. IEEE Computer Society Press (2006)
Ostrovsky, R., Persiano, G., Visconti, I.: Constant-round concurrent non-malleable zero knowledge in the bare public-key model. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 548–559. Springer, Heidelberg (2008)
Ostrovsky, R., Persiano, G., Visconti, I.: Concurrent non-malleable witness indistinguishability and its applications. Electronic Colloquium on Computational Complexity (ECCC) 13(95) (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ostrovsky, R., Persiano, G., Visconti, I. (2014). On Input Indistinguishable Proof Systems. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_74
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_74
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)