×

Secret-sharing schemes for very dense graphs. (English) Zbl 1355.94047

Summary: 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\) vertices contains \((\frac {n}{ 2}) -n^{1+\beta}\) edges for some constant \(0 \leq \beta <1\), then there is a scheme realizing the graph with total share size of \(\tilde{O}(n^{5/4+3\beta /4})\). This should be compared to \(O(n^2/\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\)-homogeneous access structures for a constant \(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})\) for a graph with \((\frac {n}{ 2}) -n^{1+\beta}\) edges.
A preliminary version appeared in Crypto 2012 [Lect. Notes Comput. Sci. 7417, 144-161 (2012; Zbl 1296.94079)].

MSC:

94A62 Authentication, digital signatures and secret sharing
05C42 Density (toughness, etc.)

Citations:

Zbl 1296.94079
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] N. Alon. Covering graphs by the minimum number of equivalence relations. Combinatorica, 6(3):201-206, 1986. · Zbl 0646.05053
[2] N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, 3rd edition, 2008. · Zbl 1148.05001
[3] L. Babai, A. Gál, and A. Wigderson. Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301-319, 1999. · Zbl 0990.68077
[4] A. Beimel. Secret-sharing schemes: A survey. In IWCC 2011, volume 6639 of Lecture Notes in Computer Science, pages 11-46, 2011. · Zbl 1272.94074
[5] A. Beimel and B. Chor. Universally ideal secret sharing schemes. IEEE Trans. on Information Theory, 40(3):786-794, 1994. · Zbl 0821.94025
[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. · Zbl 0870.68072
[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. · Zbl 1326.94072
[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.
[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. · Zbl 0715.94003
[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.
[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. · Zbl 1359.68062
[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. · Zbl 0878.94050
[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. · Zbl 0873.94012
[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. · Zbl 0816.94013
[15] E. F. Brickell. Some ideal secret sharing schemes. Journal of Combin. Math. and Combin. Comput., 6:105-113, 1989. · Zbl 0685.94003
[16] E. F. Brickell and D. M. Davenport. On the classification of ideal secret sharing schemes. J. of Cryptology, 4(73):123-134, 1991. · Zbl 0747.94010
[17] S. Bublitz. Decomposition of graphs and monotone formula size of homogeneous functions. Acta Informatica, 23:689-696, 1986. · Zbl 0585.05031
[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. · Zbl 0786.68030
[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.
[20] B. Chor and E. Kushilevitz. Secret sharing over infinite domains. J. of Cryptology, 6(2):87-96, 1993. · Zbl 0774.94003
[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. · Zbl 1082.94515
[22] G. Di Crescenzo and C. Galdi. Hypergraph decomposition and secret sharing. Discrete Applied Mathematics, 157(5):928-946, 2009. · Zbl 1163.94430
[23] L. Csirmaz. The size of a share must be large. J. of Cryptology, 10(4):223-231, 1997. · Zbl 0897.94012
[24] L. Csirmaz. Secret sharing schemes on graphs. Technical Report 2005/059, Cryptology ePrint Archive, 2005. eprint.iacr.org/. · Zbl 1164.94008
[25] L. Csirmaz. An impossibility result on graph secret sharing. Designs, Codes and Cryptography, 53(3):195-209, 2009. · Zbl 1180.94051 · doi:10.1007/s10623-009-9304-0
[26] L. Csirmaz, P. Ligeti, and G. Tardos. Erdös-pyber theorem for hypergraphs and secret sharing. Graphs and Combinatorics, 2014. · Zbl 1321.05282
[27] L. Csirmaz and G. Tardos. Secret sharing on trees: problem solved. IACR Cryptology ePrint Archive, 2009:71, 2009. · Zbl 1364.94576
[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. · Zbl 0789.68048
[29] M. van Dijk. On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography, 6:143-169, 1995. · Zbl 0829.94006
[30] P. Erdös and L. Pyber. Covering a graph by complete bipartite graphs. Discrete Mathematics, 170(1-3):249-251, 1997. · Zbl 0876.05080
[31] O. Farràs, J. Martí-Farré, and C. Padró. Ideal multipartite secret sharing schemes. J. of Cryptology, 25(1):434-463, 2012. · Zbl 1272.94078
[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. · Zbl 1028.68048
[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. · Zbl 1175.68189
[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.
[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. · Zbl 0795.68070
[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. · Zbl 0833.60070
[37] S. Jukna. On set intersection representations of graphs. Journal of Graph Theory, 61:55-75, 2009. · Zbl 1211.05086 · doi:10.1002/jgt.20367
[38] M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th IEEE Structure in Complexity Theory, pages 102-111, 1993.
[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. · Zbl 0503.94018
[40] J. Kilian and N. Nisan. Private communication, 1990.
[41] J. Martí-Farré and C. Padró. Secret sharing schemes on sparse homogeneous access structures with rank three. Electr. J. Comb., 11(1), 2004. · Zbl 1079.94015
[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. · Zbl 1074.94013
[43] J. Martí-Farré and C. Padró. On secret sharing schemes, matroids and polymatroids. Journal of Mathematical Cryptology, 4(2):95-120, 2010. · Zbl 1201.94111
[44] Y. Mintz. Information ratios of graph secret-sharing schemes. Master’s thesis, Dept. of Computer Science, Ben Gurion University, 2012.
[45] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005. · Zbl 1092.60001
[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.
[47] C. Padró and G. Sáez. Secret sharing schemes with bipartite access structure. IEEE Trans. on Information Theory, 46:2596-2605, 2000. · Zbl 0999.94031
[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. · Zbl 1043.94017
[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. · Zbl 0935.82010
[50] A. Shamir. How to share a secret. Communications of the ACM, 22:612-613, 1979. · Zbl 0414.94021
[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. · Zbl 1131.68336
[52] G. J. Simmons, W. Jackson, and K. M. Martin. The geometry of shared secret schemes. Bulletin of the ICA, 1:71-88, 1991. · Zbl 0826.94018
[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. · Zbl 0809.94010
[54] D. R. Stinson. Decomposition construction for secret sharing schemes. IEEE Trans. on Information Theory, 40(1):118-125, 1994. · Zbl 0803.94017
[55] H. Sun and S. Shieh. Secret sharing in graph-based prohibited structures. In INFOCOM ’97, pages 718-724, 1997.
[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. · Zbl 1213.94137
[57] T. Tassa. Generalized oblivious transfer by secret sharing. Des. Codes Cryptography, 58(1):11-21, 2011. · Zbl 1220.94051
[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. · Zbl 1291.94165
[59] I. Wegener. The Complexity of Boolean Functions. Wiley-Teubner, 1987. · Zbl 0623.94018
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.