Marten van Dijk
Consultant, Inventor, Researcher, Applied Mathematician, & Computer Scientist
Secret Key Sharing:
A secret sharing scheme is a method of sharing a secret among a set of participants such that only certain
groups of participants are qualified to reconstruct the secret by combining their shares. A secret sharing
scheme is called perfect if each non-qualified subset of the participants gets no information about the
secret (besides the set from which it is distributed). An access structure is the set of qualified groups.
For reasons of efficiency and security it is important to keep the sizes of the shares as small as possible.
This leads to the definition of the worst-case information rate, which is the ratio between the size of the
secret and the maximum size of the shares, and the average information rate, which is the ratio between the
size of the secret and the arithmetic mean of the size of all shares. In secret sharing, the main problems
are: finding basic constructions of secret sharing schemes (that is, building secret sharing schemes from
scratch), finding composition constructions of secret sharing schemes (that is, composing known schemes in
order to build a new scheme), finding upper bounds on the information rates, and finding upper and lower
bounds on the amount of randomness needed to construct each share.
In order to prove the non-existence of secret sharing schemes with certain parameters, [1] and [2] present
a method to upper bound information rates of access structures. This method was used to prove that a lower
bound on the optimal (average) information rate of access structures based on graphs is tight; this
solved a 15 year old open problem in secret sharing showing that shares may need to be unpractically large.
It is based on information theoretical inequalities. A different method based on combinatorics to upper
bound the linear worst-case information rate is presented in [3].
Basic constructions of perfect secret sharing schemes can be understood by using a coding approach [4,5].
This leads to an algorithm for finding new optimal perfect secret sharing schemes. A general theory of
known composition constructions of secret sharing schemes is given in [6,7]. For secret sharing schemes
on incomplete access structures (some non-qualified groups of participants may learn information about the
secret) a duality theorem (as in coding theory) was proved by using a geometric approach and by using
matroid theory [8].
Secret sharing schemes can also be combined with authentication schemes. In the conventional authentication
problem a sender wants to transmit messages to a receiver in the presence of an adversary. The sender and
receiver trust each other and the receiver wants to detect false messages sent by the adversary. The scheme
which the sender and receiver use is called an authentication scheme. The problem can be extended to the
case where the capability to authenticate a message is given to certain groups of people instead of a single
person. During a three month visit at Lund University in Sweden we studied unconditionally secure
authentication schemes based on linear perfect secret sharing schemes [9]. We gave expressions for the
probabilities of successful attacks and we gave a general construction based on maximum rank distance codes.
[1] M. van Dijk, On the Information Rate of Perfect Secret Sharing Schemes,
Designs, Codes, and Cryptography 6(2), 143-169, 1995, preliminary versions appeared in the Proceedings of
the 2nd International Winter Meeting on Coding and Information Theory, December 12 - 15, p. 27, 1993, and
in the Proceedings of ISIT'94, June 27 - July 1, p. 489, 1994.
[2] M. van Dijk, More information theoretical inequalities to be used in secret sharing,
Information Processing Letters 63(1), 41-44, 1997.
[3] M. van Dijk, The optimal linear worst-case information rate,
Proc. of ISIT'97, June 28 - July 4, p. 89, 1997.
[4] M. van Dijk, A linear construction of secret sharing schemes,
Designs, Codes and Cryptography 12(2), 161-201, 1997.
[5] M. van Dijk, A linear construction of perfect secret sharing schemes,
Advances in Cryptology - Eurocrypt'94, LNCS 950, p. 23-34, 1995.
[6] M. van Dijk, W.-A. Jackson, and K. Martin, A general decomposition construction for incomplete secret
sharing schemes, Designs, Codes and Cryptography 15(3), 301-321, 1998.
[7] M. van Dijk, T. Kevenaar, G.J. Schrijen, and P. Tuyls, Improved constructions of secret sharing schemes by
applying (lambda,omega)-decompositions, Information Processing Letters 99(4), p. 154-157, 2006. An
abstract appeared in the Proceedings of ISIT 2003, p. 282, 2003.
[8] M. van Dijk, W.-A. Jackson, and K.M. Martin, A note on duality in linear secret sharing scheme,
Bull. of the Institute of Combinatorics and its Applications 19, 93-101, 1997.
[9] M. van Dijk, C. Gehrmann, and B. Smeets, Unconditionally Secure Group Authentication,
Designs, Codes and Cryptography 14(3), 281-296, 1998.
© 2009 Marten van Dijk .
All rights reserved.