International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Yu Long Chen , KU Leuven
Stefano Tessaro , University of Washington
DOI: 10.1007/978-3-030-92075-3_10
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
Abstract: We improve upon the security of (tweakable) correlation-robust 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 etal. (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((\sqrt{q} p+q^2)/2^n). Our security proof relies on on the sum-capture 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.
Video from ASIACRYPT 2021
  title={Better Security-Efficiency Trade-Offs in Permutation-Based Two-Party Computation},
  author={Yu Long Chen and Stefano Tessaro},