Research Summary: Design and analysis of a distributed ECDSA signing service

Cryptography
1

TLDR

  • Most distributed ECDSA signing use a synchronous communication model, yet in blockchain’s use case miners/validators are located all over the world.
  • The authors introduce a new distributed ECDSA protocol, which works in an asynchronous communication model and guarantees output delivery.
  • This protocol applies to cases that need a distributed and Byzantine fault-tolerant ECDSA signing service; where an ongoing example is the Internet Computer (ICP), which will allow smart contracts to spend Bitcoin.

Core Research Question

How to efficiently and safely sign a distributed ECDSA signature?

Citation

Jens Groth and Victor Shoup. “Design and Analysis of a Distributed ECDSA Signing Service.” Cryptology EPrint Archive, 2022. eprint.iacr.org, Design and analysis of a distributed ECDSA signing service.

Background

  • ECDSA (Elliptic Curve Digital Signature Algorithm): A digital signature scheme based on the elliptic curve. Many blockchains use this scheme to verify if a message is approved by a valid party.
  • Threshold Signature: t-out-of-n threshold signature scheme determines a scheme that the signer is represented by a number n of parties, a signature is producible while at least t (the threshold) of them approved it.
  • Synchronous/ Asynchronous Communication Model: In the synchronous communication model, there exists some known finite time bound that the sent message should be delivered. If a finite time bound doesn’t exist, the communication model is asynchronous.
  • Asynchronous Common Set (ACS): Under an asynchronous communication model, each party contributes an input message and obtains an output that is a subset of all the inputs. All honest parties must obtain the same subset.
  • Guaranteed Output Delivery: If the number of honest parties is greater than the threshold, the output (signature) is always attainable.
  • Non-Interactive Zero Knowledge (NIZK): A protocol that a prover can prove to a verifier that a given statement is true without letting the verifier know additional information, and the verifier doesn’t need to interact with the prover when verifying a proof.

Summary

  • This protocol is designed to work well on the Internet Computer, and it has several applications, such as securely holding and spending Bitcoin and other cryptocurrencies in smart contracts.
  • As a distributed protocol, it must specify a communication model. The synchronous communication model is unrealistic for a protocol whose nodes are distributed around the globe since an attacker could compromise the correct behavior of the protocol by delaying honest nodes or communications between them. Hence, an asynchronous model is more commonly used.
  • In the model, it also provides guaranteed output delivery in both the pre-computation and the online signing phase and allows up to n/3 Byzantine Corruptions. (The online phase is the time from when the message is decided to the signature being produced.)
  • To construct this protocol, subprotocols that support necessary operations need to be constructed to generate public keys, private keys, presignatures, and signatures.
  • Subprotocols adopt asynchronous verifiable secret sharing to generate and share secrets. The secrets are used to compute the public key and temporal keys within subprotocols.
  • It supports additive key derivation that abides with the BIP32 standard.

Method

  • The basic subprotocols are as follows:
    • Random: generate a sharing of a random element
    • Open: retrieve the secret from a sharing
    • OpenPower: retrieve an element (will be the generator of the curve below) to the power of the secret (i.e. g^a, where a is the secret)
    • Mul: multiply two sharings to obtain a new sharing, the secret of the new sharing is the product of the original two secrets
    • Linear operations (addition of sharings and multiplication by a constant) and affine operations (adding a constant to a sharing)
  • To implement the subprotocols, an asynchronous verifiable secret sharing (AVSS) tool is used in a component MEGa (Multi-Encryption Gadget). The rough idea is as follows:
    • The used protocol is based on Pedersen VSS, while the Feldman VSS is also adaptable
    • It assumes each party has a public key, a private key, and a signing key. All parties know others’ public keys and verify keys
    • Each party selects a secret a_i and its polynomial f_i (i.e. f_i(0) = a_i), computes, encrypt, and broadcast others’ shares. These shares can recover the polynomial with Lagrange interpolation.
    • All parties select some parties with ACS protocol to decide a final secret and polynomial. The selected parties have to obtain approvals from others.
    • For a selected and corrupted party, others can recover its secret and polynomial. Hence, the protocol is safe.
  • Within OpenPower and Mul protocols, NIZK is used to prove the correctness of the sending data.
  • With this tool and subprotocols, the ECDSA key generation and signing protocols are trivial. Please refer to Chap. 2.5 for details. The rough idea is as follows:
    • In key generation. All parties use the Random protocol to select a secret with AVSS and use the OpenPower protocol to retrieve the public key
    • Before signing, presignatures can be computed in advance with a similar process as key generation. Presignatures are a part of the signature that requires the temporal key but doesn’t require the message.
  • When signing a message, the Mul and Open subprotocol are used.

Results

  • The authors designed a practical protocol for distributed ECDSA signing.
  • By adopting the presignature technique, the work in the online phase is reduced.
  • The authors proved the protocol is secure under the static corruption assumption by proving the security of components.
  • Considering adaptive corruption without erasures, the authors proved that it’s still secure.
  • The Random and Mul protocol have a communication complexity of O(n^3\lambda). The Open and OpenPower have it of O(n^2\lambda). (The communication complexity is the number of bits sent by all honest parties. n is the number of parties.)
  • The computational complexity is dominated by O(n^2) exponentiations per signature.

Discussion and Key Takeaways

  • This paper introduced a new distributed ECDSA signing service, which is running in an asynchronous communication model.
  • In this protocol, the main components are Verifiable Secret Sharing, ACS, and NIZK.

Implications and Follow-Ups

  • This work presents a way to send a transaction from a chain to other chains (that accept ECDSA). It may be implemented in existing or new blockchains as a cross-chain solution.
  • This work introduces a protocol in which all parties have the same weight. Since some industry applications may need a weighted/hierarchical threshold signature scheme, this could be the topic of future works.

Applicability

  • The protocol is being implemented and integrated into the Internet Computer.
  • It should also work well in other distributed computing environments
8 Likes
2

Thank you for the summary, @flyinglimao. It’s great to see you on the forum again, it has been awhile.

My reading of this is that the major breakthroughs here are the asynchronous communication model use and the potential application as a cross-chain solution. That’s certainly several advancements, but are there other key things we should be paying attention to while considering this paper?

I also am interested in the potential application in as a cross-chain solution. Could you expand on how the design of this protocol better enables cross-chain transaction than prior models? From my reading, it seems that cross-chain solutions have historically been vulnerable.

2 Likes
3

Hi @zube.paul ,

My reading of this is that the major breakthroughs here are the asynchronous communication model use and the potential application as a cross-chain solution. That’s certainly several advancements, but are there other key things we should be paying attention to while considering this paper?

Due to my lack of knowledge, I couldn’t give an example application other than cross-chain. However, it doesn’t only work for cross-chain use cases, there should be other applications. Personally, I think the way they design is more valuable for me than the result. It might be an example for researchers who are new to designing a distributed service.

I also am interested in the potential application in as a cross-chain solution. Could you expand on how the design of this protocol better enables cross-chain transaction than prior models? From my reading, it seems that cross-chain solutions have historically been vulnerable.

In my word, the idea is similar to “Why layer2s (whose security is based on Ethereum mainnet) are better than sidechains?” Currently, cross-chain solutions usually have their own nodes, such as Ronin and Harmony, hence, hackers are easy targeting victims. By adopting this work, once hackers want to attack, it’s nearly hacking the whole network, whose possibility is negligible in most blockchain designs. In other words, the work might bind the security of the cross-chain transactions to the underlying blockchain security.

6 Likes
4

If there has ever been a way to ensure information secrecy, then cryptography has over the years presented a perfect model to conceal information.

This post “Design and analysis of a distributed ECDSA signing service” has presented a model to implement distributed ECDSA signing service based on an asynchronous communication model.

I am going to focus on some of the basic/preliminary detail about ECDSA – this is to convey the fundamentals of information secrecy and associated importance in blockchain transactions.

The question is why is this important?

Well before we go into all that it is important to note that the term cryptography became the key concept in concealing information due to the ability to implement different models built on secrecy and obscurity.

Cryptography_block-
Cryptography_block-1151×263 18.7 KB

A bit of the past about cryptography

The history of cryptography is extensive and diverse, and it has given rise to a wide variety of methodologies and uses.

The most basic definition of cryptography describes it as the activity of keeping one’s communications private when others are present.

For generations, people have relied on cryptography as a means of shielding their identities and ensuring the confidentiality of their conversations with one another.

Cryptography began with coded language. Early civilizations sent secret communications using hieroglyphics and other symbols.

Monks used encryption in the Middle Ages to secure sacred writings from unwanted readers. Using simple substitution codes, they encrypted these messages.

A bit about ECDSA

The Elliptic Curve Digital Signature Algorithm, often known as ECDSA, is one of the most complicated encryption algorithms that are used in public key cryptography.

The use of elliptic curve cryptography results in the generation of keys that are much shorter in length than the typical key created by digital signature techniques.

Why it is important.

ECDSA is considered to be more secure than other symmetric-key algorithms, such as RSA. One reason for this is that ECDSA can be used to generate digital signatures using a different private key for each signer.

This means that if one key is compromised, the attacker cannot use that key to sign other documents.

Not to miss it up ECDSA is a digital signature algorithm that provides greater security than traditional symmetric-key algorithms.

ECDSA uses a private key and a public key to generate digital signatures. The private key is used to sign data, and the public key is used to verify the digital signature.

A public key is a key that may be distributed to everyone and used to validate the digital signature of a communication. This key can also be used to authenticate the sender of the message.

It is believed to provide a higher degree of security than RSA and is used in many digital signatures and encryption schemes. ECDSA works with the bitcoin blockchain, which is used to secure bitcoin transactions.

The communication model

When it comes to cryptography and data transmission, it is essential to have a thorough understanding of the various communication models and their relationships with each other.

Depending on the kind of transaction being processed, synchronous communication may be required instantly, but asynchronous communication may provide more flexibility and greater execution time

A bit of a Synchronous communication model

A synchronous communication model is one in which all participants communicate in real-time.

This type of communication is typically used in situations where there is a need for immediate feedback, such as when two people are talking face-to-face.

Synchronous communication can be difficult to manage, as it can become difficult to keep track of what everyone is saying.

A bit of an Asynchronous communication model

Asynchronous communication is a communication model where communication is not synchronous.

In asynchronous communication, the sender sends the message to the receiver and then waits for a response.

The response might not come immediately, and the sender might have to wait for a predetermined amount of time before resending the message.

The workings of ECDSA

ECDSA, or Elliptic Curve Digital Signature Algorithm, is a public-key cryptography algorithm used in Bitcoin and other digital currencies.

It uses a modular arithmetic scheme that allows for more efficient calculation of digital signatures.

To generate a digital signature, ECDSA first calculates a digital signature using the public key. The message is then encrypted with the private key, and the digital signature is generated using the public key.

To generate a public/private key pair, users will need a private key and a public key. The private key is unique to the user and is not shared with anyone else.

The digital signature is a checksum of the message, and it can be verified using the public key. If the digital signature is valid, then the message was encrypted using the private key and the digital signature.

ECDSA offers several advantages over other cryptosystems, including:

  • ECDSA is resistant to Sybil attacks.

  • ECDSA can be used with weak keys without compromising security.

  • ECDSA is faster than other cryptosystems.

  • ECDSA is robust against quantum computing attacks.

Protection against ECDSA-based attacks.

There are a few things that can be done to help protect against ECDSA-based cryptanalysis:

  1. It is important to make sure that the keys used to encrypt data are kept safe.

  2. It is important to use a strong ECDSA algorithm.

  3. It is important to use a strong cipher.

  4. It is important to use a secure storage location for data.

  5. It is important to use a strong password.

  6. Finally, it is important to keep up to date on the latest security updates.

Conclusion

As technology continues to evolve, so will methods to ensure information security and privacy.

ECDSA protocol being implemented on the public key infrastructure provide secure, tamper-resistant, and authentication of communications.

It is a key component of the Ethereum platform and is used to secure transactions and verify the integrity of data. With particular importance to the post of @flyinglimao am certain it can only get better.

5 Likes
5

“I am not a lawyer and the following statements are my personal opinion and are not in any way the practicing of law nor should they be taken as advice”

In my 15 years as a software developer and the last 5 US Notary Public have provided me great insight knowledge, I believe that sometimes making immutable systems are an overkill of resources and in some intances, in this case the ECDSA while it has great preventative protocols, it is very evident to me that this system is meant to not be tampered-proof.

Instead, it is the opposite, its purpose is to be found as it is tampered evident. Sometimes leaving a trail of breadcrumbs can lead you back home. As a person whos sole duty as an appointed official, digital signatures, documents are tamper-evident not just at the end of the signing process, but from the moment the transaction is started. This provides evidence that the first signer didn’t alter the document before it was sent to the second signer .
Tamper evident is a term used to describe a product or process that protects an object with seals, markings, or other resistant techniques. The purpose of these features is to protect the integrity of the contents and ensure that the consumer or end user receives the document in its intended form

Similarly, A digital signature is intended to solve the problem of tampering and impersonation in digital communications . Digital signatures can provide evidence of origin, identity and status of electronic documents, transactions or digital messages. Signers can also use them to acknowledge informed consent.
Now while I am not saying that ECDSA is a tamper evident technology, what I am saying is that it very could well be.

4 Likes
6

Thank you @flyinglimao, for posting this research paper,to be honest, this paper might be difficult for non-technical people to understand, because I noticed that even the algorithm is too complex to be able to explain in any simpler terms. I noticed that the author analyzed a new protocol that provides a distributed ECDSA signing service, with some properties. These properties were made clear in the Paper. So to obtain highly decentralized and secure protocols, we are mainly interested in networks whose nodes are distributed around the globe, and for such networks, the synchronous communication model would be highly unrealistic. Indeed, an attacker could compromise the correct behavior of the protocol by delaying honest nodes or the communication between them. Such an attack is generally easier to mount than gaining control over and corrupting
an honest node. One key fact I noted in this paper is that Consensus is a basic problem that lies at the heart of many distributed protocols. In fact, any distributed signing protocol must include as a subprotocol a distributed key generation protocol, which itself a special case of consensus, as all parties must at least generate and agree on a public key for the signature scheme. Additive key derivation is desirable in an ECDSA threshold signing protocol for two reasons. First, if the protocol is to be used to sign Bitcoin (or other cryptocurrency) transactions, then support for BIP32 key derivation is inherently valuable. Second, if the protocol is to sign on behalf of many entities, then instead of having one secret signing key per entity, the protocol can host just a single master key from which individual signing keys
can be derived via additive key derivation

What Are the uses of ECDSA?

ECDSA is used across many security systems, is popular for use in secure messaging apps, and it is the basis of Bitcoin security (with Bitcoin “addresses” serving as public keys).

ECDSA is also used for Transport Layer Security (TLS), the successor to Secure Sockets Layer (SSL), by encrypting connections between web browsers and a web application. The encrypted connection of an HTTPS website, illustrated by an image of a physical padlock shown in the browser, is made through signed certificates using ECDSA.

I would conclude that based on my understanding of this paper ECDSA algorithm is very secure, I think it is impossible to find the private key as long as the implementation is done correctly of course. If there was a way to find the private key, then the security of every computer, website, system may be compromised since a lot of systems are relying on ECDSA for their security, and it is impossible to crack. Do you feel you have a contrary view on this ?

5 Likes
8

Hi @Henry
I’d partially agree. A most known threat to ECDSA might be quantum computers. If quantum computers turn practicable, ECDSA would be no more secure (but it may be hard to have one in the following years). Besides, a private key might be revealed in many cases other than implementation problems—for example, insecure users’ actions and unknown vulnerabilities in this scheme. Thus, I’d say the possibility of being cracked is ignorable instead of impossible.

5 Likes