Constructions of some secret sharing schemes based on linear codes

S. M. Ratseev

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 24 (2024) no. 3, pp. 330-341.

Résumé

There are perfect and ideal threshold secret sharing schemes, for example, Shamir’s secret sharing scheme. For the case of general secret sharing schemes with an arbitrary access structure, it is possible to construct a perfect scheme for any access structure (for example, the Ito – Saito – Nishizeki scheme, the Benaloh – Leichter scheme), but in general, such a scheme will not be an ideal secret sharing scheme. In the paper, for some classes of access structures, the construction of perfect and ideal secret sharing schemes based on linear codes is given. We also give a construction of perfect verifiable secret sharing schemes for any access structure for which there is a line code that implements this structure.

Bibliographie

[1] McEliece R. J., Sarwate D. V., “On sharing secrets and Reed – Solomon codes”, Communications of the ACM, 24:9 (1981), 583–584 | DOI | MR

[2] Renvall A., Ding C., “The access structure of some secret-sharing schemes”, Information Security and Privacy, ACISP 1996, Lecture Notes in Computer Science, 1172, eds. Pieprzyk J., Seberry J., Springer, Berlin–Heidelberg, 1996, 67–78 | DOI

[3] Ding C., Laihonen T., Renvall A., “Linear multisecret-sharing schemes and error-correcting codes”, Journal of Universal Computer Science, 3:9 (1997), 1023–1036 | MR | Zbl

[4] Karnin E. D., Greene J. W., Hellman M. E., “On secret sharing systems”, IEEE Transactions on Information Theory, 29:1 (1983), 35–41 | DOI | MR | Zbl

[5] Pieprzyk J., Zhang X. M., “Ideal threshold schemes from MDS codes”, Information Security and Cryptology, ICISC 2002, Lecture Notes in Computer Science, 2587, eds. Lee P. J., Lim C. H., Springer, Berlin–Heidelberg, 2003, 253–263 | DOI | MR | Zbl

[6] Massey J. L., “Minimal codewords and secret sharing”, Proceedings of the 6th Joint Swedish-Russian Workshop on Information Theory (Molle, Sweden, 1993), 276–279

[7] Massey J. L., “Some applications of coding theory in cryptography”, Codes and Ciphers: Cryptography and Coding IV, ed. Farrell P. G., Formara Ltd., Essex, England, 1995, 33–47

[8] Tang C., Gao S., Zhang C., “The optimal linear secret sharing scheme for any given access structure”, Journal of Systems Science and Complexity, 26:4 (2013), 634–649 | DOI | MR | Zbl

[9] Cramer R., Damgård I. B., Döttling N., Fehr S., Spini G., “Linear secret sharing schemes from error correcting codes and universal hash functions”, Advances in Cryptology, EUROCRYPT 2015, Lecture Notes in Computer Science, 9057, eds. Oswald E., Fischlin M., Springer, Berlin–Heidelberg, 2015, 313–336 | DOI | MR | Zbl

[10] Tentu A. N., Paul P., Venkaiah V. Ch., “Ideal and perfect hierarchical secret sharing schemes based on MDS codes”, Proceeding of International Conference on Applied and Computational Mathematics (Ankara, Turkey, 2012), 256–272

[11] Ratseev S. M., Elementy vysshei algebry i teorii kodirovaniya, ucheb. posobie dlya vuzov, Lan, Sankt-Peterburg, 2022, 656 pp.

[12] Ratseev S. M., Matematicheskie metody zaschity informatsii, ucheb. posobie dlya vuzov, Lan, Sankt-Peterburg, 2022, 544 pp.