10.62. DD 62: PQ Refresh Protocol

10.62.1. Summary

This document specifies a change to GNU Taler’s refresh protocol that provides post-quantum resistance through hash-based cryptography and deterministic signatures, eliminating reliance on Diffie-Hellman operations, for the key derivation for the fresh coin from a dirty coin.

10.62.2. Motivation

The current refresh protocol uses cryptographic primitives vulnerable to quantum attacks to derive the key material for a fresh coin from the key of the dirty coin. The rational for the elaborate derivation in first place is to ensure taxability: When original and new coins remain linked (by the owner of the original coin), passing coin outside the Taler protocols is discouraged.

This redesign:

1. Removes DH operations from refresh derivation

2. Uses deterministic signatures for ownership proofs

3. Derives key material from (unforgeable) signatures

4. Maintains backward compatibility with other parts of the protocol stack

10.62.3. Requirements

• PQ-resistant refresh key derivation without computational hardness assumptions

• Preservation of unlinkability between old/new coins (except for coin owner)

• Compatibility with existing denomination types

• Minimal bandwidth/storage overhead

10.62.4. Proposed Solution

10.62.4.1. RefreshDerive Algorithm

The core mechanism uses two hash functions and deterministic signatures to derive the key material of a fresh coin from the old coin:

# Notation:
# r = random seed, cs = dirty coin secret, Cp = dirty coin public key
# pkD = denomination public key

def RefreshDerive(r, cs, Cp, pkD):
    t = Hash1a("Refresh", Cp, r)
    s = SignDeterministic(cs, t)
    x = Hash1b(s)
    b = Hash2(s)
    c2_s, C2_p = KeyGen(x)
    m = Blind(C2_p, b, pkD)
    return (s, c2_s, C2_p, m)

Key Changes to the existing RefreshDerive:

1. Proof of ownership: s proves ownership through signature, without DH

2. Key derivation: x derived through hashing of the signature

The hash functions Hash1x might be the same, but can be pair-wise different. However, the hash function Hash2 must be different from all of the others.

Note that the value r in the algorithm itself is a public value and can be considered as a kind of a commitment (“I’m going to sign this value”) by the dirty coin. Actual secret is the signature which needs to be disclosed during the reveal-part of the refresh operation.

A variant of this algorithm that is suitable for retrieving a batch of n fresh coins from a dirty coin is as follows:

# Notation:
# r = random dees, cs = dirty coin's secret, Cp = dirty coin's public key
# pkD[] = array of denomination public keys,
# meta = additional information, f.e. the index in a cut-and-choose
def RefreshDeriveBatch(r, cs, Cp, pkDs: list[denomPublicKey], meta):
    t = Hash1a("Refresh", Cp, r, pkDs, meta)
    s = SignDeterministic(cs, t)
    for i, pkD in enumerate(pkDs):
        x[i] = Hash1b(s, i) # Note: use one HKDF for all i
        b[i] = Hash2(s, i)  # Note: use one HKDF for all i
    for i, pkD in enumerate(pkDs):
        c2_s[i], C2_p[i] = KeyGen(x[i])
        m[i] = Blind(C2_p[i], b[i], pkD)
    return (s, c2_s, C2_p, m)

Note that the above deriviation will need to be done κ times with κ - 1 of the signatures s being checked by the exchange as part of the reveal state of the cut-and-choose protocol. Again, each of the κ values r is a public value and can be considered as a kind of a commitment (“I’m going to sign this value”) by the dirty coin. The actual secrets are the κ signatures s which need to be disclosed during the reveal-part of the refresh operation.

10.62.4.2. Protocol Modifications

Here is a short description of the main steps, with only one fresh coin being requested. We will provide further details, once the related paper [1] is published.

1. Melting/Commit Phase:

   • Client chooses a master (public) seed r and derives κ nonces r_1, ... r_κ.

   • Client generates, using RefreshDeriveBatch, κ*n blinded coin planchets m[1][1],...,m[1][n],...,m[κ][1],...,m[κ][n] from the nonces

   • Sends dirty coin public key Cp, seed r, all m[i][j] and fresh coin denomination selections pkD[1],...pkD[n] to the exchange, with signature σ_c made with the dirty coins’ private key cs over the request.

   • Exchange verifies the request.

   • Exchange calculates h_m[i] = H(m[i][1],...,m[i][n]) for all i from 1...κ

   • Exchange calculates H_m = H(h_m[1],...,h_m[κ])

   • Exchange calculates rc = H(r, pkD[], H_m, meta, <maybe more>)

   • Exchange chooses γ from 1...κ and signs all m[γ][], resulting in σ[γ][]. This is done now as the exchange may later have deleted (or lost) its private signing key.

   • Exchange persists rc → (r, γ, pkD[], H_m, h_m[γ], σ[γ][], σ_c), deducts the cost for the operation from the old coin balance (in the same database transaction) and returns γ to the client.

2. Reveal Phase:

   • Client discloses together with h_m all except the γ-th (secret) signatures s[1],...,s[κ] from the κ calls to RefreshDeriveBatch.

   • Exchange derives r_i from r and verifies each signature s[i] over Hash1a("Refresh", C_p, r_i, pkDs).

   • Exchange reconstructs the blinded coins m'[i][] for i != γ.

   • Exchange calculates h'_m[i] = H(m'[i][]) for all i != γ.

   • Exchange calculates H'_m = H(h'_m[1],...,h_m[γ],...h'_m[κ]).

   • Exchange verifies rc == H(r, pkD[], H'_m, ...) equality.

   • Exchange returns σ[γ][] on success.

It is worth noting that, in contrast to the existing refresh protocol, the client sends all n*κ tuples m[][] already in the commitment phase. This is necessary such that the exchange can sign the request with a valid denomination key at the moment of melting. This ensures idempotency of the melting/commit request and that caries over to the reveal phase.

Also note, as described above, the master seed r for the refresh operation is a public value and can be considered a commitment (“I’m going to sign this value”) made by the dirty coin. The actual secrets are the signatures which are reveal in the second phase.

Note that for the Linking protocol, given the dirty coin’s public key, the Exchange simply returns the master seed r and the dirty coins’ signature σ_c over the original refresh request. The owner of the private key of the dirty coin can then replay the refresh protocol and can be sure that the master seed was of its own origin. Furthermore, the coin history endpoint must already return this information (so that clients can verify the old coin history about the refresh), thus obsoleting the need for a separate “/link” endpoint.

10.62.4.3. Database Changes

Not taking sharding and coinstraints into account, the table layout will look basically like this (names might change):

SQL table layout for refresh

Field	Type	Description
refresh_id	BIGINT	autoincremented identity of the record
rc	BYTEA	refresh commitment h_m, serving as primary key
timestamp	INT8	execution date of the refresh
amount	taler_amount	amount with fee of the refresh
old_coin_pub	BYTEA	old coin’s public key Cp
old_coin_sig	BYTEA	old coin’s signature over the refresh request
old_age_com_h	BYTEA	old coin’s hash of age commitment, if applicable
noreveal_index	SMALLINT	the γ for cut-and-choose, chosen by the exchange
planchets_h	BYTEA	the hash over all blinded coin envelopes m[][]
selected_h	BYTEA	the hash over only the selected blinded envelopes m[γ][]
refresh_seed	BYTEA	the master seed for the refresh, the r above
blinding_seed	BYTEA	the master seed for CS nonces
cs_r_values	BYTEA[]	the pairs of R-Values for CS signatures
cs_r_choices	INT8	the bitvector representing the chosen public R-Values
denom_serials	INT8[]	the row ID’s of the denominations in the DB
denom_sigs	BYTEA[]	the (blinded) denom signatures σ[γ][]

10.62.4.4. API endpoints

A new /melt request takes a NewMeltRequest as request body, see below. As in the existing melting/commit phase, it updates the old coin balance and chooses a random γ for the cut-and-choose protocol. Taler uses a global parameter κ for the cut-and-choose component of the protocol, for which this request is the commitment. Thus, various arguments are given κ-times in this step. At present κ is always 3.

200 OK:

The request was successful. The response body is MeltResponse in this case.

403 Forbidden:

One of the signatures (by the old coin or the denomination signature over the old coin) is invalid.

404 Not found:

The exchange does not recognize the denomination key as belonging to the exchange, or it is past the legal expiration time (and thus forgotten entirely). If the denomination key is unknown, the response will be a DenominationUnknownMessage.

409 Conflict:

The operation is not allowed as the coin has insufficient residual value, or because the same public key of the coin has been previously used with a different denomination. Which case it is can be decided by looking at the error code (TALER_EC_EXCHANGE_GENERIC_INSUFFICIENT_FUNDS or TALER_EC_EXCHANGE_GENERIC_COIN_CONFLICTING_DENOMINATION_KEY). The response is MeltForbiddenResponse in both cases.

410 Gone:

The requested denomination key is not yet or no longer valid. It either before the validity start, past the expiration or was revoked. The response is a DenominationGoneMessage. Clients must evaluate the error code provided to understand which of the cases this is and handle it accordingly.

10.62.4.5. Wire Formats

Modified melt request structure:

interface NewMeltRequest {
   // The old coin's public key
   old_coin_pub: CoinPublicKey;

   // Hash of the denomination public key of the old coin, to determine total coin value.
   old_denom_pub_h: HashCode;

   // The hash of the age-commitment for the old coin. Only present
   // if the denomination has support for age restriction.
   old_age_commitment_h?: AgeCommitmentHash;

   // Signature over the old coin public key by the denomination.
   old_denom_sig: DenominationSignature;

   // Amount of the value of the old coin that should be melted as part of
   // this refresh operation, including melting fee.
   value_with_fee: Amount;

   // Array of n new hash codes of denomination public keys
   // for the new coins to order.
   denoms_h: HashCode[];

   // Seed from which the nonces for the n*κ coin candidates are derived
   // from.
   refresh_seed: HashCode;

   // Master seed for the Clause-Schnorr R-value
   // creation. Must match the /blinding-prepare request.
   // Must not have been used in any prior melt request.
   // Must be present if and only if one of the fresh coin's
   // denominations is of type Clause-Schnorr.
   blinding_seed?: BlindingMasterSeed;

   // κ arrays of n entries for blinded coin candidates,
   // each matching the respective entries in denoms_h.
   //
   // Note: These are essentially the m_i values in the RefreshDeriveBatch
   // function.
   coin_evs: CoinEnvelope[κ][];

   // Signature by the old coin over TALER_RefreshMeltCoinAffirmationPS.
   confirm_sig: CoinSignature;

}

TODO: definition of CoinSignature

// TODO: this needs to be fully expanded into a new interface
type CoinSignature = string;

TODO: explain /reveal-melt endpoint.

interface NewMeltRevealRequest {
   // The refresh commitment corresponding to the previous call to /melt
   // This is the Hash over:
   //   1. refresh_seed
   //   2. hash of all pairs of R-values, if applicable, skip otherwise
   //   3. denominations in order
   //   4. amount_with_fee
   //   5. κ*n blinded planchet hashes (which include denomination information),
   //      depths first: [0..n)[0..n)[0..n)
   rc: RefreshCommitmentHash;

   // The disclosed κ-1 signatures by the old coin's private key,
   // over Hash1a("Refresh", Cp, r, i), where Cp is the melted coin's public key,
   // r is the public refresh nonce from the metling step and i runs over the
   // _disclosed_ κ-1 indices.
   signatures: CoinSignature[κ-1];

   // IFF the denomination of the old coin had support for age restriction,
   // the client MUST provide the original age commitment, i. e. the
   // vector of public keys, or omitted otherwise.
   // The size of the vector MUST be the number of age groups as defined by the
   // Exchange in the field .age_groups of the extension age_restriction.
   age_commitment?: Edx25519PublicKey[];
}

10.62.5. Security Analysis

TODO

10.62.6. Drawbacks

TODO

10.62.7. Migration Strategy

TODO

10.62.8. Discussion/Q&A

TODO

10.62.9. References

[1]

Work by Jonathan Levin et al., TU Eindhoven. Reference be added here once published