nach oben

Journal of Cryptology

Erschienen in:

18.07.2016

From Private Simultaneous Messages to Zero-Information Arthur–Merlin Protocols and Back

Erschienen in: Journal of Cryptology | Ausgabe 4/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Göös et al. (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur–Merlin Protocols (\(\mathsf {ZAM}\)). In this model, which can be viewed as a private version of the standard Arthur–Merlin communication complexity game, Alice and Bob are holding a pair of inputs x and y, respectively, and Merlin, the prover, attempts to convince them that some public function f evaluates to 1 on (x, y). In addition to standard completeness and soundness, Göös et al., require a “zero-knowledge” property which asserts that on each yes-input, the distribution of Merlin’s proof leaks no information about the inputs (x, y) to an external observer. In this paper, we relate this new notion to the well-studied model of Private Simultaneous Messages (\(\mathsf {PSM}\)) that was originally suggested by Feige et al. (STOC, 1994). Roughly speaking, we show that the randomness complexity of \(\mathsf {ZAM}\) corresponds to the communication complexity of \(\mathsf {PSM}\) and that the communication complexity of \(\mathsf {ZAM}\) corresponds to the randomness complexity of \(\mathsf {PSM}\). This relation works in both directions where different variants of \(\mathsf {PSM}\) are being used. As a secondary contribution, we reveal new connections between different variants of \(\mathsf {PSM} \) protocols which we believe to be of independent interest. Our results give rise to better \(\mathsf {ZAM}\) protocols based on existing \(\mathsf {PSM}\) protocols, and to better protocols for conditional disclosure of secrets (a variant of \(\mathsf {PSM}\)) from existing \(\mathsf {ZAM} \)s.

Nächster Artikel The Hunting of the SNARK

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

Nur mit Berechtigung zugänglich

The authors of [13] seem to suggest that there is no a-priori obvious connection between the two models. Indeed, they explicitly mention \(\mathsf {PSM}\) as “a different model of private two-party computation, [...] where the best upper and lower bounds are also exponential and linear.”

Essentially, the range of \(F=(F_1,F_2)\) can be partitioned into two equal sets \(S_0\) and \(S_1\) and for every input (x, y) the function \(F_{x,y}(c)\) that maps the randomness c to the transcript (a, b) forms a bijection from the randomness space to the set \(S_{f(x)}\). In the context of randomized encoding, this notion was originally referred to as perfect randomized encoding [1]. See Sect. 4 for formal definitions.

Arithmetic span programs [21] can emulate ABPs with constant overhead, while the converse is known only with polynomial overhead [6]. Hence, the ASP-based CDS subsume, in terms of complexity, the abovementioned ABP-based construction.

Moreover, the ABP-based construction of [18] applies not only to \(\mathsf {CDS}\), but also to a more general notion of partial garbling schemes which can be viewed as an intermediate notion between \(\mathsf {CDS}\) and \(\mathsf {PSM}\).

In the original paper [10], the functions \(F_1,F_2\) are deterministic. We extend this model by allowing Alice and Bob to use local randomness that is assumed to be available freely.

B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in \(\text{NC}{}^{0}\). SIAM J. Comput. 36(4), 845–888 (2006)

B. Applebaum, Y. Ishai, E. Kushilevitz, How to garble arithmetic circuits. SIAM J. Comput. 43(2), 905–929 (2014)

B. Applebaum, Y. Ishai, E. Kushilevitz, Minimizing locality of one-way functions via semi-private randomized encodings. Electron. Colloq. Comput. Complex. (ECCC), 22, 45 (2015)

B. Applebaum, P. Raykov, From private simultaneous messages to zero-information arthur-merlin protocols and back, in E. Kushilevitz, T. Malkin, editors, Theory of Cryptography—13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10–13, 2016, Proceedings, Part II. LNCS, vol. 9563 (Springer, 2016), pp. 65–82. Available as eprint report 2015/1046 at http://eprint.iacr.org/2015/1046.

L. Babai, P. Frankl, J. Simon, Complexity classes in communication complexity theory (preliminary version), in 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986 (IEEE Computer Society, 1986), pp. 337–347

A. Beimel, A. Gál, On arithmetic branching programs. J. Comput. Syst. Sci. 59(2), 195–220 (1999)

A. Beimel, Y. Ishai, R. Kumaresan, E. Kushilevitz, On the cryptographic complexity of the worst functions, in Y. Lindell, editor, Theory of Cryptography—11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24–26, 2014. Proceedings. LNCS, vol. 8349 (Springer, 2014), pp. 317–342

L. Babai, S. Moran, Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254–276 (1988)

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

10.

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

11.

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

12.

R. Gay, I. Kerenidis, H. Wee. Communication complexity of conditional disclosure of secrets and attribute-based encryption, in R. Gennaro, M. Robshaw, editors, Advances in Cryptology - CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2015, Proceedings, Part II. LNCS, vol. 9216 (Springer, 2015), pp. 485–502

13.

M. Göös, T. Pitassi, T. Watson, Zero-information protocols and unambiguity in arthur-merlin communication, in T. Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11–13, 2015 (ACM, 2015), pp. 113–122

14.

Y. Ishai, E. Kushilevitz, Private simultaneous messages protocols with applications, in Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, June (1997), pp. 174–183

15.

Y. Ishai, E. Kushilevitz, 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 (IEEE Computer Society, 2000), pp. 294–304

16.

Y. Ishai, E. Kushilevitz, Perfect constant-round secure computation via perfect randomizing polynomials, in P. Widmayer, F. T. Ruiz, R. M. Bueno, M. Hennessy, S. Eidenbenz, R. Conejo, editors, Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8–13, 2002, Proceedings. LNCS, vol. 2380 (Springer, 2002), pp. 244–256

17.

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

18.

Y. Ishai, H. Wee, Partial garbling schemes and their applications, in J. Esparza, P. Fraigniaud, T. Husfeldt, E. Koutsoupias, editors, Automata, Languages, and Programming—41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014, Proceedings, Part I. LNCS, vol. 8572 (Springer, 2014), pp 650–662

19.

H. Klauck, Rectangle size bounds and threshold covers in communication complexity, in 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7–10 July 2003, Aarhus, Denmark (IEEE Computer Society, 2003), pp. 118–134

20.

H. Klauck, A strong direct product theorem for disjointness, in L. J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010 (ACM, 2010), pp. 77–86

21.

M. Karchmer, A. Wigderson, On span programs, in Proceedings of the Eighth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18–21, 1993 (IEEE Computer Society, 1993), pp. 102–111

22.

P. Pudlák, J. Sgall, Algebraic models of computation and interpolation for algebraic proof systems, in Proof Complexity and Feasible Arithmetic. DIMACS Series in Discrete Mathematics and Theor. Comput. Sci., vol. 39 (Am. Math. Soc., Providence, RI, 1998), pp. 279–296

Titel: From Private Simultaneous Messages to Zero-Information Arthur–Merlin Protocols and Back
Publikationsdatum: 18.07.2016
Erschienen in: Journal of Cryptology / Ausgabe 4/2017
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9239-3

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"

Weitere Artikel der Ausgabe 4/2017

Information Theoretical Cryptogenography

The Hunting of the SNARK

Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation

Efficient Authentication from Hard Learning Problems

Authenticated Confidential Channel Establishment and the Security of TLS-DHE

Reproducible Circularly Secure Bit Encryption: Applications and Realizations