Skip to main content

Wamu: A Protocol for Computation of Threshold Signatures by Multiple Decentralized Identities

Technical Specification

· 23 min read
View as PDF

1. Introduction

This document describes the Wamu protocol which augments a state-of-the-art non-interactive threshold signature scheme (e.g. CGGMP20 [1]) by cryptographically associating each signing party with a decentralized identity. This is achieved by:

  • Splitting the secret share for each party between the party and the output of a signing operation by its associated decentralized identity, thus making the signing operation a requirement for reconstructing the party's secret share.
  • Adding peer-to-peer decentralized identity authentication to the key generation and signing protocols (and optionally to the key refresh protocol) of the threshold signature scheme.
  • Defining protocols for identity rotation, access structure modification (i.e. share addition and removal and threshold modification) and share recovery that build on top of the above 2 augmentations.

Wamu is designed to operate in a decentralized, trust-minimized and asynchronous setting with:

  • no centralized or trust-based identity infrastructure.
  • signing parties being mainstream consumer devices communicating asynchronously.

NOTE: For interoperability with existing wallet solutions, the only requirement for decentralized identity providers is the ability to compute cryptographic signatures for any arbitrary message in such a way that the output signature is 1) deterministic and 2) can be verified in a non-interactive manner.

2. Preliminaries

The rest of this document describes the Wamu protocol in technical detail. For these descriptions, we'll use the following notation:

  • PP denotes a party.
  • II denotes a decentralized identity.
  • vkvk denotes the verifying key (or address) of a decentralized identity.
  • sksk denotes the secret key of a decentralized identity.
  • Sig\mathtt{Sig} denotes a signing algorithm.
  • Ver\mathtt{Ver} denotes a signature verification algorithm.
  • qq denotes the prime order of the cyclic group of the elliptic curve.
  • S\mathcal{S} denotes the set of verified decentralized identities for all parties.
  • tt denotes the threshold (i.e. the minimum number of signatories required to jointly compute a valid signature using the threshold signature scheme).
  • AA denotes a predefined prefix chosen to ensure that signatures computed for identity authentication cannot be valid transaction signatures.
  • \Vert denotes concatenation using an unambiguous encoding scheme.

NOTE: While the augmenting protocols in this document are described in relation to the current (circa. 2023) state-of-the-art CGGMP20 [1] non-interactive threshold signature scheme for ECDSA signatures, Wamu is a generic protocol that can be adapted to any non-interactive threshold signature scheme (e.g. GG20 [2], CMP20 [3] and FROST20 [4]) that allows for asynchronous communication between signing parties.

3. Share Splitting and Reconstruction

Given a secret share xx for a party PP with an associated decentralized identity II, the share splitting and reconstruction protocol describes how to split xx between PP and the output of a signing operation Sig\mathtt{Sig} by II so that the output of Sig\mathtt{Sig} is required to reconstruct the secret share xx.

This is achieved by generating a message kk (we'll refer to this message as the "signing share") and computing a "sub-share" β\beta (i.e a share of the secret share xx) in such a way that kk needs to be signed by II using Sig\mathtt{Sig} to produce another "sub-share" α\alpha, such that α\alpha and β\beta are shares of xx under Shamir's secret-sharing scheme [5].

NOTE: Share splitting and reconstruction is a single-party localized concern that happens after (and is not related to) the distributed key generation (DKG) protocol of the threshold signature scheme.

3.1. Share splitting

Given a secret share xx as input and access to the decentralized identity II with secret key sksk, the share splitting protocol proceeds as follows:

  1. Sample a random message kk (i.e. the signing share).
  2. Compute a signature (r,s)Sig(sk,k)(r, s) \leftarrow \mathtt{Sig}(sk, k).
  3. Compute the first sub-share of xx as the point α=(r,s)(modq)\alpha = (r, s) \pmod q.
  4. Generate a line LL (i.e a polynomial of degree 1) such that α\alpha is a point on the line and xx is the constant term (i.e. Polynomial Interpolation [6])
  5. Compute another point β\beta from LL such that βα\beta \neq \alpha, β\beta becomes the second sub-share of xx.
  6. Erase both α\alpha and LL from memory.
  7. Return the signing share kk and the sub-share β\beta.

3.2. Share reconstruction

Given a signing share kk and a sub-share β\beta as input (i.e. the outputs of the share splitting protocol in section 3.1) and access to the decentralized identity II with secret key sksk, the share reconstruction protocol proceeds as follows:

  1. Compute a signature (r,s)Sig(sk,k)(r, s) \leftarrow \mathtt{Sig}(sk, k).
  2. Compute a sub-share α\alpha as the point α=(r,s)(modq)\alpha = (r, s) \pmod q.
  3. Generate the line LL by performing Polynomial Interpolation [6] using α\alpha and β\beta as inputs.
  4. Compute xx as the constant term of LL.
  5. Erase both α\alpha and LL from memory.
  6. Return xx as the secret share.

NOTE: The signature parameters rr and ss in (r,s)Sig(sk,k)(r, s) \leftarrow \mathtt{Sig}(sk, k) are already computed modulo qq. We use the notation α(r,s)(modq)\alpha \leftarrow (r, s) \pmod q for the sub-share to make it clear (at a glance) that the sub-shares are computed using finite field arithmetic.

4. Threshold Signature Scheme Augmentations

The general approach for augmenting threshold signature protocols (i.e. key generation and signing - and optionally key refresh) is for each party to sign a non-interactive replay resistant challenge during the first round of communication to prove that it currently controls the associated decentralized identity. The other parties then verify the challenge signature at the beginning of the next round or identify the culprit and halt.

Key generation and key refresh protocols typically include a commitment to secret and random values in their first round while signing includes an arbitrary message, so either a commitment (e.g. for key generation and key refresh) or the message (e.g. for signing) is unambiguously concatenated with a protocol specific prefix and the current timestamp to generate a non-interactive replay resistant challenge.

NOTE: While most threshold signature schemes don't define a key refresh protocol (e.g. GG20 [2] and FROST20 [4]), it is relatively straightforward to derive such a protocol from a standard proactive secret sharing scheme like HJKY95 [7]. However, for applications that require support for access structure modification, it is preferable to derive a key refresh protocol from a share redistribution scheme like DJ97 [8] or WW01 [9], as the latter are more flexible and allow for both proactive security and access structure changes (see section 6 for details and additional considerations).

NOTE: While general (t,n)(t, n) sharing (and specifically the case where t<nt < n) is not formally specified in CGGMP20 [1], it can be derived in a relatively straightforward manner based on GG18 [10] (and GG20 [2]) for the key generation and signing protocols (as described in section 1.2.8 of CGGMP20 [1]) and HJKY95 [7] (or WW01 [9]) for the key refresh protocol. In particular, this entails performing tt-out-of-nn Feldman's verifiable secret sharing [11] of the secret shares for key generation (as described in section 2.8 and phase 2 of section 3.1 in GG20 [2] and similarly in section 2.6 and phase 2 of section 4.1 in GG18 [10]) or refresh shares for key refresh (with some modifications as described in sections 3.3 and 3.4 of HJKY95 [7] or in section 4 of WW01 [9]), and transforming (t,n)(t, n) to (t,t+1)(t, t+1) shares (using the appropriate Lagrangian coefficients) for pre-signing and signing (as described in section 3.2 in GG20 [2] and similarly in section 4.2 in GG18 [10]).

4.1. Key Generation

Follow the key generation protocol described in section 3.1 and figure 5 of CGGMP20 [1] to generate ECDSA secret shares with the following modifications:

  1. At the end of Round 1, broadcast 2 additional parameters for each PiP_i associated with the decentralized identity IiI_i with verifying key vkivk_i and secret key skisk_i as follows:
    • The decentralized identity verifying key vkivk_i.
    • The current UTC timestamp Δ\Delta.
    • The signature σiSig(ski,AΔVi)\sigma _i \leftarrow \mathtt{Sig}(sk_i, A \Vert \Delta \Vert V_i).
  2. At the beginning of Round 2, for each PiP_i, verify σj\sigma _j from all PjP_j where jij \neq i:
    • Verify that vkiSvk_i \in \mathcal{S} or report the culprit and halt.
    • Verify σj\sigma _j by checking that the output of Ver(vkj,AΔVj,σj)\mathtt{Ver}(vk_j, A \Vert \Delta \Vert V_j, \sigma _j) is valid or report the culprit and halt.
  3. After the Output phase, follow the share splitting protocol in section 3.1 to split secret share xix_i into a signing share kik_i and a sub-share βi\beta _i for each party PiP_i.
  4. Modify Stored State for each PiP_i as follows:
    • Don't store xix_i.
    • Add vkivk_i, kik_i and βi\beta _i.

4.2. Signing

Follow the signing protocol described in sections 4.2 and 4.3 and figure 8 of CGGMP20 [1] to generate an ECDSA signature with the following modifications:

  1. Before Round 1, for each party PiP_i, follow the share reconstruction protocol in section 3.2 to reconstruct secret share xix_i.
  2. At the end of Round 1, for each PiP_i associated with the decentralized identity IiI_i with verifying key vkivk_i and secret key skisk_i, send 2 additional parameters to all PjP_j where jij \neq i as follows:
    • The decentralized identity verifying key vkivk_i.
    • The current UTC timestamp Δ\Delta.
    • The signature σiSig(ski,AΔm)\sigma _i \leftarrow \mathtt{Sig}(sk_i, A \Vert \Delta \Vert m).
  3. At the beginning of the Output phase, verify σj\sigma _j from all PjP_j where jij \neq i as follows:
    • Verify that vkiSvk_i \in \mathcal{S} or report the culprit and halt.
    • Verify that tt is within the current epoch for identity authenticated requests or report the culprit and halt.
    • Verify σi\sigma _i by checking that the output of Ver(vki,AΔm,σi)\mathtt{Ver}(vk_i, A \Vert \Delta \Vert m, \sigma _i) is valid or report the culprit and halt.

4.3. Key Refresh

Follow the key refresh protocol described in section 3.2 and figure 6 of CGGMP20 [1] to generate new ECDSA secret shares with the following modifications:

  1. At the end of Round 1, broadcast 2 additional parameters for each PiP_i associated with the decentralized identity IiI_i with verifying key vkivk_i and secret key skisk_i as follows:
    • The decentralized identity verifying key vkivk_i.
    • The current UTC timestamp Δ\Delta.
    • The signature σiSig(ski,AΔVi)\sigma _i \leftarrow \mathtt{Sig}(sk_i, A \Vert \Delta \Vert V_i).
  2. At the beginning of Round 2, for each PiP_i, verify σj\sigma _j from all PjP_j where jij \neq i as follows:
    • Verify that vkiSvk_i \in \mathcal{S} or report the culprit and halt.
    • Verify σi\sigma _i by checking that the output of Ver(vkj,AΔVj,σj)\mathtt{Ver}(vk_j, A \Vert \Delta \Vert V_j, \sigma _j) is valid or report the culprit and halt.
  3. After the Output phase, follow the share splitting protocol in section 3.1 to split the new secret share xix_i^\ast into a new signing share kik_i^\ast and a new sub-share βi\beta _i^\ast for each party PiP_i.
  4. Modify Stored State for each PiP_i as follows:
    • Don't store xix_i^\ast.
    • Replace kik_i with kik_i^\ast and βi\beta _i with βi\beta _i^\ast.

5. Identity Authentication and Quorum Approval

5.1. Identity Authenticated Request

Decentralized identity authenticated requests allow parties to perform or request actions based on their associated decentralized identity.

5.1.1. Identity Authenticated Request Initiation

To initiate an identity authenticated request with a command CC from a party PiP_i associated with decentralized identity IiI_i with verifying key vkivk_i and secret key skisk_i:

  1. Read the current UTC timestamp Δ\Delta.
  2. Compute the signature σSig(ski,AΔC)\sigma \leftarrow \mathtt{Sig}(sk_i, A \Vert \Delta \Vert C).
  3. Broadcast CC, vkivk_i, Δ\Delta and σ\sigma.

5.1.2. Identity Authenticated Request Verification

To verify an identity authenticated request with a command CC from a party PiP_i given its associated decentralized identity verifying key vkivk_i, a timestamp Δ\Delta, a signature σ\sigma and a set of verified decentralized identities for all other parties S\mathcal{S} as input:

  1. Verify that vkiSvk_i \in \mathcal{S} or report the culprit and halt.
  2. Verify that tt is within the current epoch for identity authenticated requests or report the culprit and halt.
  3. Verify σ\sigma by checking that the output of Ver(vki,AΔC,σ)\mathtt{Ver}(vk_i, A \Vert \Delta \Vert C, \sigma) is valid or report the culprit and halt.

5.2. Identity Challenge

Identity challenges are used to verify that a party controls a decentralized identity.

5.2.1. Identity Challenge Initiation

To issue an identity challenge to a party PiP_i from all verifying parties PjP_j where jij \neq i for a verified request with command CC initiated at timestamp Δ\Delta:

  1. Sample a random vjv_j.
  2. Broadcast vjv_j, CC and Δ\Delta to all parties, such that all parties can compute v=jivjv = \Vert _{j \neq i} \: v_j.

5.2.2. Identity Challenge Response

For a party PiP_i with associated decentralized identity secret key skisk_i, to respond to an identity challenge for a command CC initiated at timestamp Δ\Delta, given vjv_j from all parties PjP_j where jij \neq i:

  1. Compute v=jivjv = \Vert _{j \neq i} \: v_j.
  2. Compute the signature σSig(ski,AΔCv)\sigma \leftarrow \mathtt{Sig}(sk_i, A \Vert \Delta \Vert C \Vert v).
  3. Broadcast CC, vkivk_i, Δ\Delta and σ\sigma to all verifying parties PjP_j.

5.2.3. Identity Challenge Response Verification

To verify an identity challenge response from a party PiP_i for a command CC initiated at timestamp Δ\Delta, given its associated decentralized identity verifying key vkivk_i, a signature σ\sigma and vjv_j from all verifying parties PjP_j where jij \neq i as input:

  1. Compute v=jivjv = \Vert _{j \neq i} \: v_j.
  2. Verify σ\sigma by checking that the output of Ver(vki,AΔCv,σ)\mathtt{Ver}(vk_i, A \Vert \Delta \Vert C \Vert v, \sigma) is valid or report the culprit and halt.

5.3. Identity Rotation

Identity rotation allows any party to change the decentralized identity associated with its secret share.

Identity rotation for a party PiP_i from a decentralized identity IiI_i with verifying key vkivk_i and secret key skisk_i to a decentralized identity IiI_i^ \ast with verifying key vkivk_i^ \ast and secret key skisk_i^ \ast proceeds as follows:

  1. For PiP_i, initiate an "identity-rotation" request by following the protocol in section 5.1.1.
  2. For all PjP_j where jij \neq i:
    • Verify the "identity-rotation" request by following the protocol in section 5.1.2.
    • Initiate an identity challenge for PiP_i by following the protocol in section 5.2.1.
  3. For PiP_i, respond to the identity challenge by following the protocol in section 5.2.2 with the following augmentations:
    • Compute an additional signature σiSig(ski,AΔCv)\sigma _i^ \ast \leftarrow \mathtt{Sig}(sk_i^ \ast, A \Vert \Delta \Vert C \Vert v).
    • Add vkivk_i^ \ast and σi\sigma _i^ \ast to the broadcast parameters.
  4. For all PjP_j where jij \neq i:
    • Verify the identity challenge response from PiP_i by following the protocol in section 5.2.3.
    • Verify that PiP_i controls the new decentralized identity verifying key vkivk_i^ \ast as follows:
      • Compute v=jivjv = \Vert _{j \neq i} \: v_j:
      • Verify σ\sigma ^ \ast by checking that the output of Ver(vki,AΔCv,σ)\mathtt{Ver}(vk_i^ \ast, A \Vert \Delta \Vert C \Vert v, \sigma ^ \ast) is valid or report the culprit and halt.
    • Modify Stored State as follows:
      • Create S\mathcal{S} ^ \ast by replacing vkivk_i with vkivk_i^ \ast in S\mathcal{S}.
      • Replace S\mathcal{S} with S\mathcal{S} ^ \ast.
    • Broadcast confirmation of successful rotation of the verifying key for PiP_i.
  5. For PiP_i, upon receiving confirmation of successful rotation from a quorum of PjP_j:
    • Compute the new signing share kik_i^ \ast and sub-share βi\beta _i^ \ast based on the new decentralized identity IiI_i^ \ast as follows:
      • Compute the secret share xix_i by following the share reconstruction protocol in section 3.2.
      • Follow the share splitting protocol in section 3.1 to split xix_i into a new signing share kik_i^ \ast and a new sub-share βi\beta _i^ \ast based on the new decentralized identity IiI_i^ \ast.
    • Modify Stored State as follows:
      • Replace vkivk_i with vkivk_i^ \ast in S\mathcal{S}.
      • Replace kik_i with kik_i^ \ast.
      • Replace βi\beta _i with βi\beta _i^ \ast.

5.4. Quorum Approved Request

Quorum approved requests allow any verified party to initiate actions that require explicit approval from a quorum of verified parties before execution (e.g. share addition and removal, and threshold modification).

A quorum approved request with a command CC from a party PiP_i associated with decentralized identity IiI_i with verifying key vkivk_i and secret key skisk_i proceeds as follows:

  1. For PiP_i, initiate an identity authenticated request by following the protocol in section 5.1.1.
  2. For all PjP_j where jij \neq i that approve the requested action:
    • Verify the identity authenticated request by following the protocol in section 5.1.2.
    • Initiate an identity challenge for PiP_i by following the protocol in section 5.2.1 with the following augmentations:
      • Compute a signature σjSig(skj,AΔCvj)\sigma _j \leftarrow \mathtt{Sig}(sk_j, A \Vert \Delta \Vert C \Vert v_j).
      • Add vkjvk_j and σj\sigma _j to the broadcast parameters.
  3. For PiP_i, upon receiving an augmented identity challenge from a quorum Sc\mathcal{S} _c such that ScSSct1\mathcal{S} _c \subseteq \mathcal{S} \land |\mathcal{S} _c| \geq t - 1, respond to the identity challenge by following the protocol in section 5.2.2 with the following modifications:
    • At the beginning of the identity challenge response protocol, verify that approvals have been received from a valid quorum of signatories by checking that ScS\exists \, \mathcal{S} _c \subseteq \mathcal{S} such that Sct1|\mathcal{S} _c| \geq t - 1 and vkjSc\forall \, vk_j \in \mathcal{S} _c where jij \neq i, the output of Ver(vkj,AtCvj,σj)\mathtt{Ver}(vk_j, A \Vert t \Vert C \Vert v_j, \sigma _j) is valid or report the culprit and halt.
    • Compute vv as v=jivjv = \Vert _{j \neq i} \: v_j where vjScv_j \in \mathcal{S} _c.
    • Add Sc\mathcal{S} _c to the broadcast parameters.
  4. For all PjP_j where jij \neq i:
    • Verify the augmented identity challenge response from PiP_i by following the protocol in section 5.2.3 with the following modifications:
      • Compute vv as v=jivjv = \Vert _{j \neq i} \: v_j where vjScv_j \in \mathcal{S} _c.
    • Verify that a valid quorum of signatories has approved the request as follows:
      • Verify that Sct1|\mathcal{S} _c| \geq t - 1 or report the culprit and halt.
      • Verify that ScSvkiSc\mathcal{S} _c \subseteq \mathcal{S} \land vk_i \notin \mathcal{S} _c or report the culprit and halt.
      • Verify that vkjSc\forall \, vk_j \in \mathcal{S} _c where jij \neq i, the output of Ver(vkj,AΔCvj,σj)\mathtt{Ver}(vk_j, A \Vert \Delta \Vert C \Vert v_j, \sigma _j) is valid or report the culprit and halt.

6. Access Structure Modification

Access structure modification allows a quorum of verified parties to perform any of the following actions:

  • share addition - issue a secret share to a new party and its associated decentralized identity
  • share removal - revoke the secret share of any party.
  • threshold modification - change the threshold (i.e. change the size of the quorum).

As noted in section 4, most threshold signature schemes don't define a key refresh protocol, and this is also the case for access structure modification protocols. However, it is similarly relatively straightforward to derive a suitable access structure modification protocol from a standard share redistribution scheme like DJ97 [8] or WW01 [9].

In fact, for applications that require support for access structure modification, it is preferable to replace a key refresh protocol based on (or similar to) a proactive secret sharing scheme like HJKY95 [7] (as is the case for CGGMP20 [1] key refresh) with a protocol based on (or similar to) a share redistribution scheme like DJ97 [8] or WW01 [9] as the latter are more flexible and allow for both proactive security and access structure changes.

NOTE: For threshold signature schemes with identifiable aborts (e.g. CGGMP20 [1], GG20 [2] and FROST20 [4]), key refresh protocols should be derived from verifiable share redistribution schemes like WW01 [9] to preserve the same security model.

Therefore, access structure modification can be achieved by following the augmented key refresh protocol described in section 4.3 of this document, with some modifications based on a verifiable share redistribution scheme like WW01 [9] (or similar) as described above. In particular, this entails each party (from a suitable subset of parties) performing a tt ^\prime-out-of-nn ^\prime (where tt ^\prime and nn ^\prime denote the new threshold and new number of parties respectively) Feldman's verifiable secret sharing [11] (with some modifications as described in section 4 of WW01 [9]) of its current secret share (i.e. the output from either key generation or the most recent key refresh) with other parties (in the suitable subset).

6.1. Share Addition

Share addition for a new party PiP_i with associated decentralized identity IiI_i proceeds as follows:

  1. Initiate a quorum approved "share-addition" request by following the protocol in section 5.4.
  2. Follow the augmented key refresh protocol described in section 4.3, with verifiable share redistribution modifications as described above and with PiP_i included as a participant, if the quorum approved request above succeeds.

6.2. Share Removal

Share removal for a party PiP_i with associated decentralized identity IiI_i proceeds as follows:

  1. Initiate a quorum approved "share-removal" request by following the protocol in section 5.4.
  2. Follow the augmented key refresh protocol described in section 4.3, with verifiable share redistribution modifications as described above and without PiP_i, if the quorum approved request above succeeds.

6.3. Threshold Modification

Threshold modification proceeds as follows:

  1. Initiate a quorum approved "threshold-modification" request by following the protocol in section 5.4.
  2. Follow the augmented key refresh protocol described in section 4.3, with verifiable share redistribution modifications as described above, if the quorum approved request succeeds.

7. Share Recovery

Share recovery is only possible if the user's decentralized identity either survived or can be recovered after the disastrous event. In either case, there are two options for share recovery depending on:

  • A quorum of honest parties surviving the disastrous event.
  • A backup (preferably encrypted) of a signing share kk and sub-share β\beta pair on user-controlled secondary or device-independent storage.

7.1. Share recovery with a surviving quorum of honest parties

If a quorum of honest parties survives the disastrous event, share recovery can be accomplished based on peer-to-peer decentralized identity authentication.

Share recovery for a party PiP_i with associated decentralized identity IiI_i with verifying key vkivk_i and secret key skisk_i proceeds as follows:

  1. For PiP_i, Initiate a "share-recovery" request by following the protocol in section 5.1.1.
  2. For all PjP_j where jij \neq i:
    • Verify the "share-recovery" request by following the protocol in section 5.1.2.
    • Initiate an identity challenge for PiP_i by following the protocol in section 5.2.1.
  3. For PiP_i, respond to the identity challenge by following the protocol in section 5.2.2.
  4. For all PjP_j where jij \neq i, verify the identity challenge response from PiP_i by following the protocol in section 5.2.3.
  5. Follow the key refresh protocol described in section 4.3 if all verifications above pass.

7.2. Share recovery with a backup

7.2.1. Overview of share recovery with a backup

From the share splitting and reconstruction protocol in section 3, we note that for any party PP, the combination of a signing share kk and a sub-share β\beta alone is insufficient to reconstruct the secret share xx. This is because a signature of kk from the decentralized identity II is required to compute the sub-share α\alpha, so that α\alpha and β\beta can then be used to reconstruct LL and compute the secret share xx as the constant term of LL.

Therefore, a signing share kk and sub-share β\beta pair can be safely backed up to user-controlled secondary (e.g. a secondary device or a flash drive) or device-independent storage (e.g. Apple iCloud 1, Google Drive 2, Microsoft OneDrive 3, Dropbox 4 e.t.c) without exposing the secret share xx.

7.2.2. Generating an encrypted backup for share recovery

For increased security, a signature of a standardized phrase can be used as entropy for generating an encryption secret which can then be used to encrypt the signing share kk and the sub-share β\beta using a symmetric encryption algorithm before saving them to back up storage.

Given a standardized phrase uu, a key derivation function H\mathtt{H}, a symmetric encryption algorithm E\mathtt{E}, this proceeds as follows:

  1. Compute the signature σSig(sk,u)\sigma \leftarrow \mathtt{Sig}(sk, u).
  2. Generate the encryption secret ε=H(σ)\varepsilon = \mathtt{H}(\sigma).
  3. Compute the ciphertext for the signing share kk as kc=Eenc(k,ε)k_c = \mathtt{E} _{enc}(k, \varepsilon).
  4. Compute the ciphertext for the sub-share β\beta as βc=Eenc(β,ε)\beta _c = \mathtt{E} _{enc}(\beta, \varepsilon).
  5. Erase both σ\sigma and ε\varepsilon from memory.
  6. Save kck_c and βc\beta _c to backup storage.

7.2.3. Decrypting an encrypted backup

Share recovery would then start by signing this standardized phrase, using the signature to recreate the encryption secret and then decrypting the encrypted backup to retrieve the signing share kk and the sub-share β\beta.

Given a standardized phrase uu, a key derivation function H\mathtt{H}, a symmetric encryption algorithm E\mathtt{E}, the ciphertext for the signing share kck_c and the ciphertext for the sub-share βc\beta _c, this proceeds as follows:

  1. Compute the signature σSig(sk,u)\sigma \leftarrow \mathtt{Sig}(sk, u).
  2. Generate the encryption secret ε=H(σ)\varepsilon = \mathtt{H}(\sigma).
  3. Compute the signing share k=Edec(kc,ε)k = \mathtt{E} _{dec}(k_c, \varepsilon).
  4. Compute the sub-share β=Edec(βc,ε)\beta = \mathtt{E} _{dec}(\beta _c, \varepsilon).
  5. Erase both σ\sigma and ε\varepsilon from memory.
  6. Return the signing share kk and the sub-share β\beta.

7.2.4. Further security and usability considerations for share recovery with a backup

For further improved security and usability, the signing share kk can be prefixed with a custom message that alerts the user to the purpose of the signature. This can help reduce the effectiveness of an adversary that gains access to the backup and tries to trick the user into signing mm.

Additionally, it's possible to rerun the share splitting protocol to generate a new pair of a signing share kk^ \ast and a sub-share β\beta ^ \ast such that kkk^ \ast \neq k, ββ\beta ^ \ast \neq \beta and LLL^ \ast \neq L to be specifically used for backup and recovery. This gives us the option to have separate signing shares for backup and recovery with customized prefixes that make it clear to the user that they're signing a backup signing share.

Lastly, the "backup" signing share kk^ \ast can be generated based on user input (e.g. a passphrase or security questions) removing the need for it to be backed up together with a sub-share β\beta ^ \ast but instead relying on the user to provide this input during recovery as a security-usability tradeoff.

Acknowledgements

This work is funded by a grant from the Ethereum Foundation 5.

References

[1]
Canetti, R., Gennaro, R., Goldfeder, S., Makriyannis, N. and Peled, U. 2020. UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (Virtual Event, USA, 2020), 1769–1787. https://eprint.iacr.org/2021/060.
[2]
Gennaro, R. and Goldfeder, S. 2020. One Round Threshold ECDSA with Identifiable Abort. Cryptology ePrint Archive, Paper 2020/540. https://eprint.iacr.org/2020/540.
[3]
Canetti, R., Makriyannis, N. and Peled, U. 2020. UC Non-Interactive, Proactive, Threshold ECDSA. Cryptology ePrint Archive, Paper 2020/492. https://eprint.iacr.org/2020/492.
[4]
Komlo, C. and Goldberg, I. 2020. FROST: Flexible Round-Optimized Schnorr Threshold Signatures. Cryptology ePrint Archive, Paper 2020/852. https://eprint.iacr.org/2020/852.
[5]
Shamir, A. 1979. How to Share a Secret. Commun. ACM. 22, 11 (Nov. 1979), 612–613. DOI:https://doi.org/10.1145/359168.359176.
[6]
Wikipedia. Polynomial interpolation: https://en.wikipedia.org/wiki/Polynomial_interpolation. Accessed: 2023-05-12.
[7]
Herzberg, A., Jarecki, S., Krawczyk, H. and Yung, M. 1995. Proactive Secret Sharing Or: How to Cope With Perpetual Leakage. Advances in Cryptology — CRYPT0’ 95 (Berlin, Heidelberg, 1995), 339–352. https://doi.org/10.1007/3-540-44750-4_27.
[8]
Desmedt, Y. and jodi, S.J. 1997. Redistributing Secret Shares to New Access Structures and Its Applications. Technical Report #ISSE-TR-97-01. George Mason University, Fairfax, VA 22030, Department of Computer Science. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=af623000d63f4c0251936b35c057a4d46581b4de.
[9]
Wong, T.M. and Wing, J.M. 2001. Verifiable Secret Redistribution. Technical Report #ADA458508. Carnegie Mellon University, Pittsburgh, PA 15213, School of Computer Science. https://apps.dtic.mil/sti/tr/pdf/ADA458508.pdf.
[10]
Gennaro, R. and Goldfeder, S. 2018. Fast Multiparty Threshold ECDSA with Fast Trustless Setup. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (Toronto, Canada, 2018), 1179–1194. https://eprint.iacr.org/2019/114.pdf.
[11]
Feldman, P. 1987. A Practical Scheme for Non-Interactive Verifiable Secret Sharing. Proceedings of the 28th Annual Symposium on Foundations of Computer Science (USA, 1987), 427–438. https://doi.org/10.1109/SFCS.1987.4.