Abstract
We show how to construct a perfect zero-knowledge threshold proof of knowledge of an isomorphism between two graphs, and extend this result to general access structures. The provers work sequentially and are not allowed to interact among themselves, so the number of message communications each prover sends is the same as with the Goldreich-Micali-Wigderson [12] scheme. Our construction is based on multiplicative sharing schemes in which the secret belongs to a group which is not necessarily Abelian.
A part of this work has been supported by NSF Grant NCR-9106327. Partly carried out while visiting Royal Holloway, University of London and the Università di Salerno, Italy, respectively, and supported in part by NSF Grant INT-9123464 and in part by CNR AI n.94.00011.
Preview
Unable to display preview. Download preview PDF.
References
M. Bellare, O. Goldreich: On defining proofs of knowledge. In: E. F. Brickell (ed.): Advances in Cryptology — Crypto '92, Proceedings (Lecture Notes in Computer Science 740), Berlin: Springer 1993, pp. 390–420
J. C. Benaloh, J. Leichter: Generalized secret sharing and monotone functions. In: S. Goldwasser (ed.): Advances in Cryptology, Proc. of Crypto'88 (Lecture Notes in Computer Science 403), Berlin: Springer 1990, pp. 27–35
G. R. Blakley: Safeguarding cryptographic keys. In: Proc. Nat. Computer Conf. AFIPS Conf. Proc, vol. 48, 1979, pp. 313–317
D. Chaum, J.-H. Evertse, J. van de Graaf: An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In: D. Chaum and W. L. Price (eds.): Advances in Cryptology — Eurocrypt '87 (Lecture Notes in Computer Science 304), Berlin: Springer, Berlin 1988, pp. 127–141
A. De Santis, Y. Desmedt, Y. Frankel, M. Yung: How to Share a Function Securely. Proceedings of the twenty-sixth annual ACM Symp. Theory of Computing (STOC), May 23—25, 1994, pp. 522–533 (full paper in preparation)
Y. Desmedt: Threshold cryptosystems. In: J. Seberry, Y. Zheng (eds.): Advances in Cryptology —Auscrypt '92 (Lecture Notes in Computer Science 718), Berlin: Springer 1993, pp. 3–14
Y. Desmedt, Y. Frankel: Shared generation of authenticators and signatures. In: J. Feigenbaum (ed.): Advances in Cryptology — Crypto '91, Proceedings (Lecture Notes in Computer Science 576), Berlin: Springer 1992, pp. 457–469
Y. Desmedt, Y. Frankel: Perfect zero-knowledge sharing schemes over any finite Abelian group. In: R. Capocelli, A. De Santis, and U. Vaccaro (eds.): Sequences II (Methods in Communication, Security, and Computer Science), Berlin: Springer 1993, pp. 369–378
Y. G. Desmedt, Y. Frankel: Homomorphic Zero-Knowledge Threshold Schemes over any Finite Abelian Group. SIAM Journal on Discrete Mathematics, 7(4), pp. 667–67 (1994)
U. Feige, A. Fiat, A. Shamir: Zero knowledge proofs of identity. Journal of Cryptology, 1(2), pp. 77–94 (1988)
Y. Frankel, Y. Desmedt: Parallel reliable threshold multisignature. Technical Report #TR-92-04-02, April 1992, Dept. of EE & CS, Univ. of Wisconsin-Milwaukee
O. Goldreich, S. Micali, A. Wigderson: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(1), pp. 691–729, (1991)
S. Goldwasser, S. Micali, C. Rackoff: The knowledge complexity of interactive proof systems. Siam J. Comput., 18(1), pp. 186–208 (1989)
R. Graham, D. E. Knuth, O. Patashnik: Concrete Mathematics — A foundation for computer science. Addison-Wesley, Reading, MA (1989)
T. P. Pedersen: Distributed provers with applications to undeniable signatures. In: D. W. Davies (ed.): Advances in Cryptology, Proc. of Eurocrypt '91 (Lecture Notes in Computer Science 547), Berlin: Springer April 1991, pp. 221–242
F. P. Preparata: Introduction to computer engineering. Harper & Row, New York (1985)
R. L. Rivest, A. Shamir, L. Adleman: A method for obtaining digital signatures and public key cryptosystems. Commun. ACM, 21, pp. 294–299 (1978)
A. Shamir: How to share a secret. Commun. ACM, 22, pp. 612–613 (1979)
V. M. Sidelnikov: Exponentiation-based key generation using noncommutative groups. In: Proceedings 1994 IEEE International Symposium on Information Theory, p. 497, Trondheim, Norway, June 27–July 1, 1994
G. J. Simmons, W. Jackson, K. Martin: The geometry of shared secret schemes. Bulletin of the Institute of Combinatorics and its Applications, 1, pp. 71–88 (1991)
M. Tompa, H. Woll: Random self-reducibility and zero-knowledge interactive proofs of possession of information. In: 28th Annual Symp. on Foundations of Computer Science (FOCS), pp. 472–482, IEEE Computer Society Press (1987)
A. Vandermonde: Mémoire sur des irrationnelles de différens ordres avac une application au cercle, 1772. Histoire de l'Académie Royale des Sciences, part 1, pp. 71–72; Mémoires de Mathématique et de Physique, Tirés des Registres de l'Academie Royale des Sciences, pp. 489–498
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Desmedt, Y., Di Crescenzo, G., Burmester, M. (1995). Multiplicative non-abelian sharing schemes and their application to threshold cryptography. In: Pieprzyk, J., Safavi-Naini, R. (eds) Advances in Cryptology — ASIACRYPT'94. ASIACRYPT 1994. Lecture Notes in Computer Science, vol 917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0000421
Download citation
DOI: https://doi.org/10.1007/BFb0000421
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59339-3
Online ISBN: 978-3-540-49236-8
eBook Packages: Springer Book Archive