Paper 2026/2482

Edabits Generation with Quasi-Linear Communication Complexity

Abstract

The work of (Escudero et al., CRYPTO 2020) introduces the so-called edabits, which are defined as a secret sharing of an integer over an arithmetic domain, together with its bit decomposition secret shared over a binary domain. In the same work, it is shown how edabits can be used to securely evaluate advanced primitives such as comparison, bit decomposition, and truncation, which are essential building blocks in more complex applications such as privacy-preserving machine learning and beyond. Edabits are general and can be defined over any secret-sharing scheme or corruption model. Such flexibility, coupled with their wide range of applications, makes edabits a powerful target correlation. Escudero et al.~introduced a protocol to generate edabits that works in the arithmetic black-box (ABB) model, that is, it is agnostic to the concrete secret-sharing scheme and even works both for fields $\mathbb{F}_p$ and rings $\mathbb{Z}_{2^\ell}$, as well as both for honest majority $t<n/2$ and dishonest majority $t<n$. Unfortunately, the communication complexity of their approach grows as $\Omega(n^2\ell)$ bits with $\ell$ being the bit-length of an element in the arithmetic domain. This becomes a bottleneck in larger protocols since most MPC primitives such as multiplications or openings can be done with linear communication of $O(n\ell)$ bits. In this work we present a novel approach for generating edabits in the ABB model that achieves \emph{quasi-linear} communication complexity of $O(n\ell\log n)$ bits, for the setting where $t<n(1-\epsilon)$ for a constant $\epsilon>0$. This includes the honest majority case $t<n/2$, but also dishonest majority with an (arbitrarily small) constant fraction of honest parties. Our result is achieved via novel applications of randomness extraction methods, as well as better edabit aggregation for the binary components. Along the way and of independent interest, we improve the communication complexity of dabit generation (dabits are bits shared in both binary and arithmetic domains) from $\Omega(n^2\ell)$ bits achieved in (Rotaru and Wood, INDOCRYPT 2019), to linear $O(n\ell)$ bits.