### Permuted Puzzles and Cryptographic Hardness

Elette Boyle, Justin Holmgren, and Mor Weiss

##### Abstract

A permuted puzzle problem is defined by a pair of distributions $D_0,D_1$ over $S^n$. The problem is to distinguish samples from $D_0,D_1$, where the symbols of each sample are permuted by a single secret permutation $p$ 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 $D_0,D_1$ over $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). 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: 1. 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). 2. 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 $D_0,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. 3. 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2019
Keywords
Cryptographic HardnessSecurity AssumptionsPermuted PuzzlesStatistical QueryLower Bounds
Contact author(s)
mormorweiss @ gmail com
History
2020-03-17: revised
See all versions
Short URL
https://ia.cr/2019/1256

CC BY

BibTeX

@misc{cryptoeprint:2019/1256,
author = {Elette Boyle and Justin Holmgren and Mor Weiss},
title = {Permuted Puzzles and Cryptographic Hardness},
howpublished = {Cryptology ePrint Archive, Paper 2019/1256},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1256}},
url = {https://eprint.iacr.org/2019/1256}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.