[AMR25] Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN

Authors: Damiano Abram, Giulio Malavolta, Lawrence Roy | Venue: TCC 2025 | Source

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 (ϵ=O(\log^{1+β}n/n)) for (β>0), i.e., in the so-called low-noise regime. The construction achieves (2^{\Theta(\log^{1-β}λ)}) compression factor. As an application, we obtain a private-information retrieval (PIR) with communication complexity (L/2^{\Theta(\log^{1-β}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

Copy

@Inproceedings{TCC:AbrMalRoy25,
  author = {Damiano Abram and Giulio Malavolta and Lawrence Roy},
  title = {Slightly Sublinear Trapdoor Hash Functions and {PIR} from Low-Noise {LPN}},
  pages = {280--300},
  editor = {Benny Applebaum and Huijia (Rachel) Lin},
  booktitle = {TCC~2025: 23rd Theory of Cryptography Conference, Part~I},
  volume = {16268},
  series = {Lecture Notes in Computer Science},
  address = {Aarhus, Denmark},
  month = {dec~1--5},
  publisher = {Springer, Cham, Switzerland},
  year = {2025},
  doi = {10.1007/978-3-032-12287-2_10},
}