The Asynchronous Remote Key Generation (ARKG) algorithm

1.2.1. Notation

The following notation is used throughout this document:¶

• The symbol || represents octet string concatenation.¶

• When literal text strings are to be interpreted as octet strings, they are encoded using UTF-8.¶

• Elliptic curve operations are written in multiplicative notation: * denotes point multiplication, i.e., the curve group operation; ^ denotes point exponentiation, i.e., repeated point multiplication; and + denotes scalar addition modulo the curve order.¶

• Random(min_inc, max_exc) represents a cryptographically secure random integer greater than or equal to min_inc and strictly less than max_exc.¶

1.2.2. Instance parameters

ARKG is composed of a suite of other algorithms. The parameters of an ARKG instance are:¶

• BL: An asymmetric key blinding scheme [Wilson], consisting of:¶

  • Function BL-Generate-Keypair() -> (pk, sk): Generate a blinding key pair.¶

    No input.¶

    Output consists of a blinding public key pk and a blinding secret key sk.¶

  • Function BL-Blind-Public-Key(pk, tau) -> pk_tau: Deterministically compute a blinded public key.¶

    Input consists of a blinding public key pk and a blinding factor tau.¶

    Output consists of the blinded public key pk_tau.¶

  • Function BL-Blind-Secret-Key(sk, tau) -> sk_tau: Deterministically compute a blinded secret key.¶

    Input consists of a blinding secret key sk and a blinding factor tau.¶

    Output consists of the blinded secret key sk_tau.¶

  • Integer L_bl: The length of the blinding factor tau in octets.¶

  pk and pk_tau are opaque octet strings of arbitrary length. tau is an opaque octet string of length L_bl. The representations of sk, sk_tau and L_bl are an undefined implementation detail.¶

  See [Wilson] for definitions of security properties required of the key blinding scheme BL.¶

• KEM: A key encapsulation mechanism, consisting of the functions:¶

  • KEM-Generate-Keypair() -> (pk, sk): Generate a key encapsulation key pair.¶

    No input.¶

    Output consists of public key pk and secret key sk.¶

  • KEM-Encaps(pk) -> (k, c): Generate a key encapsulation.¶

    Input consists of an encapsulation public key pk.¶

    Output consists of a shared secret k and an encapsulation ciphertext c.¶

  • KEM-Decaps(sk, c) -> k: Decapsulate a shared secret.¶

    Input consists of encapsulation secret key sk and encapsulation ciphertext c.¶

    Output consists of the shared secret k on success, or an error otherwise.¶

  pk, k and c are opaque octet strings. The representation of sk is an undefined implementation detail.¶

  See [Wilson] for definitions of security properties required of the key encapsulation mechanism KEM.¶

• MAC: A message authentication code (MAC) scheme, consisting of:¶

  • Function MAC-Tag(k, m) -> t: Generate a message authentication tag for a given message using a given key.¶

    Input consists of the shared MAC key k and the message m.¶

    Output consists of the MAC tag t.¶

  • Function MAC-Verify(k, m, t) -> { 0, 1 }: Verify a message authentication tag.¶

    Input consists of the shared MAC key k, the message m and the MAC tag t.¶

    Output is 1 if and only if MAC-Tag(k, m) = t.¶

  • Integer L_mac: The length of the MAC key k in octets.¶

  k is an opaque octet string of length L_mac. m and t are opaque octet strings of arbitrary length. The representation of L_mac is an undefined implementation detail.¶

  See [Frymann2020] for definitions of security properties required of the message authentication code scheme MAC.¶

• KDF: A variable-length key derivation function with the signature: KDF(info, ikm, L) -> okm¶

  Input consists of a domain separation parameter info, input key material ikm and output length L.¶

  Output consists of output key material okm of length L in octets.¶

  info and ikm are opaque octet strings of arbitrary length. okm is an opaque octet string of length L. L is an integer with undefined representation.¶

  See [Frymann2020] for definitions of security properties required of the key derivation function KDF.¶

A concrete ARKG instantiation MUST specify the instantiation of each of the above functions and values.¶

The output keys of the BL scheme are also the output keys of the ARKG instance as a whole. For example, if BL-Blind-Public-Key and BL-Blind-Secret-Key output ECDSA keys, then the ARKG instance will also output ECDSA keys.¶

Instantiations MUST satisfy the following compatibility criteria:¶

• The output shared secret k of KEM-Encaps and KEM-Decaps is a valid input key material ikm of KDF.¶

• Output key material okm of length L_bl of KDF is a valid input blinding factor tau of BL-Blind-Public-Key and BL-Blind-Secret-Key.¶

  It is permissible for some KDF outputs to not be valid blinding factors, as long as this happens with negligible probability - see section [Design Rationale: Using a MAC].¶

• Output key material okm of length L_mac of KDF is a valid input MAC key k of MAC-Tag(k, m) and MAC-Verify(k, m, t).¶

  It is permissible for some KDF outputs to not be valid MAC keys, as long as this happens with negligible probability - see section [Design Rationale: Using a MAC].¶

We denote a concrete ARKG instance by the pattern ARKG-BL-KEM-MAC-KDF, substituting the chosen instantiation for the BL, KEM, MAC and KDF parts. Note that this pattern cannot in general be unambiguously parsed; implementations MUST NOT attempt to construct an ARKG instance by parsing such a pattern string. Concrete ARKG instances MUST always be identified by lookup in a registry of fully specified ARKG instances. This is to prevent usage of algorithm combinations that may be incompatible or insecure.¶

1.2.3. The function ARKG-Generate-Seed

This function is performed by the delegating party. The delegating party generates the ARKG seed pair (pk, sk) and keeps the private seed sk secret, while the public seed pk is provided to the subordinate party. The subordinate party will then be able to generate public keys on behalf of the delegating party.¶

``` ARKG-Generate-Seed() -> (pk, sk) Options: BL The key blinding scheme chosen for the ARKG instantiation. KEM The key encapsulation mechanism chosen for the ARKG instantiation.¶

Inputs: None

Output:
  (pk, sk)  An ARKG seed key pair with public key pk and private key sk.

The output (pk, sk) is calculated as follows:¶

(pk_kem, sk_kem) = KEM-Generate-Keypair() (pk_bl, sk_bl) = BL-Generate-Keypair() pk = (pk_kem, pk_bl) sk = (sk_kem, sk_bl) ```¶

1.2.4. The function ARKG-Derive-Public-Key

This function is performed by the subordinate party, which holds the ARKG public seed pk = (pk_kem, pk_bl). The resulting public key pk' can be provided to external parties to use in asymmetric cryptography protocols, and the resulting key handle kh can be used by the delegating party to derive the private key corresponding to pk'.¶

This function may be invoked any number of times with the same public seed, in order to generate any number of public keys.¶

``` ARKG-Derive-Public-Key((pk_kem, pk_bl), info) -> (pk', kh) Options: BL The key blinding scheme chosen for the ARKG instantiation. KEM The key encapsulation mechanism chosen for the ARKG instantiation. MAC The MAC scheme chosen for the ARKG instantiation. KDF The key derivation function chosen for the ARKG instantiation. L_bl The length in octets of the blinding factor tau of the key blinding scheme BL. L_mac The length in octets of the MAC key of the MAC scheme MAC.¶

Inputs:
    pk_kem     A key encapsulation public key.
    pk_bl      A key blinding public key.
    info       Optional context and application specific information
                 (can be a zero-length string).

Output:
    pk'        A blinded public key.
    kh         A key handle for deriving the blinded
                 secret key sk' corresponding to pk'.

The output (pk, sk) is calculated as follows:

(k, c) = KEM-Encaps(pk_kem)
tau = KDF("arkg-blind" || 0x00 || info, k, L_bl)
mk  = KDF("arkg-mac"   || 0x00 || info, k, L_mac)
tag = MAC-Tag(mk, c || info)

pk' = BL-Blind-Public-Key(pk_bl, tau)
kh = (c, tag) ```

If this procedure aborts due to an error, for example because KDF returns an invalid tau or mk, the procedure can safely be retried with the same arguments.¶

1.2.5. The function ARKG-Derive-Secret-Key

This function is performed by the delegating party, which holds the ARKG private seed (sk_kem, sk_bl). The resulting secret key sk' can be used in asymmetric cryptography protocols to prove possession of sk' to an external party that has the corresponding public key.¶

This function may be invoked any number of times with the same private seed, in order to derive the same or different secret keys any number of times.¶

``` ARKG-Derive-Secret-Key((sk_kem, sk_bl), kh, info) -> sk' Options: BL The key blinding scheme chosen for the ARKG instantiation. KEM The key encapsulation mechanism chosen for the ARKG instantiation. MAC The MAC scheme chosen for the ARKG instantiation. KDF The key derivation function chosen for the ARKG instantiation. L_bl The length in octets of the blinding factor tau of the key blinding scheme BL. L_mac The length in octets of the MAC key of the MAC scheme MAC.¶

Inputs:
    sk_kem     A key encapsulation secret key.
    sk_bl      A key blinding secret key.
    kh         A key handle output from ARKG-Derive-Public-Key.
    info       Optional context and application specific information
                 (can be a zero-length string).

Output:
    sk'        A blinded secret key.

The output sk' is calculated as follows:

(c, tag) = kh
k = KEM-Decaps(sk_kem, c)
mk = KDF("arkg-mac" || 0x00 || info, k, L_mac)

If MAC-Verify(mk, c || info, tag) = 0:
    Abort with an error.

tau = KDF("arkg-blind" || 0x00 || info, k, L_bl)
sk' = BL-Blind-Secret-Key(sk_bl, tau) ```

Errors in this procedure are typically unrecoverable. For example, KDF might return an invalid tau or mk, or the tag may be invalid. ARKG instantiations SHOULD be chosen in a way that such errors are impossible if kh was generated by an honest and correct implementation of ARKG-Derive-Public-Key. Incorrect or malicious implementations of ARKG-Derive-Public-Key do not degrade the security of a correct and honest implementation of ARKG-Derive-Secret-Key. See also section [Design Rationale: Using a MAC].¶

1.3.1. Using elliptic curve arithmetic for key blinding

Instantiations of ARKG whose output keys are elliptic curve keys can use elliptic curve arithmetic as the key blinding scheme BL. Frymann2020 [Wilson] This section defines a general formula for such instantiations of BL.¶

Let crv be an elliptic curve. Then the BL parameter of ARKG may be instantiated as follows:¶

• Elliptic curve points are encoded to and from octet strings using the procedures defined in sections 2.3.3 and 2.3.4 of SEC 1 [SEC1].¶

• Elliptic curve scalar values are encoded to and from octet strings using the procedures defined in sections 2.3.7 and 2.3.8 of SEC 1 [SEC1].¶

• N is the order of crv.¶

• G is the generator of crv.¶

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

sk = Random(1, N)
pk_tmp = G^sk
If pk_tmp equals the point at infinity, abort with an error.
pk = pk_tmp

TODO: Also reject G?

BL-Blind-Public-Key(pk, tau) -> pk_tau¶

If tau = 0 or tau >= N, abort with an error.
pk_tau_tmp = pk * (G^tau)
If pk_tau_tmp equals the point at infinity, abort with an error.
pk_tau = pk_tau_tmp

TODO: Also reject G?

BL-Blind-Secret-Key(sk, tau) -> sk_tau¶

If tau = 0 or tau >= N, abort with an error.
sk_tau_tmp = sk + tau
If sk_tau_tmp = 0, abort with an error.
sk_tau = sk_tau_tmp

TODO: Also reject 1? ```

1.3.2. Using ECDH as the KEM

Instantiations of ARKG can use ECDH [RFC6090] as the key encapsulation mechanism. This section defines a general formula for such instantiations of KEM.¶

Let crv be an elliptic curve used for ECDH. Then the KEM parameter of ARKG may be instantiated as follows:¶

• Elliptic curve points are encoded to and from octet strings using the procedures defined in sections 2.3.3 and 2.3.4 of SEC 1 [SEC1].¶

• Elliptic curve coordinate field elements are encoded to and from octet strings using the procedures defined in sections 2.3.5 and 2.3.6 of SEC 1 [SEC1].¶

• Elliptic curve scalar values are encoded to and from octet strings using the procedures defined in sections 2.3.7 and 2.3.8 of SEC 1 [SEC1].¶

• ECDH(pk, sk) represents the compact output of ECDH [RFC6090] using public key (curve point) pk and secret key (exponent) sk.¶

• N is the order of crv.¶

• G is the generator of crv.¶

``` KEM-Generate-Keypair() -> (pk, sk)¶

sk = Random(1, N)
pk_tmp = G^sk
If pk_tmp equals the point at infinity, abort with an error.
pk = pk_tmp

TODO: Also reject G?

KEM-Encaps(pk) -> (k, c) (pk', sk') = KEM-Generate-Keypair()¶

k = ECDH(pk, sk')
c = pk'

KEM-Decaps(sk, c) -> k¶

pk' = c
k = ECDH(pk', sk) ```

1.3.3. Using both elliptic curve arithmetic for key blinding and ECDH as the KEM

If elliptic curve arithmetic is used for key blinding and ECDH is used as the KEM, as described in the previous sections, then both of them MAY use the same curve or MAY use different curves. If both use the same curve, then it is also possible to use the same public key as both the key blinding public key and the KEM public key. [Frymann2020]¶

TODO: Caveats? I think I read in some paper or thesis about specific drawbacks of using the same key for both.¶

1.3.4. Using HMAC as the MAC

Let Hash be a cryptographic hash function. Then the MAC parameter of ARKG may be instantiated using HMAC [RFC2104] as follows:¶

``` MAC-Tag(k, m) -> t¶

t = HMAC-Hash(K=k, text=m)

MAC-Verify(k, m, t) -> { 0, 1 }¶

t' = HMAC-Hash(K=k, text=m)
If t = t':
    return 1
Else:
    return 0 ```

1.3.5. Using HKDF as the KDF

Let Hash be a cryptographic hash function. Then the KDF parameter of ARKG may be instantiated using HKDF [RFC5869] as follows:¶

``` KDF(info, ikm, L) -> okm¶

PRK = HKDF-Extract with the arguments:
    Hash: Hash
    salt: not set
    IKM: ikm

okm = HKDF-Expand with the arguments:
    Hash: Hash
    PRK: PRK
    info: info
    L: L ```

1.4.1. ARKG-P256-ECDH-P256-HMAC-SHA256-HKDF-SHA256

The identifier ARKG-P256-ECDH-P256-HMAC-SHA256-HKDF-SHA256 represents the following ARKG instantiation:¶

• BL: Elliptic curve arithmetic as described in section [Using elliptic curve arithmetic for key blinding] with the parameter:¶

  • crv: The NIST curve secp256r1 [SEC2].¶

• KEM: ECDH [RFC6090] as described in section [Using ECDH as the KEM] with the parameter:¶

  • crv: The NIST curve secp256r1 [SEC2].¶

• MAC: HMAC as described in section [Using HMAC as the MAC] with the parameter:¶

  • Hash: SHA-256 [FIPS 180-4].¶

• KDF: HKDF as described in section [Using HKDF as the KDF] with the parameter:¶

  • Hash: SHA-256 [FIPS 180-4].¶

• L_bl: 32¶

• L_mac: 32¶