×

A simple combinatorial treatment of constructions and threshold gaps of ramp schemes. (English) Zbl 1283.94078

Summary: We give easy proofs of some recent results concerning threshold gaps in ramp schemes. We then generalise a construction method for ramp schemes employing error-correcting codes so that it can be applied using nonlinear (as well as linear) codes. Finally, as an immediate consequence of these results, we provide a new explicit bound on the minimum length of a code having a specified distance and dual distance.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bierbrauer, J.: Introduction to Coding Theory. Chapman & Hall/ CRC (2005) · Zbl 1060.94001
[2] Blakley, G.R., Meadows, C.: Security of ramp schemes. Lect. Notes Comput. Sci. 196, 242–268 (1985) (CRYPTO 1984) · Zbl 1359.68062 · doi:10.1007/3-540-39568-7_20
[3] Blundo, C., De Santis, A., Vaccaro, U.: Efficient sharing of many secrets. Lect. Notes Comput. Sci. 665, 692–703 (1993) (STACS ’93) · Zbl 0796.94007 · doi:10.1007/3-540-56503-5_68
[4] Cascudo, I., Cramer, R., Xing, C.: Bounds on the threshold gap in secret sharing over small fields. Cryptology ePrint Archive: Report 2012/319. http://eprint.iacr.org/2012/319 (2012) [Version 1 is dated June 5, 2012; version 2 is dated Sept. 27, 2012]
[5] Chen, H., Cramer, R.: Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. Lect. Notes Comput. Sci. 4117, 521–536 (2006) (CRYPTO 2006) · Zbl 1129.94016 · doi:10.1007/11818175_31
[6] Chen, H., Cramer, R., Goldwasser, S., de Haan, R., Vaikuntanathan, V.: Secure computation from random error correcting codes. Lect. Notes Comput. Sci. 4515, 291–310 (2007) (EUROCRYPT 2007) · Zbl 1141.94346 · doi:10.1007/978-3-540-72540-4_17
[7] Dawson, E., Mahmoodian, E.S.: Orthogonal arrays and ordered threshold schemes. Australas. J. Comb. 8, 27–44 (1993) · Zbl 0795.05035
[8] Delsarte, P.: An Algebraic Approach to the Association Schemes of Coding Theory. Philips Research Reports Supplements (1973) · Zbl 1075.05606
[9] Delsarte, P.: Four fundamental parameters of a code and their combinatorial significance. Inf. Control 23, 407–438 (1973) · Zbl 0274.94010 · doi:10.1016/S0019-9958(73)80007-5
[10] Duursma, I., Chen, J.: Multiplicative secret sharing schemes from Reed–Muller type codes. In: 2012 IEEE International Symposium on Information Theory Proceedings, pp. 264–268
[11] Hedayat, A.S., Sloane, N.J.A., Stufken, J.: Orthogonal Arrays, Theory and Applications. Springer (1999) · Zbl 0935.05001
[12] Jackson, W.-A., Martin, K.M.: A combinatorial interpretation of ramp schemes. Australas. J. Comb. 14, 51–60 (1996) · Zbl 0862.94016
[13] Kohnert, A.: Construction of linear codes having prescribed primal-dual minimum distance with applications in cryptography. Albanian J. Math. 2, 221–227 (2008) · Zbl 1183.94057
[14] Kurihara, J., Uyematsu, T., Matsumoto, R.: Secret sharing schemes based on linear codes can be precisely characterized by the relative generalized hamming weight. IEICE Trans. Fundam. E95-A(11), 2067–2075 (2012)
[15] Kurosawa, K., Satoh, T.: Design of SAC/PC() of order k boolean functions and three other cryptographic criteria. Lect. Notes Comput. Sci. 1233, 434–449 (1997) (EUROCRYPT 1997) · doi:10.1007/3-540-69053-0_30
[16] van Lint, J.H.: Introduction to Coding Theory, 3rd edn. Springer (1998) · Zbl 0485.94015
[17] van Lint, J.H., Springer, T.A.: Generalized Reed–Solomon codes from algebraic geometry. IEEE Trans. Inf. Theory 33, 305–309 (1987) · Zbl 0625.94012 · doi:10.1109/TIT.1987.1057320
[18] MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland (1977) · Zbl 0369.94008
[19] Martin, K.M., Paterson, M.B., Stinson, D.R.: Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures. Cryptogr. Commun. – Discrete Structures, Boolean Functions and Sequences 3, 65–86 (2011) · Zbl 1235.94056
[20] Massey, J.L.: Minimal codewords and secret sharing. In: Proceedings of the 6th Joint Swedish–Russian International Workshop on Information Theory, pp. 276–279 (1993)
[21] Matsumoto, R., Kurosawa, K., Itoh, T., Konno, T., Uyematsu, T.: Primal-dual distance bounds of linear codes with application to cryptography. IEEE Trans. Inf. Theory 52, 4251–4256 (2006) · Zbl 1320.94093 · doi:10.1109/TIT.2006.880050
[22] McEliece, R.J., Sarwate, D.V.: On sharing secrets and Reed–Solomon codes. Commun. ACM 24, 583–584 (1981) · doi:10.1145/358746.358762
[23] Ogata, W., Kurosawa, K.: Some basic properties of general nonperfect secret sharing schemes. J. Univers. Comput. Sci. 4, 690–704 (1998) · Zbl 0967.68060
[24] Stinson, D.R., Wei, R.: An application of ramp schemes to broadcast encryption. Inf. Process. Lett. 69, 131–135 (1999) · Zbl 1337.94073 · doi:10.1016/S0020-0190(98)00204-X
[25] Sudan, M.: Algorithmic introduction to coding theory. Lecture 21 (2001). http://people.csail.mit.edu/madhu/FT01/scribe/lect21.ps . Accessed 26 Sept 2012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.