Permuted Puzzles and Cryptographic Hardness

Elette Boyle

A {\em permuted puzzle} problem is defined by a pair of distributions D0, D1 over \Sigma^n. The problem is to distinguish samples from D0, D1, where the symbols of each sample are permuted by a single secret permutation \pi of [n].
The conjectured hardness of specific instances of permuted puzzle problems was recently used to obtain the first candidate constructions of Doubly Efficient Private Information Retrieval (DE-PIR) (Boyle et al. & Canetti et al., TCC’17). Roughly, in these works the distributions D0, D1 over F^n are evaluations of either a moderately low-degree polynomial or a random function. While permuted puzzles are a natural and general class of problems, their hardness is still poorly understood.
We initiate a formal investigation of the cryptographic hardness of permuted puzzle problems. Our contributions include:
  1. Rigorous formalizations of the problem class.
  2. Identifying natural examples in which a one-time permutation provably creates cryptographic hardness based on standard assumptions.
  3. Partial lower bound for the DE-PIR puzzle, showing that a version of the problem withstands statistical query attacks.

Joint work with Justin Holmgren and Mor Weiss.