License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2022.12
URN: urn:nbn:de:0030-drops-164905
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16490/
Go to the corresponding LIPIcs Volume Portal

Rotem, Lior ; Segev, Gil

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

pdf-format:
LIPIcs-ITC-2022-12.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{rotem_et_al:LIPIcs.ITC.2022.12,
  author =	{Rotem, Lior and Segev, Gil},
  title =	{{A Fully-Constructive Discrete-Logarithm Preprocessing Algorithm with an Optimal Time-Space Tradeoff}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16490},
  URN =		{urn:nbn:de:0030-drops-164905},
  doi =		{10.4230/LIPIcs.ITC.2022.12},
  annote =	{Keywords: Discrete logarithm, Preprocessing}
}

Keywords: Discrete logarithm, Preprocessing
Collection: 3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Issue Date: 2022
Date of publication: 30.06.2022

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