LIPIcs.STACS.2022.14.pdf
- Filesize: 0.88 MB
- 11 pages
Document
On Explicit Constructions of Extremely Depth Robust Graphs
Authors
Jeremiah Blocki 
,
Seunghoon Lee ,
-
Part of:
Volume:
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-03-09
File
Document Identifiers
Author Details
Cite AsGet BibTex
Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee, and Jin Young Son. On Explicit Constructions of Extremely Depth Robust Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 14:1-14:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.14
https://doi.org/10.4230/LIPIcs.STACS.2022.14
Abstract
A directed acyclic graph G = (V,E) is said to be (e,d)-depth robust if for every subset S ⊆ V of |S| ≤ e nodes the graph G-S still contains a directed path of length d. If the graph is (e,d)-depth-robust for any e,d such that e+d ≤ (1-ε)|V| then the graph is said to be ε-extreme depth-robust. In the field of cryptography, (extremely) depth-robust graphs with low indegree have found numerous applications including the design of side-channel resistant Memory-Hard Functions, Proofs of Space and Replication and in the design of Computationally Relaxed Locally Correctable Codes. In these applications, it is desirable to ensure the graphs are locally navigable, i.e., there is an efficient algorithm GetParents running in time polylog|V| which takes as input a node v ∈ V and returns the set of v’s parents. We give the first explicit construction of locally navigable ε-extreme depth-robust graphs with indegree O(log |V|). Previous constructions of ε-extreme depth-robust graphs either had indegree ω̃(log² |V|) or were not explicit.
Subject Classification
ACM Subject Classification
- Theory of computation → Cryptographic primitives
- Mathematics of computing → Graph theory
- Mathematics of computing → Paths and connectivity problems
- Mathematics of computing → Combinatorics
Keywords
- Depth-Robust Graphs
- Explicit Constructions
- Data-Independent Memory Hard Functions
- Proofs of Space and Replication
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Joël Alwen and Jeremiah Blocki. Efficiently computing data-independent memory-hard functions. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 241-271. Springer, Heidelberg, 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_9.
- 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, pages 1001-1017. ACM Press, October / November 2017. URL: https://doi.org/10.1145/3133956.3134031.
- 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, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 3-32. Springer, Heidelberg, April / May 2017. URL: https://doi.org/10.1007/978-3-319-56617-7_1.
- Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained space complexity. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 99-130. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_4.
- Joël Alwen and Vladimir Serbinenko. High parallel complexity graphs and memory-hard functions. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 595-603. ACM Press, 2015. URL: https://doi.org/10.1145/2746539.2746622.
- Mohammad Hassan Ameri, Jeremiah Blocki, and Samson Zhou. Computationally data-independent memory hard functions. In Thomas Vidick, editor, ITCS 2020, volume 151, pages 36:1-36:28. LIPIcs, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.36.
- Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, and Samson Zhou. Relaxed locally correctable codes in computationally bounded channels. IEEE Transactions on Information Theory, 67(7):4338-4360, 2021. URL: https://doi.org/10.1109/TIT.2021.3076396.
- Jeremiah Blocki and Samson Zhou. On the computational complexity of minimal cumulative cost graph pebbling. In Sarah Meiklejohn and Kazue Sako, editors, FC 2018, volume 10957 of LNCS, pages 329-346. Springer, Heidelberg, February / March 2018. URL: https://doi.org/10.1007/978-3-662-58387-6_18.
- Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 585-605. Springer, Heidelberg, 2015. URL: https://doi.org/10.1007/978-3-662-48000-7_29.
- P. Erdös, R.L. Graham, and E. Szemerédi. On sparse graphs with dense long paths. Computers & Mathematics with Applications, 1(3):365-369, 1975. URL: https://doi.org/10.1016/0898-1221(75)90037-1.
- Ben Fisch. Tight proofs of space and replication. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 324-348. Springer, Heidelberg, 2019. URL: https://doi.org/10.1007/978-3-030-17656-3_12.
-
Ofer Gabber and Zvi Galil. Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences, 22(3):407-420, 1981.
- Aoxuan Li. On explicit depth robust graphs. UCLA, ProQuest ID: Li_ucla_0031N_17780. Merritt ID: ark:/13030/m5130rq7, 2019. URL: https://escholarship.org/uc/item/4fx1m6dh.
- Mohammad Mahmoody, Tal Moran, and Salil P. Vadhan. Publicly verifiable proofs of sequential work. In Robert D. Kleinberg, editor, ITCS 2013, pages 373-388. ACM, 2013. URL: https://doi.org/10.1145/2422436.2422479.
- Krzysztof Pietrzak. Proofs of catalytic space. In Avrim Blum, editor, ITCS 2019, volume 124, pages 59:1-59:25. LIPIcs, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.59.
- Omer Reingold, Salil P. Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In 41st FOCS, pages 3-13. IEEE Computer Society Press, 2000. URL: https://doi.org/10.1109/SFCS.2000.892006.
- Georg Schnitger. On depth-reduction and grates. In 24th FOCS, pages 323-328. IEEE Computer Society Press, 1983. URL: https://doi.org/10.1109/SFCS.1983.38.
-
Leslie Valiant. Graph-theoretic arguments in low-level complexity. In International Symposium on Mathematical Foundations of Computer Science, pages 162-176. Springer, 1977.