taler-docs

062-pq-refresh.rst (14628B)

---

 DD 62: PQ Refresh Protocol
 ##########################
 
 Summary
 =======
 This document specifies a change to GNU Taler's refresh protocol that provides
 post-quantum resistance through hash-based cryptography and unique
 signatures, eliminating reliance on Diffie-Hellman operations, for the key
 derivation for the fresh coin from a dirty coin.
 
 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 unique signatures for ownership proofs
 3. Derives key material from (unforgeable) signatures
 4. Maintains backward compatibility with other parts of the protocol stack
 
 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
 
 Proposed Solution
 =================
 
 RefreshDerive Algorithm
 ^^^^^^^^^^^^^^^^^^^^^^^^^
 
 The core mechanism uses two hash functions and unique signatures to
 derive the key material of a fresh coin from the old coin:
 
 .. sourcecode:: python
 
     # 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 = SignUnique(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:
 
 .. sourcecode:: python
 
     # 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 = SignUnique(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.
 
 
 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.
 
 
 Database Changes
 ^^^^^^^^^^^^^^^^
 
 Not taking sharding and coinstraints into account, the table layout will look
 basically like this (names might change):
 
 .. table:: SQL table layout for refresh
    :align: left
 
    ==============  ============  ================================================
    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 ``σ[γ][]``
    ==============  ============  ================================================
 
 
 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.
 
   :http:statuscode:`200 OK`:
     The request was successful.  The response body is `MeltResponse` in this case.
   :http:statuscode:`403 Forbidden`:
     One of the signatures (by the old coin or the denomination signature over
     the old coin) is invalid.
   :http:statuscode:`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`.
   :http:statuscode:`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.
   :http:statuscode:`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.
 
 
 Wire Formats
 ^^^^^^^^^^^^
 
 Modified melt request structure:
 
 .. ts:def:: NewMeltRequest
 
     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 <eddsa-coin-pub>` 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*kappa`` 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;
 
        // kappa 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[kappa][];
 
        // Signature by the old `coin <coin-priv>` over `TALER_RefreshMeltCoinAffirmationPS`.
        confirm_sig: CoinSignature;
 
     }
 
 
 TODO: definition of ``CoinSignature``
 
 .. ts:def:: CoinSignature
 
    // TODO: this needs to be fully expanded into a new interface
    type CoinSignature = string;
 
 
 TODO: explain /reveal-melt endpoint.
 
 .. ts:def:: NewMeltRevealRequest
 
    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. kappa*n blinded planchet hashes (which include denomination information),
       //      depths first: [0..n)[0..n)[0..n)
       rc: RefreshCommitmentHash;
 
       // The disclosed kappaκ-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_ kappaκ-1 indices.
       signatures: CoinSignature[kappa-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[];
 
       // NOTE: THIS FIELD IS WORK-IN-PROGRESS
       // The old coin signs H(rc, noreveal_index).  This value MUST be stored by the
       // exchange and provided as part of the coin's history.  That way, the wallet
       // can be sure that the exchange hasn't altered the nonreveal_index when the
       // wallet does an idempotent melt request.
       noreveal_sig: CoinSignature;
    }
 
 Security Analysis
 =================
 
 TODO
 
 Drawbacks
 =========
 
 TODO
 
 Migration Strategy
 ==================
 
 TODO
 
 Discussion/Q&A
 ==============
 
 TODO
 
 
 References
 ==========
 .. [1] Work by Jonathan Levin et al., TU Eindhoven. Reference be added here once published