Paper 2018/731
An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing
Itai Dinur, Nathan Keller, and Ohad Klein
Abstract
The distributed discrete logarithm (DDL) problem was introduced by Boyle et al. at CRYPTO 2016. A protocol solving this problem was the main tool used in the share conversion procedure of their homomorphic secret sharing (HSS) scheme which allows noninteractive evaluation of branching programs among two parties over shares of secret inputs. Let $g$ be a generator of a multiplicative group $\mathbb{G}$. Given a random group element $g^{x}$ and an unknown integer $b \in [M,M]$ for a small $M$, two parties $A$ and $B$ (that cannot communicate) successfully solve DDL if $A(g^{x})  B(g^{x+b}) = b$. Otherwise, the parties err. In the DDL protocol of Boyle et al., $A$ and $B$ run in time $T$ and have error probability that is roughly linear in $M/T$. Since it has a significant impact on the HSS scheme's performance, a major open problem raised by Boyle et al. was to reduce the error probability as a function of $T$. In this paper we devise a new DDL protocol that substantially reduces the error probability to $O(M \cdot T^{2})$. Our new protocol improves the asymptotic evaluation time complexity of the HSS scheme by Boyle et al. on branching programs of size $S$ from $O(S^2)$ to $O(S^{3/2})$. We further show that our protocol is optimal up to a constant factor for all relevant cryptographic group families, unless one can solve the discrete logarithm problem in a \emph{short} interval of length $R$ in time $o(\sqrt{R})$. Our DDL protocol is based on a new type of random walk that is composed of several iterations in which the expected step length gradually increases. We believe that this random walk is of independent interest and will find additional applications.
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in CRYPTO 2018
 Keywords
 Homomorphic secret sharingshare conversionfully homomorphic encryptiondiscrete logarithmdiscrete logarithm in a short intervalrandom walk.
 Contact author(s)
 dinuri @ cs bgu ac il
 History
 20181111: revised
 20180809: received
 See all versions
 Short URL
 https://ia.cr/2018/731
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/731, author = {Itai Dinur and Nathan Keller and Ohad Klein}, title = {An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing}, howpublished = {Cryptology ePrint Archive, Paper 2018/731}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/731}}, url = {https://eprint.iacr.org/2018/731} }