Thoughts on overall architecture and possible alternatives

Here are some of my lightly-organized thoughts that were discussed on the 2024-09-02 call. Posting here as promised for record and for further consideration. These musings mostly arise from the initial question of why Derive-Local and Derive-Remote need to be distinct.

Does HDK-Root really need to be distinct from HDK-Derive-Local? Could HDK-Root(pk_device, seed) = HDK-Derive-Local((pk_device, sk_device, seed), 0) ? [Discussed on 2024-09-02 call: The distinction may not be strictly necessary, but it's useful to only need to inject the root public key once.]

I still don't really get why HDK makes a difference between HDK-Root and HDK-Derive-Local, Multi-party sequence diagrams could greatly help illustrate how the pieces fit together.

Oooh, the sk output from HDK-Derive-Local isn't actually the private key corresponding to pk, just a shard (blinding factor) of it? In that case it's been very confusing to me to call it sk instead of "blinding factor" or "key handle" or something like that.

Perhaps the hierarchy could be remodeled from a tree of (pk, sk) pairs to a tree of blinding factors? HDK-Derive-Local (re-)blinds both pk and sk with the same factor simultaneously. So maybe an appropriate abstraction for the blinding scheme could be something like:

BL-Generate-Keypair() -> (pk, sk)
BL-Derive-Blinding-Factor(seed, DST) -> tau
BL-Blind-Public-Key(pk, tau) -> pk'
BL-Blind-Private-Key(sk, tau) -> sk'
BL-Combine-Blinding-Factors(tau1, tau2) -> tau' Compute tau' such that BL-Blind-Public-Key(pk, tau') = BL-Blind-Public-Key(BL-Blind-Public-Key(pk, tau1), tau2) and BL-Blind-Private-Key(sk, tau') = BL-Blind-Private-Key(BL-Blind-Private-Key(sk, tau1), tau2)

Can't include the DST in Blind-Public-Key/Blind-Private-Key anymore, since that would break the algebra. tau becomes a BL-specific type (scalars in the EC case) instead of arbitrary octet strings.

Anyway, with this abstraction, I think the HDK tree could be something like:

(tau0, salt0) = HDK-Root(pk_device, seed)
(tau1, salt1) = HDK-Derive((tau0, salt0), index)

HDK-Root(pk_device, seed):
    salt = expand(serialize(pk_device), ID || seed, Ns)
    tau = BL-Derive-Blinding-Factor(salt, DST)
    return (tau, salt)

HDK-Derive((tau, salt), index):
    salt' = expand(salt || I2OSP(index, 4), ID, Ns)
    tau_tmp = BL-Derive-Blinding-Factor(salt', DST)
    tau' = BL-Combine-Blinding-Factors(tau, tau_tmp)
    return (tau', salt')

HDK-Derive-Public-Key((tau, salt), pk_device):
    return BL-Blind-Public-Key(pk_device, tau)

HDK-Derive-Private-Key((tau, salt), sk_device):
    return BL-Blind-Private-Key(sk_device, tau)

Maybe the distinction between Derive-Local and Derive-Remote disappears? I don't think the taus really need to be kept secret?

Not sure how this would interact with HDK-Authenticate, though. Maybe this makes it harder to implement the blinding using ECDH for multiplication, for example?

What is the advantage of the hierarchical tree structure? What capabilities does this introduce that you don't get with just a single level of blinded keys? [Discussed on 2024-09-02 call: Might enable some selective proofs of association that aren't as straightforward in a flat structure?]

Thanks @emlun!

Does HDK-Root really need to be distinct from HDK-Derive-Local? Could HDK-Root(pk_device, seed) = HDK-Derive-Local((pk_device, sk_device, seed), 0) ? [Discussed on 2024-09-02 call: The distinction may not be strictly necessary, but it's useful to only need to inject the root public key once.]

I still don't really get why HDK makes a difference between HDK-Root and HDK-Derive-Local, Multi-party sequence diagrams could greatly help illustrate how the pieces fit together.

Oooh, the sk output from HDK-Derive-Local isn't actually the private key corresponding to pk, just a shard (blinding factor) of it? In that case it's been very confusing to me to call it sk instead of "blinding factor" or "key handle" or something like that.

Indeed, sk is a blinding factor. The logic of the current naming is that pk is the associated public key if you take device_pk as the curve base point. But indeed let’s look for clearer naming, how about “bk = blinding key” as in draft-irtf-cfrg-signature-key-blinding-06?

The reason for having a separate HDK-Root is that the method to obtain the first blinded public key from device_pk will depend on the implementation, e.g. additive versus multiplicative combination on elliptic curves. If we indeed change the BL abstraction, this can be simplified.

As for diagrams, these will be needed indeed. For now possibly some of the slides help clarify: “Deriving the root HDK”, “Next: remote HDK derivation for batch issuance”.

Perhaps the hierarchy could be remodeled from a tree of (pk, sk) pairs to a tree of blinding factors? HDK-Derive-Local (re-)blinds both pk and sk with the same factor simultaneously. So maybe an appropriate abstraction for the blinding scheme could be something like:

BL-Generate-Keypair() -> (pk, sk)

BL-Derive-Blinding-Factor(seed, DST) -> tau

BL-Blind-Public-Key(pk, tau) -> pk'

BL-Blind-Private-Key(sk, tau) -> sk'

BL-Combine-Blinding-Factors(tau1, tau2) -> tau' Compute tau' such that BL-Blind-Public-Key(pk, tau') = BL-Blind-Public-Key(BL-Blind-Public-Key(pk, tau1), tau2) and BL-Blind-Private-Key(sk, tau') = BL-Blind-Private-Key(BL-Blind-Private-Key(sk, tau1), tau2)

Can't include the DST in Blind-Public-Key/Blind-Private-Key anymore, since that would break the algebra. tau becomes a BL-specific type (scalars in the EC case) instead of arbitrary octet strings.

This BL abstraction would make defining HDK less awkward indeed. The only disadvantage seems to be exposing a new datatype for blinding keys. The change however does not seem to leak new sensitive information to users, since BL already exposed private keys.

I would like to keep the abstraction consistent with ARKG – is it feasible to update ARKG accordingly?

I‘d just propose some minor changes:

BL-Generate-Key-Pair() -> (pk, sk) (not used in HDK)
BL-Derive-Blinding-Key(msg, DST) -> bk
BL-Blind-Public-Key(pk, bk) -> pk'
BL-Blind-Private-Key(sk, bk) -> sk' (not used in HDK)
BL-Combine-Blinding-Keys(bk1, bk2) -> bk'

Would BL-Combine-Blinding-Keys(a, b) not always equal BL-Blind-Private-Key(a, b) in practice? Or is this just the case for elliptic curves?

Anyway, with this abstraction, I think the HDK tree could be something like:

(tau0, salt0) = HDK-Root(pk_device, seed)
(tau1, salt1) = HDK-Derive((tau0, salt0), index)

HDK-Root(pk_device, seed):
    salt = expand(serialize(pk_device), ID || seed, Ns)
    tau = BL-Derive-Blinding-Factor(salt, DST)
    return (tau, salt)

HDK-Derive((tau, salt), index):
    salt' = expand(salt || I2OSP(index, 4), ID, Ns)
    tau_tmp = BL-Derive-Blinding-Factor(salt', DST)
    tau' = BL-Combine-Blinding-Factors(tau, tau_tmp)
    return (tau', salt')

HDK-Derive-Public-Key((tau, salt), pk_device):
    return BL-Blind-Public-Key(pk_device, tau)

HDK-Derive-Private-Key((tau, salt), sk_device):
    return BL-Blind-Private-Key(sk_device, tau)

I like this simplification. Note that HDK-Derive-Private-Key may still not be needed as the blinded private key is never used directly. And instead of HDK-Derive-Public-Key, how about HDK-Blind-Public-Key, to better reflect what operation happens?

Maybe the distinction between Derive-Local and Derive-Remote disappears? I don't think the taus really need to be kept secret?

This would break compatibility with ARKG no? The current HDK design enables sharing the public HDK-Seed-Remote output with an issuer, who can then perform ARKG-Derive-Public-Key on it without needing to know that HDK was applied.

If we drop this compatibility goal, indeed the issuer could just generate new blinding keys and pass these along with the issued attestations. But note that the wallet must then call BL-Combine-Blinding-Keys to obtain the blinding key relative to pk_device. The issuer must not be able to determine pk_device because otherwise this would become a correlation handle.

Edit 2024-09-16: If we go this path, I would still argue for keeping using a KEM as in ARKG to pass on the blinding key, to ensure that only the issuer and the wallet learn it, and not some proxy in between. Once blinding keys are exposed, the original device public key can be used for correlation.

Not sure how this would interact with HDK-Authenticate, though. Maybe this makes it harder to implement the blinding using ECDH for multiplication, for example?

This does not seem to be a problem:

def HDK-Authenticate((bk, salt), sk_device, reader_data):
    P' = EC-Scalar-Mult(reader_data, bk)  # bk as Scalar

    # Compute Z_AB within the secure cryptographic device.
    Z_AB = ECDH-Create-Shared-Secret(sk_device, P')

    return Z_AB

What is the advantage of the hierarchical tree structure? What capabilities does this introduce that you don't get with just a single level of blinded keys? [Discussed on 2024-09-02 call: Might enable some selective proofs of association that aren't as straightforward in a flat structure?]

It would not make a difference for proof of assocation since association is transitive.

It seems to make it easier to model the ARKG-compatible structure of blinding keys. At each node it is possible to create a unique HDK-Seed-Remote output (achieving unlinkability) and derive child nodes using issuer-provided ARKG key handles.

In BIP32 it seems to be used to have cross-wallet standardisation that makes it easier to recover an account structure using just a seed. This goal seems less relevant to EUDI.

I wrote:

Indeed, sk is a blinding factor. The logic of the current naming is that pk is the associated public key if you take device_pk as the curve base point. But indeed let’s look for clearer naming, how about “bk = blinding key” as in draft-irtf-cfrg-signature-key-blinding-06?

But I just realise that in draft-irtf-cfrg-signature-key-blinding-06, the blinding key bk is in practice actually used to derive a blind_ctx value as concat(bk, 0x00, ctx),, where ctx is application context string. So “blinding key” is not the right term here either. Let’s stick with “blinding factor” bf for now.

We still need to decide whether to keep using algebraic bf (scalars) or keep using bk (octet strings) in HDK, depending on the direction for ARKG and its viability as a FIDO2 extension for EUDI.

Sketch for HDK dropping ARKG compatibility and with hierarchies only based on remote key handles:

def HDK-Root(pk_device, seed):
    msg = KMS-Serialize(pk_device)
    ctx = ID || 0x00 || seed
    salt = expand(msg, ctx, Ns)
    return salt

def HDK-Delegate(seed, salt):
    ctx = ID || 0x01 || seed
    (pk_kem, _) = KEM-Derive-Key-Pair(salt, ctx)
    return pk_kem

def HDK-Take(seed, salt, kh):
    ctx = ID || 0x01 || seed
    (_, sk_kem) = KEM-Derive-Key-Pair(salt, ctx)
    bk = KEM-Decaps(sk_kem, kh, ctx)
    return bk

def HDK-Yield(bk, idx):
    msg = bk || I2OSP(idx, 4)
    ctx = ID || 0x02
    okm = expand(msg, ctx, Nk + Ns)
    bf = factor(okm[:Nk])
    salt = okm[Nk:]
    return (bf, salt)

def HDK-Fold(pk_device, seed, path):
    salt = HDK-Root(pk_device, seed)
    def callback((bf, salt), (kh, idx)):
        bk = HDK-Take(seed, salt, kh)
        (bf', salt') = HDK-Yield(bk, idx)
        bf'' = bf match:
            case nil -> bf'
            case bf -> BL-Combine-Blinding-Factors(bf, bf')
        return (bf'', salt')
    (bf, salt') = reduce(path, callback, (nil, salt))
    return (bf, salt')

# Or recursively, and it can probably be made clearer:
def HDK-Fold(pk_device, seed, path):
    salt = HDK-Root(pk_device, seed)
    (kh, idx) :: tail = path
    bk = HDK-Take(seed, salt, kh)
    (bf, salt') = HDK-Yield(bk, idx)
    def fold(path, salt, path):
        path match:
            case nil ->
                return (bf, salt)
            case (kh, idx) :: tail ->
                bk = HDK-Take(seed, salt, kh)
                (bf', salt') = HDK-Yield(bk, idx)
                bf' = BL-Combine-Blinding-Factors(bf, bf')
                return fold(tail, bf', salt')
    return fold(tail, bf, salt')

A document issuer would take a pk_bl = BL-Blind-Public-Key(pk_device, bf_folded) and a pk_kem, and apply KEM-Encaps to generate a kh.

The WSCA would expose a function HDK-Authenticate((sk_device, seed, path), reader_data). Implementations would compute HDK-Fold either within the WSCD as part of a centralised implementation, or distribute the function across a WSCA agent that computes HDK-Fold and wraps WSCD I/O generated using the plain sk_device (#60).

ARKG could be made compatible by adopting the algebraic BL structure.

What do you think?

Update: from the perspective of HDK, focus on the FIDO sign extension https://github.com/w3c/webauthn/pull/2078 and not on ARKG, which will just be one of the algorithms supported by this extension. Maybe assume a BlindSign extension.

sander / hierarchical-deterministic-keys

Thoughts on overall architecture and possible alternatives #59