International Association
for Cryptologic Research

We consider the problem of electing a leader among $n$ parties with the guarantee that each (honest) party has a reasonable probability of being elected, even in the presence of a coalition that controls a subset of parties, trying to bias the output. This notion is called ``game-theoretic fairness'' because such protocols ensure that following the honest behavior is an equilibrium and also the best response for every party and coalition. In the two-party case, Blum's commit-and-reveal protocol (where if one party aborts, then the other is declared the leader) satisfies this notion and it is also known that one-way functions are necessary. Recent works study this problem in the multi-party setting. They show that composing Blum's 2-party protocol for $\log n$ rounds in a tournament-tree-style manner results with {perfect game-theoretic fairness}: each honest party has probability $\ge 1/n$ of being elected as leader, no matter how large the coalition is. Logarithmic round complexity is also shown to be necessary if we require perfect fairness against a coalition of size $n-1$. Relaxing the above two requirements, i.e., settling for approximate game-theoretic fairness and guaranteeing fairness against only constant fraction size coalitions, it is known that there are $O(\log ^* n)$ round protocols. This leaves many open problems, in particular, whether one can go below logarithmic round complexity by relaxing only one of the strong requirements from above. We manage to resolve this problem for commit-and-reveal style protocols, showing that \begin{itemize} \item $\Omega(\log n/\log\log n)$ rounds are necessary if we settle for approximate fairness against very large (more than constant fraction) coalitions; \item $\Omega(\log n)$ rounds are necessary if we settle for perfect fairness against $n^\epsilon$ size coalitions (for any constant $\epsilon>0$). \end{itemize} These show that both relaxations made in prior works are necessary to go below logarithmic round complexity. Lastly, we provide several additional upper and lower bounds for the case of single-round commit-and-reveal style protocols.

We study the local leakage resilience of Shamir's secret sharing scheme. In Shamir's scheme, a random polynomial $f$ of degree $t$ is sampled over a field of size $p>n$, conditioned on $f(0)=s$ for a secret $s$. Any $t$ points can be used to fully recover $f$ and thereby $f(0)$. But, any $t-1$ evaluations of $f$ at non-zero coordinates are completely independent of $f(0)$. Recent works ask whether the secret remains hidden even if say only 1 bit of information is leaked from \emph{each} share, independently. This question is well motivated due to the wide range of applications of Shamir's scheme. For instance, it is known that if Shamir's scheme is leakage resilient in some range of parameters, then known secure computation protocols are secure in a local leakage model. Over characteristic-2 fields, the answer is known to be negative (e.g., Guruswami and Wootters, STOC~'16). Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO~'18) were the first to give a positive answer assuming computation is done over prime-order fields. They showed that if $t \ge 0.907n$, then Shamir's scheme is leakage resilient. Since then, there has been extensive efforts to improve the above threshold and after a series of works, the current record shows leakage resilience for $t\ge 0.78n$ (Maji et al., ISIT~'22). All existing analyses of Shamir's leakage resilience for general leakage functions follow a single framework for which there is a known barrier for any $t \le 0.5 n$. In this work, we a develop a new analytical framework that allows us to significantly improve upon the previous record and obtain additional new results. Specifically, we show: \begin{enumerate} \item Shamir's scheme is leakage resilient for any $t \ge 0.69n$. \item If the leakage functions are guaranteed to be ``balanced'' (i.e., splitting the domain of possible shares into 2 roughly equal-size parts), then Shamir's scheme is leakage resilient for any $t \ge 0.58n$. \item If the leakage functions are guaranteed to be ``unbalanced'' (i.e., splitting the domain of possible shares into 2 parts of very different sizes), then Shamir's scheme is leakage resilient as long as $t \ge 0.01 n$. Such a result is \emph{provably} impossible to obtain using the previously known technique. \end{enumerate} All of the above apply more generally to any MDS codes-based secret sharing scheme. Confirming leakage resilience is most important in the range $t \leq n/2$, as in many applications, Shamir’s scheme is used with thresholds $t\leq n/2$. As opposed to the previous approach, ours does not seem to have a barrier at $t=n/2$, as demonstrated by our third contribution.

The distributed discrete logarithm (DDL) problem was introduced by Boyle, Gilboa and Ishai 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 non-interactive evaluation of branching programs among two parties over shares of secret inputs. Let g be a generator of a multiplicative group $${\mathbb {G}}$$ G . Given a random group element $$g^{x}$$ g x and an unknown integer $$b \in [-M,M]$$ b ∈ [ - 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$$ 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})$$ O ( M · 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)$$ O ( S 2 ) to $$O(S^{3/2})$$ 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 short interval of length R in time $$o(\sqrt{R})$$ o ( 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.

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 non-interactive evaluation of branching programs among two parties over shares of secret inputs.Let g be a generator of a multiplicative group $$\mathbb {G}$$G. Given a random group element $$g^{x}$$gx and an unknown integer $$b \in [-M,M]$$b∈[-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$$A(gx)-B(gx+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})$$O(M·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)$$O(S2) to $$O(S^{3/2})$$O(S3/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 short interval of length R in time $$o(\sqrt{R})$$o(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.