CryptoDB
Randomized Functions with High Round Complexity
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| 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 folklore conjecture asserts that this phenomenon extends to functions with randomized output. Our work falsifies this folklore conjecture -- revealing intricate subtleties even for this elementary security notion. For every $r$, there is 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. This 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. |
BibTeX
@inproceedings{tcc-2023-33603,
title={Randomized Functions with High Round Complexity},
publisher={Springer-Verlag},
author={Saugata Basu and Hamidreza Amini Khorasgani and Hemanta Maji and Hai H. Nguyen},
year=2023
}