Trapdoor Hash Functions and PIR from Low-Noise LPN

Damiano Abram; Giulio Malavolta; Lawrence Roy

Paper 2025/416

Trapdoor Hash Functions and PIR from Low-Noise LPN

Damiano Abram

, Bocconi University

Giulio Malavolta

, Bocconi University

Lawrence Roy

, Aarhus University

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 for , i.e., in the so-called low-noise regime. The construction achieves compression factor. As an application, we obtain a private-information retrieval (PIR) with communication complexity , for a database of size L. This is the first PIR scheme with non-trivial communication complexity (asymptotically smaller than ) from any code-based assumption.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Private Information Retrieval LPN Trapdoor Hashing
Contact author(s): abram damiano @ protonmail com
giulio malavolta @ hotmail it
ldr709 @ gmail com
History: 2025-03-05: approved; 2025-03-04: received; See all versions
Short URL: https://ia.cr/2025/416
License: CC BY

BibTeX

@misc{cryptoeprint:2025/416,
      author = {Damiano Abram and Giulio Malavolta and Lawrence Roy},
      title = {Trapdoor Hash Functions and {PIR} from Low-Noise {LPN}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/416},
      year = {2025},
      url = {https://eprint.iacr.org/2025/416}
}