Abstract
A black-box secret sharing scheme for the threshold access structure T t,n is one which works over any finite Abelian group G. Briefly, such a scheme differs from an ordinary linear secret sharing scheme (over, say, a given finite field) in that distribution matrix and reconstruction vectors are defined over ℤ and are designed independently of the group G from which the secret and the shares are sampled. This means that perfect completeness and perfect privacy are guaranteed regardless of which group G is chosen. We define the black-box secret sharing problem as the problem of devising, for an arbitrary given T t,n , a scheme with minimal expansion factor, i.e., where the length of the full vector of shares divided by the number of players n is minimal.
Such schemes are relevant for instance in the context of distributed cryptosystems based on groups with secret or hard to compute group order. A recent example is secure general multi-party computation over black-box rings.
In 1994 Desmedt and Frankel have proposed an elegant approach to the black-box secret sharing problem based in part on polynomial interpolation over cyclotomic number fields. For arbitrary given T t,n with 0 < t < n - 1, the expansion factor of their scheme is O(n). This is the best previous general approach to the problem.
Using certain low degree integral extensions of ℤ over which there exist pairs of sufficiently large Vandermonde matrices with co-prime determinants, we construct, for arbitrary given T t,n with 0 < t < n - 1, a black-box secret sharing scheme with expansion factor O(log n), which we show is minimal.
Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.
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
A. Beimel. Secure schemes for secret sharing and key distribution. Ph.D.-thesis, Technion, Haifa, June 1996.
J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In: Proc. CRYPTO’ 88, Springer LNCS, vol. 765, pp. 274–285, 1988.
M. Bertilsson, I. Ingemarsson. A construction of practical secret sharing schemes using linear block codes. In Proc. AUSCRYPT’ 92, Springer LNCS, vol. 718, pp. 67–79, 1993.
S. Blackburn, M. Burmester, Y. Desmedt, and P. Wild. Efficient multiplicative sharing scheme. In: Proc. EUROCRYPT’ 96, Springer LNCS, vol. 1070, pp. 107–118, 1996.
G. R. Blakley. Safeguarding cryptographic keys. In: Proc. National Computer Conference’ 79, AFIPS Proceedings, vol. 48, pp. 313–317, 1979.
E. F. Brickell. Some ideal secret sharing schemes. In: J. Combin. Maths. & Combin. Comp. vol. 9, pp. 105–113, 1989.
T. Cover and J. Thomas. Elements of information theory. Wiley Series in Telecommunications, 1991.
R. Cramer, I. Damgaard, and U. Maurer. Efficient general secure multi-party computation from any linear secret-sharing scheme. In: Proc. EUROCRYPT’ 00, Springer LNCS, vol. 1807, pp. 316–334, 2000.
R. Cramer, S. Fehr, Y. Ishai, and E. Kushilevitz. Efficient multi-party computation over rings. Manuscript, February 2002.
Y. Di Crescenzo, and Y. Frankel. Existence of Multiplicative Secret Sharing Schemes with Polynomial Share Expansion. In: Proc. SODA’ 99, ACM Press, pp. 895–896, 1999.
Y. Desmedt and Y. Frankel. Theshold cryptosystem. In: Proc. CRYPTO’ 89, Springer LNCS, vol. 435, pp. 307–315, 1990.
Y. Desmedt and Y. Frankel. Homomorphic zero-knowledge threshold schemes over any finite Abelian group. In: SIAM Journal on Discrete Mathematics, 7(4), pp. 667–679, 1994.
Y. Desmedt, A. De Santis, Y. Frankel, and M. Yung. How to share a function securely. In: Proc. STOC’ 94, ACM Press, pp. 22–33, 1994.
Y. Desmedt, G. Di Crescenzo, and M. Burmester. Multiplicative non-abelian sharing schemes and their application to threshold cryptography. In: Proc. ASIACRYPT’ 94, Springer LNCS, vol. 917, pp. 21–31, 1995.
Y. Desmedt, B. King, W. Kishimoto, and K. Kurosawa. A comment on the efficiency of secret sharing scheme over any finite Abelian group. In: Proc. ACISP’ 98, Springer LNCS, vol. 1438, pp. 391–402, 1998.
M. van Dijk. Secret key sharing and secret key generation. Ph. D. Thesis, Eindhoven University of Technology, 1997.
Y. Frankel, P. Gemmell, P. MacKenzie, and M. Yung. Optimal resilience proactive public-key cryptosystems. In: Proc. FOCS’ 97, IEEE Press, pp. 384–393, 1997.
Y. Frankel, P. Gemmell, P. MacKenzie, and M. Yung. Proactive RSA. In: Proc. CRYPTO’ 97, Springer LNCS, vol. 1294, pp. 440–454, 1997.
A. Gál. Combinatorial methods in boolean function complexity. Ph.D.-thesis, University of Chicago, 1995.
M. Karchmer and A. Wigderson. On span programs. In: Proc. Structures in Complexity Theory’ 93, IEEE Computer Society Press, pp. 102–111, 1993.
B. King. Some results in linear secret sharing. Ph.D.-thesis, University of Wisconsin-Milwaukee, 2001.
B. King. Randomness required for linear threshold sharing schemes defined over any finite abelian group. In: Proc. ACISP’ 01, Springer LNCS, vol. 2119, pp. 376–391, 2001.
S. Lang. Algebra. Addison-Wesley Publishing Co., 2nd edition, 1984.
A. Shamir. How to share a secret. In: Communications of the ACM, (22) pp. 612–613, 1979.
V. Shoup. Practical threshold signatures. In: Proc. EUROCRYPT’ 00, Springer LNCS, vol. 1807, pp. 207–220, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cramer, R., Fehr, S. (2002). Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_18
Download citation
DOI: https://doi.org/10.1007/3-540-45708-9_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44050-5
Online ISBN: 978-3-540-45708-4
eBook Packages: Springer Book Archive