Document Open Access Logo

On Locally Decodable Codes in Resource Bounded Channels

Authors Jeremiah Blocki , Shubhang Kulkarni , Samson Zhou

PDF
Thumbnail PDF

File

LIPIcs.ITC.2020.16.pdf
  • Filesize: 0.8 MB
  • 23 pages

Document Identifiers

Author Details

Jeremiah Blocki
  • Purdue University, West Lafayette, IN, USA
Shubhang Kulkarni
  • Purdue University, West Lafayette, IN, USA
Samson Zhou
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

This research was supported in part by the National Science Foundation (CCF Award #1910659).

Acknowledgements

We would like to thank anonymous reviewers for helpful feedback that improved the presentation of this paper.

Cite AsGet BibTex

Jeremiah Blocki, Shubhang Kulkarni, and Samson Zhou. On Locally Decodable Codes in Resource Bounded Channels. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITC.2020.16

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Locally Decodable Codes
  • Resource Bounded Channels

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Joël Alwen and Jeremiah Blocki. Efficiently computing data-independent memory-hard functions. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 241-271, Santa Barbara, CA, USA, August 14-18 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-53008-5_9.
  2. Joël Alwen, Jeremiah Blocki, and Ben Harsha. Practical graphs for optimal side-channel resistant memory-hard functions. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017: 24th Conference on Computer and Communications Security, pages 1001-1017, Dallas, TX, USA, October 31 - November 2 2017. ACM Press. URL: https://doi.org/10.1145/3133956.3134031.
  3. Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Depth-robust graphs and their cumulative memory complexity. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017, Part III, volume 10212 of Lecture Notes in Computer Science, pages 3-32, Paris, France, April 30 - May 4 2017. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-56617-7_1.
  4. Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained space complexity. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, pages 99-130, Tel Aviv, Israel, April 29 - May 3 2018. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-78375-8_4.
  5. Joël Alwen, Binyi Chen, Krzysztof Pietrzak, Leonid Reyzin, and Stefano Tessaro. Scrypt is maximally memory-hard. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017, Part III, volume 10212 of Lecture Notes in Computer Science, pages 33-62, Paris, France, April 30 - May 4 2017. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-56617-7_2.
  6. Joël Alwen and Vladimir Serbinenko. High parallel complexity graphs and memory-hard functions. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th Annual ACM Symposium on Theory of Computing, pages 595-603, Portland, OR, USA, June 14-17 2015. ACM Press. URL: https://doi.org/10.1145/2746539.2746622.
  7. L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. Bpp has subexponential time simulations unless exptime has publishable proofs. In [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pages 213-219, June 1991. URL: https://doi.org/10.1109/SCT.1991.160263.
  8. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pages 21-31, 1991. URL: https://doi.org/10.1145/103418.103428.
  9. Amos Beimel and Yuval Ishai. Information-theoretic private information retrieval: A unified construction. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, Automata, Languages and Programming, pages 912-926, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. Google Scholar
  10. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust pcps of proximity, shorter pcps, and applications to coding. SIAM J. Comput., 36(4):889-974, 2006. A preliminary version appeared in the Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC). Google Scholar
  11. Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters. Time-lock puzzles from randomized encodings. In Madhu Sudan, editor, ITCS 2016: 7th Conference on Innovations in Theoretical Computer Science, pages 345-356, Cambridge, MA, USA, January 14-16 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2840728.2840745.
  12. Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, and Samson Zhou. Relaxed locally correctable codes in computationally bounded channels. In IEEE International Symposium on Information Theory, ISIT, page (to appear), 2019. Google Scholar
  13. Jeremiah Blocki, Shubhang Kulkarni, and Samson Zhou. On locally decodable codes in resource bounded channels. CoRR, abs/1909.11245, 2019. Google Scholar
  14. Joseph Bonneau and Stuart E. Schechter. Towards reliable storage of 56-bit secrets in human memory. In Kevin Fu and Jaeyeon Jung, editors, USENIX Security 2014: 23rd USENIX Security Symposium, pages 607-623, San Diego, CA, USA, August 20-22 2014. USENIX Association. Google Scholar
  15. Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology - EUROCRYPT '99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, pages 402-414, 1999. Google Scholar
  16. Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval. J. ACM, 45(6):965-981, November 1998. URL: https://doi.org/10.1145/293347.293350.
  17. Bram Cohen and Krzysztof Pietrzak. Simple proofs of sequential work. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, pages 451-467, Tel Aviv, Israel, April 29 - May 3 2018. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-78375-8_15.
  18. A. Deshpande, R. Jain, T. Kavitha, S. V. Lokam, and J. Radhakrishnan. Better lower bounds for locally decodable codes. In Proceedings 17th IEEE Annual Conference on Computational Complexity, pages 184-193, May 2002. URL: https://doi.org/10.1109/CCC.2002.1004354.
  19. Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. SIAM J. Comput., 40(4):1154-1178, 2011. Google Scholar
  20. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM J. Comput., 41(6):1694-1703, 2012. Google Scholar
  21. Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC '91, pages 33-42, New York, NY, USA, 1991. ACM. URL: https://doi.org/10.1145/103418.103429.
  22. Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed locally correctable codes. In 9th Innovations in Theoretical Computer Science Conference, ITCS, pages 27:1-27:11, 2018. Google Scholar
  23. Venkatesan Guruswami and Adam Smith. Optimal rate code constructions for computationally simple channels. J. ACM, 63(4):35:1-35:37, September 2016. URL: https://doi.org/10.1145/2936015.
  24. Brett Hemenway and Rafail Ostrovsky. Public-key locally-decodable codes. In Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Proceedings, pages 126-143, 2008. Google Scholar
  25. Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, and Mary Wootters. Public key locally decodable codes with short keys. In 14th International Workshop, APPROX, and 15th International Workshop, RANDOM, Proceedings, pages 605-615, 2011. Google Scholar
  26. John Hopcroft, Wolfgang Paul, and Leslie Valiant. On time versus space. J. ACM, 24(2):332-337, April 1977. URL: https://doi.org/10.1145/322003.322015.
  27. Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC '00, pages 80-86, New York, NY, USA, 2000. ACM. URL: https://doi.org/10.1145/335305.335315.
  28. Iordanis Kerenidis and Ronald de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci., 69(3):395-420, 2004. Google Scholar
  29. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally correctable and locally testable codes with sub-polynomial query complexity. J. ACM, 64(2):11:1-11:42, 2017. Google Scholar
  30. E. Kushilevitz and R. Ostrovsky. Replication is not needed: single database, computationally-private information retrieval. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 364-373, October 1997. URL: https://doi.org/10.1109/SFCS.1997.646125.
  31. Richard J. Lipton. A new approach to information theory. In STACS 94, pages 699-708, Berlin, Heidelberg, 1994. Google Scholar
  32. Silvio Micali, Chris Peikert, Madhu Sudan, and David A. Wilson. Optimal error correction against computationally bounded noise. In Joe Kilian, editor, Theory of Cryptography, pages 1-16, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  33. Rafail Ostrovsky, Omkant Pandey, and Amit Sahai. Private locally decodable codes. In Automata, Languages and Programming, pages 387-398, 2007. Google Scholar
  34. Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. In Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, STOC '76, pages 149-160, New York, NY, USA, 1976. ACM. URL: https://doi.org/10.1145/800113.803643.
  35. C. Percival. Stronger key derivation via sequential memory-hard functions. In BSDCan 2009, 2009. Google Scholar
  36. Ronald L Rivest, Adi Shamir, and David A Wagner. Time-lock puzzles and timed-release crypto. Technical report, Massachusetts Institute of Technology, USA, 1996. Google Scholar
  37. Ronen Shaltiel and Jad Silbak. Explicit list-decodable codes with optimal rate for computationally bounded channels. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 45:1-45:38, 2016. Google Scholar
  38. Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62(2):236-266, 2001. URL: https://doi.org/10.1006/jcss.2000.1730.
  39. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1):1:1-1:16, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact