nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Conditional Disclosure of Secrets via Non-linear Reconstruction

verfasst von : Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate.

For general predicates \(\mathsf {P}: [N] \times [N] \rightarrow \{0,1\}\), we present two protocols that achieve \(o(N^{1/2})\) communication: the first achieves \(O(N^{1/3})\) communication and the second achieves sub-polynomial \(2^{O(\sqrt{\log N \log \log N})} = N^{o(1)}\) communication.
As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on N vertices, there is a secret-sharing scheme for N parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in G are connected, and where each party gets a share of size \(2^{O(\sqrt{\log N \log \log N})} = N^{o(1)}\).

Prior to this work, the best protocols for both primitives required communication complexity \(\tilde{O}(N^{1/2})\). Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called “linear reconstruction”. This is the first work to break this \(O(N^{1/2})\) “linear reconstruction” barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval.

We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials.

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 Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-Bounds, and Separations

Nur mit Berechtigung zugänglich

There are two reasons why we work with multi-linear polynomials with the tensor product notation: first, it yields a cleaner and more efficient reduction for \(\mathbf {MPOLY}^{k}_{n_1,\ldots ,n_k} \Rightarrow \mathbf {INDEX}_{n_1 \cdots n_k}\) (saving a factor of k), and second, it is easier to work with for our CDS schemes in Sects. 3.1 and 3.2.

Note that the sums in \(G,G'\) are performed over \(\mathbb Z_3\), whereas the computation in the exponents of \(-1\) are performed over \(\mathbb Z_2\). This means that we will treat elements of \(\mathbb Z_6\) (as used in the matching vector family) as elements of \(\mathbb Z_2\) and \(\mathbb Z_3\).

[AARV17]

Applebaum, B., Arkis, B., Raykov, P., Vasudevan, P.N.: Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations. IACR Cryptology ePrint Archive 2017:164 (2017)

[ACC+14]

Ada, A., Chattopadhyay, A., Cook, S.A., Fontes, L., Koucký, M., Pitassi, T.: The hardness of being private. TOCT 6(1), 1:1–1:24 (2014)MathSciNetCrossRefMATH

[Att14]

Attrapadung, N.: Dual system encryption via doubly selective security: framework, fully secure functional encryption for regular languages, and more. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 557–577. Springer, Heidelberg (2014). doi:10.1007/978-3-642-55220-5_31 CrossRef

[Bei11]

Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20901-7_2 CrossRef

[BFG06]

Beigel, R., Fortnow, L., Gasarch, W.I.: A tight lower bound for restricted pir protocols. Comput. Complex. 15(1), 82–91 (2006)MathSciNetCrossRefMATH

[BGP95]

Beimel, A., Gál, A., Paterson, M.: Lower bounds for monotone span programs. In: FOCS, pp. 674–681 (1995)

[BI01]

Beimel, A., Ishai, Y.: On the power of nonlinear secret-sharing. In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, 18–21 June 2001, pp. 188–202. IEEE Computer Society (2001)

[BIKK14]

Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317–342. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54242-8_14 CrossRef

[BIKO12]

Beimel, A., Ishai, Y., Kushilevitz, E., Orlov, I.: Share conversion and private information retrieval. In: Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, 26–29 June 2012, pp. 258–268. IEEE Computer Society (2012)

[BSGV96]

Blundo, C., De Santis, A., Gargano, L., Vaccaro, U.: On the information rate of secret sharing schemes. Theor. Comput. Sci. 154(2), 283–306 (1996)MathSciNetCrossRefMATH

[BSSV97]

Blundo, C., De Santis, A., De Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Des. Codes Crypt. 11(2), 107–122 (1997)MathSciNetCrossRefMATH

[Bub86]

Bublitz, S.: Decomposition of graphs and monotone formula size of homogeneous functions. Acta Inf. 23(6), 689–696 (1986)MathSciNetCrossRefMATH

[CGW15]

Chen, J., Gay, R., Wee, H.: Improved dual system ABE in prime-order groups via predicate encodings. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 595–624. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46803-6_20

[CK91]

Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy. SIAM J. Discrete Math. 4(1), 36–47 (1991)MathSciNetCrossRefMATH

[CKGS98]

Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965–981 (1998)MathSciNetCrossRefMATH

[Csi97]

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

[Csi05]

Csirmaz, L.: Secret sharing schemes on graphs. IACR Cryptology ePrint Archive 2005:59 (2005)

[DG15]

Dvir, Z., Gopi, S.: 2-server PIR with sub-polynomial communication. In: STOC, pp. 577–584 (2015)

[DGY11]

Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. SIAM J. Comput. 40(4), 1154–1178 (2011)MathSciNetCrossRefMATH

[DPP14]

Data, D., Prabhakaran, M.M., Prabhakaran, V.M.: On the communication complexity of secure computation. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 199–216. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44381-1_12 CrossRef

[Efr09]

Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC, pp. 39–44 (2009)

[EP97]

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

[FKN94]

Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Leighton, F.T., Goodrich, M.T. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23–25 May 1994, Montréal, Québec, Canada, pp. 554–563. ACM (1994)

[GIKM00]

Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci. 60(3), 592–629 (2000)MathSciNetCrossRefMATH

[GKW15]

Gay, R., Kerenidis, I., Wee, H.: Communication complexity of conditional disclosure of secrets and attribute-based encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 485–502. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7_24 CrossRef

[GPSW06]

Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM Conference on Computer and Communications Security, pp. 89–98 (2006)

[Gro00]

Grolmusz, V.: Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica 20(1), 71–86 (2000)MathSciNetCrossRefMATH

[IK97]

Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS, pp. 174–184 (1997)

[IK00]

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12–14 November 2000, Redondo Beach, California, USA, pp. 294–304. IEEE Computer Society (2000)

[IK02]

Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244–256. Springer, Heidelberg (2002). doi:10.1007/3-540-45465-9_22 CrossRef

[ISN89]

Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. Electron. Commun. Jpn (Part III: Fundam. Electron. Sci.) 72(9), 56–64 (1989)MathSciNetCrossRef

[KNR99]

Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Comput. Complex. 8(1), 21–49 (1999)MathSciNetCrossRefMATH

[Lew12]

Lewko, A.: Tools for simulating features of composite order bilinear groups in the prime order setting. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 318–335. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29011-4_20 CrossRef

[LOS+10]

Lewko, A.B., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 62–91. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_4 CrossRef

[LW10]

Lewko, A.B., Waters, B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 455–479. Springer, Heidelberg (2010). doi:10.1007/978-3-642-11799-2_27 CrossRef

[LW11]

Lewko, A.B., Waters, B.: Decentralizing attribute-based encryption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 568–588. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20465-4_31 CrossRef

[Nay99]

Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: FOCS, pp. 369–377 (1999)

[OS08]

Ostrovsky, R., Skeith III, W.E.: Communication complexity in algebraic two-party protocols. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 379–396. Springer, Heidelberg (2008). doi:10.1007/978-3-540-85174-5_21 CrossRef

[OT10]

Okamoto, T., Takashima, K.: Fully secure functional encryption with general relations from the decisional linear assumption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 191–208. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14623-7_11 CrossRef

[OT12]

Okamoto, T., Takashima, K.: Adaptively attribute-hiding (hierarchical) inner product encryption. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 591–608. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29011-4_35. Also, Cryptology ePrint Archive, Report 2011/543CrossRef

[RPRC16]

Robere, R., Pitassi, T., Rossman, B., Cook, S.A.: Exponential lower bounds for monotone span programs. In: FOCS, pp. 406–415 (2016)

[Sha79]

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)MathSciNetCrossRefMATH

[SS97]

Sun, H.-M., Shieh, S.-P.: Secret sharing in graph-based prohibited structures. In: INFOCOM, pp. 718–724 (1997)

[SW05]

Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). doi:10.1007/11426639_27 CrossRef

[vD95]

van Dijk, M.: On the information rate of perfect secret sharing schemes. Des. Codes Crypt. 6(2), 143–169 (1995)MathSciNetCrossRefMATH

[VV15]

Vaikuntanathan, V., Vasudevan, P.N.: Secret sharing and statistical zero knowledge. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 656–680. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48797-6_27 CrossRef

[Wat09]

Waters, B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619–636. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03356-8_36 CrossRef

[Wee14]

Wee, H.: Dual system encryption via predicate encodings. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 616–637. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54242-8_26 CrossRef

[WY05]

Woodruff, D.P., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: CCC, pp. 275–284 (2005)

[Yek08]

Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. J. ACM 55(1), 1:1–1:16 (2008)MathSciNetCrossRefMATH

Titel: Conditional Disclosure of Secrets via Non-linear Reconstruction
verfasst von: Tianren Liu
Vinod Vaikuntanathan
Hoeteck Wee
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2017
Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-63688-7_25

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"