Document Open Access Logo

A Fully-Constructive Discrete-Logarithm Preprocessing Algorithm with an Optimal Time-Space Tradeoff

Authors Lior Rotem, Gil Segev

PDF
Thumbnail PDF

File

LIPIcs.ITC.2022.12.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Lior Rotem
  • School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel
Gil Segev
  • School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel

Funding

Supported by the European Union’s Horizon 2020 Framework Program (H2020) via an ERC Grant (Grant No. 714253).
  • Rotem, Lior: Supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities.

Cite As Get BibTex

Lior Rotem and Gil Segev. A Fully-Constructive Discrete-Logarithm Preprocessing Algorithm with an Optimal Time-Space Tradeoff. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITC.2022.12

Abstract

Identifying the concrete hardness of the discrete logarithm problem is crucial for instantiating a vast range of cryptographic schemes. Towards this goal, Corrigan-Gibbs and Kogan (EUROCRYPT '18) extended the generic-group model for capturing "preprocessing" algorithms, offering a tradeoff between the space S required for storing their preprocessing information, the time T required for their online phase, and their success probability. Corrigan-Gibbs and Kogan proved an upper bound of Õ(S T²/N) on the success probability of any such algorithm, where N is the prime order of the group, matching the known preprocessing algorithms.
However, the known algorithms assume the availability of truly random hash functions, without taking into account the space required for storing them as part of the preprocessing information, and the time required for evaluating them in essentially each and every step of the online phase. This led Corrigan-Gibbs and Kogan to pose the open problem of designing a discrete-logarithm preprocessing algorithm that is fully constructive in the sense that it relies on explicit hash functions whose description lengths and evaluation times are taken into account in the algorithm’s space-time tradeoff. 
We present a fully constructive discrete-logarithm preprocessing algorithm with an asymptotically optimal space-time tradeoff (i.e., with success probability Ω̃(S T²/N)). In addition, we obtain an algorithm that settles the corresponding tradeoff for the computational Diffie-Hellman problem. Our approach is based on derandomization techniques that provide rather weak independence guarantees. On the one hand, we show that such guarantees can be realized in our setting with only a minor efficiency overhead. On the other hand, exploiting such weak guarantees requires a more subtle and in-depth analysis of the underlying combinatorial structure compared to that of the known preprocessing algorithms and their analyses.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
  • Security and privacy → Mathematical foundations of cryptography
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Discrete logarithm
  • Preprocessing

Metrics

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

References

  1. Martin Aumüller, Martin Dietzfelbinger, and Philipp Woelfel. Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica, 70(3):428-456, 2014. Google Scholar
  2. Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62-73, 1993. Google Scholar
  3. Itay Berman, Iftach Haitner, Ilan Komargodski, and Moni Naor. Hardness-preserving reductions via cuckoo hashing. Journal of Cryptology, 32(2):361-392, 2019. Google Scholar
  4. Daniel J. Bernstein and Tanja Lange. Non-uniform cracks in the concrete: The power of free precomputation. In Advances in Cryptology - ASIACRYPT '13, pages 321-340, 2013. Google Scholar
  5. Sandro Coretti, Yevgeniy Dodis, and Siyao Guo. Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In Advances in Cryptology - CRYPTO '18, Lecture Notes in Computer Science, pages 693-721, 2018. Google Scholar
  6. Henry Corrigan-Gibbs and Dmitry Kogan. The discrete-logarithm problem with preprocessing. In Advances in Cryptology - EUROCRYPT '18, pages 415-447, 2018. Google Scholar
  7. Anindya De, Luca Trevisan, and Madhur Tulsiani. Time space tradeoffs for attacks against one-way functions and PRGs. In Advances in Cryptology - CRYPTO '10, pages 649-665, 2010. Google Scholar
  8. Martin Dietzfelbinger and Rasmus Pagh. Succinct data structures for retrieval and approximate membership. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pages 385-396, 2008. Google Scholar
  9. Martin Dietzfelbinger and Michael Rink. Applications of a splitting trick. ICALP 2009: Automata, Languages and Programming, pages 354-365, 2009. Google Scholar
  10. Martin Dietzfelbinger and Philipp Woelfel. Almost random graphs with simple hash functions. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 629-638, 2003. Google Scholar
  11. Yevgeniy Dodis, Siyao Guo, and Jonathan Katz. Fixing cracks in the concrete: Random oracles with auxiliary input, revisited. In Advances in Cryptology - EUROCRYPT '17, volume 10211, pages 473-495, 2017. Google Scholar
  12. Amos Fiat and Moni Naor. Rigorous time/space trade-offs for inverting functions. SIAM Journal on Computing, 29(3):709-803, 1999. Google Scholar
  13. David Freeman, Michael Scott, and Edlyn Teske. A taxonomy of pairing-friendly elliptic curves. Journal of Cryptology, 23(2):224-280, 2010. Google Scholar
  14. Torben Hagerup, Peter Bro Miltersen, and Rasmus Pagh. Deterministic dictionaries. Journal of Algorithms, 41(1):69-85, 2001. Google Scholar
  15. Martin E. Hellman. A cryptanalytic time-memory trade-off. IEEE Transaction on Information Theory, 26(4):401-406, 1980. Google Scholar
  16. Neal Koblitz, Alfred Menezes, and Scott A. Vanstone. The state of elliptic curve cryptography. Designs, Codes and Cryptography, 19(2/3):173-193, 2000. Google Scholar
  17. Hyung Tae Lee, Jung Hee Cheon, and Jin Hong. Accelerating ID-based encryption based on trapdoor DL using pre-computation. Cryptology ePrint Archive, Report 2011/187, 2011. Google Scholar
  18. Ueli Maurer. Abstract models of computation in cryptography. In Proceedings of the 10th IMA International Conference on Cryptography and Coding, pages 1-12, 2005. Google Scholar
  19. Ueli Maurer, Christopher Portmann, and Jiamin Zhu. Unifying generic group models. Cryptology ePrint Archive, Report 2020/996, 2020. Google Scholar
  20. Peter Bro Miltersen. Cell probe complexity - a survey. In Proceedings of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science, Advances in Data Structures Workshop, 1999. Google Scholar
  21. Anna Pagh and Rasmus Pagh. Uniform hashing in constant time and optimal space. SIAM Journal on Computing, 38(1):85-96, 2008. Google Scholar
  22. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122-144, 2004. Google Scholar
  23. Victor Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology - EUROCRYPT '97, pages 256-266, 1997. Google Scholar
  24. Alan Siegel. On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing, 33(3):505-543, 2004. Google Scholar
  25. Dominique Unruh. Random oracles and auxiliary input. In Advances in Cryptology - CRYPTO '07, pages 205-223, 2007. 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 About DROPS Imprint Privacy Contact