CryptoDB
Permuted Puzzles and Cryptographic Hardness
| Authors: | |
|---|---|
| Download: | |
| Abstract: | A permuted puzzle problem is defined by a pair of distributions $$\mathcal{D}_0,\mathcal{D}_1$$ over $$\varSigma ^n$$ . The problem is to distinguish samples from $$\mathcal{D}_0,\mathcal{D}_1$$ , 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 $$\mathcal{D}_0,\mathcal{D}_1$$ over $${\mathbb F}^n$$ are evaluations of either a moderately low-degree polynomial or a random function. This new conjecture seems to be quite powerful, and is the foundation for the first DE-PIR candidates, almost two decades after the question was first posed by Beimel et al. (CRYPTO’00). However, 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 lie in three main directions: Rigorous formalization. We formalize a notion of permuted puzzle distinguishing problems, extending and generalizing the proposed permuted puzzle framework of Boyle et al. (TCC’17).Identifying hard permuted puzzles. We identify natural examples in which a one-time permutation provably creates cryptographic hardness, based on “standard” assumptions. In these examples, the original distributions $$\mathcal{D}_0,\mathcal{D}_1$$ are easily distinguishable, but the permuted puzzle distinguishing problem is computationally hard. We provide such constructions in the random oracle model, and in the plain model under the Decisional Diffie-Hellman (DDH) assumption. We additionally observe that the Learning Parity with Noise (LPN) assumption itself can be cast as a permuted puzzle.Partial lower bound for the DE-PIR problem. We make progress towards better understanding the permuted puzzles underlying the DE-PIR constructions, by showing that a toy version of the problem, introduced by Boyle et al. (TCC’17), withstands a rich class of attacks, namely those that distinguish solely via statistical queries. |
BibTeX
@article{tcc-2019-30004,
title={Permuted Puzzles and Cryptographic Hardness},
booktitle={Theory of Cryptography},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11892},
pages={465-493},
doi={10.1007/978-3-030-36033-7_18},
author={Elette Boyle and Justin Holmgren and Mor Weiss},
year=2019
}