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.ITC.2020.16
URN: urn:nbn:de:0030-drops-121216
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12121/
Go to the corresponding LIPIcs Volume Portal

Blocki, Jeremiah ; Kulkarni, Shubhang ; Zhou, Samson

On Locally Decodable Codes in Resource Bounded Channels

pdf-format:
LIPIcs-ITC-2020-16.pdf (0.8 MB)

Abstract

Constructions of locally decodable codes (LDCs) have one of two undesirable properties: low rate or high locality (polynomial in the length of the message). In settings where the encoder/decoder have already exchanged cryptographic keys and the channel is a probabilistic polynomial time (PPT) algorithm, it is possible to circumvent these barriers and design LDCs with constant rate and small locality. However, the assumption that the encoder/decoder have exchanged cryptographic keys is often prohibitive. We thus consider the problem of designing explicit and efficient LDCs in settings where the channel is slightly more constrained than the encoder/decoder with respect to some resource e.g., space or (sequential) time. Given an explicit function f that the channel cannot compute, we show how the encoder can transmit a random secret key to the local decoder using f(⋅) and a random oracle ?(⋅). We then bootstrap the private key LDC construction of Ostrovsky, Pandey and Sahai (ICALP, 2007), thereby answering an open question posed by Guruswami and Smith (FOCS 2010) of whether such bootstrapping techniques are applicable to LDCs in channel models weaker than just PPT algorithms. Specifically, in the random oracle model we show how to construct explicit constant rate LDCs with locality of polylog in the security parameter against various resource constrained channels.

BibTeX - Entry

@InProceedings{blocki_et_al:LIPIcs:2020:12121,
  author =	{Jeremiah Blocki and Shubhang Kulkarni and Samson Zhou},
  title =	{{On Locally Decodable Codes in Resource Bounded Channels}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12121},
  URN =		{urn:nbn:de:0030-drops-121216},
  doi =		{10.4230/LIPIcs.ITC.2020.16},
  annote =	{Keywords: Locally Decodable Codes, Resource Bounded Channels}
}

Keywords: Locally Decodable Codes, Resource Bounded Channels
Collection: 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Issue Date: 2020
Date of publication: 04.06.2020

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