On identification secret sharing schemes. (English) Zbl 1054.68048

Cai, Ning; Lam, Kwok Yan

Inf. Comput. 184, No. 2, 298-310 (2003).

Summary: Let \(\mathcal P\) be a set of participants sharing a secret from a set of secrets. A secret sharing scheme is a protocol such that any qualified subset of \(\mathcal P\) can determine the secret by pooling their shares, the messages which they receive, without error, whereas non-qualified subsets of \(\mathcal P\) cannot obtain any knowledge about the secret when they pool what they receive. In (optimal) schemes, the sizes of shared secrets depend on the sizes of shares given to the participants. Namely the former grow up exponentially as the latter increase exponentially. In this paper, instead of determining the secret, we require the qualified subsets of participants to identify the secret. This change would certainly make no difference from determining secret if no error for identification were allowed. So here we relax the requirement to identification such that an error may occur with a vanishing probability as the sizes of the secrets grow up. Under relaxed condition this changing allows us to share a set of secrets with double exponential size as the sizes of shares received by the participants exponentially grow. Thus much longer secret can be shared. On the other hand, by the continuity of Shannon entropy we have that the relaxation makes no difference for (ordinary) secret sharing schemes. We obtain the characterizations of relations of sizes of secrets and sizes of the shares for identification secret sharing schemes without and with public message. Our idea originates from Ahlswede-Dueck’s awarded work in 1989, where the identification codes via channels were introduced.

MSC:

68P25

Data encryption (aspects in computer science)

Keywords:

Identification; Secret sharing; Public message

References:

[1]	R. Ahlswede, General theory of information transfer, Preprint 97-118, SFB 343 Diskrete Strukturen in der Mathematik, 1997; R. Ahlswede, General theory of information transfer, Preprint 97-118, SFB 343 Diskrete Strukturen in der Mathematik, 1997 · Zbl 1158.94329
[2]	Ahlswede, R.; Dueck, G., Identification via channels, IEEE Trans. Inform. Theory, 35, 15-29 (1989) · Zbl 0671.94007
[3]	Ahlswede, R.; Dueck, G., Identification in presence of feedback – a discovery of new capacity formulas, IEEE Trans. Inform. Theory, 35, 30-39 (1989) · Zbl 0671.94008
[4]	Blakley, G. R., Safeguarding cryptographic keys, AFIPS Conf. Proc., 48, 313-317 (1979)
[5]	Brickell, E. F.; Davenport, D. M., On the classification of ideal secret sharing schemes, J. Crypt., 4, 123-134 (1991) · Zbl 0747.94010
[6]	Capocelli, R. M.; De Santis, A.; Gargano, L.; Vaccaro, U., On the size of shares for secret sharing schemes, J. Crypt., 6, 157-168 (1993) · Zbl 0786.68030
[7]	Han, T. S.; Verdu, S., New results in the theory and application of identification via channels, IEEE Trans. Inform. Theory, 38, 14-25 (1992) · Zbl 0745.93079
[8]	M. Ito, A. Saito, T. Nishizeki, Secret sharing scheme realizing general access structure, in: Proceedings of the EEE Globecom’87, 1987, pp. 99-102; M. Ito, A. Saito, T. Nishizeki, Secret sharing scheme realizing general access structure, in: Proceedings of the EEE Globecom’87, 1987, pp. 99-102
[9]	Karnin, E. D.; Greene, J. W.; Hellman, M. E., On secret sharing schemes, IEEE Trans. Inform. Theory, 29, 35-41 (1983) · Zbl 0503.94018
[10]	Shamir, A., How to share a secret, Commun.ACM, 22, 612-613 (1979) · Zbl 0414.94021
[11]	Shannon, C. E., A mathematics theory of communication, Bell Syst. Technol. J., 27, 339-425 (1948), 623-656 · Zbl 1154.94303
[12]	Steinberg, New converses in the theory of identification via channels, IEEE Trans. Inform. Theory, 984-998 (1998) · Zbl 0910.94012
[13]	Stinson, D. R., An explication of secret sharing schemes, Des. Codes Cryptogr., 2, 357-390 (1992) · Zbl 0793.68111
[14]	Stinson, D. R., Decomposition constructions for secret-sharing schemes, IEEE Trans. Inform. Theory, 118-125 (1998) · Zbl 0803.94017