International Association
for Cryptologic Research

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.