Metadata only
Date
2023Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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 ⨍ᵣ 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. Show more
Publication status
publishedExternal links
Book title
Theory of Cryptography: 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 – December 2, 2023, Proceedings, Part IJournal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerEvent
Edition / version
1st editionSubject
Two-party secure computation; Information-theoretic security; Semi-honest adversary; Round complexity; Geometry of secure computation; Generalized convex hull; Lamination hull; HydrodynamicsMore
Show all metadata
ETH Bibliography
yes
Altmetrics