Efficient Distributed Key Generation For Threshold Signatures Dfinity

admin
  1. Abe, M.: Securing encryption + proof of knowledge in the random oracle model. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 277–289. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  2. Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. IEEE Journal on Selected Areas in Communications 18(4), 593–610 (2000)CrossRefGoogle Scholar
  3. Bellare, M., et al.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 26. Springer, Heidelberg (1998)Google Scholar
  4. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)Google Scholar
  5. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computation. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988, ACM, New York (1988)Google Scholar
  6. Cachin, C.: Efficient private bidding and auctions with an oblivious third party. In: 6th ACM Conference on Computer and Communications Security (CCS), pp. 120–127. ACM, New York (1999)CrossRefGoogle Scholar
  7. Camenisch, J., Damgård, I.: Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 331–345. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  8. Canetti, R., et al.: Adaptive security for threshold cryptosystems. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 98–115. Springer, Heidelberg (1999)Google Scholar
  9. Cramer, R., et al.: Multi-authority secret ballot elections with linear work. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 72–83. Springer, Heidelberg (1999)Google Scholar
  10. Desmedt, Y.: Society and group oriented cryptography: A new concept. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 120–127. Springer, Heidelberg (1987)Google Scholar
  11. Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, Heidelberg (1990)Google Scholar
  12. Diffie, W., Hellman, M.: New directions in cryptography. IEEE Transactions on Information Theory IT-22(6), 644–654 (1976)CrossRefMathSciNetGoogle Scholar
  13. Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problem. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)Google Scholar
  14. Fouque, P., Stern, J.: One round threshold discrete-log key generation without private channels. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 300–316. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  15. Franklin, M., Reiter, M.: Verifiable signature sharing. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 50–63. Springer, Heidelberg (1995)Google Scholar
  16. Gennaro, R., et al.: Distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295–310. Springer, Heidelberg (1999)Google Scholar
  17. Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001)zbMATHCrossRefGoogle Scholar
  18. Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: 19th STOC, pp. 25–27. Springer, Heidelberg (1987)Google Scholar
  19. Hirt, M., Sako, K.: Efficient receipt-free voting based on homomorphic encryption. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 539–556. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  20. http://tycho.usno.navy.mil/gps.html
  21. Jarecki, S., Lysyanskaya, A.: Adaptively secure threshold cryptography: Introducing concurrency, removing erasures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 221–242. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  22. Lysyanskaya, A., Peikert, C.: Adaptive security in the threshold setting: From cryptosystems to signature schemes. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 331–350. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  23. Mao, W.: Verifiable escrowed signature. In: Mu, Y., Pieprzyk, J.P., Varadharajan, V. (eds.) ACISP 1997. LNCS, vol. 1270, pp. 240–248. Springer, Heidelberg (1997)CrossRefGoogle Scholar
  24. Micali, S.: Fair public-key cryptosystems. In: Brickell, E.F. (ed.) CRYPTO 1992, vol. 740, pp. 113–138. Springer, Heidelberg (1993)Google Scholar
  25. Paillier, P.: Public key cryptosystem based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)Google Scholar
  26. Pedersen, T.P.: A threshold cryptosystem without a trusted party. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 522–526. Springer, Heidelberg (1991)Google Scholar
  27. Pfitzmann, B., Schunter, M., Waidner, M.: Optimal efficiency of optimistic contract signing. In: 17th PODC, pp. 113–122. Springer, Heidelberg (1998)Google Scholar
  28. Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: 21th STOC. LNCS, pp. 73–85. Springer, Heidelberg (1989)Google Scholar
  29. Schnorr, C.P.: Ecient signature generation for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)Google Scholar
  30. Shamir, A.: How to share a secret. Communications of ACM 22, 612–613 (1979)zbMATHCrossRefMathSciNetGoogle Scholar
  31. Shoup, V., Gennaro, R.: Securing threshold cryptosystems against chosen ciphertext attacks. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 1–16. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  32. Stadler, M.: Publicly verifiable secret sharing. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 190–199. Springer, Heidelberg (1996)Google Scholar
00:00 / 00:00

Author: Omer Shlomovits, ZenGo.

Threshold Signature Scheme (TSS) is a cryptographic primitive for distributed key generation and signing. The use of TSS in blockchain clients is a new paradigm that can provide numerous benefits, especially in terms of security. In the broader sense, TSS can influence the design of key management systems (such as crypto wallets) and lead the way for native support in DeFi use cases. Having said that, TSS is still a new technology, so the risks and limitations should also be considered.

In this article, we will cover what a TSS is, what are the potential advantages it brings to the blockchain space, how it can be implemented in a blockchain client, how it compares to Shamir secret sharing and Multisig, what are the different ways to use TSS for distributed key management and finally we discuss the risks and limitations.

Mar 25, 2017  To be clear, these threshold signature schemes are not like the optimized BLS system we use in DFINITY Threshold Relay that can combine outputs from hundreds of signers to create a unique.


  1. Feb 03, 2018 This is where Dfinity has made a major breakthrough. They’re using BLS rather than RSA or ECDSA, due to the fact that has a unique. threshold version as well as a distributed key generation for this unique threshold version. This allows for a signature to be valid if a threshold of private keys signing the message is reached.
  2. View Enzo Haussecker’s profile on LinkedIn, the world's largest professional community. ∙Developed an efficient distributed key generation protocol for threshold signatures in Haskell.

The power of cryptography

To understand TSS, we first need some basic knowledge of cryptography. Since the 1970s, more and more Internet systems (such as TLS and PGP) employed asymmetric cryptography, which is also known as public key cryptography (PKC). PKC makes use of two keys: one public and one private. While the public key is no secret and can be published and used by anyone, the private key is a piece of secret information that represents the security of the system.

Encryption and digital signatures are the two most common usages for PKC. Both encryption and digital signatures schemes rely on sets of three algorithms. First is the private and public key pair generation, second is the generation of a ciphertext/signature, and third is the process of decryption/verification. In regards to digital signatures, the signing algorithm requires the private key, which is known only to its owner, to produce a unique signature. The signature is attached to a given message in a way that anyone holding the public key will be able to verify its authenticity and correctness.


Blockchain

There is no doubt that blockchain is a very powerful technology. It provides a consensus layer that organizes and records events. Such an infrastructure gives us, the users, potential power to build decentralized economies and even governments. Surprisingly enough, the cryptography needed to run a basic blockchain can be based solely on digital signatures. In the context of a blockchain, the private keys represent identities while a signature is a public statement or claim done by an identity. The blockchain will order the statements and validate them according to a set of rules, which ensure, among other things, that the signatures are unforgeable and correct.

In contrast to the more classical cryptography utilized in the blockchain, the modern cryptographic toolbox includes some awesome magic tricks: zero-knowledge proofs, homomorphic encryption, and multi-party computation, to name a few. As we saw over the past decade, blockchain research pushed applied cryptography tremendously, with recent breakthroughs in all of the above and much more.

In this article, we will focus on a single such breakthrough: efficient secure threshold signatures (TSS).


MPC and the threshold signature scheme (TSS)

Multi-party computation (MPC) is a branch of cryptography that started with the seminal work of Andrew C. Yao, almost 40 years ago. In MPC, a set of parties that do not trust each other try to jointly compute a function over their inputs while keeping those inputs private.

As an example, let us say that n employees of a company wants to know who is getting paid the most but without revealing to each other their actual salary. Here the private inputs are salaries and the output will be the name of the employee with highest salary. Doing this computation using MPC we get that not even a single salary is leaked during the computation.

The two main properties of MPC are correctness and privacy:

  • Correctness: the output produced by an algorithm is correct (as expected).

  • Privacy: the secret input data that a party holds would not leak to the other parties.

We will use MPC to compute a digital signature in a distributed way. Let's see how the above properties can be applied to signatures. Recall that, for signatures, we have three steps:

  • Key Generation: the first step is also the most complex. We need to generate a key which will be public and used to verify future signatures. But, we also need to generate an individual secret for each party, which we will call a secret share. In terms of correctness and privacy we say that the function will output the same public key to all parties, and a different secret share for each such that: (1) privacy: no secret shares data is leaked between the parties, and (2) correctness: the public key is a function of the secret shares.

  • Signing: this step involves a signature generation function. The input of each party will be its secret share, created as output of the previous step (distributed key generation). There is also public input known to all, which is the message to be signed. The output will be a digital signature, and the property of privacy ensures that no leakage of secret shares occurred during the computation.

  • /injustice-2-legendary-edition-pc-key-generator.html. Verification: the verification algorithm remains as it is in the classical setting. To be compatible with single key signatures, everyone with knowledge of the public key should be able to verify and validate the signatures. This is exactly what blockchain validating nodes do.

Threshold signature scheme (TSS) is the name we give to this composition of distributed key generation (DKG) and distributed signing a threshold signature scheme.


Combining TSS with blockchains

The natural way in which TSS can be put to use in a blockchain is by changing a blockchain client to generate keys and signatures using TSS. Here, we use the term blockchain client to refer to the set of commands executed by a full node. In practice, the TSS technology allows us to replace all private key related commands with distributed computations.

To explain it in more detail, we start by describing briefly how new addresses are created on the classical blockchain design. Simply put, we can create a new address by generating a private key, and then computing the public key from the private key. Finally, the blockchain address is derived out of the public key.

Now, using TSS, we would have a set of n parties jointly computing the public key, each holding a secret share of the private key (the individual shares are not revealed to the other parties). From the public key, we can derive the address in the same way as in the traditional system, making the blockchain agnostic to how the address is generated. The advantage is that the private key is not a single point of failure anymore because each party holds just one part of it.

The same can be done when signing transactions. In this case, instead of a single party signing with their private key, we run a distributed signature generation between multiple parties. So each party can produce a valid signature as long as enough of them are acting honestly. Again we moved from local computation (single point of failure) to an interactive one.

It is important to mention that the distributed key generation can be done in a way that allows different types of access structures: the general “t out of n” setting will be able to withstand up to t arbitrary failures in private key related operations, without compromising security.


TSS vs. Multisig

Some blockchains offer TSS functionality as a built-in or programmable part of the software. We call this functionality multisig or multi-signature. To better understand the differences, we can look at multisig as a TSS in the application layer of the blockchain.

Put differently, both multisig and TSS are essentially trying to achieve similar goals, but TSS is using cryptography off-chain, while multisig happens on-chain. However, the blockchain needs a way to encode multisig, which might harm privacy because the access structure (number of signers) is exposed on the blockchain. The cost of a multisig transaction is higher because the information on the different signers also needs to be communicated on the blockchain.

In TSS, the signers’ details are folded into a regular looking transaction, reducing cost and maintaining privacy. On the other hand, multisig can be non-interactive, which saves the trouble of running a complex communication layer between the different signers.

The main point of difference is that multisig is blockchain-specific and needs to be reimplemented for every blockchain, and in some cases, it is not supported at all. Conversely, TSS is relying on pure cryptography, so support is always possible. A great article with illustrations on the differences can be found here.

Efficient Distributed Key Generation For Threshold Signatures Definity Meaning


TSS vs. Shamir secret sharing scheme

The Shamir secret sharing scheme (SSSS) provides a way to store the private key in a distributed manner such that while the private key is at rest, it is stored in multiple locations. There are two differences between SSSS and TSS:

  • Key Generation: in SSSS, there is a single party called “the dealer” that is in charge of generating the private key secret shares. It means that at time of Key Generation, the private key is generated at a single location and then distributed by the dealer to the different locations. In TSS, there is no dealer as its role is distributed such that the full private key is never at a single location.

  • Signing: in SSSS, the parties must reconstruct the full private key in order to sign, which again results in a single point of failure each time a signature is needed. In TSS, the signing is done in a distributed way without ever reconstructing the secret shares.

As we can see, in TSS the private key (which represents the security of the system) is never at a single location throughout its entire lifetime.


Threshold wallets

A wallet based on TSS technology is a bit different than traditional cryptocurrency wallets. Typically, a conventional wallet generates a seed phrase and use it to deterministically derive the addresses. The user can later use this hierarchical deterministic (HD) structure to 1) reach the private keys that correspond to the wallet addresses and sign transactions with them, and 2) to recover all wallet keys using the seed phrase.

In a threshold wallet, things are more complex. Although it is possible to generate an HD structure, its generation must be computed in a distributed manner, as another MPC protocol. The parties need to jointly decide on what is the next key to be used. In other words, each party will have a seed phrase of its own. The seed phrases are generated separately and never combined so that one party alone can’t derive the private keys from its seed.

TSS-based wallets, also have a nice security feature, which is enabling of private key rotation without changing the corresponding public key and blockchain address. Private key rotation, also known as proactive secret sharing, is yet another MPC protocol that takes the secret shares as input, and outputs a new set of secret shares. The old secret shares can be deleted and the new ones can be used in the same way.

Such a structure adds a time dimension to the security, which means an attacker must be at multiple locations at the same time to attack a threshold wallet. Combining secret shares before rotation and after the rotation will give the attacker no extra power if they want to forge a signature.

A downside of this type of wallet is that the lack of a seed phrase makes it incompatible with single-key wallet systems. So it’s important to consider which parties will hold the secret shares.

There are a few possible architectures:

  • Outsourcing TSS: the user will let “n” servers run the computation on their behalf. Effectively outsourcing the key generation, management and signing to service providers who are not the owners of the assets but provide a security layer in return to some incentive.

  • Using multiple devices: The user will run the TSS between the devices they own. For example - one party will be some IoT device, another party will be the user mobile, another party their laptop, and so on.

  • Hybrid: TSS will run such that some parties are controlled by outside service providers and some parties run on user-owned devices.

The first method offloads the heavy TSS computation from the user client side. On the other hand, the service providers can collude (we assume enough of them are not attacked at the same time, but in practice, they might) and steal the assets of the user.

The second method gives the user full control but makes it cumbersome to conduct transactions as you need multiple devices to go online and engage with the TSS computation.

The third option is considered the best of both worlds as it gives the user an easy and fast way to conduct transactions but without compromising on having transactions done without the user authorization.

Efficient Distributed Key Generation For Threshold Signatures Definity X


TSS and smart contracts

Over the years, researchers have found many uses for digital signatures, and some are surprisingly non-trivial. As mentioned, TSS is a cryptographic primitive that can greatly increase security. In the context of blockchains, we may say that many functionalities can be replaced with TSS-based cryptography. Decentralized applications, layer 2 scaling solutions, atomic swaps, mixing, inheritance, and much more can be built on top of a TSS framework. This would eventually allow for expensive and risky on-chain smart contract operations to be replaced by cheaper and more reliable alternatives.

To give some concrete examples: Multi-Hop Locks makes use of two-party signatures in a clever way and can be used as an alternative to Bitcoin lightning network with a more secure and private payment channel network. ShareLock is probably the cheapest on-chain mixing solution for Ethereum, based on verification of a single threshold signature.


Risks

In the last couple of years, there was a significant increase in TSS implementations. However, as a relatively new technology, it still has some limitations and concerns. Compared to classic public key cryptography, TSS protocols can be very complex and are yet to be “battle-tested”. Dead rising 2 key generator. Usually, TSS requires additional, weaker, cryptographic assumptions compared to simple digital signatures. As a result, cryptographic attack vectors that did not exist in traditional setups are now being discovered (see this presentation from Breaking Bitcoin Conference 2019). Security engineers and applied cryptographers can assist in safely deploying TSS in your system.

On the positive side, existing and new implementations are becoming stronger due to an increase in quality contributions, peer reviews, audits, and algorithmic performance improvements.


Closing thoughts

In this article, we introduced the basics of the threshold signature scheme (TSS), which is a fascinating cryptographic primitive that has the potential to change significantly the way we use blockchain.

Efficient Distributed Key Generation For Threshold Signatures Definity For Echo

Since this article did not discuss the Threshold ECDSA that can be used in Binance Chain and Bitcoin, the ones interested may refer to the following list of recent papers. Also, if you want to play with some TSS implementations you can find a code for two-party Binance Chain wallet here or try ZenGo wallet, which utilizes the hybrid method to provide a non-custodial two-party Binance Chain wallet.


Efficient Distributed Key Generation For Threshold Signatures Definity 2016

Further reading:

Related