Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs Kapitel lesen Erstes Kapitel lesen

2023 | OriginalPaper | Buchkapitel

Randomized Functions with High Round Complexity

verfasst von : Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

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

search-config
loading …

Abstract

Consider two-party secure function evaluation against an honest-but-curious adversary in the information-theoretic plain model. We study the round complexity of securely realizing a given secure function evaluation functionality.
Chor-Kushilevitz-Beaver (1989) proved that the round complexity of securely evaluating a deterministic function depends solely on the cardinality of its domain and range. A natural conjecture asserts that this phenomenon extends to functions with randomized output.
Our work falsifies this conjecture – revealing intricate subtleties even for this elementary security notion. For every r, we construct a function \(f_r\) with binary inputs and five output alphabets that has round complexity r. Previously, such a construction was known using \((r+1)\) output symbols. Our counter-example is optimal – we prove that any securely realizable function with binary inputs and four output alphabets has round complexity at most four.
We work in the geometric framework Basu-Khorasgani-Maji-Nguyen (FOCS–2022) introduced to investigate randomized functions’ round complexity. Our work establishes a connection between secure computation and the lamination hull (geometric object originally motivated by applications in hydrodynamics). Our counterexample constructions are related to the “tartan square” construction in the lamination hull literature.

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 Cryptography from Planted Graphs: Security with Logarithmic-Size Messages
Nächstes Kapitel Towards Topology-Hiding Computation from Oblivious Transfer
Fußnoten
1
Both parties know which party speaks in which round.
 
2
We assume that parties have access to randomness with arbitrary bias; more concretely, consider the Blum-Schub-Smale model of computation [5]. For example, parties can have a random bit that is 1 with probability \(1/\pi \).
 
3
\(\mathcal M _{m \times n }(\mathbb {R})\) denotes the set of all m-by-n matrices with elements in \(\mathbb {R}\).
 
4
We highlight a subtlety. We only need to prove that \(\mathcal S ^{\left( 4\right) } =\mathcal S ^{\left( 5\right) } \). It is inconsequential if they have stabilized even earlier. For example, it may be the case that \(\mathcal S ^{\left( j\right) } =\mathcal S ^{\left( j+1\right) } \) for some \(j\in \{0,1,2,3\}\).
 
Literatur
1.
Basu, S., Khorasgani, H.A., Maji, H.K., Nguyen, H.H.: Geometry of secure two-party computation. In: 63rd FOCS, pp. 1035–1044. IEEE Computer Society Press, October/November 2022
2.
3.
4.
Beaver, D.: Perfect privacy for two-party protocols. In: Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, vol. 2, pp. 65–77 (1991)
5.
Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal machines (1989)
6.
7.
Carathéodory, C.: Über den variabilitätsbereich der fourier’schen konstanten von positiven harmonischen funktionen. Rendiconti Del Circolo Matematico di Palermo (1884–1940), 32(1), 193–217 (1911)
8.
Chor, B., Kushilevitz, E.: A zero-one law for Boolean privacy (extended abstract). In: 21st ACM STOC, pp. 62–72. ACM Press, May 1989
9.
Cordoba, D., Faraco, D., Gancedo, F.: Lack of uniqueness for weak solutions of the incompressible porous media equation. Arch. Ration. Mech. Anal. 200, 725–746 (2011)MathSciNetCrossRefMATH
10.
Córdoba, D., Gancedo, F.: Contour dynamics of incompressible 3-d fluids in a porous medium with different densities. Commun. Math. Phys. 273, 445–471 (2007)MathSciNetCrossRefMATH
11.
12.
De Lellis, C., Székelyhidi Jr., L.: The Euler equations as a differential inclusion. Ann. Math. 1417–1436 (2009)
13.
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218–229. ACM Press, May 1987
14.
Hitruhin, L., Lindberg, S.: Lamination convex hull of stationary incompressible porous media equations. SIAM J. Math. Anal. 53(1), 491–508 (2021)MathSciNetCrossRefMATH
15.
Kilian, J.: More general completeness theorems for secure two-party computation. In: 32nd ACM STOC, pp. 316–324. ACM Press, May 2000
16.
Kolář, J.: Non-compact lamination convex hulls. In: Annales de l’Institut Henri Poincaré C, Analyse non linéaire, vol. 20, pp. 391–403. Elsevier (2003)
17.
Kushilevitz, E.: Privacy and communication complexity. In: 30th FOCS, pp. 416–421. IEEE Computer Society Press, October/November 1989
18.
Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986
Metadaten
Titel
Randomized Functions with High Round Complexity
verfasst von
Saugata Basu
Hamidreza Amini Khorasgani
Hemanta K. Maji
Hai H. Nguyen
Copyright-Jahr
2023
Buch
Theory of Cryptography

Print ISBN: 978-3-031-48614-2

Electronic ISBN: 978-3-031-48615-9

Copyright-Jahr: 2023

DOI
https://doi.org/10.1007/978-3-031-48615-9_12

Premium Partner

    Bildnachweise