[CIMR25] Secret-Key PIR from Random Linear Codes

Authors: Caicai Chen, Yuval Ishai, Tamer Mour, Alon Rosen | Venue: preprint | Source

Abstract

Private information retrieval (PIR) allows to privately read a chosen bit from an $N$-bit database $x$ with $o(N)$ bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing $x$ into an encoded database $x^{\prime }$, it suffices to access only $\mathrm{polylog}(N)$ bits of $x^{\prime }$ per query. This requires $|x^{\prime }|\ge N\cdot \mathrm{polylog}(N)$, and prohibitively large server circuit size.

We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding $x^{\prime }$ depends on a client’s short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with $O(N^{ϵ})$ communication, for any constant $ϵ>0$, from the Learning Parity with Noise assumption in a parameter regime not known to imply public-key encryption. This is evidence against public-key encryption being necessary for sk-PIR.

Under a new conjecture related to the hardness of learning a hidden linear subspace of ${\mathbb{F}}_2^n$ with noise, we construct sk-PIR with similar communication and encoding size $|x^{\prime }|=(1+ϵ)\cdot N$ in which the server is implemented by a Boolean circuit of size $(4+ϵ)\cdot N$. This is the first candidate PIR scheme with such a circuit complexity.

Notes

They conjecture hardness of the Learning Subspace with Noise (LSN) problem of DKL09 in a new regime ($k\ge \rho n$, $\mu \ge 1-o(1)$). They show how to build secret-key PIR from both LPN and LSN.

• Unlike SK-PIR, which bounds only communication, the secret-key DEPIR of BIPW17 also makes per-query server work sublinear; see Permuted puzzles ⇒ SK-DEPIR.

How is SK-PIR different from preprocessing PIR?

• The secret key is independent of the PIR database
• So, first sk is generated → then used to encode a database $x$
• But only the sk is given to decoding
• Idea (unverified): preprocess the database and store the client state encrypted on the server, then run a two-round protocol whose first round downloads the encrypted state. This moves the state but not the server’s work: the result is SK-DEPIR only if the underlying scheme already has $o(n)$ server computation, and per-query communication is at least $|\mathsf{st}|$ unless amortised.

Circuit Sizes

• The paper focuses on minimizing the communication and circuit size, rather than the sublinear runtime in the RAM/cell-probe model
  • Although, some of their constructions also achieve this

Learning Subspace with Noise (LSN)

The learning subspace with noise assumption $(k,n,\mu )$-LSN asserts that for a uniformly random secret rank-$k$ matrix $\mathbf{C}\in {\mathbb{F}}^{k\times n}$ and any polynomial number of samples $m:=m(\lambda )$, it holds that

$$({\mathbf{c}}_1+{\mathbf{e}}_1,\dots ,{\mathbf{c}}_m+{\mathbf{e}}_m){\approx }_c({\mathbf{u}}_1,\dots ,{\mathbf{u}}_m),$$

where ${\mathbf{c}}_i={\mathbf{a}}_i^T\mathbf{C}$ for ${\mathbf{a}}_i\stackrel{\$}{\leftarrow }{\mathbb{F}}^k$, and ${\mathbf{e}}_i$ is uniform in ${\mathbb{F}}^n$ with probability $\mu$ and $0$ otherwise.

About $(1-\mu )m$ samples lie in the row space of $\mathbf{C}$, hidden among about $\mu m$ uniform vectors.

Conjecture: For every $0<\rho <1$, the $(k,n,\mu )$-LSN assumption holds when $k\ge \rho n$ and $\mu \ge 1-o(1)$.

• So basically, all but a small fraction of the samples are random

LSN facts

1. If $\mu <1-(k/n{)}^d$, there is a $n^{O(d)}$-time LSN distinguisher
2. For a constant code rate $\rho =k/n$ and $\eta =1-\mu =o(1)$, $(k,n,\mu )$-LSN implies LPN with code dimension $k$, code length $k(1+\Omega (\eta ))$, and noise rate $\eta$
3. LPN with noise rate $\epsilon$ implies a variant of LSN with the following noise pattern: Let $I$ be a random set of $k$ linearly independent columns of $\mathbf{C}$. Then, for each sampled codeword ${\mathbf{c}}_i$, flip each bit outside $I$ with $\epsilon$ probability.
4. CDV21 showed that when $n=k+1$, the search version of the LSN assumption of ${\mathbb{F}}_2$ is equivalent to the standard LPN assumption with noise rate $\mu /2$

Split LSN

BibTeX

Copy

@Misc{EPRINT:CIMR25,
  author = {Caicai Chen and Yuval Ishai and Tamer Mour and Alon Rosen},
  title = {Secret-Key {PIR} from Random Linear Codes},
  year = {2025},
  url = {https://eprint.iacr.org/2025/646},
  howpublished = {Cryptology ePrint Archive, Report 2025/646},
}