VOLE-ACT

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 23 April 2027.¶

Copyright Notice

Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

• WARNING This document specifies a cryptographic protocol that has not yet undergone significant security analysis. It's not yet suitable for real world applications. Implement at your own risk.¶

Modern web services face a fundamental tension between operational needs and user privacy. Services need to implement rate limiting to prevent abuse, charge for API usage to sustain operations, and allocate computational resources fairly. However, traditional approaches require tracking user identities and creating detailed logs of user behavior, raising significant privacy concerns in an era of increasing data protection awareness and regulation.¶

An Anonymous Credit Token (ACT) resolves this tension by enabling credit-based systems without user tracking: an Issuer can grant a Client a token worth some number of credits, and the Client can later spend those credits anonymously, in whole or in part, without the Issuer being able to link the spend to the issuance or to any other spend by the same Client.¶

The elliptic-curve construction [EC-ACT] achieves this privacy goal information-theoretically, meaning no attacker, regardless of its computational resources, can link the presentation of a token to its issuance. However, it is based on elliptic curve cryptography, which means a quantum attacker can forge a token by recovering the Issuer's secret key from its public key.¶

This document specifies VOLE-ACT, an ACT that is plausibly fully post-quantum secure. Its design is based on the PoMFRIT blind signature scheme [PoMFRIT], which combines a post-quantum signature scheme with a suitable zero-knowledge proof system and commitment scheme. Specifically, the signer signs a commitment to the message, and the verifier checks a zero-knowledge proof-of-knowledge of the signature and the opening of the commitment. VOLE-ACT generalizes this from a one-time use token to a token with updatable state: the commitment binds a nullifier together with the remaining credits, and each presentation additionally proves that the spend was subtracted correctly and the balance stays in range, with the Issuer re-signing the updated commitment so that every spend chains into the next token.¶

VOLE-ACT uses [UOV] as its signature scheme. Two instantiations of the commitment are defined, one based on the Keccak permutation [FIPS202] and another based on the Multivariate Quadratic (MQ) problem [BFMRSV25]. The latter composes more naturally with UOV, is much simpler to evaluate in zero knowledge, and, with its current parameterization, has significantly lower communication cost than the hash-based variant.¶

• WARNING Adopters should not implement the MQ variant just yet. MQ commitments are understudied, and we don't know if the parameters we've chosen are sufficient for either unlinkability or unforgeability. Our goal for this variant is to give researchers a sense of the parameter regime for which MQ commitments are useful in our application. In particular, if communication cost is at or below hash-based commitments, then their relative simplicity makes them a good choice.¶

Both variants of VOLE-ACT have higher bandwidth cost than [EC-ACT]:¶

1. the Issuer's public key is 45.5 KB, which corresponds to the uov-Ip parameter set for UOV (the MQ instantiation has a larger public key in order to accommodate the commitment parameters);¶

2. the Client uploads 6.9 KB during initial issuance (4.3 KB for the MQ variant); and¶

3. the Client uploads 17.0 KB during a spend (9.0 KB for the MQ variant).¶

In both the initial issuance and a spend, the Issuer's reply is a single UOV signature, which is below a couple of hundred bytes for both instantiations.¶

Unlike [EC-ACT], VOLE-ACT tokens are publicly verifiable, meaning they can be presented to any party with the Issuer's public key. Of course, this has implications for privacy, since the token necessarily reveals the identity of the Moderator that issued it.¶

The remainder of this document is structured as follows. Section 2 defines some conventions and notation. Section 3 provides a high-level overview of the protocol. Section 4 defines the relevant interfaces for the signature scheme, commitment scheme, and proof system used by VOLE-ACT, and provides normative references for their specifications. Section 5 specifies the protocol in terms of a generic commitment scheme; Section 6 gives our two instantiations of the commitment. Finally, Section 7 enumerates some security considerations for implementers and adopters.¶

2. Conventions and Definitions

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

3. Overview

VOLE-ACT makes use of three cryptographic primitives:¶

1. The Unbalanced Oil and Vinegar [UOV] digital signature scheme. The Issuer, such as a MoLE Moderator [ARCHITECTURE], uses a long-lived UOV secret key to issue tokens, and the Client uses the corresponding public key to generate proofs of knowledge.¶

2. The VOLE-in-the-Head (VOLEitH) zero-knowledge proof system, a component of the FAEST digital signature scheme [FAEST].¶

3. A commitment scheme, instantiated either with the Keccak permutation [FIPS202] or with the Multivariate Quadratic (MQ) commitment of [BFMRSV25].¶

A UOV public key is a map P from F_q^n to F_q^m. A UOV signature is a solution s to an equation P(s) = y, where y is called the target and is normally computed by hashing the message to be signed. The UOV secret key is a trapdoor for P that can be used to efficiently sample signatures for a given target.¶

A token is a tuple (nf, t, r, x, s) that binds a nullifier nf to the Client's current state. The state is an effective balance t + x, where t is the credit held by the Client and x is a refund chosen by the Issuer. r is the opening of a commitment c = Com(nf, ctx_iss, t, r) and s is a signature P(s) = Tag(c, x) that certifies the state committed to by c and binds the refund to the state. Here ctx_iss is the issuance context agreed upon out of band by the Client and Issuer.¶

Initially t = T_init, where T_init is a parameter agreed upon out of band by the Client and Issuer, and x = 0. The initial issuance protocol is as follows:¶

1. The Client samples a nullifier nf and an opening r, then constructs a commitment c = Com(nf, ctx_iss, T_init, r) and VOLEitH proof pf_iss of knowledge of the nf, r for which c = Com(nf, ctx_iss, T_init, r). It then sends c, pf_iss to the Issuer.¶

2. The Issuer verifies pf_iss, samples a solution s to P(s) = Tag(c, 0), then sends s to the Client.¶

3. The Client finalizes issuance by checking that P(s) = Tag(c, 0).¶

To spend credits, the Client reveals the nullifier nf for the current state, commits to an updated state, and proves the updated state is consistent with the previous state and the requested spend. It must do so without revealing the current state, as this would allow the Issuer to link the spend to the initial issuance or to a previous spend. To spend d credits from a token with effective balance t + x:¶

1. The Client samples a fresh nullifier nf' and opening r', then constructs a commitment c' = Com(nf', ctx_iss, t', r') to the change t' = t + x - d. It then constructs a VOLEitH proof pf_spend of knowledge of t, r, x, s, nf', t', r' for which:¶

   • the current state was certified by the Issuer, i.e., P(s) = Tag(Com(nf, ctx_iss, t, r), x);¶

   • the updated state is consistent, i.e., c' = Com(nf', ctx_iss, t', r') and t' = t + x - d; and¶

   • the updated state is valid, i.e., t' is at least 0 but no greater than a maximum value specified by the parameters of the protocol.¶

   Finally, the Client sends nf, d, c', pf_spend to the Issuer.¶

2. The Issuer checks that nf has not been spent and verifies pf_spend. It then chooses a refund x', certifies the updated state by sampling a solution s' to P(s') = Tag(c', x'), then sends x', s' to the Client.¶

3. The Client finalizes the spend by checking that P(s') = Tag(c', x'). Its new token is (nf', t', r', x', s').¶

The commitment Com() and tag Tag() are instantiated in one of two ways.¶

In the hash-based variant of VOLE-ACT (Section 6.1), both are instantiated with a single evaluation of the Keccak-p[800,12] permutation [FIPS202]. Similar to TurboSHAKE [RFC9861], this parameterization of Keccak uses half as many rounds as SHA-3. However, its state is also half the size of the state used by either SHA-3 or TurboSHAKE. This helps reduce the size of the VOLEitH proof. See Section 7 for justification.¶

• NOTE The size of the spend proof is dominated by Keccak evaluations, of which there are three: one Tag() and two Com()s. If we can forego the refund feature, then we don't need the Tag() at all. Refunding can be emulated at the protocol level by having the Client and Issuer negotiate the requested spend so that it accounts for the refund.¶

The MQ-based variant of VOLE-ACT (Section 6.2) uses the MQ commitment of [BFMRSV25] to instantiate Com(). The tag function Tag() updates the commitment homomorphically with the refund.¶

• TODO Determine if this homomorphic trick is sound. See Section 7 for discussion.¶

4. Preliminaries

We write stream := SHAKE128(msg) to denote the absorb phase of the SHAKE128 eXtendable Output Function (XOF) on input msg [FIPS202]. The stream object denotes the XOF state. We write out := stream.next(n) to denote squeezing out the next n bytes and assigning them to out in F_256^n.¶

Define KP800(state) as the output of applying Keccak-p[800,12] [FIPS202] to state in F_q^100. Note that this is a non-standard size for the Keccak permutation; see Section 7 for discussion.¶

We write (cpk, csk) := UOV.CompactKeyGen() to denote execution of the compact key generation algorithm of [UOV], Figure 2. Output cpk is the public key and csk is the secret key. The input parameters are omitted and are instead hard-coded to the uov-Ip parameter set (see [UOV], Table 4).¶

We write P := UOV.ExpandPK(cpk) to denote expansion of the public key into the UOV map P : F_q^n -> F_q^m using the procedure in [UOV], Figure 2. Likewise, we write td := UOV.ExpandSK(csk) to denote expansion of the secret key into the trapdoor td for P.¶

We write s := UOV.DerivePreimage(td, t) to denote deriving the preimage of target t under P, i.e., an s for which P(s) = t. Similar to the UOV signing procedure (Figure 2 of [UOV]), the preimage is derived deterministically by hashing the target together with the secret key seed.¶

• TODO(cjpatton) Define preimage sampling precisely. In UOV, the target is: t := Hash(mu || salt)¶

  To compute the preimage, we start by computing a vector v by: v := Expand_v(mu || salt || seed_sk || ctr)¶

  We instead would compute v as: v := Expand_v(t || seed_sk || ctr)¶

We write PKDigest(P) to denote the 32-byte SHAKE256 [FIPS202] digest of the compact public key cpk from which P was expanded, i.e., SHAKE256(cpk) truncated to 32 bytes. It is used to bind a public key to a proof.¶

• NOTE The choice of SHAKE256() is for consistency with the XOF used with our VOLEitH parameters [FAEST].¶

We consider UOV parameters over F_256. That is, for the remainder of this document, we let q = 256.¶

We write pf := VOLEitH.Prove(R, X, W, msg) to denote proving knowledge of a witness W for which the pair (X, W) is in the relation R, where X is the instance, using the VOLE-in-the-Head proof system defined in [FAEST]. We write v := VOLEitH.Verify(R, X, pf, msg) to denote verification of pf under the same relation and instance, where the output v is a bit. The message msg is a byte string agreed upon by the prover and verifier out-of-band. This parameter is optional: if unspecified, it is implicitly defined to be the empty string.¶

In addition to its constraints, each relation R specifies a domain separation tag and an encoding of the instance as a byte string. Internally, the prover binds the tag, instance, and the message to the proof such that the verifier must agree on their values in order to accept. This is analogous to how the message to be signed is bound to the proof in FAEST (Figure 8.2 of [FAEST]).¶

• TODO(cjpatton) Define mu := H_2^0(R.encodeInstance(X) || msg || R.DST) and how it's used in VOLEitH (Figure 8.2, Line 1 of [FAEST]).¶

Relations are specified in the style of Section 3.4 of [SIGMA] as a sequence of constraints. Each constraint is an equation of the instance and witness variables. Unlike [SIGMA], these equations need not be linear: each side of the equation is a polynomial of arbitrary degree. However, because the degree of the polynomial influences the size of the proof, the relation must be designed to balance the size of the witness with the degree of the constraints.¶

Each witness variable is a vector over either F_2 or F_q. In VOLEitH, the witness is committed bit by bit, and the proof implicitly checks that each committed value is in F_2. A variable in F_q^k is therefore committed as 8*k bits, and the relation can use either these bits or the elements of F_q they encode.¶

• TODO(cjpatton) Figure out how to cite [FAEST] more precisely. Ideally it specifies a compiler of constraints into a proof, as in [SIGMA], but this is currently beyond the scope of what the FAEST spec does. The degree of constraints is coupled tightly to the proof generation procedure, which means I think we'll end up pulling some details of the proof construction into this document.¶

5. Protocol Specification

• TODO Specify wire formats for each of the messages. For now we will ignore how things are encoded until we're more certain of the shape of the protocol.¶

  TODO Make all of these algorithms deterministic, passing any randomness they would generate as input. This will make it easier to generate test vectors. We'll also need to plumb this through VOLEitH proving and UOV signing.¶

This section specifies VOLE-ACT in terms of a generic configuration: Section 5.1 defines the various parameters and functions that are determined by a concrete configuration, and Section 6 specifies two concrete configurations, called VOLE-ACT-KP800 and VOLE-ACT-MQ. A deployment MUST fix its configuration for the lifetime of an Issuer key.¶

A global constant VERSION in F_q is defined. Its value SHALL be 0. This constant is used for domain separation and is meant to be kept in sync with revisions to this document. The overall template for domain separation is as follows: the first four bytes of each permutation input identify the protocol; the next byte is the document version (VERSION); the next byte indicates the usage (commit, tag, or MQ map derivation); and the last byte indicates the configuration (KP800 or MQ).¶

The rest of this section is organized as follows: Section 5.2 specifies Issuer key generation; Section 5.3 specifies initial token issuance; and Section 5.4 specifies token spending.¶

Com(nf, ctx_iss, t, r):
  Input:
    - nf: nullifier, in F_q^nf_len
    - ctx_iss: issuance context, in F_q^ctx_len
    - t: credit value, in [2^(8*L)]
    - r: commitment opening, in F_q^r_len
  Output:
    - c: commitment

Tag(c, x):
  Input:
    - c: commitment
    - x: refund, in [2^(8*L)]
  Output:
    - y: UOV target, in F_q^{m_uov}

KeyGen():
  Output:
    - P: a public UOV map from F_q^{n_uov} to F_q^{m_uov}
    - td: a secret UOV trapdoor for P

  Steps:
    1. (cpk, csk) := UOV.CompactKeyGen()
    2. P := UOV.ExpandPK(cpk)
    3. td := UOV.ExpandSK(csk)
    4. return (P, td)

Relation IssueRelation(c, T_init, ctx_iss):
  Instance:
    - c: commitment
    - T_init: agreed initial credit balance, in [1..2^(8*L)]
    - ctx_iss: issuance context, in F_q^ctx_len

  Witness:
    - nf: nullifier, in F_q^nf_len
    - r: commitment opening, in F_q^r_len

  Constraints:
    - c = Com(nf, ctx_iss, T_init, r)

IssueRequest(T_init, ctx_iss):
  Input:
    - T_init: initial credit balance, in [1..2^(8*L)]
    - ctx_iss: issuance context, in F_q^ctx_len

  Output:
    - pending_token: Client state
    - request: issuance request, or INVALID

  Steps:
    1. if T_init = 0: return INVALID
    2. nf <- F_q^nf_len
    3. r  <- F_q^r_len
    4. c  := Com(nf, ctx_iss, T_init, r)
    5. pf_iss := VOLEitH.Prove(
         IssueRelation,         // relation
         (c, T_init, ctx_iss),  // instance
         (nf, r),               // witness
       )
    6. request := (c, pf_iss)
    7. pending_token := (nf, r, T_init, c)
    8. return (pending_token, request)

IssueResponse(td, request, T_init, ctx_iss):
  Input:
    - td: Issuer secret key
    - request: issuance request
    - T_init: initial credit balance, in [1..2^(8*L)]
    - ctx_iss: issuance context, in F_q^ctx_len

  Output:
    - s: Issuer signature, in F_q^{n_uov}, or INVALID

  Steps:
    1. if T_init = 0: return INVALID
    2. (c, pf_iss) := request  // commitment, issuance proof
    3. v := VOLEitH.Verify(
         IssueRelation,         // relation
         (c, T_init, ctx_iss),  // instance
         pf_iss,
       )
    4. if v = 0: return INVALID
    5. s := UOV.DerivePreimage(td, Tag(c, 0))
    6. return s

FinalizeIssue(P, pending_token, s):
  Input:
    - P: Issuer public key
    - pending_token: Client state
    - s: Issuer signature, in F_q^{n_uov}

  Output:
    - token: the issued token, or INVALID

  Steps:
    1. (nf, r, T_init, c) := pending_token
    2. if P(s) != Tag(c, 0): return INVALID
    3. token := (nf, T_init, r, 0, s)
    4. return token

Relation SpendRelation(P, nf, d, c', ctx_iss):
  Instance:
    - P: Issuer public key
    - nf: nullifier of the current state, in F_q^nf_len
    - d: credits to spend, in [2^(8*L)]
    - c': commitment to the updated state
    - ctx_iss: issuance context, in F_q^ctx_len

  Witness:
    - t: credit of the current state, in F_2^(8*L)
    - r: commitment opening of the current state, in F_q^r_len
    - x: refund carried by the current state, in F_2^(8*L)
    - s: Issuer signature over the current state, in F_q^{n_uov}
    - nf': nullifier of the updated state, in F_q^nf_len
    - t': credit of the updated state, in F_2^(8*L)
    - r': commitment opening of the updated state, in F_q^r_len

  Constraints:
    - P(s) = Tag(Com(nf, ctx_iss, t, r), x)  // V1: current state was certified
    - c' = Com(nf', ctx_iss, t', r')         // V2: c' commits to updated state
    - t' = t + x - d                         // V3: credits are conserved
    - t', x, d in [2^(8*L)]                  // V4: credits are in range

SpendRequest(P, token, d, ctx_iss):
  Input:
    - P: Issuer public key
    - token: the token to spend
    - d: credits to spend, in [2^(8*L)]
    - ctx_iss: issuance context, in F_q^ctx_len

  Output:
    - pending_spend: Client state
    - request: spend request, or INVALID

  Steps:
    1.  (nf, t, r, x, s) := token
    2.  if P(s) != Tag(Com(nf, ctx_iss, t, r), x):
          return INVALID              // not issued by P for ctx_iss
    3.  if d > t + x: return INVALID  // insufficient balance
    4.  t'  := t + x - d              // credit of the updated state
    5.  if t' >= 2^(8*L): return INVALID  // change overflows
    6.  nf' <- F_q^nf_len             // nullifier of the updated state
    7.  r'  <- F_q^r_len              // opening of the updated state
    8.  c'  := Com(nf', ctx_iss, t', r')
    9.  pf_spend := VOLEitH.Prove(
          SpendRelation,              // relation
          (P, nf, d, c', ctx_iss),    // instance
          (t, r, x, s, nf', t', r'),  // witness
        )
    10. request := (nf, d, c', pf_spend)
    11. pending_spend := (nf', t', r', c')
    12. return (pending_spend, request)

SpendResponse(P, td, request, ctx_iss, x'):
  Input:
    - P: Issuer public key
    - td: Issuer secret key
    - request: spend request
    - ctx_iss: issuance context, in F_q^ctx_len
    - x': granted refund, in [2^(8*L)]

  Output:
    - response: spend response, or INVALID
    - nf: nullifier of the spent token, in F_q^nf_len
    - d: credits spent, in [2^(8*L)]

  Steps:
    1. (nf, d, c', pf_spend) := request
    2. if d not in [2^(8*L)]: return INVALID
    3. if x' not in [2^(8*L)]: return INVALID
    4. v := VOLEitH.Verify(
         SpendRelation,            // relation
         (P, nf, d, c', ctx_iss),  // instance
         pf_spend,
       )
    5. if v = 0: return INVALID
    6. s' := UOV.DerivePreimage(td, Tag(c', x'))
    7. response := (x', s')
    8. return (response, nf, d)

FinalizeSpend(P, pending_spend, response):
  Input:
    - P: Issuer public key
    - pending_spend: Client state
    - response: spend response

  Output:
    - token: the change token, or INVALID

  Steps:
    1. (nf', t', r', c') := pending_spend
    2. (x', s') := response
    3. if x' not in [2^(8*L)]: return INVALID
    4. if P(s') != Tag(c', x'): return INVALID
    5. token := (nf', t', r', x', s')
    6. return token

6. Instantiations

This section specifies two concrete configurations of VOLE-ACT (Section 5.1): VOLE-ACT-KP800 (Section 6.1) and VOLE-ACT-MQ (Section 6.2).¶

Com(nf, ctx_iss, t, r):
  Input:
    - nf: nullifier, in F_q^nf_len
    - ctx_iss: issuance context, in F_q^ctx_len
    - t: credit value, in [2^(8*L)]
    - r: commitment opening, in F_q^r_len
  Output:
    - c: commitment, in F_q^32

  Steps:
    1. state := "rata" || VERSION || "c0" || r || 0^(25 - r_len) ||
                ctx_iss || <t>_L || nf || 0^(68 - nf_len - ctx_len - L)
    2. c := KP800(state)[0..32]
    3. return c

Tag(c, x):
  Input:
    - c: commitment, in F_q^32
    - x: refund, in [2^(8*L)]
  Output:
    - y: UOV target, in F_q^{m_uov}

  Steps:
    1. state := "rata" || VERSION || "t0" || 0^25 ||
                c || <x>_L || 0^(36 - L)
    2. y := KP800(state)[0..m_uov]
    3. return y

GenerateParameters():
  Output:
    - F: F_q^{n_com} -> F_q^k,
    - G: F_q^{n_com} -> F_q^{m_uov-k}

  Steps:
    1.  u_com := n_com * (n_com + 1) / 2
    2.  stream := SHAKE128("rata" || VERSION || "m1")
    3.  for i in [m_uov]:
    4.    // quadratic part
    5.    M_i := bytesIntoUpper(stream.next(u_com))
    6.    // linear part
    7.    l_i := stream.next(n_com)
    8.    // constant part
    9.    a_i := stream.next(1)[0]
    10.   // affine quadratic map F_q^{n_com} -> F_q
    11.   Q_i(x) := x^T*M_i*x + l_i*x + a_i
    12. F := (Q_0, ..., Q_{k-1})
    13. G := (Q_k, ..., Q_{m_uov-1})
    14. return (F, G)

Com(nf, ctx_iss, t, r):
  Input:
    - nf: nullifier, in F_q^nf_len
    - ctx_iss: issuance context, in F_q^ctx_len
    - t: credit value, in [2^(8*L)]
    - r: commitment opening, in F_q^r_len

  Output:
    - c: commitment, in F_q^{m_uov}

  Steps:
    1. (F, G) := GenerateParameters()
    2. msg := EmbedState(nf, ctx_iss, t)
    3. c := (F(r) + msg) || G(r)
    4. return c

Tag(c, x):
  Input:
    - c: commitment, in F_q^{m_uov}
    - x: refund, in [2^(8*L)]

  Output:
    - y: UOV target, in F_q^{m_uov}

  Steps:
    1. refund := EmbedRefund(x)
    2. y := c + refund
    3. return y

7. Security Considerations

P(s) = Tag(Com(nf, 0, 1, 0), 0).

P(alpha*s) = Tag(Com(beta*nf, 0, beta, 0), 0).

8. IANA Considerations

This document has no IANA actions.¶

9. References

Acknowledgments

The use of Keccak-p[800,12] in this application was proposed by Bas Westerbaan.¶

Authors' Addresses