Paper 2026/929

On the Statistical vs. Computational Security of the DKLs23 Multiparty ECDSA Protocol

Abstract

The DKLs23 protocol (Doerner, Kondi, Lee and shelat, IEEE S&P '24) is a state-of-the-art multiparty ECDSA signing protocol. Due to its exceptional combination of simplicity, efficiency, and statistical UC security within an elegant hybrid model providing access to standard ideal functionalities, it is rapidly seeing widespread adoption. We provide a comprehensive security analysis of the DKLs23 protocol, showing that although it is not statistically secure as originally claimed, it is nevertheless computationally secure, and can be made statistically secure via a lightweight refinement. Our contributions are as follows: -- Statistical insecurity: Within the hybrid model utilized for the original analysis, we construct a computationally-unbounded "split-view" adversary that successfully attacks the protocol by causing two or more honest parties to output different valid signatures on the same message (specifically, signatures with independent nonces). Considering any ideal ECDSA signing functionality that outputs a single signature per session, such an attack cannot be simulated in the ideal model, and thus the protocol is not statistically secure. -- Computational security: We prove that the protocol is nevertheless computationally secure based on the assumption that ECDSA is strongly unforgeable up to sign (i.e., up to the trivial $(r, \pm s)$ malleability), as defined by Groth and Shoup (EUROCRYPT '22). Specifically, complementing our split-view attack, we show that any adversary for which the protocol's execution is distinguishable from its ideal-model simulation can be efficiently transformed into an algorithm that breaks the strong unforgeability up to sign of ECDSA. -- A refined statistically-secure protocol: Identifying the root cause of our split-view attack, we present a refined protocol that is statistically secure. Our refinement incorporates a lightweight consistency check, where each party sends a single group element as part of the protocol's third-round message. Our refinement additionally introduces a relaxed zero-sharing functionality that serves as a drop-in replacement for the original protocol's zero-sharing functionality. We show that this relaxed functionality can be unconditionally realized by a simple one-round protocol (executed in parallel with the first round of signing) without a dedicated setup or pre-shared seeds. Consequently, when paired with a compatible (e.g., Paillier-based) VOLE instantiation, this eliminates the need for long-term secure pairwise storage across the entire signing protocol.