You are looking at a specific version 20220123:125716 of this paper. See the latest version.

Paper 2022/080

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

Yu Long Chen and Stefano Tessaro

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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2021
Keywords
Correlation-robust hashingtwo-party computationprovable security
Contact author(s)
yulong chen @ kuleuven be
tessaro @ cs washington edu
History
2022-01-23: received
Short URL
https://ia.cr/2022/080
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.