CryptoDB
Enhanced Trapdoor Hashing from DDH and DCR
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | We introduce improved constructions of trapdoor hash (TDH) schemes under either DDH or DCR. Compared with the original construction of (Döttling et al., Crypto 2019), our new schemes are more expressive and feature more compact encoding keys. Expressivity: Our TDH scheme allows computing arbitrary functions of the form f(x,y) = ∑ᵢf_i(x) . g_i(y), where f_i, g_i are logarithmic-depth functions. This improves over the original construction that was restricted to computing the inner product between x and y. Compactness: Our TDH scheme has encoding keys of length |y|.(1+o(1)), shaving an Ω(λ) factor compared to the original construction. Equipped with our new scheme, we revisit numerous applications of TDH and construct various low-communication cryptographic primitives that improve over the state of the art, including: - Rate-1 batch OT with semi-honest statistical sender privacy from DDH. Previously, it was only known under DDH+LPN (even without semi-honest statistical sender privacy). As a consequence of our rate-1 batch OT, we also obtain rate-1 lossy trapdoor functions with public keys of size o(n) from DDH. - Optimal preprocessing PIR from DCR, where after a single broadcast of o(n) bits, a server with a size-n database and a client can execute any number of PIR queries adaptively with fully optimal communication (upload communication exactly log(n), download communication exactly 1). Previously, such communication features were not known, even under strong cryptographic assumptions. - Rate-1/2 PSI and fuzzy PSI from DCR, where after a single broadcast of o(n) bits, a server with a size-n database and a client can execute any number of (fuzzy) membership queries with upload and download communication exactly log(n). Previously, such communication features were not known, even under strong cryptographic assumptions. - Secure 2-party computation of layered circuit with one-sided statistical security and communication sublinear in both the circuit size and the largest input, from DCR. Previously, similar results were only known from FHE. |
BibTeX
@inproceedings{eurocrypt-2025-35088,
title={Enhanced Trapdoor Hashing from DDH and DCR},
publisher={Springer-Verlag},
author={Geoffroy Couteau and Aditya Hegde and Sihang Pu},
year=2025
}