Constant-time implementation with security proof

[sander]

Discussed during the 2025-01-20 meeting with @mickrau and @emlun: we may replace:

def DeriveBlindingFactor(bk, ctx) =
    HashToScalar(bk || 0x00 || ctx)
def BlindPublicKey(pk, bk, ctx) =
    blind pk using DeriveBlindingFactor(bk, ctx)
def BlindPrivateKey(sk, bf) =
    Combine(sk, bf) mod Order()

with:

def DeriveBlindingFactor(pk, bk, ctx) =
    HashToScalar(bk || 0x00 || SerializeElement(pk) || ctx)
def BlindPublicKey(pk, bk, ctx) =
    blind pk using DeriveBlindingFactor(pk, bk, ctx)
def BlindPrivateKey(sk, bk, ctx, bf) =
    sk' = Combine(sk, bf)
    pk' = ScalarBaseMult(sk')
    Combine(sk', DeriveBlindingFactor(pk', bk, ctx))

Or instead, taking ctx = SerializeElement(pk) || ctx_original as input to BlindPublicKey, this could be reformulated using the original construct, but where the implementation of BlindPrivateKey needs to also provide:

def BlindBlindedPrivateKey(sk, bk, ctx, bf) =
    sk' = Combine(sk, bf)
    pk' = ScalarBaseMult(sk')
    BlindPrivateKey(sk', bk, SerializeElement(pk' || ctx)

That function would inherit the security properties of BlindPrivateKey, such as not leaking information about Combine(sk, bf), making it impossible to form bf in such a way that it leaks information about sk. Furthermore, by including bf in the context over which the blinding factor is derived using a hash, it is infeasible to construct bf in such a way that it cancels the DeriveBlindingFactor output.

This would require no updates to Key Blinding for Signature Schemes, but would require changes to ARKG:

• make ARKG-Derive-Private-Key to accept a bf parameter (default 0 for additive, 1 for multiplicative blinding), which is used to call BlindBlindedPrivateKey
• make ARKG-Derive-Public-Key prefix the application context string with SerializeElement(pk)

[emlun]

I have formulated a potential security proof for this here: https://github.com/Yubico/arkg-rfc/blob/pqarkg-h/pqarkg-h-security/pqarkg-h.pdf

Anyone, please review and comment whether you agree the proof is valid!

[sander]

Thank you @emlun! Some first thoughts in the context of remote HDK.

1. The subordinate party will in practice always use $b=1$ and receive $\mathsf{pk_\Delta}=\mathsf{\Delta.BlindPK}(\mathsf{pk_\Delta^0},b')$ for unknown device public key $\mathsf{pk_\Delta^0}$ and unknown $b'$. We need to keep $b'$ unknown to the subordinate party since otherwise they could unblind $\mathsf{pk_\Delta}$, breaking unlinkability. So the value of $b$ at the subordinate party does not relate to the value of $b'$ at the delegating party. Does this affect the $\mathsf{mkKS}$ security experiment? Should we also have an unlinkability security experiment?
2. The subordinate party will $\mathsf{\Pi.Encaps}$ once and use the result with many values of $\mathsf{aux}\in{0,1,2,\ldots}$. Does this affect the $\mathsf{mkKS}$ security experiment?

[sander]

I agree the proof is valid. While reading, I have proposed several changes in: Yubico/arkg-rfc#31

This addresses 1. I still need to reflect on the unlinkability question but this seems to be higher level than mkKS and possibly out of scope.

[sander]

Re: 1. I’ve reviewed the pku experiment for public-key unlinkability in Wilson’s thesis. In a pqARKG-H adaptation, we would need to position $b$, either as additional challenger-generated data, or as first oracle input. The first makes most sense for a model of the intended application, since only the delegating party will know $b$ and the subordinate works with $b=1$. In that case, since the proof seems to rely on PRF pseudorandomness alone, pqARKG-H would be pku-secure.

If instead we would allow the adversary to set $b$, the argument for pku could be similar to the one for mkKS. I don’t think it’s worthwhile to define that for pqARKG-H, but maybe we should discuss the limitation?

Additionaly, Stebila & Wilson 2024 critique the pku model for not exposing the oracle-generated KEM ciphertext to the adversary, rendering them underpowered, but I don’t foresee consequences for the HDK use case. Our need for unlinkability gears towards third parties who anyway do not invoke any ARKG functions.

Re: 2. The critique above seems to apply to mkKS as well. By not returning $k$ in line 5 of $\mathcal O'_\mathsf{pk}$ we deny the adversary the opportunity keep the encapsulation fixed and find an advantageous value of $\mathsf{aux}$. I have not checked if this would affect the security proof for either pqARKG or pqARKG-H, but I expect not, given PRF properties which cancel any chance for the adversary to use any algebraic relation.