[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes

  • Conference paper
  • First Online:
Security and Cryptography for Networks (SCN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13409))

Included in the following conference series:

Abstract

We formally introduce, define, and construct memory-hard puzzles. Intuitively, for a difficulty parameter t, a cryptographic puzzle is memory-hard if any parallel random access machine (PRAM) algorithm with “small” cumulative memory complexity (\(\ll t^2\)) cannot solve the puzzle; moreover, such puzzles should be both “easy” to generate and be solvable by a sequential RAM algorithm running in time t. Our definitions and constructions of memory-hard puzzles are in the standard model, assuming the existence of indistinguishability obfuscation (\(i\mathcal {O}\)) and one-way functions (OWFs), and additionally assuming the existence of a memory-hard language. Intuitively, a language is memory-hard if it is undecidable by any PRAM algorithm with “small” cumulative memory complexity, while a sequential RAM algorithm running in time t can decide the language. Our definitions and constructions of memory-hard objects are the first such definitions and constructions in the standard model without relying on idealized assumptions (such as random oracles).

We give two applications which highlight the utility of memory-hard puzzles. For our first application, we give a construction of a (one-time) memory-hard function (MHF) in the standard model, using memory-hard puzzles and additionally assuming \(i\mathcal {O}\) and OWFs. For our second application, we show any cryptographic puzzle (e.g., memory-hard, time-lock) can be used to construct resource-bounded locally decodable codes (LDCs) in the standard model, answering an open question of Blocki, Kulkarni, and Zhou (ITC 2020). Resource-bounded LDCs achieve better rate and locality than their classical counterparts under the assumption that the adversarial channel is resource bounded (e.g., a low-depth circuit). Prior constructions of MHFs and resource-bounded LDCs required idealized primitives like random oracles.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Such hash functions generate a hashing key that statistically binds the i-th input bit. For example, a hash output y may have many different preimages, but all preimages have the same i-th bit. Construction of such hash functions exist under standard cryptographic assumptions such as DDH and LWE, among others [78].

  2. 2.

    Our one-time security definition differs from those in prior literature (e.g., [6, 7]), and is, in fact, stronger. See Sect. 2.3 for discussion.

  3. 3.

    In fact, one can provably show that the \(\mathsf {cmc} \) is \(t^{2-\varepsilon }\) in the random oracle model.

  4. 4.

    Informally, a language is non-parallelizing if any polynomial sized circuit deciding the language has large depth.

  5. 5.

    For our purposes, we require the size of the succinct circuit to be poly-logarithmic in the size of the full circuit. One can easily replace this requirement with the requirement presented in Definition 1.

  6. 6.

    In this example, we assume sub-exponentially secure \(i\mathcal {O} \).

References

  1. Agrawal, S., Pellet-Mary, A.: Indistinguishability obfuscation without maps: attacks and fixes for noisy linear FE. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 110–140. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_5

    Chapter  Google Scholar 

  2. Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 241–271. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_9

    Chapter  Google Scholar 

  3. Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: CCS, pp. 1001–1017. ACM (2017)

    Google Scholar 

  4. Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_1

    Chapter  Google Scholar 

  5. Alwen, J., Blocki, J., Pietrzak, K.: Sustained space complexity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 99–130. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_4

    Chapter  Google Scholar 

  6. Alwen, J., Chen, B., Pietrzak, K., Reyzin, L., Tessaro, S.: Scrypt is maximally memory-hard. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 33–62. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_2

    Chapter  Google Scholar 

  7. Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: STOC, pp. 595–603. ACM (2015)

    Google Scholar 

  8. Alwen, J., Tackmann, B.: Moderately hard functions: definition, instantiations, and applications. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 493–526. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_17

    Chapter  Google Scholar 

  9. Ameri, M.H., Block, A.R., Blocki, J.: Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes. IACR Cryptology ePrint Archive, p. 801 (2021)

    Google Scholar 

  10. Ameri, M.H., Blocki, J., Zhou, S.: Computationally data-independent memory hard functions. In: ITCS. LIPIcs, vol. 151, pp. 36:1–36:28. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  11. Applebaum, B.: Garbled circuits as randomized encodings of functions: a primer. In: Tutorials on the Foundations of Cryptography. ISC, pp. 1–44. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57048-8_1

    Chapter  Google Scholar 

  12. Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC\(^{0}\). SIAM J. Comput. 36(4), 845–888 (2006)

    Article  MathSciNet  Google Scholar 

  13. Barak, B., et al.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6:1–6:48 (2012)

    Google Scholar 

  14. Bartusek, J., Ishai, Y., Jain, A., Ma, F., Sahai, A., Zhandry, M.: Affine determinant programs: a framework for obfuscation and witness encryption. In: ITCS. LIPIcs, vol. 151, pp. 82:1–82:39. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  15. Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889–974 (2006)

    Article  MathSciNet  Google Scholar 

  16. Biryukov, A., Dinu, D., Khovratovich, D.: Argon2: new generation of memory-hard functions for password hashing and other applications. In: EuroS &P, pp. 292–302. IEEE (2016)

    Google Scholar 

  17. Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: STOC, pp. 439–448. ACM (2015)

    Google Scholar 

  18. Bitansky, N., Garg, S., Telang, S.: Succinct randomized encodings and their applications. IACR Cryptology ePrint Archive, p. 771 (2014)

    Google Scholar 

  19. Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: ITCS, pp. 345–356. ACM (2016)

    Google Scholar 

  20. Block, A.R., Blocki, J.: Private and resource-bounded locally decodable codes for insertions and deletions. In: ISIT, pp. 1841–1846. IEEE (2021)

    Google Scholar 

  21. Block, A.R., Blocki, J., Grigorescu, E., Kulkarni, S., Zhu, M.: Locally decodable/correctable codes for insertions and deletions. In: FSTTCS. LIPIcs, vol. 182, pp. 16:1–16:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  22. Blocki, J., Cheng, K., Grigorescu, E., Li, X., Zheng, Y., Zhu, M.: Exponential lower bounds for locally decodable and correctable codes for insertions and deletions. In: FOCS, pp. 739–750. IEEE (2021)

    Google Scholar 

  23. Blocki, J., Cinkoske, M., Lee, S., Son, J.Y.: On explicit constructions of extremely depth robust graphs. In: STACS. LIPIcs, vol. 219, pp. 14:1–14:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

    Google Scholar 

  24. Blocki, J., Gandikota, V., Grigorescu, E., Zhou, S.: Relaxed locally correctable codes in computationally bounded channels. IEEE Trans. Inf. Theory 67(7), 4338–4360 (2021)

    Article  MathSciNet  Google Scholar 

  25. Blocki, J., Harsha, B., Kang, S., Lee, S., Xing, L., Zhou, S.: Data-independent memory hard functions: new attacks and stronger constructions. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 573–607. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_20

    Chapter  Google Scholar 

  26. Blocki, J., Kulkarni, S., Zhou, S.: On locally decodable codes in resource bounded channels. In: ITC. LIPIcs, vol. 163, pp. 16:1–16:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  27. Blocki, J., Ren, L., Zhou, S.: Bandwidth-hard functions: Reductions and lower bounds. In: CCS, pp. 1820–1836. ACM (2018)

    Google Scholar 

  28. Blocki, J., Zhou, S.: On the depth-robustness and cumulative pebbling cost of Argon2i. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 445–465. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_15

    Chapter  MATH  Google Scholar 

  29. Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_15

    Chapter  Google Scholar 

  30. Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 280–300. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42045-0_15

    Chapter  Google Scholar 

  31. Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_29

    Chapter  Google Scholar 

  32. Brakensiek, J., Guruswami, V., Zbarsky, S.: Efficient low-redundancy codes for correcting multiple deletions. IEEE Trans. Inf. Theory 64(5), 3403–3410 (2018)

    Article  MathSciNet  Google Scholar 

  33. Brakerski, Z., Döttling, N., Garg, S., Malavolta, G.: Candidate iO from homomorphic encryption schemes. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 79–109. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_4

    Chapter  Google Scholar 

  34. Chen, B., Tessaro, S.: Memory-hard functions from cryptographic primitives. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 543–572. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_19

    Chapter  Google Scholar 

  35. Cheng, K., Guruswami, V., Haeupler, B., Li, X.: Efficient linear and affine codes for correcting insertions/deletions. In: SODA, pp. 1–20. SIAM (2021)

    Google Scholar 

  36. Cheng, K., Haeupler, B., Li, X., Shahrasbi, A., Wu, K.: Synchronization strings: highly efficient deterministic constructions over small alphabets. In: SODA, pp. 2185–2204. SIAM (2019)

    Google Scholar 

  37. Cheng, K., Jin, Z., Li, X., Wu, K.: Deterministic document exchange protocols, and almost optimal binary codes for edit errors. In: FOCS, pp. 200–211. IEEE Computer Society (2018)

    Google Scholar 

  38. Cheng, K., Jin, Z., Li, X., Wu, K.: Block edit errors with transpositions: deterministic document exchange protocols and almost optimal binary codes. In: ICALP. LIPIcs, vol. 132, pp. 37:1–37:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

    Google Scholar 

  39. Cheng, K., Li, X.: Efficient document exchange and error correcting codes with asymmetric information. In: SODA, pp. 2424–2443. SIAM (2021)

    Google Scholar 

  40. Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. SIAM J. Comput. 40(4), 1154–1178 (2011)

    Article  MathSciNet  Google Scholar 

  41. Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_10

    Chapter  Google Scholar 

  42. Efremenko, K.: 3-query locally decodable codes of subexponential length. SIAM J. Comput. 41(6), 1694–1703 (2012)

    Article  MathSciNet  Google Scholar 

  43. Forler, C., Lucks, S., Wenzel, J.: Memory-demanding password scrambling. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 289–305. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_16

    Chapter  Google Scholar 

  44. Garay, J.A., MacKenzie, P.D., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. J. Cryptol. 24(4), 615–658 (2011)

    Article  MathSciNet  Google Scholar 

  45. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput. 45(3), 882–929 (2016)

    Article  MathSciNet  Google Scholar 

  46. Garg, S., Srinivasan, A.: A simple construction of iO for Turing machines. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11240, pp. 425–454. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03810-6_16

    Chapter  MATH  Google Scholar 

  47. Guruswami, V., Haeupler, B., Shahrasbi, A.: Optimally resilient codes for list-decoding from insertions and deletions. IEEE Trans. Inf. Theory 67(12), 7837–7856 (2021)

    Article  MathSciNet  Google Scholar 

  48. Guruswami, V., Li, R.: Polynomial time decodable codes for the binary deletion channel. IEEE Trans. Inf. Theory 65(4), 2171–2178 (2019)

    Article  MathSciNet  Google Scholar 

  49. Guruswami, V., Li, R.: Coding against deletions in oblivious and online models. IEEE Trans. Inf. Theory 66(4), 2352–2374 (2020)

    Article  MathSciNet  Google Scholar 

  50. Guruswami, V., Smith, A.D.: Optimal rate code constructions for computationally simple channels. J. ACM 63(4), 35:1–35:37 (2016)

    Google Scholar 

  51. Guruswami, V., Wang, C.: Deletion codes in the high-noise and high-rate regimes. IEEE Trans. Inf. Theory 63(4), 1961–1970 (2017)

    Article  MathSciNet  Google Scholar 

  52. Haeupler, B.: Optimal document exchange and new codes for insertions and deletions. In: FOCS, pp. 334–347. IEEE Computer Society (2019)

    Google Scholar 

  53. Haeupler, B., Rubinstein, A., Shahrasbi, A.: Near-linear time insertion-deletion codes and (1+\(\epsilon \))-approximating edit distance via indexing. In: STOC, pp. 697–708. ACM (2019)

    Google Scholar 

  54. Haeupler, B., Shahrasbi, A.: Synchronization strings: explicit constructions, local decoding, and applications. In: STOC, pp. 841–854. ACM (2018)

    Google Scholar 

  55. Haeupler, B., Shahrasbi, A.: Synchronization strings: codes for insertions and deletions approaching the singleton bound. J. ACM 68(5), 36:1–36:39 (2021)

    Google Scholar 

  56. Haeupler, B., Shahrasbi, A., Sudan, M.: Synchronization strings: list decoding for insertions and deletions. In: ICALP. LIPIcs, vol. 107, pp. 76:1–76:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

    Google Scholar 

  57. Hubácek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS, pp. 163–172. ACM (2015)

    Google Scholar 

  58. Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: FOCS, pp. 294–304. IEEE Computer Society (2000)

    Google Scholar 

  59. Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions. In: STOC, pp. 60–73. ACM (2021)

    Google Scholar 

  60. Jakobsson, M., Juels, A.: Proofs of work and bread pudding protocols. In: Communications and Multimedia Security. IFIP Conference Proceedings, vol. 152, pp. 258–272. Kluwer (1999)

    Google Scholar 

  61. Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC, pp. 80–86. ACM (2000)

    Google Scholar 

  62. Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci. 69(3), 395–420 (2004)

    Article  MathSciNet  Google Scholar 

  63. Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: CCS, pp. 669–684. ACM (2013)

    Google Scholar 

  64. Kiwi, M., Loebl, M., Matoušek, J.: Expected length of the longest common subsequence for large alphabets. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 302–311. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24698-5_34

    Chapter  Google Scholar 

  65. Kopparty, S., Meir, O., Ron-Zewi, N., Saraf, S.: High-rate locally correctable and locally testable codes with sub-polynomial query complexity. J. ACM 64(2), 11:1–11:42 (2017)

    Google Scholar 

  66. Kopparty, S., Saraf, S.: Guest column: local testing and decoding of high-rate error-correcting codes. SIGACT News 47(3), 46–66 (2016)

    Article  MathSciNet  Google Scholar 

  67. Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for Turing machines with unbounded memory. In: STOC, pp. 419–428. ACM (2015)

    Google Scholar 

  68. Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady 10(8), 707–710 (1966). Doklady Akademii Nauk SSSR, 163(4), 845–848 (1965)

    Google Scholar 

  69. Lin, H., Matt, C.: Pseudo flawed-smudging generators and their application to indistinguishability obfuscation. IACR Cryptology ePrint Archive, p. 646 (2018)

    Google Scholar 

  70. Lin, H., Pass, R., Seth, K., Telang, S.: Output-compressing randomized encodings and applications. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 96–124. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_5

    Chapter  Google Scholar 

  71. Lipton, R.J.: A new approach to information theory. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 699–708. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-57785-8_183

    Chapter  Google Scholar 

  72. Liu, S., Tjuawinata, I., Xing, C.: On list decoding of insertion and deletion errors (2020)

    Google Scholar 

  73. Mahmoody, M., Moran, T., Vadhan, S.: Time-lock puzzles in the random oracle model. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 39–50. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_3

    Chapter  MATH  Google Scholar 

  74. Malavolta, G., Thyagarajan, S.A.K.: Homomorphic time-lock puzzles and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 620–649. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_22

    Chapter  Google Scholar 

  75. May, T.C.: Timed-release crypto (1993). http://cypherpunks.venona.com/date/1993/02/msg00129.html

  76. Micali, S., Peikert, C., Sudan, M., Wilson, D.A.: Optimal error correction against computationally bounded noise. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 1–16. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_1

    Chapter  Google Scholar 

  77. Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system. Decentralized Bus. Rev., 21260 (2008)

    Google Scholar 

  78. Okamoto, T., Pietrzak, K., Waters, B., Wichs, D.: New realizations of somewhere statistically binding hashing and positional accumulators. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 121–145. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_6

    Chapter  Google Scholar 

  79. Ostrovsky, R., Pandey, O., Sahai, A.: Private locally decodable codes. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 387–398. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73420-8_35

    Chapter  Google Scholar 

  80. Ostrovsky, R., Paskin-Cherniavsky, A.: Locally decodable codes for edit distance. In: Lehmann, A., Wolf, S. (eds.) ICITS 2015. LNCS, vol. 9063, pp. 236–249. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-17470-9_14

    Chapter  Google Scholar 

  81. Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)

    Google Scholar 

  82. Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. ACM 26(2), 361–381 (1979)

    Article  MathSciNet  Google Scholar 

  83. Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report, USA (1996)

    Google Scholar 

  84. Shaltiel, R., Silbak, J.: Explicit list-decodable codes with optimal rate for computationally bounded channels. Comput. Complex. 30(1), 3 (2021)

    Article  MathSciNet  Google Scholar 

  85. Sima, J., Bruck, J.: Optimal k-deletion correcting codes. In: ISIT, pp. 847–851. IEEE (2019)

    Google Scholar 

  86. Sudan, M., Trevisan, L., Vadhan, S.P.: Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci. 62(2), 236–266 (2001)

    Article  MathSciNet  Google Scholar 

  87. Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. J. ACM 55(1), 1:1–1:16 (2008)

    Google Scholar 

  88. Yekhanin, S.: Locally decodable codes. Found. Trends Theor. Comput. Sci. 6(3), 139–255 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

Mohammad Hassan Ameri was supported in part by NSF award #1755708, by IARPA under the HECTOR program, and by a Summer Research Grant from Purdue University. Alexander R. Block was supported in part by NSF CCF #1910659. Jeremiah Blocki was supported in part by NSF CNS #1755708, NSF CNS #2047272, and NSF CCF #1910659 and by IARPA under the HECTOR program.

Author information

Authors and Affiliations

  1. Purdue University, West Lafayette, IN, 47907, USA

    Mohammad Hassan Ameri, Alexander R. Block & Jeremiah Blocki

Authors
  1. Mohammad Hassan Ameri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexander R. Block
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jeremiah Blocki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeremiah Blocki .

Editor information

Editors and Affiliations

  1. Università degli Studi di Salerno, Fisciano, Italy

    Clemente Galdi

  2. University of California at Irvine, Irvine, CA, USA

    Stanislaw Jarecki

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ameri, M.H., Block, A.R., Blocki, J. (2022). Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes. In: Galdi, C., Jarecki, S. (eds) Security and Cryptography for Networks. SCN 2022. Lecture Notes in Computer Science, vol 13409. Springer, Cham. https://doi.org/10.1007/978-3-031-14791-3_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-14791-3_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-14790-6

  • Online ISBN: 978-3-031-14791-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation