Permuted puzzles ⇒ SK-DEPIR

Standard model · BIPW17

Statement

Under the permuted-puzzles assumption of BIPW17 — a secretly permuted set of Reed–Muller local-decoding queries is indistinguishable from a uniformly random set of points — there is a secret-key DEPIR: the database is encoded once at polynomial cost, after which the key holder retrieves any bit by reading a sublinear number of encoding positions, and the access pattern hides the index from an observer who sees the encoding but not the key — BIPW17.

Sketch

The database is encoded as a Reed–Muller codeword, the evaluation table of a low-degree multivariate polynomial, with positions permuted by a secret permutation. To fetch a bit, the client reads the positions of a random low-degree curve through the target point and interpolates, so each query is a permuted Reed–Muller decoding set, which the assumption makes indistinguishable from random positions.

Notes

• The assumption family is formalized and studied as permuted puzzles — BHW19.
• An attack breaks the BIPW17 toy conjecture, a simplified variant posed for cryptanalysis, but not the assumption underlying the construction — BHMW21.