License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.6
URN: urn:nbn:de:0030-drops-116918
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11691/
Go to the corresponding LIPIcs Volume Portal

Bitansky, Nir ; Gerichter, Idan

On the Cryptographic Hardness of Local Search

pdf-format:
LIPIcs-ITCS-2020-6.pdf (0.7 MB)

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 PLS 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 PLS can be traded with a simple incremental completeness property.

BibTeX - Entry

@InProceedings{bitansky_et_al:LIPIcs:2020:11691,
  author =	{Nir Bitansky and Idan Gerichter},
  title =	{{On the Cryptographic Hardness of Local Search}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{6:1--6:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11691},
  URN =		{urn:nbn:de:0030-drops-116918},
  doi =		{10.4230/LIPIcs.ITCS.2020.6},
  annote =	{Keywords: Cryptography, PLS, Lower Bounds, Incremental Computation}
}

Keywords: Cryptography, PLS, Lower Bounds, Incremental Computation
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI