Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On the Bit Security of Cryptographic Primitives Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing

verfasst von : Oriol Farràs, Tarik Kaced, Sebastià Martín, Carles Padró

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.

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 Towards Breaking the Exponential Barrier for General Secret Sharing
Literatur
1.
Ahlswede, R., Körner, J.: On the connection between the entropies of input and output distributions of discrete memoryless channels. In: Proceedings of the 5th Brasov Conference on Probability Theory, Brasov, Editura Academiei, Bucuresti, pp. 13–23 (1977)
2.
Ahlswede, R., Körner, J.: Appendix: on common information and related characteristics of correlated information sources. In: Ahlswede, R., Bäumer, L., Cai, N., Aydinian, H., Blinovsky, V., Deppe, C., Mashurian, H. (eds.) General Theory of Information Transfer and Combinatorics. LNCS, vol. 4123, pp. 664–677. Springer, Heidelberg (2006). https://​doi.​org/​10.​1007/​11889342_​41CrossRef
3.
Babai, L., Gál, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19, 301–319 (1999)MathSciNetCrossRefMATH
4.
5.
6.
7.
8.
Beimel, A., Orlov, I.: Secret sharing and non-Shannon information inequalities. IEEE Trans. Inform. Theory 57, 5634–5649 (2011)MathSciNetCrossRefMATH
9.
Blakley, G.R.: Safeguarding cryptographic keys. In: AFIPS Conference Proceedings, vol. 48, pp. 313–317 (1979)
10.
Blundo, C., De Santis, A., De Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Des. Codes Cryptogr. 11, 107–122 (1997)MathSciNetCrossRefMATH
11.
Brickell, E.F., Davenport, D.M.: On the classification of ideal secret sharing schemes. J. Cryptol. 4, 123–134 (1991)MATH
12.
Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. Cryptol. 6, 157–167 (1993)CrossRefMATH
13.
Chen, B.L., Sun, H.M.: Weighted decomposition construction for perfect secret sharing schemes. Comput. Math. Appl. 43, 877–887 (2002)MathSciNetCrossRefMATH
14.
Csirmaz, L.: The dealer’s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar. 32, 429–437 (1996)MathSciNetMATH
15.
16.
17.
18.
Csirmaz, L., Tardos, G.: Optimal information rate of secret sharing schemes on trees. IEEE Trans. Inf. Theory 59, 2527–2530 (2013)MathSciNetCrossRefMATH
19.
Csiszar, I., Körner, J.: Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, Akademiai Kiado, New York, Budapest (1981)MATH
20.
21.
22.
Dougherty, R., Freiling, C., Zeger, K.: Six new non-Shannon information inequalities. In: 2006 IEEE International Symposium on Information Theory, pp. 233–236 (2006)
23.
24.
25.
Farràs, O., Metcalf-Burton, J.R., Padró, C., Vázquez, L.: On the optimization of bipartite secret sharing schemes. Des. Codes Cryptogr. 63, 255–271 (2012)MathSciNetCrossRefMATH
26.
27.
Fujishige, S.: Entropy functions and polymatroids-combinatorial structures in information theory. Electron. Comm. Japan 61, 14–18 (1978)MathSciNet
28.
Gács, P., Körner, J.: Common information is far less than mutual information. Probl. Control Inf. Theory 2, 149–162 (1973)MathSciNetMATH
29.
Gharahi, M: On the complexity of perfect secret sharing schemes. Ph.D. Thesis, Iran University of Science and Technology (2013) (in Persian)
30.
Gharahi, M., Dehkordi, M.H.: The complexity of the graph access structures on six participants. Des. Codes Cryptogr. 67, 169–173 (2013)MathSciNetCrossRefMATH
31.
Gharahi, M., Dehkordi, M.H.: Average complexities of access structures on five participants. Adv. Math. Commun. 7, 311–317 (2013)MathSciNetCrossRefMATH
32.
Gharahi, M., Dehkordi, M.H: Perfect secret sharing schemes for graph access structures on six participants. J. Math. Cryptol. 7, 143–146 (2013)
33.
Gharahi, M., Khazaei, S.: Optimal linear secret sharing schemes for graph access structures on six participants. Cryptology ePrint Archive: Report 2017/1232 (2017)
34.
Hammer, D., Romashchenko, A.E., Shen, A., Vereshchagin, N.K.: Inequalities for Shannon entropy and Kolmogorov complexity. J. Comput. Syst. Sci. 60, 442–464 (2000)MathSciNetCrossRefMATH
35.
Ingleton, A.W.: Representation of matroids. In: Welsh, D.J.A. (ed.) Combinatorial Mathematics and its Applications, pp. 149–167. Academic Press, London (1971)
36.
37.
Jackson, W.A., Martin, K.M.: Perfect secret sharing schemes on five participants. Des. Codes Cryptogr. 9, 267–286 (1996)MathSciNetMATH
38.
39.
40.
41.
Li, Q., Li, X.X., Lai, X.J., Chen, K.F.: Optimal assignment schemes for general access structures based on linear programming. Des. Codes Cryptogr. 74, 623–644 (2015)MathSciNetCrossRefMATH
42.
Makarychev, K., Makarychev, Y., Romashchenko, A., Vereshchagin, N.: A new class of non-Shannon-type inequalities for entropies. Commun. Inf. Syst. 2, 147–166 (2002)MathSciNetMATH
43.
Martí-Farré, J., Padró, C.: Secret sharing schemes with three or four minimal qualified subsets. Des. Codes Cryptogr. 34, 17–34 (2005)MathSciNetCrossRefMATH
44.
45.
Martí-Farré, J., Padró, C., Vázquez, L.: Optimal complexity of secret sharing schemes with four minimal qualified subsets. Des. Codes Cryptogr. 61, 167–186 (2011)MathSciNetCrossRefMATH
46.
Martín, S., Padró, C., Yang, A.: Secret sharing, rank inequalities, and information inequalities. IEEE Trans. Inform. Theory 62, 599–609 (2016)MathSciNetCrossRefMATH
47.
Matúš, F.: Infinitely many information inequalities. In: Proceedings of the IEEE International Symposium on Information Theory, (ISIT), pp. 2101–2105 (2007)
48.
Metcalf-Burton, J.R.: Improved upper bounds for the information rates of the secret sharing schemes induced by the Vámos matroid. Discret. Math. 311, 651–662 (2011)MathSciNetCrossRefMATH
49.
Oxley, J.G: Matroid Theory. Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (1992)
50.
Padró, C.: Lecture Notes in secret sharing. Cryptology ePrint Archive, Report 2012/674 (2912)
51.
Padró, C., Sáez, G.: Secret sharing schemes with bipartite access structure. IEEE Trans. Inform. Theory 46, 2596–2604 (2000)MathSciNetCrossRefMATH
52.
Padró, C., Vázquez, L., Yang, A.: Finding lower bounds on the complexity of secret sharing schemes by linear programming. Discret. Appl. Math. 161, 1072–1084 (2013)MathSciNetCrossRefMATH
53.
Pitassi T., Robere R., Lifting Nullstellensatz to Monotone Span Programs over any Field. Electronic Colloquium on Computational Complexity (ECCC), vol. 165 (2017)
54.
55.
Robere, R., Pitassi, T., Rossman, B., Cook, S.A.: Exponential lower bounds for monotone span programs. In: FOCS 2016, pp. 406–415 (2016)
56.
57.
58.
59.
60.
61.
Thakor, S., Chan, T., Grant, A.: Capacity bounds for networks with correlated sources and characterisation of distributions by entropies. IEEE Trans. Inf. Theory 63, 3540–3553 (2017)MathSciNetCrossRefMATH
62.
63.
Yeung, R.W.: A First Course in Information Theory. Kluwer Academic/Plenum Publishers, New York (2002)CrossRef
64.
Yeung, R.W.: Information Theory and Network Coding. Springer, Boston (2008)MATH
65.
Zhang, Z.: On a new non-Shannon type information inequality. Commun. Inf. Syst. 3, 47–60 (2003)MathSciNetMATH
66.
Zhang, Z., Yeung, R.W.: On characterization of entropy function via information inequalities. IEEE Trans. Inf. Theory 44, 1440–1452 (1998)MathSciNetCrossRefMATH
Metadaten
Titel
Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing
verfasst von
Oriol Farràs
Tarik Kaced
Sebastià Martín
Carles Padró
Copyright-Jahr
2018
Buch
Advances in Cryptology – EUROCRYPT 2018

Print ISBN: 978-3-319-78380-2

Electronic ISBN: 978-3-319-78381-9

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-78381-9_22

Premium Partner

    Bildnachweise