Distributing the elliptic curve digital signature algorithm both securely and efficiently

January 15, 2020

Ida Tucker


Distributing the elliptic curve digital signature algorithm both securely and efficiently

Time:   10:45am
Location:   Meeting room 302 (Mountain View), level 3

The Elliptic Curve Digital Signature Algorithm (ECDSA) is a widely adopted digital signature standard; in particular it is employed to validate bitcoin transactions. In this context, the theft of a secret signing key results in an immediate financial loss, thereby creating a single point of failure. An interesting solution to reduce the risk of key theft is that of sharing the secret signing key among various devices, such that a signature can only be produced if these devices collaborate to jointly produce a signature, thereby distributing the signature protocol. In this talk I will focus on the two party case, which allows for instance to share a secret key between a mobile phone and a laptop. Unfortunately, efficient distributed variants of ECDSA are notoriously hard to achieve and prior to our work, solutions required expensive zero knowledge proofs to deal with malicious adversaries (MacKenzie et al. (Crypto’01)), relied on non standard interactive assumptions (Lindell (Crypto’17)) or induced a high communication cost (Doerner et al. (IEEE S&P’18)). I will explain how, in a recent article from Crypto’19 we overcome all of the above drawbacks, and — using class groups of imaginary quadratic fields — provide a provably secure two party ECDSA protocol, relying only on standard assumptions, which is the most efficient to date in terms of bandwidth consumption while remaining competitive in terms of timings. I will further justify that — by resorting to two recently introduced computational assumptions on class groups — we can dramatically improve the efficiency of the zero knowledge proofs needed by our protocol (and thereby that of the overall protocol).