Paper 2022/521

On The Distributed Discrete Logarithm Problem with Preprocessing

Pavel Hubáček, Ľubica Jančová, and Veronika Králová

Abstract

Protocols solving the Distributed Discrete Logarithm (DDLog) problem are a core component of many recent constructions of group-based homomorphic secret sharing schemes. On a high-level, these protocols enable two parties to transform multiplicative shares of a secret into additive share locally without any communication. Due to their important applications, various generic optimized DDLog protocols were proposed in the literature, culminating in the asymptotically optimal generic protocol of Dinur, Keller, and Klein (J. Cryptol. 2020) solving DDLog in time $T$ with error probability $O(W/T^2)$ when the magnitude of the secret is bounded by $W$. Given that DDLog is solved repeatedly with respect to a fixed group in its applications, a natural approach for improving the efficiency of DDLog protocols could be via leveraging some precomputed group-specific advice. To understand the limitations of this approach, we revisit the distributed discrete logarithm problem in the preprocessing model and study the possible time-space trade-offs for DDLog in the generic group model. As our main result, we show that, in a group of size $N$, any generic DDLog protocol for secrets of magnitude $W$ with parties running in time $T$ using precomputed group-specific advice of size $S$ has success probability \[ \epsilon = O\left(\dfrac{T^2}{W} + \dfrac{\max\{S,\log W\} \cdot T^2}{N}\right). \] Thus, assuming $N \geq W \log W$, we get a lower bound $ST^2= \Omega(\epsilon N)$ on the time-space trade-off for DDLog protocols using large advice of size $S= \Omega(N/W)$. Interestingly, for DDLog protocols using \emph{small advice} of size $S=O(N/W)$, we get a lower bound $T^2=\Omega(\epsilon W)$ on the running time, which, in the constant-error regime, asymptotically matches the running time of the DDLog protocol \emph{without any advice} of Dinur et al. (J. Cryptol. 2020). In other words, we show that generic DDLog protocols achieving constant success probability do not benefit from any advice of size $S= O(N/W)$ in the online phase of the DDLog problem.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.ITC 2022
Keywords
distributed discrete logarithm problempreprocessinggeneric group model
Contact author(s)
hubacek @ iuuk mff cuni cz
History
2022-05-02: received
Short URL
https://ia.cr/2022/521
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/521,
      author = {Pavel Hubáček and Ľubica Jančová and Veronika Králová},
      title = {On The Distributed Discrete Logarithm Problem with Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/521},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/521}},
      url = {https://eprint.iacr.org/2022/521}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.