CryptoDB
Better Security-Efficiency Trade-Offs in Permutation-Based Two-Party Computation
| Authors: |
|
|---|---|
| Download: | |
| 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
BibTeX
@inproceedings{asiacrypt-2021-31408,
title={Better Security-Efficiency Trade-Offs in Permutation-Based Two-Party Computation},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-92075-3_10},
author={Yu Long Chen and Stefano Tessaro},
year=2021
}