×

Quadratic secret sharing and conditional disclosure of secrets. (English) Zbl 1489.94116

Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12827, 748-778 (2021).
Summary: There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes for arbitrary \(n\)-party access structures, and consistent with our current knowledge the optimal share size can be anywhere between polynomial in \(n\) and exponential in \(n\). For linear secret-sharing schemes, we know that the share size for almost all \(n\)-party access structures must be exponential in \(n\). Furthermore, most constructions of efficient secret-sharing schemes are linear. We would like to study larger classes of secret-sharing schemes with two goals. On one hand, we want to prove lower bounds for larger classes of secret-sharing schemes, possibly shedding some light on the share size of general secret-sharing schemes. On the other hand, we want to construct efficient secret-sharing schemes for access structures that do not have efficient linear secret-sharing schemes. Given this motivation, A. Paskin-Cherniavsky and A. Radune [“On polynomial secret sharing schemes”, LIPIcs – Leibniz Int. Proc. Inform 163, 12:1–12:21 (2020; doi:10.4230/LIPIcs.ITC.2020.12)] defined and studied a new class of secret-sharing schemes in which the shares are generated by applying degree-\(d\) polynomials to the secret and some random field elements. The special case \(d=1\) corresponds to linear and multi-linear secret-sharing schemes.
We define and study two additional classes of polynomial secret-sharing schemes: (1) schemes in which for every authorized set the reconstruction of the secret is done using polynomials and (2) schemes in which both sharing and reconstruction are done by polynomials. For linear secret-sharing schemes, schemes with linear sharing and schemes with linear reconstruction are equivalent. We give evidence that for polynomial secret-sharing schemes, schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction. We also prove lower bounds on the share size for schemes with polynomial reconstruction. On the positive side, we provide constructions of secret-sharing schemes and conditional disclosure of secrets (CDS) protocols with quadratic sharing and reconstruction. We extend a construction of T. Liu et al. [Lect. Notes Comput. Sci. 10820, 567–596 (2018; Zbl 1423.94131)] and construct optimal quadratic \(k\)-server CDS protocols for functions \(f:[N]^k\mapsto\{0,1\}\) with message size \(O(N^{(k-1)/3})\). We show how to transform our quadratic \(k\)-server CDS protocol to a robust CDS protocol, and use the robust CDS protocol to construct quadratic secret-sharing schemes for arbitrary access structures with share size \(O(2^{0.705n})\); this is better than the best known share size of \(O(2^{0.7576n})\) for linear secret-sharing schemes and worse than the best known share size of \(O(2^{0.585n})\) for general secret-sharing schemes.
For the entire collection see [Zbl 1484.94002].

MSC:

94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography

Citations:

Zbl 1423.94131
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aiello, W.; Ishai, Y.; Reingold, O.; Pfitzmann, B., Priced oblivious transfer: how to sell digital goods, Advances in Cryptology — EUROCRYPT 2001, 119-135 (2001), Heidelberg: Springer, Heidelberg · Zbl 0981.94042 · doi:10.1007/3-540-44987-6_8
[2] Applebaum, B., Arkis, B.: On the power of amortization in secret sharing: d-uniform secret sharing and CDS with constant information rate. ACM Trans. Comput. Theor. 12(4), 24:1-24:21 (2020) · Zbl 1495.94077
[3] Applebaum, B.; Arkis, B.; Raykov, P.; Vasudevan, PN, Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations, SIAM J. Comput., 50, 1, 32-67 (2021) · Zbl 1459.94156 · doi:10.1137/18M1217097
[4] Applebaum, B.; Beimel, A.; Farràs, O.; Nir, O.; Peter, N.; Ishai, Y.; Rijmen, V., Secret-sharing schemes for general and uniform access structures, Advances in Cryptology - EUROCRYPT 2019, 441-471 (2019), Cham: Springer, Cham · Zbl 1509.94149 · doi:10.1007/978-3-030-17659-4_15
[5] Applebaum, B.; Beimel, A.; Nir, O.; Peter, N., Better secret sharing via robust conditional disclosure of secrets, STOC, 2020, 280-293 (2020) · Zbl 07298248 · doi:10.1145/3357713.3384293
[6] Applebaum, B., Beimel, A., Nir, O., Peter, N.: Better secret sharing via robust conditional disclosure of secrets. Cryptology ePrint Archive, Report 2020/080 (2020) · Zbl 07298248
[7] Applebaum, B.; Holenstein, T.; Mishra, M.; Shayevitz, O.; Nielsen, JB; Rijmen, V., The communication complexity of private simultaneous messages, revisited, Advances in Cryptology - EUROCRYPT 2018, 261-286 (2018), Cham: Springer, Cham · Zbl 1428.94054 · doi:10.1007/978-3-319-78375-8_9
[8] Applebaum, B., Nir, O.: Upslices, downslices, and secret-sharing with complexity of \(1.5^{\text{n}} \). IACR Cryptol. ePrint Arch. 2021, 470 (2021). https://eprint.iacr.org/2021/470. To appear in CRYPTO 2021
[9] Applebaum, B., Vasudevan, P.N.: Placing conditional disclosure of secrets in the communication complexity universe. In: 10th ITCS, pp. 4:1-4:14 (2019) · Zbl 1467.94026
[10] Attrapadung, N.; Nguyen, PQ; Oswald, E., Dual system encryption via doubly selective security: framework, fully secure functional encryption for regular languages, and more, Advances in Cryptology - EUROCRYPT 2014, 557-577 (2014), Heidelberg: Springer, Heidelberg · Zbl 1327.94028 · doi:10.1007/978-3-642-55220-5_31
[11] Babai, L.; Gál, A.; Wigderson, A., Superpolynomial lower bounds for monotone span programs, Combinatorica, 19, 3, 301-319 (1999) · Zbl 0990.68077 · doi:10.1007/s004930050058
[12] Beimel, A.: Secure schemes for secret sharing and key distribution. Ph.D. thesis, Technion (1996). www.cs.bgu.ac.il/ beimel/pub.html
[13] Beimel, A.; Chee, YM, Secret-sharing schemes: a survey, Coding and Cryptology, 11-46 (2011), Heidelberg: Springer, Heidelberg · Zbl 1272.94074 · doi:10.1007/978-3-642-20901-7_2
[14] Beimel, A.; Farràs, O.; Pass, R.; Pietrzak, K., The share size of secret-sharing schemes for almost all access structures and graphs, Theory of Cryptography, 499-529 (2020), Cham: Springer, Cham · Zbl 1485.94130 · doi:10.1007/978-3-030-64381-2_18
[15] Beimel, A.; Gál, A.; Paterson, M., Lower bounds for monotone span programs, Comput. Complex., 6, 1, 29-45 (1997) · Zbl 0870.68072 · doi:10.1007/BF01202040
[16] Beimel, A.; Ishai, Y., On the power of nonlinear secret-sharing, SIAM J. Discrete Math., 19, 1, 258-280 (2005) · Zbl 1086.94020 · doi:10.1137/S0895480102412868
[17] Beimel, A., Othman, H., Peter, N.: Quadratic secret sharing and conditional disclosure of secrets. Cryptology ePrint Archive, Report 2021/285 (2021). https://eprint.iacr.org/2021/285
[18] Beimel, A.; Peter, N.; Peyrin, T.; Galbraith, S., Optimal linear multiparty conditional disclosure of secrets protocols, Advances in Cryptology - ASIACRYPT 2018, 332-362 (2018), Cham: Springer, Cham · Zbl 1447.94059 · doi:10.1007/978-3-030-03332-3_13
[19] Benaloh, J.; Leichter, J.; Goldwasser, S., Generalized secret sharing and monotone functions, Advances in Cryptology — CRYPTO’ 88, 27-35 (1990), New York: Springer, New York · Zbl 0715.94003 · doi:10.1007/0-387-34799-2_3
[20] Bertilsson, M.; Ingemarsson, I.; Seberry, J.; Zheng, Y., A construction of practical secret sharing schemes using linear block codes, Advances in Cryptology — AUSCRYPT ’92, 67-79 (1993), Heidelberg: Springer, Heidelberg · Zbl 0869.94012 · doi:10.1007/3-540-57220-1_53
[21] Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the 1979 AFIPS National Computer Conference, vol. 48, pp. 313-317 (1979)
[22] Brickell, EF, Some ideal secret sharing schemes, J. Combin. Math. Combin. Comput., 6, 105-113 (1989) · Zbl 0685.94003
[23] Csirmaz, L., The dealer’s random bits in perfect secret sharing schemes, Studia Sci. Math. Hungar., 32, 3-4, 429-437 (1996) · Zbl 0880.05025
[24] Csirmaz, L., The size of a share must be large, J. Cryptol., 10, 4, 223-231 (1997) · Zbl 0897.94012 · doi:10.1007/s001459900029
[25] Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation. In: 26th STOC, pp. 554-563 (1994) · Zbl 1344.68030
[26] Gál, A., A characterization of span program size and improved lower bounds for monotone span programs, Comput. Complex., 10, 4, 277-296 (2002) · Zbl 1039.68051 · doi:10.1007/s000370100001
[27] Gál, A.; Pudlák, P., Monotone complexity and the rank of matrices, Inf. Process. Lett., 87, 321-326 (2003) · Zbl 1175.68189 · doi:10.1016/S0020-0190(03)00334-X
[28] Gay, R.; Kerenidis, I.; Wee, H.; Gennaro, R.; Robshaw, M., Communication complexity of conditional disclosure of secrets and attribute-based encryption, Advances in Cryptology - CRYPTO 2015, 485-502 (2015), Heidelberg: Springer, Heidelberg · Zbl 1369.94536 · doi:10.1007/978-3-662-48000-7_24
[29] Gertner, Y.; Ishai, Y.; Kushilevitz, E.; Malkin, T., Protecting data privacy in private information retrieval schemes, JCSS, 60, 3, 592-629 (2000) · Zbl 0958.68059
[30] Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: 5th Israel Symposium on Theory of Computing and Systems, pp. 174-183 (1997)
[31] Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Globecom, vol. 87, pp. 99-102 (1987). Journal version: Multiple assignment scheme for sharing secret. J. Cryptol. 6(1), 15-20 (1993) · Zbl 0795.68070
[32] Karchmer, M., Wigderson, A.: On span programs. In: 8th Structure in Complexity Theory, pp. 102-111 (1993)
[33] Korshunov, AD, On the number of monotone Boolean functions, Probl. Kibern, 38, 5-108 (1981) · Zbl 0521.94018
[34] Larsen, KG; Simkin, M.; Galdi, C.; Kolesnikov, V., Secret sharing lower bound: either reconstruction is hard or shares are long, Security and Cryptography for Networks, 566-578 (2020), Cham: Springer, Cham · Zbl 1506.94082 · doi:10.1007/978-3-030-57990-6_28
[35] Liu, T., Vaikuntanathan, V.: Breaking the circuit-size barrier in secret sharing. In: 50th STOC, pp. 699-708 (2018) · Zbl 1428.94108
[36] Liu, T.; Vaikuntanathan, V.; Wee, H.; Katz, J.; Shacham, H., Conditional disclosure of secrets via non-linear reconstruction, Advances in Cryptology - CRYPTO 2017, 758-790 (2017), Cham: Springer, Cham · Zbl 1407.94140 · doi:10.1007/978-3-319-63688-7_25
[37] Liu, T.; Vaikuntanathan, V.; Wee, H.; Nielsen, JB; Rijmen, V., Towards breaking the exponential barrier for general secret sharing, Advances in Cryptology - EUROCRYPT 2018, 567-596 (2018), Cham: Springer, Cham · Zbl 1423.94131 · doi:10.1007/978-3-319-78381-9_21
[38] Paskin-Cherniavsky, A., Radune, A.: On polynomial secret sharing schemes. In: ITC 2020. LIPIcs, vol. 163, pp. 12:1-12:21 (2020) · Zbl 1525.94049
[39] Peter, N.: Secret-sharing schemes and conditional disclosure of secrets protocols. Thesis at Ben-Gurion Universiy (2020). https://aranne5.bgu.ac.il/others/PeterNaty19903.pdf
[40] Pitassi, T., Robere, R.: Strongly exponential lower bounds for monotone computation. In: 49th STOC, pp. 1246-1255 (2017) · Zbl 1370.68111
[41] Pitassi, T., Robere, R.: Lifting Nullstellensatz to monotone span programs over any field. In: 50th STOC, pp. 1207-1219 (2018) · Zbl 1428.68152
[42] Robere, R., Pitassi, T., Rossman, B., Cook, S.A.: Exponential lower bounds for monotone span programs. In: 57th FOCS, pp. 406-415 (2016)
[43] Shamir, A., How to share a secret, Commun. ACM, 22, 612-613 (1979) · Zbl 0414.94021 · doi:10.1145/359168.359176
[44] Vaikuntanathan, V.; Vasudevan, PN; Iwata, T.; Cheon, JH, Secret sharing and statistical zero knowledge, Advances in Cryptology - ASIACRYPT 2015, 656-680 (2015), Heidelberg: Springer, Heidelberg · Zbl 1380.94128 · doi:10.1007/978-3-662-48797-6_27
[45] Wee, H.; Lindell, Y., Dual system encryption via predicate encodings, Theory of Cryptography, 616-637 (2014), Heidelberg: Springer, Heidelberg · Zbl 1326.94120 · doi:10.1007/978-3-642-54242-8_26
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.