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 groupbased homomorphic secret sharing schemes. On a highlevel, 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 groupspecific advice. To understand the limitations of this approach, we revisit the distributed discrete logarithm problem in the preprocessing model and study the possible timespace tradeoffs 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 groupspecific 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 timespace tradeoff 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 constanterror 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)
 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
 20220502: received
 Short URL
 https://ia.cr/2022/521
 License

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} }