We're happy to reveal Web3Auth's development of a new feature that supports key derivation, allowing users to derive multiple private keys from a single account for improved asset organization. This post explores key derivation techniques in MPC-based key management systems, where the secret master key does not exist in one place but is distributed across multiple devices. We'll also detail our approach to implementing MPC-friendly key derivation in Web3Auth.

Overview

Key derivation allows multiple private keys to be derived from a single master secret key. We use a function ƒ, which takes the master private key 𝘬 and a derivation path 𝑑 as inputs, to produce a new private key 𝘬_𝑑 = ƒ(𝘬,𝑑). BIP32 is a renowned key derivation scheme for single-party settings. In multiparty context, however, there are tradeoffs to consider regarding security guarantees and technical complexity.

We distinguish the different approaches to MPC-friendly key derivation by the following properties:

• Key relatability: Can different keys derived from the same master key be identified with each other? Does the leakage of one of the keys result in the leakage of all keys?
• Technical complexity: Does the solution require advanced cryptographic primitives such as zero-knowledge proofs or multi-party computation? Or does it only rely on simple primitives such as cryptographic hash functions?

We review these solutions, starting from those offering the highest security and complexity to those with lower guarantees and complexity.

Threshold PRF-based key derivation

The most secure but also the most complex variant of MPC-friendly key derivation is by running a threshold pseudo-random function (tPRF) protocol such as LaKey. Such a protocol computes the entire key derivation in MPC. Derived keys are completely unrelatable to each other as long as the master key is not leaked. Moreover, even if one of the derived keys leaks, all other keys are still secure as long as the master key is still kept secret. Finally, this approach is composable with MPC signing protocols as the output of the MPC key derivation protocol is already in secret-shared form. However, due to the high complexity, the protocol is more involved to implement and requires more computation and communication to run compared to the other approaches.

Secret nonce-based key derivation

Another approach to MPC-friendly key derivation is via a secret nonce. The general idea is that a secret master nonce N is kept and used for key derivation. Concretely, key shareholder i derives a key share 𝘬_𝑑i for path 𝑑 by computing n_𝑑 = H(n + 𝑑), where H is a hash function, and 𝘬_𝑑i  = 𝘬_i + n_𝑑. The derived secret key is then 𝘬_𝑑 = 𝘬 + n_𝑑 and the corresponding public key is K_𝑑 = K + G * n_𝑑 where G is the elliptic curve generator point. We note that without knowledge of the secret nonce n the derived keys are not relatable to each other. However, once the secret nonce and one of the keys leak, all other keys can be computed by an attacker.

A variation of this approach is also used by Coinbase WaaS. In their implementation, they additionally employ a distributed VRF to ensure verifiability of the derived key 𝘬_𝑑 .

Public nonce-based key derivation

The simplest approach to MPC-friendly key derivation uses a public nonce such as a simple counter for each derived key. Concretely, keyshare holder i derives a key share 𝘬_𝑑i for path 𝑑 by computing 𝘬_𝑑i = 𝘬_i  + 𝑑. The derived secret key is then 𝘬_𝑑 = 𝘬 + 𝑑 and the corresponding public key is K_𝑑 = K + G * 𝑑. In this case, we note that there is no hidden relation between any of the keys. This also means that it is easy for external parties to correlate different public keys back to the same account, and therefore, no privacy guarantees are made for the user.

Implementation in Web3Auth

We have seen 3 approaches for MPC-friendly key derivation ranging from high security and complexity to low security and complexity.

At Web3Auth, we took the intermediate approach based on a secret nonce. Our solution ensures that external parties cannot easily correlate derived accounts of the same master account, thereby ensuring the privacy of our users. On the other hand, we decided to optimize for less complexity and better performance compared to running the key derivation fully in MPC. We believe this is an optimal trade-off for most of our user base.

If you want to learn more about multiple key derivation or have any questions regarding the topic, don’t hesitate to reach out!