On the Cryptographic Hardness of Local Search

Nir Bitansky; Idan Gerichter

Paper 2020/013

On the Cryptographic Hardness of Local Search

Nir Bitansky and Idan Gerichter

Abstract

We show new hardness results for the class of Polynomial Local Search problems ( $PLS$ ): * Hardness of $PLS$ based on a falsifiable assumption on bilinear groups introduced by Kalai, Paneth, and Yang (STOC 2019), and the Exponential Time Hypothesis for randomized algorithms. Previous standard model constructions relied on non-falsifiable and non-standard assumptions. * Hardness of relative to random oracles. The construction is essentially different than previous constructions, and in particular is unconditionally secure. The construction also demonstrates the hardness of parallelizing local search. The core observation behind the results is that the unique proofs property of incrementally-verifiable computations previously used to demonstrate hardness in can be traded with a simple incremental completeness property.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. ITCS 2020
Keywords: TFNP PLS Lower Bounds Incremental Computation
Contact author(s): idangerichter @ gmail com
History: 2020-01-06: received
Short URL: https://ia.cr/2020/013
License: CC BY

BibTeX

@misc{cryptoeprint:2020/013,
      author = {Nir Bitansky and Idan Gerichter},
      title = {On the Cryptographic Hardness of Local Search},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/013},
      year = {2020},
      url = {https://eprint.iacr.org/2020/013}
}