Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN
摘要
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.