Paper 2022/080

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

Yu Long Chen and Stefano Tessaro


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 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((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.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2021
Correlation-robust hashingtwo-party computationprovable security
Contact author(s)
yulong chen @ kuleuven be
tessaro @ cs washington edu
2022-01-23: received
Short URL
Creative Commons Attribution


      author = {Yu Long Chen and Stefano Tessaro},
      title = {Better Security-Efficiency Trade-Offs in Permutation-Based Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/080},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.