Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Correlation-robust hashing, two-party computation, provable security

Original Publication (with major differences): IACR-ASIACRYPT-2021

Date: received 20 Jan 2022

Contact author: yulong chen at kuleuven be, tessaro at cs washington edu

Available format(s): PDF | BibTeX Citation

Version: 20220123:125716 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]