Cited By
View all- Lin JFeng LWang JQiu FYu BCheng JYao S(2024)FGDB‐MLPPIET Communications10.1049/cmu2.1273718:4(309-321)Online publication date: 7-Mar-2024
Partial Secret Sharing Schemes
Pages 5364 - 5385
Abstract
The following standard relaxations of perfect security for secret sharing schemes (SSSs) exist in the literature: <italic>quasi-perfect</italic>, <italic>almost-perfect</italic>, and <italic>statistical</italic>. Understanding the power of these relaxations on the efficiency of SSSs, measured via a parameter called <italic>information ratio</italic>, is a long-standing open problem. In this article, we introduce and study an extremely relaxed security notion, called <italic>partial security</italic>, for which it is only required that any qualified set gains strictly more information about the secret than any unqualified one. To get a meaningful efficiency measure, we normalize the (standard) information ratio of such schemes by an appropriate parameter and refer to the new measure as <italic>partial information ratio</italic>. We present three main results in this paper. <italic>First</italic>, we prove that partial and perfect information ratios coincide for the class of linear SSSs. <italic>Second</italic>, we prove that for the general (i.e., non-linear) class of SSSs, partial and statistical information ratios are equal. <italic>Third</italic>, we show that partial and almost-perfect information ratios do not coincide for the class of mixed-linear schemes (i.e., schemes constructed by combining linear schemes with different underlying finite fields). We also use the notion of partial secret sharing to strengthen and unify the previous <italic>decomposition</italic> theorems for constructing SSSs.
References
[1]
A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, 1979. 10.1145/359168.359176.
[2]
G. R. Blakley, “Safeguarding cryptographic keys,” in Proc. Nat. Comput. Conf., vol. 48, Jun. 1979, pp. 313–317.
[3]
M. Ito, A. Saito, and T. Nishizeki, “Secret sharing scheme realizing general access structure,” Electron. Commun. Jpn., vol. 72, no. 9, pp. 56–64, 1989.
[4]
E. F. Brickell and D. R. Stinson, “Some improved bounds on the information rate of perfect secret sharing schemes,” J. Cryptol., vol. 5, no. 3, pp. 153–166, Oct. 1992.
[5]
C. Blundo, A. D. Santis, D. R. Stinson, and U. Vaccaro, “Graph decompositions and secret sharing schemes,” in Proc. Workshop Theory Appl. Cryptograph. Techn., Balatonfüred, Hungary, May 1992, pp. 1–24. 10.1007/3-540-47555-9_1.
[6]
K. M. Martin, “New secret sharing schemes from old,” J. Combinat. Math. Combinat. Comput., vol. 14, pp. 65–77, 1993.
[7]
A. Jafari and S. Khazaei, “On abelian and homomorphic secret sharing schemes,” J. Cryptol., vol. 34, no. 4, p. 43, 2021. 10.1007/s00145-021-09410-2.
[8]
T. H. Chan and R. W. Yeung, “On a relation between information inequalities and group theory,” IEEE Trans. Inf. Theory, vol. 48, no. 7, pp. 1992–1995, Jul. 2002.
[9]
R. Kaboli, S. Khazaei, and M. Parviz, “On group-characterizability of homomorphic secret sharing schemes,” Theor. Comput. Sci., vol. 891, pp. 116–130, Nov. 2021. 10.1016/j.tcs.2021.08.032.
[10]
A. Beimel and Y. Ishai, “On the power of nonlinear secret-sharing,” in Proc. 16th Annu. IEEE Conf. Comput. Complex., Chicago, IL, USA, Jun. 2001, pp. 188–202. 10.1109/CCC.2001.933886.
[11]
T. Kaced, “Information inequalities are not closed under polymatroid duality,” IEEE Trans. Inf. Theory, vol. 64, no. 6, pp. 4379–4381, Jun. 2018.
[12]
L. Csirmaz, “Secret sharing and duality,” 2019, arXiv:1909.13663.
[13]
T. Kaced, “Secret sharing and algorithmic information theory. (Partage de secret et the’orie algorithmique de l’information),” Ph.D. dissertation, Lab. Comput. Sci., Robot. Microelectron. Montpellier, Univ. Montpellier, CNRS, Montpellier, France, 2012. [Online]. Available: https://tel.archives-ouvertes.fr/tel-00763117
[14]
A. D. Wyner, “The wire-tap channel,” Bell Syst. Tech. J., vol. 54, no. 8, pp. 1355–1387, 1975. 10.1002/j.1538-7305.1975.tb02040.x.
[15]
U. M. Maurer, “Secret key agreement by public discussion from common information,” IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 733–742, May 1993.
[16]
U. M. Maurer, “The strong secret key rate of discrete random triples,” in Communications and Cryptography. Cham, Switzerland: Springer, 1994, pp. 271–285.
[17]
I. Csiszár, “Almost independence and secrecy capacity,” Problemy Peredachi Inf., vol. 32, no. 1, pp. 48–57, 1996.
[18]
I. Csiszár and P. Narayan, “Common randomness and secret key generation with a helper,” IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 344–366, Feb. 2000.
[19]
U. M. Maurer and S. Wolf, “Information-theoretic key agreement: From weak to strong secrecy for free,” in Proc. Int. Conf. Theory Appl. Cryptograph. Techn., Bruges, Belgium, May 2000, pp. 351–368. 10.1007/3-540-45539-6_24.
[20]
M. H. Yassaee, M. R. Aref, and A. Gohari, “Achievability proof via output statistics of random binning,” IEEE Trans. Inf. Theory, vol. 60, no. 11, pp. 6760–6786, Nov. 2014.
[21]
H.-M. Sun and B.-L. Chen, “Weighted decomposition construction for perfect secret sharing schemes,” Comput. Math. Appl., vol. 43, nos. 6–7, pp. 877–887, Mar. 2002.
[22]
M. Gharahi and S. Khazaei, “Optimal linear secret sharing schemes for graph access structures on six participants,” Theor. Comput. Sci., vol. 771, pp. 1–8, Jun. 2019. 10.1016/j.tcs.2018.11.007.
[23]
R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro, “On the size of shares for secret sharing schemes,” J. Cryptol., vol. 6, no. 3, pp. 157–167, 1993. 10.1007/BF00198463.
[24]
L. Csirmaz, “The size of a share must be large,” J. Cryptol., vol. 10, no. 4, pp. 223–231, 1997. 10.1007/s001459900029.
[25]
Z. Zhang and R. W. Yeung, “A non-Shannon-type conditional inequality of information quantities,” IEEE Trans. Inf. Theory, vol. 43, no. 6, pp. 1982–1986, Nov. 1997.
[26]
A. Beimel, N. Livne, and C. Padró, “Matroids can be far from ideal secret sharing,” in Proc. 5th Theory Cryptogr. Conf., New York, NY, USA, Mar. 2008, pp. 194–212. 10.1007/978-3-540-78524-8_12.
[27]
O. Farràs, T. Kaced, S. M. Molleví, and C. Padró, “Improving the linear programming technique in the search for lower bounds in secret sharing,” in Proc. 37th Annu. Int. Conf. Theory Appl. Cryptograph. Techn., Tel Aviv, Israel, Apr. 2018, pp. 597–621. 10.1007/978-3-319-78381-9_22.
[28]
E. Gürpinar and A. E. Romashchenko, “How to use undiscovered information inequalities: Direct applications of the copy lemma,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Paris, France, Jul. 2019, pp. 1377–1381. 10.1109/ISIT.2019.8849309.
[29]
W.-A. Jackson and K. M. Martin, “Geometric secret sharing schemes and their duals,” in Designs, Codes and Cryptography, vol. 4, 1994, pp. 83–95. 10.1007/BF01388562.
[30]
O. Farrás, T. B. Hansen, T. Kaced, and C. Padró, “On the information ratio of non-perfect secret sharing schemes,” Algorithmica, vol. 79, no. 4, pp. 987–1013, Dec. 2017.
[31]
A. Beimel and M. K. Franklin, “Weakly-private secret sharing schemes,” in Proc. 4th Theory Cryptography Conf. (TCC), Amsterdam, The Netherlands, Feb. 2007, pp. 253–272. 10.1007/978-3-540-70936-7_14.
[32]
P. D’Arco, R. D. Prisco, A. D. Santis, A. L. P. del Pozo, and U. Vaccaro, “Probabilistic secret sharing,” in Proc. 43rd Int. Symp. Math. Found. Comput. Sci. (MFCS), Aug. 2018, Liverpool, U.K., 2018, p. 64. 10.4230/LIPIcs.MFCS.2018.64.
[33]
I. Csiszár and J. Korner, “Broadcast channels with confidential messages,” IEEE Trans. Inf. Theory, vol. IT-24, no. 3, pp. 339–348, May 1978.
[34]
D. R. Stinson, “Decomposition constructions for secret-sharing schemes,” IEEE Trans. Inf. Theory, vol. 40, no. 1, pp. 118–125, Jan. 1994.
[35]
M. V. Dijk, W.-A. Jackson, and M. K. Martin, “A general decomposition construction for incomplete secret sharing schemes,” Des., Codes Cryptogr., vol. 15, pp. 301–321, Dec. 1998. 10.1023/A:1008381427667.
[36]
L. Lai, Y. Liang, W. Du, and S. Shamai Shitz, “Secret sharing via noisy broadcast channels,” in Proc. IEEE Int. Symp. Inf. Theory, St. Petersburg, Russia, Jul. 2011, pp. 1955–1959. 10.1109/ISIT.2011.6033894.
[37]
S. Zou, Y. Liang, L. Lai, and S. Shamai Shitz, “An information theoretic approach to secret sharing,” IEEE Trans. Inf. Theory, vol. 61, no. 6, pp. 3121–3136, Apr. 2015.
[38]
A. Beimel and N. Livne, “On matroids and non-ideal secret sharing,” in Proc. 3rd Theory Cryptography Conf. (TCC), New York, NY, USA, Mar. 2006, pp. 482–501. 10.1007/11681878_25.
[39]
M. van Dijk, T. Kevenaar, G.-J. Schrijen, and P. Tuyls, “Improved constructions of secret sharing schemes by applying (λ, ω)-decompositions,” Inf. Process. Lett., vol. 99, no. 4, pp. 154–157, 2006. 10.1016/j.ipl.2006.01.016.
[40]
M. Gharahi and M. Hadian Dehkordi, “Perfect secret sharing schemes for graph access structures on six participants,” J. Math. Cryptol., vol. 7, no. 2, pp. 143–146, Jan. 2013.
[41]
M. Gharahi, “On the complexity of perfect secret sharing schemes,” Ph.D. thesis, Persian, Shool Math., Iran Univ. Sci. Technol., Tehran, Iran, 2013.
[42]
M. Gharahi and S. Khazaei, “Reduced access structures with four minimal qualified subsets on six participants,” Adv. Math. Commun., vol. 12, no. 1, pp. 199–214, 2018.
[43]
S. Bahariyan, “A systematic approach for determining the linear CONVEC set of small access structures (in persian),” M.S. thesis, Dept. Math. Sci., Sharif Univ. Technol., Tehran, Iran, 2019.
[44]
M. Van Dijk, “On the information rate of perfect secret sharing schemes,” Designs, Codes Cryptography, vol. 6, no. 2, pp. 143–169, Sep. 1995.
[45]
W.-A. Jackson and K. M. Martin, “Perfect secret sharing schemes on five participants,” Designs, Codes Cryptogr., vol. 9, no. 3, pp. 267–286, 1996.
[46]
B. Applebaum and P. N. Vasudevan, “Placing conditional disclosure of secrets in the communication complexity universe,” in Proc. 10th Innov. Theor. Comput. Sci. Conf. (ITCS), vol. 124, A. Blum, Ed. San Diego, CA, USA: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Jan. 2019, p. 4. 10.4230/LIPIcs.ITCS.2019.4.
[47]
B. Applebaum and O. Nir, “Upslices, downslices, and secret-sharing with complexity of 1.5n,” in Advances in Cryptology- CRYPTO (Lecture Notes in Computer Science), vol. 12827, T. Malkin and C. Peikert, Eds. Cham, Switzerland: Springer, Aug. 2021, pp. 627–655. 10.1007/978-3-030-84252-9_21.
[48]
T. Liu, V. Vaikuntanathan, and H. Wee, “Towards breaking the exponential barrier for general secret sharing,” in Advances in Cryptology—EUROCRYPT (Lecture Notes in Computer Science), vol. 10820, J. B. Nielsen and V. Rijmen, Eds. Tel Aviv, Israel: Springer, May 2018, pp. 567–596. 10.1007/978-3-319-78381-9_21.
[49]
B. Applebaum, A. Beimel, O. Farràs, O. Nir, and N. Peter, “Secret-sharing schemes for general and uniform access structures,” in Advances in Cryptology—EUROCRYPT (Lecture Notes in Computer Science), vol. 11478, Y. Ishai and V. Rijmen, Eds. Darmstadt, Germany: Springer, 2019, pp. 441–471. 10.1007/978-3-030-17659-4_15.
[50]
B. Applebaum, A. Beimel, O. Nir, and N. Peter, “Better secret-sharing via robust conditional disclosure of secrets,” in Proc. Electron. Colloq. Comput. Complex. (ECCC), vol. 27, 2020, p. 8. [Online]. Available: https://eccc.weizmann.ac.il/report/2020/008
[51]
R. Ahlswede and I. Csiszar, “Common randomness in information theory and cryptography. I. Secret sharing,” IEEE Trans. Inf. Theory, vol. 39, no. 4, pp. 1121–1132, Jul. 1993.
[52]
Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci., vol. 60, no. 3, pp. 592–629, 2000. 10.1006/jcss.1999.1689.
[53]
B. Applebaum and B. Arkis, “On the power of amortization in secret sharing: D-uniform secret sharing and CDS with constant information rate,” in Proc. 16th Int. Conf. (TCC), Panaji, India, Nov. 2018, pp. 317–344. 10.1007/978-3-030-03807-6_12.
[54]
A. Beimel, “Secret-sharing schemes: A survey,” in Coding and Cryptology, Qingdao, China, Jun. 2011, pp. 11–46. 10.1007/978-3-642-20901-7_2.
[55]
G. R. Blakley and C. Meadows, “Security of ramp schemes,” in Proc. Workshop Theory Appl. Cryptograph. Techn. Cham, Switzerland: Springer, 1984, pp. 242–268.
[56]
K. Kurosawa, K. Okada, K. Sakano, W. Ogata, and S. Tsujii, “Nonperfect secret sharing schemes and matroids,” in Advances in Cryptology—EUROCRYPT, Lofthus, Norway, May 1993, pp. 126–141. 10.1007/3-540-48285-7_11.
[57]
M. Karchmer and A. Wigderson, “On span programs,” in Proc. 8th Annu. Struct. Complex. Theory Conf., San Diego, CA, USA, May 1993, pp. 102–111. 10.1109/SCT.1993.336536.
[58]
A. Beimel, A. Ben-Efraim, C. Padró, and I. Tyomkin, “Multi-linear secret-sharing schemes,” in Proc. 11th Theory Cryptography Conf. (TCC), San Diego, CA, USA, Feb. 2014, pp. 394–418. 10.1007/978-3-642-54242-8_17.
[59]
D. Hammer, A. Romashchenko, A. Shen, and N. Vereshchagin, “Inequalities for Shannon entropy and Kolmogorov complexity,” J. Comput. Syst. Sci., vol. 60, no. 2, pp. 442–464, 2000. 10.1006/jcss.1999.1677.
[60]
M. Bertilsson and I. Ingemarsson, “A construction of practical secret sharing schemes using linear block codes,” in Proc. Workshop Theory Appl. Cryptograph. Techn., Gold Coast, QLD, Australia, Dec. 1992, pp. 67–79. 10.1007/3-540-57220-1_53.
[61]
T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. Hoboken, NJ, USA: Wiley, 2006.
[62]
I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,” IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3047–3061, Dec. 2004.
[63]
E. F. Brickell and D. M. Davenport, “On the classification of ideal secret sharing schemes,” J. Cryptol., vol. 4, no. 2, pp. 123–134, 1991. 10.1007/BF00196772.
[64]
P. D. Seymour, “On secret-sharing matroids,” J. Comb. Theory B, vol. 56, no. 1, pp. 69–73, 1992. 10.1016/0095-8956(92)90007-K.
[65]
W.-A. Jackson and K. M. Martin, “Combinatorial models for perfect secret sharing schemes,” J. Combinat. Math. Combinat. Comput., vol. 28, pp. 249–266, 1998.
[66]
S. Ho and S. Verdú, “Convexity/concavity of Renyi entropy and α-mutual information,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Hong Kong, Jun. 2015, pp. 745–749. 10.1109/ISIT.2015.7282554.
[67]
M. H. Yassaee, “Almost exact analysis of soft covering lemma via large deviation,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Paris, France, Jul. 2019, pp. 1387–1391. 10.1109/ISIT.2019.8849341.
[68]
A. Beimel and N. Livne, “On matroids and nonideal secret sharing,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2626–2643, Jun. 2008.
[69]
F. Matúš, “Matroid representations by partitions,” Discrete Math., vol. 203, pp. 169–194, May 1999. 10.1016/S0012-365X(99)00004-7.
[70]
F. Matúš, “Two constructions on limits of entropy functions,” IEEE Trans. Inf. Theory, vol. 53, no. 1, pp. 320–330, Jan. 2007.
Recommendations
Secret sharing schemes with partial broadcast channels
In a conventional secret sharing scheme a dealer uses secure point-to-point channels to distribute the shares of a secret to a number of participants. At a later stage an authorised group of participants send their shares through secure point-to-point ...
Efficient (n, t, n) secret sharing schemes
Highlights We propose an efficient (n, t, n)-VSS. We propose a (n, t, n)-MSS. We propose a (n, t, n)-VMSS. All our (n, t, n) SS are unconditionally secure. Recently, Harn and Lin introduced a notion of strong t-consistency of a (t, n) secret sharing ...
Randomness in secret sharing and visual cryptography schemes
Secret sharing schemes allow a secret to be shared among a group of participants so that only qualified subsets of participants can recover the secret. A visual cryptography scheme (VCS) is a special kind of secret sharing scheme in which the secret to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
0018-9448 © 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 August 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025
Other Metrics
Citations
Cited By
View all- Lin JFeng LWang JQiu FYu BCheng JYao S(2024)FGDB‐MLPPIET Communications10.1049/cmu2.1273718:4(309-321)Online publication date: 7-Mar-2024