Enhanced Trapdoor Hashing from DDH and DCR

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) = i 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.

Equipped with our enhanced TDH scheme, we revisit numerous applications of TDH. In all cases, we obtain significant improvements in terms of compactness and/or underlying assumptions. We also introduce new applications enabled by the larger class of function handled by our scheme. We provide informal corollaries and discuss how our new results compare to the state of the art below; the list of results is non-exhaustive.

Batch OT with optimal rate. A batch oblivious transfer with optimal rate is a two-message protocol for computing n independent copies of a 1-out-of-2 bit oblivious transfer where for sufficiently large n, the size of each message is n • (1 + o(1)), matching asymptotically the information-theoretic lower bound of n bits per party. We show the following:

Corollary 1. Assuming the DDH assumption, there exists a batch oblivious transfer with optimal rate and semi-honest statistical sender privacy.

This improves over the results of [BBDP22] that required the LPN assumption in addition to DDH, and over the result of [BGI17] that assumes only DDH but achieves total communication (4+o(1))•n, require a PKI setup, and does not achieve semi-honest statistical sender privacy. For the simpler task of download-rate-1 string OT, where the sender has two length-n message (m 0 , m 1 ) and the receiver with selection bit b receives m b , we achieve receiver-to-sender communication sublinear in n: Corollary 2. Assuming the DDH assumption, there exists a 1-out-of-2 2-message string oblivious transfer for strings of length n with semi-honest statistical sender privacy, where the receiver sends poly(λ)•n 2/3 = o(n) bits, and the sender sends back n+poly(λ)•n 2/3 = n•(1+o(1)) bits. Furthermore, after a single string OT, the sender and the receiver can execute any additional number of string OTs with identical sender-to-receiver communication (n + poly(λ) • n 2/3 = n • (1 + o(1)) bits) but receiver-to-sender communication reduced to a single bit.

This improves significantly over the result of [DGI + 19] under DDH, where the receiver-tosender communication scales as λ • n 2 (for each string OT), over the result of [GHO20] that relies on the power-DDH assumption and where the receiver-to-sender communication scales as λ • n (for each string OT), and over the result of [CGH + 21] which achieves amortized string OT with O(λ) amortized receiver-to-sender communication assuming the SXDH assumption over pairing groups.

Eventually, when assuming DCR instead of DDH, we get a stronger flavor of rate-1 batch-OT where, after a one-time simultaneous broadcast of o(n)-bit strings (where the sender message depends on her inputs, but the receiver message is independent of her selection bits), allows performing an arbitrary number of OTs on-the-fly with fully optimal communication: Corollary 3. Assuming the DCR assumption, there exists a batch oblivious transfer protocol with semi-