nChain Finds a More than Hundredfold Efficiency Increase for Threshold Signatures

Share on Twitter
Share on LinkedIn
Send via Email

In a recently presented conference paper, titled Efficient Threshold-Optimal ECDSA, nChain Researcher Dr Michaella Pettit explains her invention of a new method for the efficient and secure creation of a digital signature using multiple parties.

What Are Threshold Signatures, Their Benefits, and Their Challenges?

A threshold signature scheme is a method for generating a signature on a message across a certain number of participants.  The first such scheme using the widely adopted Elliptic Curve Digital Signature Algorithm (ECDSA) dates back to the ‘90s.  Its benefit lies in the alleviation of scenarios where the private key needed for a signature is compromised, whether by attack or loss.

In a threshold signature scheme, the private key need not exist on any device at any point in time.  Rather, without revealing private information, participants collectively form a shared secret that corresponds to the shared private key, giving way to more secure structures.  Still, to an external party, including on the Bitcoin network, the resulting signature looks the same as one created without the threshold scheme, obscuring its nature and leaving any potential attack surface unexposed.  The result is a valid signature that protects user privacy and minimises costs.

But despite such beneficial properties, threshold signature schemes up to now have faced significant delays in being adopted across otherwise up-to-date systems, in part because of the challenges associated with achieving threshold-optimality in which the private key and signing thresholds are the same.  Such challenges have included inefficiencies stemming from complex cryptography such as homomorphic encryption and zero-knowledge proofs and the need for either interactive or predetermined signers, posing difficulties in providing feasible threshold signatures at scale.

Efficient Threshold-Optimal ECDSA

Efficient threshold-optimal ECDSA signatures, as presented at the 20th International Conference on Cryptology And Network Security (CANS2021), take advantage of a new mechanism invented by Dr Pettit.  The core of the mechanism lies in precalculating all multiplications of secrets before receiving a message, achieving threshold-optimality, yet removing the need for complex cryptography and expensive computation.  Her paper offers a proof that the new scheme is secure under feasible assumptions.

The proposed solution gives way to a new level of efficiency.  Taking advantage of fewer rounds of communication required for the key generation and signature, and of removing the need for complex cryptography and expensive computation, the new scheme was tested and compared to others using different numbers of participants.

Under the new scheme, benchmarking has shown that 8000 signatures per second can be generated after precomputation.  Overall, for two participants required to generate a signature, it was demonstrated to be 144 to 240 times faster than other non-interactive schemes.  More importantly, the higher the threshold, the greater the relative efficiency of the new scheme compared to the others.  The new scheme is thereby significantly more scalable.

The new scheme also comes with other appealing properties:

  • it allows the much sought-after scheme where two out of three participants generate a signature, which presents a more efficient set-up;
  • there is no need for predetermined signers, allowing participants to act in place of one that is offline or otherwise fails, without rerunning the whole scheme; and
  • through the mechanism of identifiable abort, malicious actors can easily be detected and prevented from participating again.

Multiparty Authorisation and Extensions by nChain

While not bound to the use of blockchain technology, the threshold signature scheme can easily be implemented to be used on the BSV blockchain, taking advantage of its low and stable fees and a sustainable network structure.  More generally, possible applications extend to scenarios where secure and efficient multiparty signatures and authorisation may be desired, including:

  • automated contracts;
  • custody solutions for digital assets;
  • joint or co-ownership accounts;
  • allowances and inheritance;
  • executive board proceedings; or
  • certificate authorities.

nChain is actively looking at the best route to implementing this invention within our product portfolio.

Kensei, our blockchain platform, is designed to bring the benefits of data integrity to enterprise without the need for them to undertake complex blockchain development or worry about blockchain operations like managing coins or keys.  The invention by Dr Pettit offers ways to improve performance in important areas of modern enterprises, and is another example of nChain solving complex problems through accessible solutions.