# Homogeneous Key Derivation

To securely implement threshold signing and hierarchical key derivation, the following changes are necessary. With these changes, Lit Protocol can maintain a root key and rotate that key and not necessarily rotate any sub key.

NOTE: Some testing will be done to ensure viability.

Security considerations:

The security of a single signing key $\widetilde{d}$ still depends on protecting the nonce.

## Notation

| Name | Description |
| -------- | -------- |
| $\mathcal{C}$ | An elliptic curve |
| $p$ | Field modulus in $\mathcal{C}$ |
| $q$ | Subgroup order in $\mathcal{C}$ |
| $\mathbb{G}$ | The set of points in $\mathcal{C}$ of order $p$ |
| $1_{\mathbb{G}}$ | The point at infinity |
| $\mathbb{G}^*$ | The set of points in $\mathcal{C}$ of order $p$ excluding the point at infinity $1_\mathbb{G}$ |
| $P$ | Base point or generator in $\mathbb{G}^*$ |
| ${\mathbb{Z}}$ | The ring of integers modulo $q$ |
| ${\mathbb{Z}}^*$ | The ring of non-zero integers modulo $q$ |
|$$\xleftarrow{\$} \mathcal{S}$$|Uniform randomly sampled integer in $\mathbb{Z}^*$|
|$\mathcal{H}_{\mathbb{Z}}$|Hash an arbitrary length byte sequence to a value in $\mathbb{Z}^*$|
|$e$|A tweak value in $\mathbb{Z}^*$|

## Setup

1. Master secret key $$\{d, d'\} \xleftarrow{\$} \{\mathbb{Z}^*,\mathbb{Z}^*\}$$
2. Master public key ${D, D'} = \{dP, 'dP\}$
3. The tweak is computed $e = \mathcal{H}_{\mathbb{Z}}(id)$.
4. $id$ is an identifier.

For a given "tweak" $e \in \mathbb{Z}^*$, the corresponding derived secret key is $\widetilde{d} = d + e.d'$, and the corresponding public key is $\widetilde{D} = D+eD'$.

In a threshold setting ${d, d'}$ are secret shares represented as $\{\widehat{d}, \widehat{d'}\}$ distributed among nodes.

## Signing

1. Input is the message $m$ to be signed with some $id$
2. Derive $e = \mathcal{H}_{\mathbb{Z}}(id)$
3. Compute $\widetilde{d} = d + e.d'$
3. Check $\widetilde{d} \ne 0$ otherwise use different $id$
4. The presignature values $(r', R')$ where $$r' \xleftarrow{\$} \mathbb{Z}^*$$ and $R' = r'P$
5. During presigning phases also compute random number $$\delta \xleftarrow{\$} \mathbb{Z}$$ s.t. $(r, R) = (r' + \delta, R'+\delta P)$
6. Sign $z = \mathcal{H}_{\mathbb{Z}}(m)$ using $\widetilde{d}$
7. Output signature $\sigma = \{r, s\}$

### Alternative

$\delta$ can be computed using $\mathcal{H}_{\mathbb{Z}}(R')$ but security would be somewhat weaker but still acceptable.

## Verify

1. Derive $e = \mathcal{H}_{\mathbb{Z}}(id)$
2. Compute $\widetilde{D} = D+eD'$
3. Check $\widetilde{D} \ne 1_{\mathbb{G}}$, otherwise fail due to invalid $id$
4. Use $\widetilde{D}$ to verify signature

## Proposal

1. DKG generates say 10+ keys instead of just 2. So instead of d and d' we'd have, d0, d1, ..., d10. This allows for up to 9 child keys to be compromised before the root keys must be rotated. If we go higher than obviously we have a better threshold but more keys to manage.
1. Compute the tweak 'e' involves hashing the path to 64 bytes then reducing by the subgroup order mod q. This should minimize biases in the tweak.
1. The child key is computed as d0.e^0 + d1.e^1 + d2.e^2 + d3.e^3... like a polynomial. This algorithm is simple so we don't have to derive multiple tweaks especially if the alternative uses XOF's where the squeeze operation is just as expensive as scalar multiplication.
1. During the presigning phase, each party contributes an additional random value.
1. When signing, hash all of those values + the message + other context info to get the rerandomization value for signing.