# Key Derivation for Batch Issuance
by Philipp-Florens Lehwalder, TU Darmstadt

> As the currently proposed approach to cope with linkability of SD-JWT credential presentations by the [German Architecture Proposal](https://gitlab.opencode.de/bmi/eudi-wallet/eidas-2.0-architekturkonzept/-/blob/main/architecture-proposal.md), credentials shall be only used once (or per relying party) such that the issuer issues a batch of multiple *credential instances* of the same credential type. As each of them has to be bound to a unique public key, this approach causes an overhead for the wallet to maintain many different key pairs for the same credential. Ideally, only one key pair should be managed and all others for the instances should be derived from the master key pair while being compatible to the smartphone’s secure element.
>

## Batched Key Derivation using a Wallet Seed

In this approach, the wallet instructs the Secure Element (SE) to generate a "master" ECDSA key pair for this credential type. The wallet then generates and sends a secret seed along the master public key during the batch issuance process to the issuer. Using the seed, the issuer derives single credential instance public keys such that each public key is unlinkable from each other. Doing so removes the need for the wallet from managing a dedicated key-pair for each credential instance along with a Proof of Possession (PoP) (as well as the corresponding verification for the issuer) but instead just manage a single master key pair.

## ECDSA Refresher

- ECDSA Algorithms

**Key-Generation**: $(sk,pk)=(x,X)=(x,xG)$ with $x\leftarrow \mathbb{Z}_p$

**Signing**: Let $m$ be the message to be signed

1. Compute $c\leftarrow H(m1,m2...)$
2. Sample nonce $k\leftarrow \mathbb{Z}_p$
1. Compute $R\leftarrow kG$
2. Set $r=R.x$
3. Compute $s\leftarrow(c+x\cdot r)\cdot k^{-1}$
4. Output signature $\sigma=(r,s)$

**Verification:** Given $\sigma ,m$, and $X$

- Check if $s\cdot R = h(m) G+ r X$

## 📲 Issuance

The issuer wants to issue $n$ credential instances $cred_1,...,cred_n$ to the holder’s wallet. The SE of the holder’s device generated a ECDSA master key pair for this credential type by sampling a random $x\in \mathbb{Z}_p$, and $X\leftarrow xG$ such that $(sk,pk):=(x,X)$. They then proceed as follows:

1. The wallet submits a OS-specific key attestation for $pk$ proving that it is hardware-backed
2. The wallet generates a secret seed $s\in\{0,1\}^\lambda$
3. The issuer derives $n$ one-time public keys by computing $a_i\leftarrow H(s,i)$ for $i\in[n]$ and $pk_i'\leftarrow a_i \cdot pk$ and then includes $pk_i'$ in credential instance $cred_i$, which are sent to the wallet
4. The wallet verifies the received credential instances and securely stores them


## 🪪 Presentation

Upon a presentation request including some nonce $nonce$ from a relying party (RP) to the wallet, the first wallet decides on a unused credential instance $cred_i$ and generates a fresh PoP as follows:

1. Compute hash of the nonce $\bar{c}\leftarrow H(nonce)$ and the blinding value $a_i \leftarrow H(s,i)$
2. Request an ECDSA signature on $c\leftarrow a_i^{-1}\cdot \bar{c}$ w.r.t to the master $pk$ from the TPM
3. Given the signature $\bar{\sigma}=(\bar{s},r)$ from the SE, the wallet computes $s\leftarrow a_i\cdot \bar{s}$ and sends the signature $\sigma_{PoP}=(s,r)$ back to the RP

Note that $\sigma_{PoP}$ is a valid signature on the $nonce$ for the one-time public key $pk'_i=H(s,i)\cdot pk$ that is valid for $cred_i$.

### ✅ Correctness of the Signature

Given $\sigma_{PoP}=(s,r)$ and let $a_i=H(s,i)$, then we have:

$$
s=a_i \cdot \bar{s} = a_i \cdot (c+x\cdot r)k^{-1} \\ = a_i\cdot (a_i^{-1}\cdot \bar{c} +x\cdot r)k^{-1} =(\bar{c}+a_i\cdot x\cdot r) k^{-1}
$$

Therefore, $\sigma_{PoP}$ is a valid signature on the message $nonce$ with respect to the instance public key $pk'_i=a_i\cdot pk=a_i X$


---

### In OpenID4VC

Example of how a credential request could look like for requesting a batch of credential instances of a credential type, whereas the instance keys are derived from a single public key given a seed:

{
  "credential_encryption_jwk": "...",
  "credential_response_encryption_alg": "...",
  "credential_response_encryption_enc": "...",
  "credential_requests": [
    // Requesting Issuance of 100 instances of a credential bound to derived keys given by the seed.
    {
      "credential_identifier" : "BaseID-2024",
      "num_instances": 100,
      "key_derivation": {
        "derivation_type": "deriv-256",
        "key_derivation_seed": "..."
      },
      "proof": {
          "proof_type": "jwt",
          "jwt": "..."
        }
    }
  ]
}