Abstract
An interactive proof is transferred if a person, while interacting with the prover, convinces a (second) verifier of the statement. Divertible proof systems, first introduced by Desmedt et al., offer a more subtle way of transferring a proof: the messages are blinded such that neither the prover nor the second verifier can ever discover what is going on. While the ability to transfer (and divert) interactive proofs is useful in many situations it also has the disadvantage that the prover has less control over the use of the proofs. This paper investigates (and limits) the possibilities of transferring and diverting certain interactive proofs. In particular it is shown that zero-knowledge proof systems based on a polynomial number of sequential iterations of a three-move protocol cannot be transferred (and hence diverted) to two independent third parties even with just a very small (polynomial fraction) probability of success unless the proof is insecure for the prover. Furthermore, if the three move protocol in itself constitutes a witness hiding proof of knowledge it is shown that it cannot be diverted to two independent third parties simultaneously with overwhelming probability. This result rules out one possible attack on the blind signature scheme suggested by Ohta and Okamoto.
Funded by Carlsbergfondet
Chapter PDF
Keywords
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
M. Burmester and Y. Desmedt. All Languages in NP Have Divertible Zero-Knowledge Proofs and Arguments under Cryptographic Assumptions. In Advances in Cryptology — proceedings of EUROCRYPT 90, Lecture Notes in Computer Science, pages 1–10, 1991.
D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of a discrete logarithm and some generalizations. In Advances in Cryptology — proceedings of EUROCRYPT 87, Lecture Notes in Computer Science, pages 127–141, 1987.
D. Chaum. Zero-knowledge undeniable signatures. In Advances in Cryptology — proceedings of EUROCRYPT 90, Lecture Notes in Computer Science, pages 458–464. Springer Verlag, 1991.
Chen Lidong. Witness Hiding Proofs and Applications. PhD thesis, Aarhus University, Mathematics Institute, 1994.
Y. Desmedt, C. Goutier, and S. Bengio. Special Uses and Abuses of the Fiat-Shamir Passport Protocol. In Advances in Cryptology — proceedings of CRYPTO 87, Lecture Notes in Computer Science, pages 21–39. Springer-Verlag, 1988.
U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1(2):77–94, 1988.
A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology — proceedings of EUROCRYPT 86, Lecture Notes in Computer Science, pages 186–194. Springer-Verlag, 1987.
U. Feige and A. Shamir. Witness indistinguishable and witness hiding protocols. In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, pages 416–426, 1990.
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal of Computation, 18(1):186–208, 1989.
T. Itoh, K. Sakurai, and H. Shizuya. Any Language in IP Has a Divertible ZKIP. In Advances in Cryptology — proceedings of ASIACRYPT 91, Lecture Notes in Computer Science, pages 382–397. Springer-Verlag, 1993.
T. Okamoto and K. Ohta. Divertible Zero Knowledge Interactive Proofs and Commutative Random Self-Reducibility. In Advances in Cryptology — proceedings of EUROCRYPT 89, Lecture Notes in Computer Science, pages 134–149. Springer-Verlag, 1990.
G. J. Simmons. The Prisoner's Problem and the Subliminal Problem. In Advances in Cryptology — proceedings of CRYPTO 83, pages 51–67, 1984.
M. Tompa and H. Woll. Random self-reducibility and zero knowledge interactive proofs of possession of information. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, pages 472–482, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, L., Damgård, I.B., Pedersen, T.P. (1995). Parallel divertibility of proofs of knowledge. In: De Santis, A. (eds) Advances in Cryptology — EUROCRYPT'94. EUROCRYPT 1994. Lecture Notes in Computer Science, vol 950. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0053431
Download citation
DOI: https://doi.org/10.1007/BFb0053431
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60176-0
Online ISBN: 978-3-540-44717-7
eBook Packages: Springer Book Archive