Topic K: Combined Presentation of Attestations

[AltmannPeter]

Welcome to the discussion on Combined Presentation of Attestations, part of the ongoing development of the Architecture and Reference Framework (ARF) for the European Digital Identity (EUDI) Wallet.

This discussion is based on Issue #341 about Topic K: Combined Presentation of Attestations, and aims to provide input to the forthcoming discussion paper.

This text suggests a definition of combined presentations and proposes two security requirements derived from what a Verifier must be able to achieve. The security requirements then guide the initial proposals on various PoA approaches.

One such approach, related-key PoA, is given extra consideration given the attention they have received.

@skounis and others feel free to edit and take over this discussion.

[AltmannPeter]

Topic K - Combined presentations and Proof of Association

Disclamer: This text is not intended to communicate a favored approach, but to guide a fruitful discussion. Favoritism on the author's behalf is clearly communicated. Furthermore, the text does not consider protocol choices already made for the EUDIW context, but may reference these when suitable.

Defining secure combined presentations

Issue #341 defines combined presentations and aims to outline implementation requirements.

A slight refinement could better clarify security requirements and shift the focus to what the Verifier must determine (rather than attribute requests and consolidation).

I propose defining a combined presentation as a transaction where at least two attributes from distinct attestations are presented to a Verifier so that the Verifier:

1. determines whether the two attributes describe the same identity subject (Identity Binding), and
2. ensures that the attributes are properly paired when presented (Valid Composition).

The first requirement is straightforward, but the second is more nuanced. Example A illustrates why proper pairing is crucial (see also the VC implementation guidelines "selective disclosure" subsection under ZKP).

Example A: The risk of improper attribute pairing
The following two attestations describe the same identity subject:

{
  "attestation_id": 1,
  "employer": "UK ltd",
  "role": "CEO",
  "name": "John Doe"
}
{
  "attestation_id": 2,
  "employer": "SE ABB",
  "role": "Board member"
}

A valid composition maintains logical consistency:

{
  "employer": "SE ABB",
  "name": "John Doe"
}

The following example is NOT a valid composition as it improperly pairs the employer and role values.

{
  "employer": "SE ABB",
  "role": "CEO"
}

With the above in mind, the following security requirements must be met:

1. Identity Binding: The Verifier must determine whether the presented attributes refer to the same identity subject.
   • Note that this does not mean the attributes must describe the same identity subject—only that the Verifier can assess whether they do.
   • Some combined presentations may include attributes from different identity subjects (e.g., a child and their legal guardian).
2. Valid Composition: The Verifier must ensure that all attributes are properly paired according to their original attestations and not combined in a way that alters their intended meaning.

Achieving Identity Binding

To determine Identity Binding, there needs to be some sort of Proof of Association between the presented attributes. I am aware of the following general solutions:

Session-based PoA

Session-based PoA ensures that all attestations sent over a secured session originate from the same certified WSCD and refer to the same identity subject.

Session-based PoA requirements include:

1. The WSCD must protect the User's attestations, not just the cryptographic keys.
2. The WSCD must only protect attestations that describe the same identity subject.
3. The Verifier must bind the secure session to a User identity and WSCD.

I am not familiar enough with session-based PoA approaches to provide a detailed list of drawbacks and benefits, but some considerations may include:

• Questionable offline support. Given that a session must exist for PoA, offline support is difficult.
• Lightweight. No need for cryptography beyond establishing a secure session as all attestations sent over the session are assumed to be associated.
• Adaptable to existing protocols. Existing standards like OAuth 2.0, OIDC, and TLS session binding can be leveraged but I am unaware of a widely deployed session-based PoA-specific standard.

Claim-based PoA

Claim-based binding allows a Verifier to perform identity binding solely based on the claims presented by the User. There are two general approaches:

1. Unblinded PoA inputs (Verifier linkable)
2. Blinded PoA inputs (Verifier unlinkable)

Since Verifier unlinkability is a requirement, we will only consider the Verifier unlinkable blinded PoA inputs below.

Note: Issuer unlinkability is irrelevant if the attestation includes other Issuer-linkable correlation handles (e.g., salt values, public keys etc.).

To achieve Verifier unlinkability, the User only present blinded claim statements. Blinded claim statements are particularly suitable when attestation Issuers rely on a attestation (e.g., a PID) to identify the User before issuing new attestations. In this model, Issuers and Verifiers receive different identifying attestations:

• Issuers recieve a PID that contains a claim statement with a unique value (only shown to Issuers). Each Issuer blinds the claim statement before embedding it in the issued attestation.
• The User reveals only blinded claim statements with a PoA to a Verifier.

During verification, the User must prove that the blinded claim statements are equivalent in some way (c.f. Appendix A for a ZKP-based approach that offers third party repudiation).

Some limitations of blinded claim-based PoAs include:

• Verifier burden. Verifiers must process and validate the PoA.
• Issuer burden: Issuers must create and include blinded PoA inputs in each attestation.
• Not standardized. A blinded claims based PoA requires standardization and also protocol support.
• Single-use. Blinded claim values are static unique values and thus single-use only to prevent Verifier linkability.

Benefits include:

• Compliant with existing protocols. A blinded claim based PoA is entirely software based and can be achieved using a separate PoA endpoint / out-of-band channel.
• Separation of concerns. The PoA does not require WSCD protection. However, a Verifier will only request a PoA if the User proves PoP of WSCD-protected keys in the Combined Presentation.
• Repudiable compositions. With an IZKP (but not NIZKP) PoA, a Verifier can generate a simulated transcript indistinguishable from a real one, providing Users repudiability against third parties.
• Curve\algo independence. With a ZKP-based PoA, you can prove that two keys are associated even across curves and algorithms (e.g., signature and key exchange).

Signature-based PoA

Signature-based PoA uses at least two keypairs in a process that establishes their association. These approaches do not inherently provide PoA and instead rely on certified hardware to enforce signing rules. Possible adaptations could leverage:

• Countersignatures: One key signs a signature from another key, ensuring both are linked, e.g., $Sign(k_a, Sign(k_b, M))$.
• Cross-signing: A private key signs a statement containing another public key, proving their relationship, e.g., $Sign(k_a, K_b)$.
• Multi-signatures: Multiple keys jointly create a valid signature. Some schemes, like Schnorr, allow for signature aggregation, e.g., $Sign(k_a, k_b, M)$.

There are some major limitation of signature-based PoA.

• Requires certified hardware. Every signature-based PoA approach relies on certified hardware to enforce signature policies that only allow the generation of PoAs if all involved keys are under the same device's sole control. Without it, an attacker can trivially generate PoAs.
• Repurposed techniques. A signature-based PoA repurposes cryptographic methods that were not designed to inherently enforce PoA and must be adapted for this purpose:
  • Countersignatures are used for stepwise accountability, such as timestamping, document notarization, and email receipt non-repudiation.
  • Cross-signing is intended for a trusted entity vouching for another trusted entity's key. It can be used for identity binding; implementations of PGP rely on cross-signing to establish identity binding between a primary key and a subkey.
  • Multi-signatures are used for threshold security and collaborative signing.
• Verifier burden. The Verifier must process and validate the PoA. While not equally complex, signature based PoAs add overhead and requires a peer reviewed standardization process.
• Linkability. Signature-based PoA publicly links two keys, making it suitable only for one-time-use keys.
• Non-repudiable compositions. Signature-based PoA creates a permanent, non-repudiable link between two attestations, exceeding the minimal proof required and enabling third-party behavioral profiling.

Despite its drawbacks, signature-based PoA offers several benefits:

• The cryptographic primitives are widely understood and easy to implement.
• Signature-based PoA techniques are highly unlikely to raise patent concerns.
• While these techniques require repurposing, they are well-documented, widely used, and supported by clear standards.

Related key PoA

A related key PoA establishes an association between public keys based on relationships between their private keys.

NOTE: Related key PoA has known security risks (e.g., with ECDSA) and potential patent concerns, requiring careful and extensive examination.

Two primary approaches exist. Both leverage homomorphic relationships between private and public key operations:

1. Key ratio associations. Verheul (2025) presents a well-developed approach.
   • An association key. Given private keys $(p_1, p_2)$, an association key is defined as the ratio of private key scalars: $z = p_2 \cdot p_1^{-1}$.
   • The multiplicative structure of $z$ is preserved in the public key domain enabling PoA.
   • Based on a modified Schnorr signature / Chaum-Pedersen proof.
   • Requires both PoA and PoP from the User.
   • Depends on certified WSCD capable of arbitrary private key computations.
2. Derived associations with key blinding. Detailed in BIP-32 and SLIP-0010 (both widely adopted), adapted for an EUDIW context in ARKG, and HDK; further detailed in KBSS.
   • Applies a blinding factor, $p_b$, to an existing private key $p_1$.
   • The blinding factor can be applied additively, $p_1 + p_b$, or multiplicative $p_1 \cdot p_b$, depending on the scheme and leverages existing key generation subroutines.
   • When locally computed the User derives $p_b$ for use with new keys. An Issuer would here require PoP and PoA.
   • In joint computation, a shared secret ensures that both the User and Issuer can compute the public key association, while only the User derives the private key association.
   • Implicitly ensures PoP and PoA requiring proof of neither.
   • Explicit PoA possible via Chaum-Pedersen proofs (c.f. Appendix A).

NOTE 1: Key generation and PoA are intertwined in key ratio assocations, but separate (and potentially software based) in derived assocation using key blinding.

NOTE 2: Due to the private key relationships introduced, both approaches require safeguards with malleable schemes like ECDSA to prevent signature forgeries.

Both approaches require extensive scrutiny before their benefits and drawbacks can be fully assessed. This discussion aims to contribute to their respective evaluations.

I actively support and contribute to the derived associations via key blinding approach, and would like to initiate this discussion with the following remarks:

• Related discussion: See Topic B
• Critical review of Verheul (2015): Available in this publicly accessible document, where all comments are public.

I greatly appreciate Verheul's work and the effort invested; my critique is intended to be constructive and support further improvement. To this end, I offer the following comments:

• The security requirements are heuristically derived from a specific deployment model, which may bias conclusions and be unsuitable for the EUDIW in general. Alternatives like threat scenarios or using established security standards/specifications are preferable. If a use-case driven approach is necessary, it should model valid/malicious interactions and clearly define system goals and what participants MUST (NOT) be able to do.
• Particularly, I challenge SW2 in Verheul's work, but also raise issues with SW1.
• Seemingly, due to the single-generator constraint and potentially overly restrictive security assumptions, Verheul's approach introduces three key requirements:
  • (a) an association key,
  • (b) a WSCD capable of arbitrary private key operations, and
  • (c) a heavily modified Schnorr algorithm.
• I am concerned about the relationship introduced in (a) and that (c) deviates significantly from a standard Schnorr or Chaum-Pedersen proof.
• If (b) is required, it raises the question of why (a) and (c) are needed at all, given that much simpler methods (c.f. Appendix B) exist assuming (b).
• Verheul's approach blurs the distinction between Proof of Possession (PoP) and Proof of Association (PoA), which may not be ideal for modular security designs.

NOTE: The HDK approach I am involved in has received criticism as discussed in Topic B.

Achieving Valid Composition

I have no idea how to do this generally. The only viable ways I can think of are:

1. limit attribute compositions to a single identity subject, and
2. a claims based approach where attributes evidence valid compositions (e.g., values in the first attestation for parents that can be matched with the corresponding subject identifer values in the second attestation).

If a solution exist, I would be very interested in seeing it. If no solution exists, I propose we discuss what limitations need to be in place for Combined Presentations to circumvent concerns with Valid Composition.

Author contributions

The text was written by Peter Altmann, with conceptual input on session-based PoA from Stefan Santesson, and review by Sander Dijkhuis.

Appendices available here: https://github.com/AltmannPeter/TopicsReview/blob/main/Topic_K_Appendices.ipynb

[rmayr]

Thanks for the excellent summary on "Achieving Identity Binding", to which I don't have anything to add. In our experiments we have leaned more towards what you describe as a "Claim-based PoA", but related key approaches seem similarly capable, pending more detailed review. Session and signature based PoA both seem to fail in practice when we require offline support and cannot (practically) assume all wallets to have custom WSCDs (e.g. with custom SE applets).

On "Achieving Valid Composition", the only practical approach that comes to mind is requiring schema specifications of attribute combinations to indicate "classes" of composability that could rule out your counter-example of, e.g., employment based sub-attributes. However, I am not aware of an existing ontogology that this could be based upon.

[shifteverywhere]

Verifiable selective disclosure is generally advanced, but it becomes more complicated when combining attributes from different attestations, particularly when trying to avoid invalid paring, as referenced above. The contextual scope is lost. The context must be preserved to prevent invalid pairing, which is challenging when providing PoA for this. It may be easier to issue valid combined presentations rather than allow arbitrary combinations. Although, pre-combined presentations may be a challenge by itself and somewhat miss the point.

PoA does not necessarily by itself prevent invalid pairing.

[phin10]

I close the discussion here. Please proceed in this thread:

Topic K - Combined presentation of Attestations