Moussaka

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 9 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.¶

Rollatini [ROLLATINI], an Issuer-Hiding Anonymous Token, allows a Client to redeem a token with a Moderator without revealing which Anchor issued the token. Instead, the client proves the token was issued by some Anchor in the Anchor Set trusted by the Moderator. Rollatini is also designed to be post-issuance unlinkable, meaning the redemption of a token cannot be linked to its issuance.¶

Rollatini meets these privacy goals unconditionally, meaning regardless of its computational resources, no attacker can learn which Anchor issued a token or to which Client it was issued. On the other hand, it is well known that a quantum attacker can forge tokens by recovering the Anchor's secret key from its public key.¶

This document specifies Moussaka, an Issuer-Hiding Anonymous Token that is plausibly fully post-quantum secure. Similar to [VOLE-ACT], 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. Moussaka extends this paradigm in the natural way: rather than prove knowledge of a signature under the public key of a particular Anchor, the Client proves knowledge of a signature under some public key in the Anchor Set.¶

Moussaka has significantly higher bandwidth cost compared to Rollatini:¶

1. each Anchor public key is 42.6KB (this corresponds to the uov-Ip parameter set [UOV]);¶

2. ~8KB are transmitted during issuance; and¶

3. ~9KB are transmitted during redemption, plus a couple bytes per Anchor in the Anchor Set.¶

• NOTE(cjpatton) These numbers aren't based on an actual implementation. They are the result of an analysis from Claude Opus 5 looking at the FAEST spec and an arithmetization of Keccak in a work in progress implementation.¶

• NOTE(tnyuzg) We might be able to reduce the size of both VOLEitH proofs (one for issuance and another for redemption) using the more invasive techniques from [PoMFRIT], Algorithm 2.¶

On the other hand, Moussaka is round optimal: only two moves are required for issuance, whereas Rollatini requires three.¶

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 Moussaka and provides normative references for their specifications. Section 5 specifies the protocol in full detail. Finally, Section 6 enumerates some security considerations for implementers and adopters.¶

• TODO(cjpatton) Resolve gaps with [ROLLATINI]:¶

  1. The protocol wants to bind the challenge that triggered redemption to the redemption process so that the Client and Moderator confirm agreement. This is a 32-byte challenge_digest. Since this value isn't determined until redemption time, we can't include it in the commitment. The most natural solution is analogous to Rollatini: include challenge_digest in the VOLEitH transcript. This is mildly invasive, but shouldn't be too bad to support. PoMFRIT does a similar thing with the public key.¶

  2. The APIs are a bit misaligned. This is unavoidable to some extent for issuance, since our protocol is 2 moves and theirs is 3, but it should be possible to align redemption precisely.¶

  3. Our pseudocode is derived from ACT, but theirs is more in line with VOPRF. Perhaps all MoLE drafts should use the same pseudocode eventually? Likewise for Ratatouille.¶

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.¶

This document follows the same conventions and uses the same notation as [VOLE-ACT].¶

3. Overview

Moussaka makes use of three cryptographic primitives:¶

1. The Unbalanced Oil and Vinegar [UOV] digital signature scheme. Each Anchor uses a UOV secret key to issue tokens, and during redemption, the Client and Moderator agree on a sequence of UOV public keys to use as the Anchor Set.¶

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

3. A commitment scheme based on the Keccak permutation [FIPS202].¶

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) = t, where t is called the target and is 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.¶

Issuance binds a token to an issuance context ctx_iss agreed upon by the Client, Anchor, and Moderator, and a redemption context ctx_red agreed upon by the Client and Moderator [ROLLATINI]. The protocol commits to both contexts during issuance: the Anchor verifies the ctx_iss binding during issuance, and the Moderator verifies both the ctx_iss and ctx_red binding during redemption. Note that Moussaka constrains how these values are chosen compared to [ROLLATINI]; see Section 5.2 for details.¶

The issuance protocol is as follows:¶

• TODO(cjpatton) Add an illustration of the issuance flow.¶

1. The Client constructs a commitment t = Com(nf, ctx_iss, ctx_red, r) to a nullifier nf and the intended issuance and redemption context, where r is the opening. It also constructs a VOLEitH proof pf_iss of knowledge of the nf, r, ctx_red from which t was computed, then sends t, pf_iss to the Anchor.¶

2. The Anchor verifies pf_iss, samples a solution s to P(s) = t, then sends s to the Client.¶

3. The Client finalizes issuance by checking that P(s) = t.¶

The process resembles RSA blind signature issuance [RFC9474]. The key difference is that the Anchor observes the signature s in plaintext. To ensure unlinkability, the Client must hide the signature from the Moderator during redemption.¶

Let P[0], ..., P[N-1] denote the Anchor Set. To redeem a token, the Client presents the nullifier in plaintext along with a VOLEitH proof of knowledge of i, s, r for which P[i](s) = t without revealing i. In order to prove this statement with VOLEitH, we need to express it as a system of constraints over F_q.¶

The idea is to extend the witness with a "selector" vector b[0], ..., b[N-1] for which b[u] = 1 if u = i and 0 otherwise. The constraints then check that the public key selected by b maps s to Com(nf, ctx_iss, ctx_red, r) and that b is the indicator vector of a single Anchor. See Section 5.4 for details.¶

The commitment Com() is 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 6 for justification.¶

• NOTE Both issuance and redemption involve a Com() evaluation. An alternative is to have the Anchor bind the issuance context by applying an outer commit, like Com(Com(nf, ctx_red, r_red), ctx_iss, r_iss). This way no issuance proof is required. It would also have the benefit of not requiring the stronger one-more-UOV assumption. See Section 6 for details.¶

• NOTE We can add multishow and late binding of redemption context by adding another hash evaluation to the redemption proof. See issue 45.¶

4. Preliminaries

The procedures KP800(), UOV.CompactKeyGen(), UOV.ExpandPK(), UOV.ExpandSK(), UOV.SPre(), VOLEitH.Prove(), and VOLEitH.Verify() are defined as in [VOLE-ACT]. We adopt the uov-Ip parameter set (NIST Level 1) for UOV. That is, for the remainder of this document, let n=112, m=44, and q=2^8.¶

Moussaka also fixes the following parameters, named as in [VOLE-ACT]:¶

• nf_len: the nullifier length in bytes. Its value SHALL be 24.¶

• r_len: the commitment opening length in bytes. Its value SHALL be 16.¶

• ctx_len: the context length in bytes. Its value SHALL be 16.¶

5. Protocol

• 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.¶

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 template for domain separation is the same as [VOLE-ACT].¶

KeyGen():
  Output:
    - P: a public UOV map from F_q^n to F_q^m
    - 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)

Com(nf, ctx_iss, ctx_red, r):
  Input:
    - nf: the nullifier, in F_q^nf_len
    - ctx_iss: issuance context, in F_q^ctx_len
    - ctx_red: redemption context, in F_q^ctx_len
    - r: the commitment opening, in F_q^r_len

  Output:
    - t: the commitment, in F_q^m

  Steps:
    1. state := "mous" || VERSION || "c0" || r || 0^(25 - r_len) ||
                ctx_iss || ctx_red || nf || 0^(68 - nf_len - 2*ctx_len)
    2. t := KP800(state)[0..m]
    3. return t

Relation IssueRelation(t, ctx_iss):
  Instance:
    - t: commitment, in F_q^m
    - 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
    - ctx_red: redemption context, in F_q^ctx_len

  Constraints:
    - t = Com(nf, ctx_iss, ctx_red, r)

IssueRequest(ctx_iss, ctx_red):
  Input:
    - ctx_iss: issuance context, in F_q^ctx_len
    - ctx_red: redemption context, in F_q^ctx_len

  Output:
    - pending_token: Client state
    - request: issuance request

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

IssueResponse(td, request, ctx_iss):
  Input:
    - td: Anchor secret key
    - request: issuance request
    - ctx_iss: issuance context, in F_q^ctx_len

  Output:
    - s: Anchor signature, in F_q^n, or INVALID

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

FinalizeIssue(P, pending_token, s, ctx_iss, ctx_red):
  Input:
    - P: Anchor public key
    - pending_token: Client state
    - s: Anchor signature, in F_q^n
    - ctx_iss: issuance context, in F_q^ctx_len
    - ctx_red: redemption context, in F_q^ctx_len

  Output:
    - token: the issued token, or INVALID

  Steps:
    1. (nf, r) := pending_token
    2. if P(s) != Com(nf, ctx_iss, ctx_red, r): return INVALID
    3. token := (nf, r, s)
    4. return token

Select(b, P):
  Input:
    - b: selector vector, in F_q^N
    - P: Anchor Set, a sequence of N maps from F_q^n to F_q^m

  Output:
    - Q: the selected map from F_q^n to F_q^m

  Steps:
    1. M := m * n * (n + 1) / 2
    2. Q := 0^M
    3. for u in [N]:
    4.   for j in [M]:
    5.     Q[j] += b[u] * P[u][j]
    6. return Q

Relation RedeemRelation(P, nf, ctx_iss, ctx_red):
  Instance:
    - P: Anchor Set of length N
    - nf: nullifier, in F_q^nf_len
    - ctx_iss: issuance context, in F_q^ctx_len
    - ctx_red: redemption context, in F_q^ctx_len

  Witness:
    - r: F_q^r_len
    - s: F_q^n
    - b: F_q^N

  Where:
    - Q = Select(b, P)

  Constraints:
    - Q(s) = Com(nf, ctx_iss, ctx_red, r)
    - sum(b[0..u+1]) * b[u+1] = 0            for u in [N-1]
    - sum(b) = 1

RedeemRequest(P, i, token, ctx_iss, ctx_red):
  Input:
    - P: Anchor Set of length N
    - i: index of the issuing Anchor, in [N]
    - token: the issued token
    - ctx_iss: issuance context, in F_q^ctx_len
    - ctx_red: redemption context, in F_q^ctx_len

  Output:
    - request: redemption request

  Steps:
    1. (nf, r, s) := token
    2. b := 0^N  // selector vector
    3. b[i] := 1
    4. pf_red := VOLEitH.Prove(
         RedeemRelation,             // relation
         (P, nf, ctx_iss, ctx_red),  // instance
         (r, s, b),                  // witness
       )
    5. request := (nf, pf_red)
    6. return request

FinalizeRedeem(P, request, ctx_iss, ctx_red):
  Input:
    - P: Anchor Set of length N
    - request: redemption request
    - ctx_iss: issuance context, in F_q^ctx_len
    - ctx_red: redemption context, in F_q^ctx_len

  Output:
    - nf: the nullifier of the redeemed token, in F_q^nf_len, or INVALID

  Steps:
    1. (nf, pf_red) := request
    2. v := VOLEitH.Verify(
         RedeemRelation,             // relation
         (P, nf, ctx_iss, ctx_red),  // instance
         pf_red,
       )
    3. if v = 0: return INVALID
    4. return nf

6. Security Considerations

• TODO Prove the following claims.¶

Issuer-hiding and post-issuance unlinkability of Moussaka reduce to the zero-knowledge property of the VOLEitH proof system and the hiding property of our commitment. One-more-unforgeability reduces to witness-extractability of VOLEitH, binding of the commitment, and the one-more-UOV assumption ([PoMFRIT], Definition 8). The one-more-UOV assumption is a stronger assumption than standard UOV ([UOV], Definition 2) that requires some scrutiny before we rely on it too heavily.¶

• NOTE Here's a sketch of the reduction to one-more-UOV. We consider a simplified version of Moussaka, similar to PoMFRIT. During redemption, the Client proves knowledge of s, r for which P(s) = c and c = Com(nf, r).¶

  Our goal is to transform a one-more-redemption forger B into a one-more-UOV forger A. We simulate B's RO queries using the random targets we got as input to our one-more-UOV instance; when B requests issuance, we forward the target to our own SPre oracle.¶

  On input P, t[0], ..., t[Q-1] and with oracle SPre: Run B with P as the issuer public key and respond to its queries as follows:¶

  • When B asks Com(nf, r): for the i-th such query, counting from zero, respond with c = t[i].¶

  • When B requests issuance for c: respond with s = SPre(c).¶

  • When B requests redemption for nf, pf: extract the witness s, r for pf and let c = Com(nf, r). (If this fails, then witness extractability of VOLEitH implies the Moderator will reject.) If we didn't issue s for c, then B has successfully one-more-forged. Furthermore, c = t[i] for some i in [Q], hence s is a solution to our one-more-UOV instance.¶

• NOTE We previously looked at an alternative to the outer commitment in which c was "tagged" with issuance context x via either c || x or c XOR x. A reduction to one-more-UOV is possible, but it incurs a significant loss in concrete security, since the reduction has to guess x so that it can program the random oracle accordingly. Matching attack: XORing the tag into the image under the hash means the attacker gets to pick any prefix it wants. It now only needs to find a collision in the remaining bits of the image.¶

• TODO Justify halving the Keccak state from 1600 to 800 (relative to TurboSHAKE).¶

7. IANA Considerations

This document has no IANA actions.¶

8. References

Acknowledgments

The use of Keccak-p[800,12] in this application was proposed by Bas Westerbaan. Claude Opus 5 suggested the parity constraints for the redemption proof.¶

Authors' Addresses