Better Security-Efficiency Trade-Offs in Permutation-Based Two-Party Computation

Abstract

We improve upon the security of (tweakable) correlationrobust hash functions, which are essential components of garbling schemes and oblivious-transfer extension schemes. We in particular focus on constructions from permutations, and improve upon the work by Guo et al. (IEEE S&P '20) in terms of security and efficiency. We present a tweakable one-call construction which matches the security of the most secure two-call construction - the resulting security bound takes form O((p + q)q/2(n)), where q is the number of construction evaluations and p is the number of direct adversarial queries to the underlying n-bit permutation, which is modeled as random. Moreover, we present a new two-call construction with much better security degradation - in particular, for applications of interest, where only a constant number of evaluations per tweak are made, the security degrades as O((root qp + q(2))/2(n)). Our security proof relies on the sumcapture theorems (Babai '02; Steinberger '12, Cogliati and Seurin '18), as well as on new balls-into-bins combinatorial lemmas for limited independence ball-throws. Of independent interest, we also provide a self-contained concrete security treatment of oblivious transfer extension.