CryptoDB
Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given a encoding key for a function $f$, a hash on $x$ together with a (small) input encoding allow one to recover $f(x)$. TDHs are a versatile tool and a useful building block for more complex cryptographic protocols. In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate $\epsilon = O(\log^{1+\beta} n / n)$ for $\beta>0$, i.e., in the so-called low-noise regime. The construction achieves $2^{\Theta(\log^{1-\beta} \lambda)}$ compression factor. As an application, we obtain private-information retrieval (PIR) with communication complexity $L / 2^{\Theta(\log^{1-\beta} L)}$, for a database of size L. This is the first PIR scheme with non-trivial communication complexity (asymptotically smaller than $L$) from any code-based assumption. |
BibTeX
@inproceedings{tcc-2025-36259,
title={Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN},
publisher={Springer-Verlag},
author={Damiano Abram and Giulio Malavolta and Lawrence Roy},
year=2025
}