On the Distributed Discrete Logarithm Problem with Preprocessing

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²) 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 ε = O (T²/W + max{S,log W} ⋅ T²/N) . Thus, assuming N ≥ W log W, we get a lower bound ST² = Ω(ε N) on the time-space trade-off for DDLog protocols using large advice of size S = Ω(N/W). Interestingly, for DDLog protocols using small advice of size S = O(N/W), we get a lower bound T² = Ω(ε W) on the running time, which, in the constant-error regime, asymptotically matches the running time of the DDLog protocol 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.