Skip to main content
Top
Published in: Designs, Codes and Cryptography 3/2015

01-03-2015

Optimal assignment schemes for general access structures based on linear programming

Authors: Qiang Li, Xiang Xue Li, Xue Jia Lai, Ke Fei Chen

Published in: Designs, Codes and Cryptography | Issue 3/2015

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The paper proposes a type of secret sharing schemes called ramp assignment schemes (RAS’s) to realize general access structures (AS’s). In such a scheme, each participant is assigned a subset of primitive shares of an optimal \((k,L,m)\)-ramp scheme in such a way that the number of primitive shares assigned to each qualified subset is not less than \(k\) whereas the one corresponding to any forbidden subset is not greater than \(k-L\). RAS’s can be viewed as a generalization of multiple assignment schemes (MAS’s). For a same AS, the minimum information rate achieved by MAS’s can not be less than that achieved by RAS’s. With our method, one can find efficient suitable decompositions for general AS’s. And it provides a possibility to refine an existing \((\lambda ,\omega )\)-decomposition. We show that a RAS with minimal worst or/and average information rate can be obtained by linear programming (LP), which is in the complexity class P and much easier than the NP-hard integer programming (IP) applied to constructing optimal MAS’s. Several well-designed algorithms are further presented to cut down the size of the LP/IP problems for optimal RAS’s/MAS’s. Other contributions of the paper include: (1) the current best upper bounds of information rates of two graph AS’s on six participants are improved; (2) some specific AS’s are recognized so that one can obtain the corresponding optimal RAS’s directly, i.e., even without the need of solving LP problems; and (3) we characterize the AS’s of ideal RAS’s and of ideal MAS’s.
Appendix
Available only for authorised users
Footnotes
1
For the convenience of linear processing, we inverse the original ratios throughout this paper. And as a result, a SSS with a smaller (worst/average) information rate is more efficient than that with a larger one.
 
2
We should notice that, when we say a RAS is optimal for \(\mathcal{A }\), it means that it is the most efficient scheme among all RAS’s (instead of all SSS’s) realizing \(\mathcal{A }\). Similarly, an optimal MAS for \(\mathcal{A }\) is the most efficient scheme among all MAS’s (instead of all RAS’s) realizing \(\mathcal{A }\).
 
Literature
1.
go back to reference Shamir A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979). Shamir A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979).
2.
go back to reference Blakley G.R.: Safeguarding cryptographic keys. In: AFIPS 1979. National Computer Conference, New York, vol. 48, pp. 137–313 (1979). Blakley G.R.: Safeguarding cryptographic keys. In: AFIPS 1979. National Computer Conference, New York, vol. 48, pp. 137–313 (1979).
3.
go back to reference Brickell E.F., Stinson D.R.: Some improved bounds on the information rate of perfect secret sharing schemes. J. Cryptol. 5(3), 153–166 (1992). Brickell E.F., Stinson D.R.: Some improved bounds on the information rate of perfect secret sharing schemes. J. Cryptol. 5(3), 153–166 (1992).
4.
go back to reference Blundo C.: Secret sharing schemes for access structures based on graphs (in Italian). Tesi di Laurea (1991). Blundo C.: Secret sharing schemes for access structures based on graphs (in Italian). Tesi di Laurea (1991).
5.
go back to reference Martin K.M.: Discrete structures in the theory of secret sharing. Ph.D. thesis, Royal Holloway and Bedford New College, University of London, London (1991). Martin K.M.: Discrete structures in the theory of secret sharing. Ph.D. thesis, Royal Holloway and Bedford New College, University of London, London (1991).
6.
go back to reference Martin K.M.: New secret sharing schemes from old. J. Comb. Math. Comb. Comput. 14, 65–77 (1993). Martin K.M.: New secret sharing schemes from old. J. Comb. Math. Comb. Comput. 14, 65–77 (1993).
7.
go back to reference Karnin E.D., Greene J.W., Hellman M.E.: On secret sharing systems. IEEE Trans. Inf. Theory 29, 35–41 (1983). Karnin E.D., Greene J.W., Hellman M.E.: On secret sharing systems. IEEE Trans. Inf. Theory 29, 35–41 (1983).
8.
go back to reference Capocelli R.M., Santis A.D., Gargano L., Vaccaro U.: On the size of shares for secret sharing schemes. J. Cryptol. 6(3), 157–167 (1993). Capocelli R.M., Santis A.D., Gargano L., Vaccaro U.: On the size of shares for secret sharing schemes. J. Cryptol. 6(3), 157–167 (1993).
9.
go back to reference Csirmaz L.: The size of a share must be large. J. Cryptol. 10, 223–231 (1997). Csirmaz L.: The size of a share must be large. J. Cryptol. 10, 223–231 (1997).
10.
go back to reference Brickell E.F.: Some ideal secret sharing schemes. In: EUROCRYPT ’89, Houthalen, vol. 434, pp. 468–475 (1990). Brickell E.F.: Some ideal secret sharing schemes. In: EUROCRYPT ’89, Houthalen, vol. 434, pp. 468–475 (1990).
11.
go back to reference Blakley G.R., Meadows C.: Security of ramp schemes. In: CRYPTO’84, Santa Barbara, vol. 196, pp. 242–268 (1985). Blakley G.R., Meadows C.: Security of ramp schemes. In: CRYPTO’84, Santa Barbara, vol. 196, pp. 242–268 (1985).
12.
go back to reference Yamamoto Y.: On secret sharing systems using \((k, L, n)\)-threshold scheme (in Japanese). Trans. IEICE J68-A(9), 945–952 (1985). Yamamoto Y.: On secret sharing systems using \((k, L, n)\)-threshold scheme (in Japanese). Trans. IEICE J68-A(9), 945–952 (1985).
13.
go back to reference Ito M., Saito A., Nishizeki T.: Secret sharing scheme realizing any access structure. In: IEEE Globecom 1987, Tokyo, pp. 99–102 (1987). Ito M., Saito A., Nishizeki T.: Secret sharing scheme realizing any access structure. In: IEEE Globecom 1987, Tokyo, pp. 99–102 (1987).
14.
go back to reference Benaloh J., Leichter J.: Generalized secret sharing and monotone functions. In: CRYPTO’88, Santa Barbara, No. 403, pp. 25–35 (1988). Benaloh J., Leichter J.: Generalized secret sharing and monotone functions. In: CRYPTO’88, Santa Barbara, No. 403, pp. 25–35 (1988).
15.
go back to reference Stinson D.R.: An explication of secret sharing schemes. Des. Codes Cryptogr. 2, 357–390 (1992). Stinson D.R.: An explication of secret sharing schemes. Des. Codes Cryptogr. 2, 357–390 (1992).
16.
go back to reference Stinson D.R.: New general lower bounds on the information rate of secret sharing schemes. In: CRYPTO’92, Santa Barbara, No. 740, pp. 168–182 (1993). Stinson D.R.: New general lower bounds on the information rate of secret sharing schemes. In: CRYPTO’92, Santa Barbara, No. 740, pp. 168–182 (1993).
17.
go back to reference Stinson D.R.: Decomposition constructions for secret-sharing schemes. IEEE Trans. Inf. Theory 40, 118–125 (1994). Stinson D.R.: Decomposition constructions for secret-sharing schemes. IEEE Trans. Inf. Theory 40, 118–125 (1994).
18.
go back to reference Blundo C., Santis A.D., Stinson D.R., Vaccaro U.: Graph decompositions and secret sharing schemes. J. Cryptol. 8, 39–64 (1995). Blundo C., Santis A.D., Stinson D.R., Vaccaro U.: Graph decompositions and secret sharing schemes. J. Cryptol. 8, 39–64 (1995).
19.
go back to reference Blundo C., Santis A.D., Gaggia A.G., Vaccaro U.: New bounds on the information rate of secret sharing schemes. IEEE Trans. Inf. Theory 41(2), 549–554 (1995). Blundo C., Santis A.D., Gaggia A.G., Vaccaro U.: New bounds on the information rate of secret sharing schemes. IEEE Trans. Inf. Theory 41(2), 549–554 (1995).
20.
go back to reference Dijk M.V.: On the information rate of perfect secret sharing schemes. Des. Codes Cryptogr. 6, 143–169 (1995). Dijk M.V.: On the information rate of perfect secret sharing schemes. Des. Codes Cryptogr. 6, 143–169 (1995).
21.
go back to reference Jackson W.A., Martin K.M.: Perfect secret sharing schemes on five participants. Des. Codes Cryptogr. 9, 267–286 (1996). Jackson W.A., Martin K.M.: Perfect secret sharing schemes on five participants. Des. Codes Cryptogr. 9, 267–286 (1996).
22.
go back to reference Dijk M.V., Jackson W.A., Martin K.M.: A general decomposition construction for incomplete secret sharing schemes. Des. Codes Cryptogr. 15, 301–321 (1998). Dijk M.V., Jackson W.A., Martin K.M.: A general decomposition construction for incomplete secret sharing schemes. Des. Codes Cryptogr. 15, 301–321 (1998).
23.
go back to reference Li Q., Yan H., Chen K.F.: A new method of using \((k, n)\)-threshold scheme to realize any access structure (in Chinese). J. Shanghai Jiaotong Univ. 38(1), 103–106 (2004). Li Q., Yan H., Chen K.F.: A new method of using \((k, n)\)-threshold scheme to realize any access structure (in Chinese). J. Shanghai Jiaotong Univ. 38(1), 103–106 (2004).
24.
go back to reference Iwamoto M., Yamamoto H., Ogawa H.: Optimal multiple assignments based on integer programming in secret sharing schemes. In: ISIT 2004, Chicago, pp. 16–16 (2004). Iwamoto M., Yamamoto H., Ogawa H.: Optimal multiple assignments based on integer programming in secret sharing schemes. In: ISIT 2004, Chicago, pp. 16–16 (2004).
25.
go back to reference Dijk M.V., Kevenaar T., Schrijen G., Tuyls P.: Improved constructions of secret sharing schemes by applying \((\lambda ,\omega )\)-decompositions. Inf. Process. Lett. 99(4), 154–157 (2006). Dijk M.V., Kevenaar T., Schrijen G., Tuyls P.: Improved constructions of secret sharing schemes by applying \((\lambda ,\omega )\)-decompositions. Inf. Process. Lett. 99(4), 154–157 (2006).
26.
go back to reference Iwamoto M., Yamamoto H., Ogawa H.: Optimal multiple assignments based on integer programming in secret sharing schemes with general access structure. Trans. IEICE E90-A(1), 101–112 (2007). Iwamoto M., Yamamoto H., Ogawa H.: Optimal multiple assignments based on integer programming in secret sharing schemes with general access structure. Trans. IEICE E90-A(1), 101–112 (2007).
27.
go back to reference Chvátal V.: Linearing Programming. W.H. Freeman, New York (1983). Chvátal V.: Linearing Programming. W.H. Freeman, New York (1983).
28.
go back to reference Karmarkar N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984). Karmarkar N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984).
29.
go back to reference Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1990). Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1990).
30.
go back to reference Brickell E.F., Davenport D.M.: On the classification of ideal secret sharing schemes. J. Cryptol. 4(73), 123–134 (1991). Brickell E.F., Davenport D.M.: On the classification of ideal secret sharing schemes. J. Cryptol. 4(73), 123–134 (1991).
31.
go back to reference Blundo C., De Santis A., Vaccaro U.: Efficient sharing of many secrets. In: STACS’93, Würzburg, vol. 665, pp. 692–703 (1993). Blundo C., De Santis A., Vaccaro U.: Efficient sharing of many secrets. In: STACS’93, Würzburg, vol. 665, pp. 692–703 (1993).
32.
go back to reference Kurosawa K., Okada K., Sakano K., Ogata W., Tsujii T.: Nonperfect secret sharing schemes and matroids. In: EUROCRYPT’93, Lofthus, pp. 126–141 (1993). Kurosawa K., Okada K., Sakano K., Ogata W., Tsujii T.: Nonperfect secret sharing schemes and matroids. In: EUROCRYPT’93, Lofthus, pp. 126–141 (1993).
33.
go back to reference Simmons G.J., Jackson W.A., Martin K.M.: The geometry of shared secret schemes. Bull. Inst. Comb. Appl. 1, 71–88 (1991). Simmons G.J., Jackson W.A., Martin K.M.: The geometry of shared secret schemes. Bull. Inst. Comb. Appl. 1, 71–88 (1991).
35.
go back to reference Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009). Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009).
36.
go back to reference Ye Y.: Interior Point Algorithms, Theory and Analysis. Wiley, New York (1997). Ye Y.: Interior Point Algorithms, Theory and Analysis. Wiley, New York (1997).
37.
go back to reference Jackson W.A., Martin K.M.: A combinatorial interpretation of ramp schemes. Australas. J. Comb. 14, 51–60 (1996). Jackson W.A., Martin K.M.: A combinatorial interpretation of ramp schemes. Australas. J. Comb. 14, 51–60 (1996).
38.
go back to reference Beimel A., Chor B.: Universally ideal secret sharing schemes. IEEE Trans. Inf. Theory 40(3), 786–794 (1994). Beimel A., Chor B.: Universally ideal secret sharing schemes. IEEE Trans. Inf. Theory 40(3), 786–794 (1994).
39.
go back to reference Beimel A., Tassa T., Weinreb E.: Characterizing ideal weighted threshold secret sharing. In: TCC’05, Cambridge, vol. 3378, pp. 600–619 (2005). Beimel A., Tassa T., Weinreb E.: Characterizing ideal weighted threshold secret sharing. In: TCC’05, Cambridge, vol. 3378, pp. 600–619 (2005).
40.
go back to reference Beimel A., Livne N., Padró C.: Matroids can be far from ideal secret sharing. In: TCC’08, New York, vol. 4948, pp. 194–212 (2008). Beimel A., Livne N., Padró C.: Matroids can be far from ideal secret sharing. In: TCC’08, New York, vol. 4948, pp. 194–212 (2008).
Metadata
Title
Optimal assignment schemes for general access structures based on linear programming
Authors
Qiang Li
Xiang Xue Li
Xue Jia Lai
Ke Fei Chen
Publication date
01-03-2015
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 3/2015
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-013-9879-3

Other articles of this Issue 3/2015

Designs, Codes and Cryptography 3/2015 Go to the issue

Premium Partner