Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given an 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 $\varepsilon = O(\log ^{1+\beta } n / n)$ for $\beta >0$ , i.e., in the so-called low-noise regime. The construction achieves $2^{\varTheta (\log ^{1-\beta } \lambda )}$ compression factor. As an application, we obtain private-information retrieval (PIR) with communication complexity $L / 2^{\varTheta (\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.Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given an 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 $$\varepsilon = O(\log ^{1+\beta } n / n)$$ for $$\beta >0$$ , i.e., in the so-called low-noise regime. The construction achieves $$2^{\varTheta (\log ^{1-\beta } \lambda )}$$ compression factor. As an application, we obtain private-information retrieval (PIR) with communication complexity $$L / 2^{\varTheta (\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.

Lecture notes in computer scienceDec 1, 20251 citation

STRONGER SECURITY NOTIONS FOR TRAPDOOR FUNCTIONS AND APPLICATIONS

Phyllis O’Neill

Jan 1, 20100 citations

All-But-Many Lossy Trapdoor Functions from Lattices and Applications

Xavier Boyen, Qinyi Li

Lecture notes in computer scienceJan 1, 201731 citations

\varepsilon = O(\log ^{1+\beta } n / n)

for

\beta >0

, i.e., in the so-called low-noise regime. The construction achieves

2^{\varTheta (\log ^{1-\beta } \lambda )}

compression factor. As an application, we obtain private-information retrieval (PIR) with communication complexity

L / 2^{\varTheta (\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.