Abstract
Multiplicative threshold schemes are useful tools in thresh- old cryptography. For example, such schemes can be used with a wide variety of practical homomorphic cryptosystems (such as the RSA, the El Gamal and elliptic curve systems) for threshold decryption, signa- tures, or proofs. The paper describes a new recursive construction for multiplicative threshold schemes which makes it possible to extend the number of users of such schemes for a relatively small expansion of the share size. We discuss certain properties of the schemes, such as the information rate and zero knowledge aspects.
The paper extends the Karnin-Greene-Hellman bound on the parame- ters of ideal secret sharing schemes to schemes which are not necessarily ideal and then uses this as a yardstick to compare the performance of currently known multiplicative sharing schemes.
This author is supported by an E.P.S.R.C. Advanced Fellowship.
This author was supported by N.S.F. NCR-9508528 and the E.P.S.R.C.
Chapter PDF
Similar content being viewed by others
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
J.C. Benaloh: Secret sharing homomorphisms: Keeping shares of a secret secret. In: A. Odlyzko (ed.): Advances in Cryptology — Crypto’ 86, Proceedings. Lecture Notes in Computer Science 263. Berlin: Springer 1987, pp. 251–260
G.R. Blakley: Safeguarding cryptographic keys. In: Proc. Nat. Computer Conf. AFIPS Conf. Proc., 48, 1979, pp. 313–317
A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung: How to share a function securely. In: Proceedings of the twenty-sixth annual ACM Symp. Theory of Computing (STOC), IEEE Press 1994, pp. 522–533. Full paper in preparation (available from authors when completed)
Y. Desmedt, G. Di Crescenzo, and M. Burmester: Multiplicative non-abelian sharing schemes and their application to threshold cryptography. In: J. Pieprzyk, R. Safavi-Naini (eds.): Advances in Cryptology — Asiacrypt’ 94, Proceedings. Lecture Notes in Computer Science 917. Berlin: Springer 1995, pp. 21–32
Y. Desmedt and Y. Frankel: Threshold cryptosystems. In: G. Brassard (ed.): Advances in Cryptology — Crypto’ 89, Proceedings. Lecture Notes in Computer Science 435. Berlin: Springer 1990, pp. 307–315
Y. Desmedt and 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 and Y. Frankel: Homomorphic zero-knowledge threshold schemes over any finite abelian group. SIAM Journal on Discrete Mathematics, 7(4), 667–679 (1994)
Y. Frankel and Y. Desmedt. Classification of ideal homomorphic threshold schemes over finite Abelian groups. In: R.A. Rueppel (ed.): Advances in Cryptology — Eurocrypt’ 92, Proceedings. Lecture Notes in Computer Science 658. Berlin: Springer 1993, pp 25–34
Y. Frankel, Y. Desmedt and M. Burmester. Non-existence of homomorphic general sharing schemes for some key spaces. In: E.F. Brickell (ed.): Advances in Cryptology — Crypto’ 92, Proceedings. Lecture Notes in Computer Science 740. Berlin: Springer 1993, pp 549–557
Z. Galil, S. Haber, and M. Yung: Minimum-knowledge interactive proofs for decision problems. SIAM J. Comput., 18(4), 711–739 (1989)
S. Goldwasser, S. Micali, and C. Rackoff: The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1), 186–208 (1989)
E.D. Karnin, J.W. Greene, and M. Hellman: On secret sharing systems. IEEE Trans. Inform. Theory, 29(1), 35–41 (1983)
A. Shamir: How to share a secret. Commun. ACM, 22, 612–613 (1979)
R.C. Singleton: Maximal distance q-nary codes. IEEE Trans. Inform. Theory, IT-10, 116–118 (1964)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blackburn, S.R., Burmester, M., Desmedt, Y., Wild, P.R. (1996). Efficient Multiplicative Sharing Schemes. In: Maurer, U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68339-9_10
Download citation
DOI: https://doi.org/10.1007/3-540-68339-9_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61186-8
Online ISBN: 978-3-540-68339-1
eBook Packages: Springer Book Archive