Efficient Range-Trapdoor Functions and Applications: Rate-1 OT and More

Substantial work on trapdoor functions (TDFs) has led to many powerful notions and applications. However, despite tremendous work and progress, all known constructions have prohibitively large public keys. In this work, we introduce new techniques for realizing so-called range-trapdoor hash functions with short public keys. This notion, introduced by Döttling et al. [Crypto 2019], allows for encoding a range of indices into a public key in a way that the public key leaks no information about the range, yet an associated trapdoor enables recovery of the corresponding input part. We give constructions of range-trapdoor hash functions, where for a given range I the public key consists of O(n) group elements, improving upon O(n|I|) achieved by Döttling et al. Moreover, by designing our evaluation algorithm in a special way involving Toeplitz matrix multiplication and by showing how to perform fast-Fourier transforms in the exponent, we arrive at $$O(n \log n)$$ group operations for evaluation, improving upon $$O(n^2)$$ , required of previous constructions. Our constructions rely on power-DDH assumptions in pairing-free groups. As applications of our results we obtain