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.
H. H. Nguyen—This work was done while the author was at Purdue.
Basu was partially supported by NSF grants CCF-1910441 and CCF-2128702. Khorasgani, Maji, and Nguyen are supported in part by an NSF CRII Award CNS–1566499, NSF SMALL Awards CNS–1618822 and CNS–2055605, the IARPA HECTOR project, MITRE Innovation Program Academic Cybersecurity Research Awards (2019–2020, 2020–2021), a Ross-Lynn Research Scholars Grant, a Purdue Research Foundation (PRF) Award, and The Center for Science of Information, an NSF Science and Technology Center, Cooperative Agreement CCF–0939370.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 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\}\).
References
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
Basu, S., Khorashgani, H.A., Maji, H.K., Nguyen, H.H.: Geometry of secure two-party computation (2022). https://www.cs.purdue.edu/homes/hmaji/papers/BKMN22.pdf. Accessed 15 Feb 2023
Basu, S., Kummer, M., Netzer, T., Vinzan, C.: New directions in real algebraic geometry. https://publications.mfo.de/bitstream/handle/mfo/4031/OWR_2023_15.pdf?sequence=-1 &isAllowed=y
Beaver, D.: Perfect privacy for two-party protocols. In: Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, vol. 2, pp. 65–77 (1991)
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)
Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03549-4_20
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)
Chor, B., Kushilevitz, E.: A zero-one law for Boolean privacy (extended abstract). In: 21st ACM STOC, pp. 62–72. ACM Press, May 1989
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)
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)
Data, D., Prabhakaran, M.: Towards characterizing securely computable two-party randomized functions. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10769, pp. 675–697. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76578-5_23
De Lellis, C., Székelyhidi Jr., L.: The Euler equations as a differential inclusion. Ann. Math. 1417–1436 (2009)
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
Hitruhin, L., Lindberg, S.: Lamination convex hull of stationary incompressible porous media equations. SIAM J. Math. Anal. 53(1), 491–508 (2021)
Kilian, J.: More general completeness theorems for secure two-party computation. In: 32nd ACM STOC, pp. 316–324. ACM Press, May 2000
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)
Kushilevitz, E.: Privacy and communication complexity. In: 30th FOCS, pp. 416–421. IEEE Computer Society Press, October/November 1989
Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Basu, S., Khorasgani, H.A., Maji, H.K., Nguyen, H.H. (2023). Randomized Functions with High Round Complexity. In: Rothblum, G., Wee, H. (eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14369. Springer, Cham. https://doi.org/10.1007/978-3-031-48615-9_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-48615-9_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-48614-2
Online ISBN: 978-3-031-48615-9
eBook Packages: Computer ScienceComputer Science (R0)