nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

The Communication Complexity of Private Simultaneous Messages, Revisited

verfasst von : Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

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

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC ’94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function \(f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}\) admits a PSM protocol with exponential communication of \(2^{k/2}\) (Beimel et al., TCC ’14), the best known (non-explicit) lower-bound is \(3k-O(1)\) bits. To prove this lower-bound, FKN identified a set of simple requirements, showed that any function that satisfies these requirements is subject to the \(3k-O(1)\) lower-bound, and proved that a random function is likely to satisfy the requirements.

We revisit the FKN lower-bound and prove the following results:

(Counterexample) We construct a function that satisfies the FKN requirements but has a PSM protocol with communication of \(2k+O(1)\) bits, revealing a gap in the FKN proof.

(PSM lower-bounds) We show that, by imposing additional requirements, the FKN argument can be fixed leading to a \(3k-O(\log k)\) lower-bound for a random function. We also get a similar lower-bound for a function that can be computed by a polynomial-size circuit (or even polynomial-time Turing machine under standard complexity-theoretic assumptions). This yields the first non-trivial lower-bound for an explicit Boolean function partially resolving an open problem of Data, Prabhakaran and Prabhakaran (Crypto ’14, IEEE Information Theory ’16). We further extend these results to the setting of imperfect PSM protocols which may have small correctness or privacy error.

(CDS lower-bounds) We show that the original FKN argument applies (as is) to some weak form of PSM protocols which are strongly related to the setting of Conditional Disclosure of Secrets (CDS). This connection yields a simple combinatorial criterion for establishing linear \(\varOmega (k)\)-bit CDS lower-bounds. As a corollary, we settle the complexity of the Inner Product predicate resolving an open problem of Gay, Kerenidis, and Wee (Crypto ’15).

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 More Efficient (Almost) Tightly Secure Structure-Preserving Signatures

Nächstes Kapitel The Complexity of Multiparty PSM Protocols and Related Models

In the FKN terminology such an input (x, y) is referred to as being dangerous.

The constant 2 can be replaced by any constant larger than 1.

It is worth mentioning that the proof of Theorem 4 strongly relies on the explicit combinatorial condition given in Theorem 3 (and we do not know how to obtain it directly from Corollary 1). This illustrates again the importance of relating PSM complexity to other more explicit properties of functions.

Usually, it is assumed that both Alice and Bob hold the secret s. It is not hard to see that this variant and our variant (in which only Alice knows the secret) are equivalent up to at most 1-bit of additional communication.

One may consider imperfect variants of CDS. In this paper we restrict our attention to the (more common) setting of perfect CDS.

This is analogous to the relation between Functional Encryption and Attribute Based Encryption. Indeed, CDS can be viewed as an information-theoretic one-time variant of Attribute Based Encryption.

When \(k-1\) is even, there is a simple deterministic construction: Take \(\mathbf {T}_0\) (resp., \(\mathbf {T}_1\)) to be the upper triangular matrix (resp., lower triangular matrix) whose entries on and above main diagonal (resp., on and below the diagonal) are ones and all other entries are zero. It is not hard to verify that both matrices are non-singular. Also \(\mathbf {T}=\mathbf {T}_0+\mathbf {T}_1\) has a zero diagonal and ones in all other entries and so \(\mathbf {T}\) has full rank if \(k-1\) is even. The same construction can be used when \(k-1\) is odd, at the expense of obtaining a matrix \(\mathbf {T}\) with an almost full rank that has only minor affect on the parameter M obtained in Lemma 1.

We thank the anonymous reviewer for pointing this out.

Aiello, B., Ishai, Y., Reingold, O.: Priced oblivious transfer: how to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_8CrossRef

Applebaum, B.: Garbled circuits as randomized encodings of functions: a primer. Tutorials on the Foundations of Cryptography. ISC, pp. 1–44. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57048-8_1

Applebaum, B., Arkis, B.: Conditional disclosure of secrets and \(d\)-uniform secret sharing with constant information rate. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 24, p. 189 (2017)

Applebaum, B., Arkis, B., Raykov, P., Vasudevan, P.N.: Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 727–757. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_24CrossRef

Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC\({}^{\text{0}}\). In: FOCS, pp. 166–175 (2004)

Applebaum, B., Raykov, P.: From private simultaneous messages to zero-information arthur-merlin protocols and back. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 65–82. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49099-0_3CrossRef

Barak, B., Jinong, S., Vadhan, S.P.: Derandomization in cryptography. SIAM J. Comput. 37(2), 380–400 (2007)MathSciNetCrossRefMATH

Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: STOC, pp. 503–513 (1990)

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). https://doi.org/10.1007/978-3-642-54242-8_14CrossRef

10.

Ben-or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC, pp. 1–10 (1988)

11.

Brickell, E.F., Davenport, D.M.: On the classification of ideal secret sharing schemes. J. Cryptol. 4(2), 123–134 (1991)CrossRefMATH

12.

Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. Cryptol. 6(3), 157–167 (1993)CrossRefMATH

13.

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: STOC, pp. 11–19 (1988)

14.

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

15.

Data, D., Prabhakaran, V.M., Prabhakaran, M.M.: Communication and randomness lower bounds for secure computation. IEEE Trans. Inf. Theor. 62(7), 3901–3929 (2016)MathSciNetCrossRefMATH

16.

Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: STOC, pp. 554–563 (1994)

17.

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). https://doi.org/10.1007/978-3-662-48000-7_24CrossRef

18.

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

19.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC (1987)

20.

Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Juels, A., Wright, R.N., De Capitani di Vimercati, S., (eds.), Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, 30 October–3 November 2006, vol. 1, pp. 89–98. ACM (2006)

21.

Gutfreund, D., Shaltiel, R., Ta-Shma, A.: Uniform hardness versus randomness tradeoffs for arthur-merlin games. Comput. Complex. 12(3–4), 85–130 (2003)MathSciNetMATH

22.

Ishai, Y.: Randomization techniques for secure computation. In: Prabhakaran, M., Sahai, A., (eds), Secure Multi-Party Computation of Cryptology and Information Security Series, vol. 10, pp. 222–248. IOS Press (2013)

23.

Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS (Israel Symposium on Theory of Computing and Systems), pp. 174–184 (1997)

24.

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: FOCS, pp. 294–304 (2000)

25.

Ishai, Y., Wee, H.: Partial garbling schemes and their applications. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 650–662. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43948-7_54

26.

Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)CrossRefMATH

27.

Liu, T., Vaikuntanathan, V., Wee, H.: Conditional disclosure of secrets via non-linear reconstruction. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 758–790. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_25CrossRef

28.

Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. In: FOCS, pp. 71–80 (1999)

29.

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

30.

Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 656–715 (1949)MathSciNetCrossRefMATH

31.

Sun, H.-M., Shieh, S.-P.: Secret sharing in graph-based prohibited structures. In: Proceedings IEEE INFOCOM 1997, The Conference on Computer Communications, Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Driving the Information Revolution, Kobe, Japan, pp. 718–724. IEEE, 7–12 April 1997

32.

Waters, B.: Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_4CrossRef

33.

Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: FOCS, pp. 160–164 (1982)

Titel: The Communication Complexity of Private Simultaneous Messages, Revisited
verfasst von: Benny Applebaum
Thomas Holenstein
Manoj Mishra
Ofer Shayevitz
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2018
Print ISBN: 978-3-319-78374-1

Electronic ISBN: 978-3-319-78375-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78375-8_9

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"

Premium Partner