Abstract
We consider proof of knowledge protocols where the cheating prover may communicate with some external adversarial environment during the run of the proof. Without additional setup assumptions, no witness hiding protocol can securely ensure that the prover knows a witness in this scenario. This is because the prover may just be forwarding messages between the environment and the verifier while the environment performs all the necessary computation.
In this paper we consider an ℓ-isolated prover, which is restricted to exchanging at most ℓ bits of information with its environment. We introduce a new notion called ℓ-isolated proofs of knowledge (ℓ-IPoK). These protocols securely ensure that an ℓ-isolated prover knows the witness. To prevent the above-mentioned attack, an ℓ-IPoK protocol has to have communication complexity greater than ℓ. We show that for any relation in NP and any value ℓ, there is an ℓ-IPoK protocol for that relation. In addition, the communication complexity of such a protocol only needs to be larger than ℓ by a constant multiplicative factor.
Chapter PDF
Similar content being viewed by others
Keywords
- Secret Sharing
- Communication Complexity
- Secret Sharing Scheme
- Random Oracle Model
- Common Reference String
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barak, B.: How to go beyond the black-box simulation barrier. In: Proc. 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA, October 14–17, pp. 106–115. IEEE, Los Alamitos (2001)
Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390–420. Springer, Heidelberg (1993)
Barak, B., Goldreich, O., Goldwasser, S., Lindell, Y.: Resettably-Sound Zero-Knowledge and its Applications. In: 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, Nevada, October 14–17, IEEE, Los Alamitos (2001)
Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable Zero-Knowledge Cryptology ePrint Archive 1999/022
Cramer, R., Damgård, I.: Fast and Secure Immunization Against Adaptive Man-in-the-Middle Impersonations. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 75–87. Springer, Heidelberg (1997)
Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 68–86. Springer, Heidelberg (2003)
Chen, H., Cramer, R.: Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 521–536. Springer, Heidelberg (2006)
Chen, H., Cramer, R., Goldwasser, S., de Haan, R., Vaikuntanathan, V.: Secure Computation from Random Error Correcting Codes. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 291–310. Springer, Heidelberg (2007)
Damgård, I., Nielsen, J.B., Wichs, D.: Universally Composable Multiparty Computation with Partially Isolated Parties. Cryptology ePrint Archive 2007/332
Feige, U., Lapidot, D., Shamir, A.: Multiple Non-Interactive Zero-Knowledge Proofs Under General Assumptions, Society for Industrial and Applied Mathematics. SIAM Journal on Computing 29(1), 1–28 (1999)
García, A., Stichtenoth, H.: On the asymptotic behavior of some towers offunction fields over finite fields. J. Number Theory 61, 248–273 (1996)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, Providence, Rhode Island, May 6–8, pp. 291–304 (1985)
Katz, J.: Universally Composable Multi-party Computation Using Tamper-Proof Hardware. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 115–128. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I., Nielsen, J.B., Wichs, D. (2008). Isolated Proofs of Knowledge and Isolated Zero Knowledge. In: Smart, N. (eds) Advances in Cryptology – EUROCRYPT 2008. EUROCRYPT 2008. Lecture Notes in Computer Science, vol 4965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78967-3_29
Download citation
DOI: https://doi.org/10.1007/978-3-540-78967-3_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78966-6
Online ISBN: 978-3-540-78967-3
eBook Packages: Computer ScienceComputer Science (R0)