Paper 2026/130

ARES/ARES+: Online-Friendly Robust Threshold ECDSA with Amortized Costs

Abstract

Threshold ECDSA has been an active research topic in recent years, driven by its wide-ranging applications, particularly in blockchain domains. In these real-world applications, robustness is a critical requirement. It ensures that a signature is successfully generated as long as $t+1$ honest parties are present, regardless of malicious behavior from others. Existing robust constructions generally fall into two categories: those based on threshold linearly homomorphic encryption (TLHE) and those leveraging the Multiplicative-to-Additive (MtA) paradigm. The TLHE-based approach (e.g., WMC24 in NDSS'24) achieves constant sending communication per party but incurs an expensive online phase. In contrast, the MtA-based approach (e.g., TX25 in S\&P'25) is online-friendly, requiring only finite-field operations and a minimal number of elliptic-curve group operations during the online phase. However, it has the drawback of requiring $O(n)$ communication and $O(n^2)$ computation per party when $n$ parties are involved. In this work, we propose two schemes, $\mathsf{ARES}$ and $\mathsf{ARES}^+$, to reduce the communication and computational complexity of robust threshold ECDSA within the online-friendly MtA framework. Our first construction, $\mathsf{ARES}$, achieves a constant per-party sending communication of 2.22 KB during the offline phase, a significant reduction from the 4.1 KB required by the TLHE-based WMC24. While it substantially improves upon the overall efficiency of TX25, its computational complexity remains quadratic. Building on this, our second scheme, $\mathsf{ARES}^+$, leverages packed secret sharing to achieve linear amortized computational complexity and constant online communication. This enables $\mathsf{ARES}^+$ to match the asymptotic efficiency of WMC24 while preserving the online-friendly characteristics inherent to MtA-based designs. On the other hand, to achieve amortization across $\ell$ signatures, we incur a trade-off by increasing the party count by $\ell$.