nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

verfasst von : Amos Beimel, Oriol Farràs, Yuval Mintz, Naty Peter

Erschienen in: Theory of Cryptography

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph \(G=(V,E)\) if a pair of vertices can reconstruct the secret if and only if it is an edge in G. Secret-sharing schemes for forbidden graph access structures of bipartite graphs are equivalent to conditional disclosure of secrets protocols, a primitive that is used to construct attributed-based encryption schemes.

We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes. A secret-sharing scheme is linear if the reconstruction of the secret from the shares is a linear mapping. In many applications of secret-sharing, it is required that the scheme will be linear. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and dense graphs, closing the gap between upper and lower bounds: Given a sparse graph with n vertices and at most \(n^{1+\beta }\) edges, for some \( 0 \le \beta < 1\), we construct a linear secret-sharing scheme realizing its forbidden graph access structure in which the total size of the shares is \(\tilde{O} (n^{1+\beta /2})\). We provide an additional construction showing that every dense graph with n vertices and at least \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) - n^{1+\beta }\) edges can be realized by a linear secret-sharing scheme with the same total share size.

We provide lower bounds on the share size of linear secret-sharing schemes realizing forbidden graph access structures. We prove that for most forbidden graph access structures, the total share size of every linear secret-sharing scheme realizing these access structures is \(\varOmega (n^{3/2})\), which shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every \( 0 \le \beta < 1\) there exist a graph with at most \(n^{1+\beta }\) edges and a graph with at least \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }\) edges, such that the total share size of every linear secret-sharing scheme realizing these forbidden graph access structures is \(\varOmega (n^{1+\beta /2})\). This shows that our constructions are optimal (up to poly-logarithmic factors).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Evolving Secret Sharing: Dynamic Thresholds and Robustness

Nächstes Kapitel Near-Optimal Secret Sharing and Error Correcting Codes in

A linear CDS is a CDS in which if the predicate holds, then the reconstruction function of the referee is linear.

We label a row by a party rather than by a variable \(x_j\) as done in [37].

In [46], the access structure is specified by the complement graph, i.e., by the edges that are forbidden from learning information on the secret.

In [8, Lemma 3.8], it is only stated that the total share size in the scheme is O(nd), however, in their scheme the size of the share of each vertex is O(d).

Notice that the rows are not necessarily linearly independent (since rows labeled by different parties can be dependent). Therefore, the number of columns can actually be smaller than the number of rows.

By adding all-zero rows we can assume that the size is exactly S.

Ambrona, M., Barthe, G., Schmidt, B.: Generic transformations of predicate encodings: constructions and applications. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 36–66. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_2 CrossRef

Applebaum, B., Arkis, B., Raykov, P., Vasudevan, P.N.: Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 727–757. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_24 CrossRef

Attrapadung, N.: Dual system encryption via doubly selective security: framework, fully secure functional encryption for regular languages, and more. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 557–577. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_31 CrossRef

Beimel, A.: Secure schemes for secret sharing and key distribution. Ph.D. thesis, Technion (1996). www.cs.bgu.ac.il/ beimel/pub.html

Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20901-7_2 CrossRef

Beimel, A., Chor, B.: Universally ideal secret sharing schemes. IEEE Trans. Inf. Theory 40(3), 786–794 (1994)CrossRefMATHMathSciNet

Beimel, A., Farràs, O., Mintz, Y.: Secret-sharing schemes for very dense graphs. J. Cryptology 29(2), 336–362 (2016)CrossRefMATHMathSciNet

Beimel, A., Farràs, O., Peter, N.: Secret sharing schemes for dense forbidden graphs. In: Zikas, V., De Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 509–528. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44618-9_27

Beimel, A., Gál, A., Paterson, M.: Lower bounds for monotone span programs. Comput. Complex. 6(1), 29–45 (1997)CrossRefMATHMathSciNet

10.

Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317–342. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_14 CrossRef

11.

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 1–10 (1988)

12.

Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27–35. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_3

13.

Bertilsson, M., Ingemarsson, I.: A construction of practical secret sharing schemes using linear block codes. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 67–79. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57220-1_53

14.

Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the 1979 AFIPS National Computer Conference. AFIPS Conference proceedings, vol. 48, pp. 313–317. AFIPS Press (1979)

15.

Blundo, C., De Santis, A., de Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Des. Codes Crypt. 11(2), 107–122 (1997)CrossRefMATHMathSciNet

16.

Blundo, C., De Santis, A., Stinson, D.R., Vaccaro, U.: Graph decomposition and secret sharing schemes. J. Cryptology 8(1), 39–64 (1995)CrossRefMATHMathSciNet

17.

Brickell, E.F.: Some ideal secret sharing schemes. J. Comb. Math. Comb. Comput. 6, 105–113 (1989)MATHMathSciNet

18.

Brickell, E.F., Davenport, D.M.: On the classification of ideal secret sharing schemes. J. Cryptology 4(73), 123–134 (1991)MATH

19.

Bublitz, S.: Decomposition of graphs and monotone formula size of homogeneous functions. Acta Inf. 23(6), 689–696 (1986)CrossRefMATHMathSciNet

20.

Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. Cryptology 6(3), 157–168 (1993)CrossRefMATH

21.

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 11–19 (1988)

22.

Chor, B., Kushilevitz, E.: Secret sharing over infinite domains. J. Cryptology 6(2), 87–96 (1993)CrossRefMATHMathSciNet

23.

Cramer, R., Damgård, I., Maurer, U.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_22 CrossRef

24.

Csirmaz, L.: The dealer’s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar. 32(3–4), 429–437 (1996)MATHMathSciNet

25.

Csirmaz, L.: The size of a share must be large. J. Cryptology 10(4), 223–231 (1997)CrossRefMATHMathSciNet

26.

Csirmaz, L.: Secret sharing schemes on graphs. Technical Report 2005/059, Cryptology ePrint Archive (2005). eprint.iacr.org/

27.

Desmedt, Y., Frankel, Y.: Shared generation of authenticators and signatures. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 457–469. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_37

28.

Dijk, M.V., Jackson, W., Martin, K.M.: A note on duality in linear secret sharing schemes. Bull. Inst. Comb. Appl. 19, 98–101 (1997)MATHMathSciNet

29.

Erdös, P., Pyber, L.: Covering a graph by complete bipartite graphs. Discrete Math. 170(1–3), 249–251 (1997)CrossRefMATHMathSciNet

30.

Fehr, S.: Efficient construction of the dual span program (1999). Manuscript

31.

Gál, A.: Combinatorial methods in boolean function complexity. Ph.D. thesis, University of Chicago (1995). www.eccc.uni-trier.de/eccc-local/ECCC-Theses/gal.html

32.

Gay, R., Kerenidis, I., Wee, H.: Communication complexity of conditional disclosure of secrets and attribute-based encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 485–502. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_24 CrossRef

33.

Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci. 60(3), 592–629 (2000)CrossRefMATHMathSciNet

34.

Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, pp. 89–98 (2006)

35.

Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proceedings of the IEEE Global Telecommunication Conference, Globecom, vol. 87, pp. 99–102 (1987). Journal version: multiple assignment scheme for sharing secret. J. Cryptology 6(1), 15–20 (1993)

36.

Jackson, W., Martin, K.M.: Geometric secret sharing schemes and their duals. Des. Codes Crypt. 4, 83–95 (1994)CrossRefMATHMathSciNet

37.

Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the 8th IEEE Structure in Complexity Theory, pp. 102–111 (1993)

38.

Liu, T., Vaikuntanathan, V., Wee, H.: Conditional disclosure of secrets via non-linear reconstruction. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 758–790. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_25 CrossRef

39.

Mintz, Y.: Information ratios of graph secret-sharing schemes. Master’s thesis, Department of Computer Science, Ben Gurion University (2012)

40.

Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)CrossRefMATH

41.

Naor, M., Wool, A.: Access control and signatures via quorum secret sharing. In: 3rd ACM Conference on Computer and Communications Security, pp. 157–167 (1996)

42.

Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_27 CrossRef

43.

Shamir, A.: How to share a secret. Commun. ACM 22, 612–613 (1979)CrossRefMATHMathSciNet

44.

Shankar, B., Srinathan, K., Rangan, C.P.: Alternative protocols for generalized oblivious transfer. In: Rao, S., Chatterjee, M., Jayanti, P., Murthy, C.S.R., Saha, S.K. (eds.) ICDCN 2008. LNCS, vol. 4904, pp. 304–309. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77444-0_31 CrossRef

45.

Stinson, D.R.: Decomposition construction for secret sharing schemes. IEEE Trans. Inf. Theory 40(1), 118–125 (1994)CrossRefMATHMathSciNet

46.

Sun, H., Shieh, S.: Secret sharing in graph-based prohibited structures. In: Proceedings IEEE INFOCOM 1997, pp. 718–724 (1997)

47.

Tassa, T.: Generalized oblivious transfer by secret sharing. Des. Codes Crypt. 58(1), 11–21 (2011)CrossRefMATHMathSciNet

48.

Waters, B.: Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_4 CrossRef

49.

Wee, H.: Dual system encryption via predicate encodings. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 616–637. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_26 CrossRef

Titel: Linear Secret-Sharing Schemes for Forbidden Graph Access Structures
verfasst von: Amos Beimel
Oriol Farràs
Yuval Mintz
Naty Peter
Verlag: Springer International Publishing
Buch: Theory of Cryptography
Print ISBN: 978-3-319-70502-6

Electronic ISBN: 978-3-319-70503-3

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-70503-3_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"