article

Secret-Sharing Schemes for Very Dense Graphs

Authors:

Amos Beimel,

Oriol Farràs,

Yuval MintzAuthors Info & Claims

Journal of Cryptology, Volume 29, Issue 2

Pages 336 - 362

https://doi.org/10.1007/s00145-014-9195-8

Published: 01 April 2016 Publication History

Abstract

A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access structures, there are gaps between the known lower bounds and upper bounds on the share size for graphs. Motivated by the question of what makes a graph "hard" for secret-sharing schemes (that is, they require large shares), we study very dense graphs, that is, graphs whose complement contains few edges. We show that if a graph with $$n$$n vertices contains $$\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }$$n2-n1+β edges for some constant $$0 \le \beta <1$$0≤β<1, then there is a scheme realizing the graph with total share size of $$\tilde{O}(n^{5/4+3\beta /4})$$O~(n5/4+3β/4). This should be compared to $$O(n^2/\log (n))$$O(n2/log(n)), the best upper bound known for the total share size in general graphs. Thus, if a graph is "hard," then the graph and its complement should have many edges. We generalize these results to nearly complete $$k$$k-homogeneous access structures for a constant $$k$$k. To complement our results, we prove lower bounds on the total share size for secret-sharing schemes realizing very dense graphs, e.g., for linear secret-sharing schemes, we prove a lower bound of $$\Omega (n^{1+\beta /2})$$Ω(n1+β/2) for a graph with $$\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }$$n2-n1+β edges.

References

[1]

N. Alon. Covering graphs by the minimum number of equivalence relations. Combinatorica, 6(3):201---206, 1986.

Digital Library

Google Scholar

[2]

N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, 3rd edition, 2008.

Crossref

Google Scholar

[3]

L. Babai, A. Gál, and A. Wigderson. Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301---319, 1999.

Crossref

Google Scholar

[4]

A. Beimel. Secret-sharing schemes: A survey. In IWCC 2011, volume 6639 of Lecture Notes in Computer Science, pages 11---46, 2011.

Digital Library

Google Scholar

[5]

A. Beimel and B. Chor. Universally ideal secret sharing schemes. IEEE Trans. on Information Theory, 40(3):786---794, 1994.

Digital Library

Google Scholar

[6]

A. Beimel, A. Gál, and M. Paterson. Lower bounds for monotone span programs. Computational Complexity, 6(1):29---45, 1997. Conference version: FOCS '95.

Digital Library

Google Scholar

[7]

A. Beimel, Y. Ishai, R. Kumaresan, and E. Kushilevitz. On the cryptographic complexity of the worst functions. In Y. Lindell, editor, Proc. of the Eleventh Theory of Cryptography Conference--- TCC 2014, volume 8349 of Lecture Notes in Computer Science, pages 317---342. Springer-Verlag, 2014.

Crossref

Google Scholar

[8]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non cryptographic fault-tolerant distributed computations. In Proc. of the 20th ACM Symp. on the Theory of Computing, pages 1---10, 1988.

Digital Library

Google Scholar

[9]

J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In S. Goldwasser, editor, Advances in Cryptology --- CRYPTO '88, volume 403 of Lecture Notes in Computer Science, pages 27---35. Springer-Verlag, 1990.

Digital Library

Google Scholar

[10]

G. R. Blakley. Safeguarding cryptographic keys. In R. E. Merwin, J. T. Zanca, and M. Smith, editors, Proc. of the 1979 AFIPS National Computer Conference, volume 48 of AFIPS Conference proceedings, pages 313---317. AFIPS Press, 1979.

Crossref

Google Scholar

[11]

G. R. Blakley and C. Meadows. The security of ramp schemes. In G. R. Blakley and D. Chaum, editors, Advances in Cryptology --- CRYPTO '84, volume 196 of Lecture Notes in Computer Science, pages 242---268. Springer-Verlag, 1985.

Digital Library

Google Scholar

[12]

C. Blundo, A. De Santis, R. de Simone, and U. Vaccaro. Tight bounds on the information rate of secret sharing schemes. Designs, Codes and Cryptography, 11(2):107---122, 1997.

Digital Library

Google Scholar

[13]

C. Blundo, A. De Santis, L. Gargano, and U. Vaccaro. On the information rate of secret sharing schemes. Theoretical Computer Science, 154(2):283---306, 1996.

Digital Library

Google Scholar

[14]

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

Digital Library

Google Scholar

[15]

E. F. Brickell. Some ideal secret sharing schemes. Journal of Combin. Math. and Combin. Comput., 6:105---113, 1989.

Google Scholar

[16]

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

Digital Library

Google Scholar

[17]

S. Bublitz. Decomposition of graphs and monotone formula size of homogeneous functions. Acta Informatica, 23:689---696, 1986.

Digital Library

Google Scholar

[18]

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

Digital Library

Google Scholar

[19]

D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols. In Proc. of the 20th ACM Symp. on the Theory of Computing, pages 11---19, 1988.

Digital Library

Google Scholar

[20]

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

Digital Library

Google Scholar

[21]

R. Cramer, I. Damgård, and U. Maurer. General secure multi-party computation from any linear secret-sharing scheme. In B. Preneel, editor, Advances in Cryptology --- EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 316---334. Springer-Verlag, 2000.

Digital Library

Google Scholar

[22]

G. Di Crescenzo and C. Galdi. Hypergraph decomposition and secret sharing. Discrete Applied Mathematics, 157(5):928---946, 2009.

Digital Library

Google Scholar

[23]

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

Digital Library

Google Scholar

[24]

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

Google Scholar

[25]

L. Csirmaz. An impossibility result on graph secret sharing. Designs, Codes and Cryptography, 53(3):195---209, 2009.

Digital Library

Google Scholar

[26]

L. Csirmaz, P. Ligeti, and G. Tardos. Erdös-pyber theorem for hypergraphs and secret sharing. Graphs and Combinatorics, 2014.

Digital Library

Google Scholar

[27]

L. Csirmaz and G. Tardos. Secret sharing on trees: problem solved. IACR Cryptology ePrint Archive, 2009:71, 2009.

Google Scholar

[28]

Y. Desmedt and Y. Frankel. Shared generation of authenticators and signatures. In J. Feigenbaum, editor, Advances in Cryptology --- CRYPTO '91, volume 576 of Lecture Notes in Computer Science, pages 457---469. Springer-Verlag, 1992.

Digital Library

Google Scholar

[29]

M. van Dijk. On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography, 6:143---169, 1995.

Digital Library

Google Scholar

[30]

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

Digital Library

Google Scholar

[31]

O. Farràs, J. Martí-Farré, and C. Padró. Ideal multipartite secret sharing schemes. J. of Cryptology, 25(1):434---463, 2012.

Digital Library

Google Scholar

[32]

A. Gál. A characterization of span program size and improved lower bounds for monotone span programs. In Proc. of the 30th ACM Symp. on the Theory of Computing, pages 429---437, 1998.

Digital Library

Google Scholar

[33]

A. Gál and P. Pudlák. A note on monotone complexity and the rank of matrices. Inform. Process. Lett., 87:321---326, 2003.

Digital Library

Google Scholar

[34]

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

Digital Library

Google Scholar

[35]

M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structure. In Proc. of the IEEE Global Telecommunication Conf., Globecom 87, pages 99---102, 1987. Journal version: Multiple assignment scheme for sharing secret. J. of Cryptology, 6(1):15---20, 1993.

Digital Library

Google Scholar

[36]

M. Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures & Algorithms, 7:157---166, 1995.

Crossref

Google Scholar

[37]

S. Jukna. On set intersection representations of graphs. Journal of Graph Theory, 61:55---75, 2009.

Digital Library

Google Scholar

[38]

M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th IEEE Structure in Complexity Theory, pages 102---111, 1993.

Crossref

Google Scholar

[39]

E. D. Karnin, J. W. Greene, and M. E. Hellman. On secret sharing systems. IEEE Trans. on Information Theory, 29(1):35---41, 1983.

Digital Library

Google Scholar

[40]

J. Kilian and N. Nisan. Private communication, 1990.

Google Scholar

[41]

J. Martí-Farré and C. Padró. Secret sharing schemes on sparse homogeneous access structures with rank three. Electr. J. Comb., 11(1), 2004.

Google Scholar

[42]

J. Martí-Farré and C. Padró. Secret sharing schemes with three or four minimal qualified subsets. Designs, Codes and Cryptography, 34(1):17---34, 2005.

Digital Library

Google Scholar

[43]

J. Martí-Farré and C. Padró. On secret sharing schemes, matroids and polymatroids. Journal of Mathematical Cryptology, 4(2):95---120, 2010.

Crossref

Google Scholar

[44]

Y. Mintz. Information ratios of graph secret-sharing schemes. Master's thesis, Dept. of Computer Science, Ben Gurion University, 2012.

Google Scholar

[45]

M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.

Crossref

Google Scholar

[46]

M. Naor and A. Wool. Access control and signatures via quorum secret sharing. In 3rd ACM Conf. on Computer and Communications Security, pages 157---167, 1996.

Digital Library

Google Scholar

[47]

C. Padró and G. Sáez. Secret sharing schemes with bipartite access structure. IEEE Trans. on Information Theory, 46:2596---2605, 2000.

Digital Library

Google Scholar

[48]

C. Padró and G. Sáez. Lower bounds on the information rate of secret sharing schemes with homogeneous access structure. Inf. Process. Lett., 83(6):345---351, 2002.

Digital Library

Google Scholar

[49]

J. Salas and A. D. Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Statist. Phys., 86:551---579, 1997.

Crossref

Google Scholar

[50]

A. Shamir. How to share a secret. Communications of the ACM, 22:612---613, 1979.

Digital Library

Google Scholar

[51]

B. Shankar, K. Srinathan, and C. Pandu Rangan. Alternative protocols for generalized oblivious transfer. In Proceedings of the 9th International Conference on Distributed Computing and Networking (ICDCN'08), volume 4904 of Lecture Notes in Computer Science, pages 304---309. Springer-Verlag, 2008.

Digital Library

Google Scholar

[52]

G. J. Simmons, W. Jackson, and K. M. Martin. The geometry of shared secret schemes. Bulletin of the ICA, 1:71---88, 1991.

Google Scholar

[53]

D. R. Stinson. New general lower bounds on the information rate of secret sharing schemes. In E. F. Brickell, editor, Advances in Cryptology --- CRYPTO '92, volume 740 of Lecture Notes in Computer Science, pages 168---182. Springer-Verlag, 1993.

Digital Library

Google Scholar

[54]

D. R. Stinson. Decomposition construction for secret sharing schemes. IEEE Trans. on Information Theory, 40(1):118---125, 1994.

Digital Library

Google Scholar

[55]

H. Sun and S. Shieh. Secret sharing in graph-based prohibited structures. In INFOCOM '97, pages 718---724, 1997.

Digital Library

Google Scholar

[56]

H.-M. Sun, H. Wang, B.-H. Ku, and J. Pieprzyk. Decomposition construction for secret sharing schemes with graph access structures in polynomial time. SIAM J. Discret. Math., 24:617---638, 2010.

Digital Library

Google Scholar

[57]

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

Digital Library

Google Scholar

[58]

B. Waters. Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In Proc. of the 14th International Conference on Practice and Theory in Public Key Cryptography, volume 6571 of Lecture Notes in Computer Science, pages 53---70. Springer-Verlag, 2011.

Digital Library

Google Scholar

[59]

I. Wegener. The Complexity of Boolean Functions. Wiley-Teubner, 1987.

Digital Library

Google Scholar

Cited By

View all

Farràs ORibes-González J(2024)One-Out-of-q OT CombinersIEEE Transactions on Information Theory10.1109/TIT.2023.334029470:4(2984-2998)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3340294
Gyarmati M(2024)Information Ratio of Unicyclic GraphsIEEE Transactions on Information Theory10.1109/TIT.2023.332260170:1(722-734)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3322601
Applebaum BBeimel AIshai YKushilevitz ELiu TVaikuntanathan VSaha BServedio R(2023)Succinct Computational Secret SharingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585127(1553-1566)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585127
Show More Cited By

Index Terms

Secret-Sharing Schemes for Very Dense Graphs

Recommendations

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures
Theory of Cryptography
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 ...
$^{}$ $\overset{}{}^{}$ $(\begin{matrix} \end{matrix})^{}$
$^{}$ $^{}$ $(\begin{matrix} \end{matrix})^{}$ $^{}$
Secret Sharing Schemes for Dense Forbidden Graphs
Proceedings of the 10th International Conference on Security and Cryptography for Networks - Volume 9841

A secret-sharing scheme realizes a given graph if every two vertices connected by an edge can reconstruct the secret and every independent set in the graph does not get any information about the secret. A secret-sharing scheme realizes a forbidden graph ...
Secret Sharing Schemes for Very Dense Graphs
Proceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 7417

A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access ...

Reviews

Reviewer: Zubair Baig

Secret-sharing schemes are common when it comes to distributing a secret among individual participants so as to ascertain that no individual has full knowledge of the secret at any given time. The paper presents an approach for maintaining small share sizes of secrets to ascertain efficiency, through the bridging of the gap that exists between the lower and upper bounds on share sizes. The best bounds on the share sizes are formally defined in the paper, and the significance of reducing the gap between the upper and lower bounds is emphasized. In addition, the correlation between the bounds and the length of a secret is also emphasized. The proposal is specific to "a special family of access structures," namely those with minimal authorized sets of size two, thus enabling representation of such structures through graphs. Through the proposal, the authors have also attempted to identify hard graphs, that is, dense graphs, and subsequently compute the best share size. The study focused on very dense graphs as otherwise a typical graph with edges "can be realized by a trivial secret-sharing scheme" with a total share size equivalent to 2 times the length of the secret. The authors aim to address two particular problems. The first is one where a graph has its edges removed iteratively with the corresponding increase in the share size studied. Second, the authors "study the removal of minimal authorized subsets from k -out-of- n threshold access structures and present a construction" of shares wherein the size of every individual secret is fairly small, that is, k << n . This well-written paper is easy to follow for cryptography enthusiasts and researchers alike. A background in discrete mathematics would be beneficial in gaining thorough insight into the field of secret sharing. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Cryptology Volume 29, Issue 2

April 2016

248 pages

ISSN:0933-2790

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Farràs ORibes-González J(2024)One-Out-of-q OT CombinersIEEE Transactions on Information Theory10.1109/TIT.2023.334029470:4(2984-2998)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3340294
Gyarmati M(2024)Information Ratio of Unicyclic GraphsIEEE Transactions on Information Theory10.1109/TIT.2023.332260170:1(722-734)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3322601
Applebaum BBeimel AIshai YKushilevitz ELiu TVaikuntanathan VSaha BServedio R(2023)Succinct Computational Secret SharingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585127(1553-1566)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585127
Farràs ORibes-González JRicci S(2021)Privacy-preserving data splitting: a combinatorial approachDesigns, Codes and Cryptography10.1007/s10623-021-00884-689:7(1735-1756)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10623-021-00884-6
Applebaum BArkis B(2020)On the Power of Amortization in Secret SharingACM Transactions on Computation Theory10.1145/341775612:4(1-21)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1145/3417756
Gyarmati MLigeti P(2020)Smallest Graphs Achieving the Stinson BoundIEEE Transactions on Information Theory10.1109/TIT.2020.296510266:7(4609-4612)Online publication date: 18-Jun-2020
https://dl.acm.org/doi/10.1109/TIT.2020.2965102
Sun LZhao YSun WLiu Z(2020)Study on supply chain strategy based on cost income model and multi-access edge computing under the background of the Internet of ThingsNeural Computing and Applications10.1007/s00521-019-04125-932:19(15357-15368)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s00521-019-04125-9
Beimel AFarràs O(2020)The Share Size of Secret-Sharing Schemes for Almost All Access Structures and GraphsTheory of Cryptography10.1007/978-3-030-64381-2_18(499-529)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64381-2_18
Farràs ORibes-González JRicci S(2019)Local bounds for the optimal information ratio of secret sharing schemesDesigns, Codes and Cryptography10.1007/s10623-018-0529-787:6(1323-1344)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10623-018-0529-7
Ogiela MOgiela L(2018)Cognitive cryptography techniques for intelligent information managementInternational Journal of Information Management: The Journal for Information Professionals10.1016/j.ijinfomgt.2018.01.01140:C(21-27)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.ijinfomgt.2018.01.011
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

Secret Sharing Schemes for Dense Forbidden Graphs