TS14 - Implementation of ZKP based on multimessage signatures in the EUDI Wallet

[pinamiranda]

Welcome to the discussion on the specification for the implementation of Zero-Knowledge Proofs based on arithmetic circuits in the EUDI Wallet, part of the ongoing standardisation process of the Architecture and Reference Framework (ARF) for the European Digital Identity (EUDI) Wallet.

This discussion is based on the document TS14 - Implementation of ZKP based on multimessage signatures in the EUDI Wallet and on the result of related discussions documented in the Topic G Discussion Paper and in TS 4 - Specification for ZKP Implementation in EUDI Wallet.

The work in TS4 acknowledges two broad approaches to zero-knowledge proofs (ZKP) within the EUDI Wallet. The first, based on arithmetic circuits, is developed in TS13. The second is founded on multi-message signature schemes that natively support a wide range of ZKPs.

There are three main reasons to dedicate focused work on multi-message signature schemes:

1. They enable highly succinct attestations with fixed message structures and types; message commitments are single field elements. This property can significantly reduce the circuit complexity associated with approaches such as those in TS13.
2. The selective disclosure techniques used in multi-message signature schemes support a modular proof logic, allowing multiple zero-knowledge statements to be composed. It also enables a proof logic that substantially reduces the circuit complexity required in approaches such as those explored in TS13.
3. The design of zk-friendly multi-message signature schemes is also well established in academia, and certification of such schemes may prove more tractable than certifying arithmetic circuits.

This discussion is part of a structured process to refine and complement the ARF, with your input playing a vital role. We invite you to share your comments, insights, and suggestions here. Your contributions will be carefully reviewed and considered as we work towards the next version of the Technical Specification, which will incorporate updates on this topic.

Thank you for participating in this important conversation.

[ad-Orange]

Thanks for taking the time to explain all things MMS in the context of eIDAS.
While the bare fact that TS14 exists is a big jump forward in terms of bringing AC closer to use in eIDAS2.0, I still see serious issues in this document that need to be tackled.

First, the structure of the document can be confusing at times with MMS/ZKP related descriptive parts of the document being mixed with proposed solutions and / or recommendation in a way that is not easy to track. I would rather propose an architecture around the line of:

• Problem statement
• An intro on MMS, ZKP, low level technological aspects / definitions (like EC curves, pairings etc…) if this is really appropriate in this document
• The different kinds of solutions that can be envisioned
• The challenges to be tackled and the associated criteria to evaluate the possible ways forward
• Fact based comparison
• Recommendations (including deployment plans)

Maybe the biggest issue of them all is the unclear problem statement. The general idea seems to be related to the soonest possible operational deployment of MMS based standard AC for eIDAS 2.0 for at least level substantial and ideally level high. However, the following aspects are unclear, confusing or simply absent:

• As a starter, chapter 2 related to the scope is extremely difficult to grasp for a rational mind. While it is understandable that the requirements ZkP_08 (lack of existing standard) and “Investigation of intellectual property considerations related to cryptographic schemes referenced in this document” (lack of a proper legal framework in the current group) are out of scope, I see no obvious reason why the other requirements are declared “out of scope”. The one related to “Parameters for instantiations of cryptographic schemes” is particularly concerning for a topic related to cryptographic matters. Given the usually high standard of the commission for transparency, I think that any decision to leave a requirement on the side shall be duly justified in written.

• Level of security: do we want to achieve substantial, high, or both ? The unclear comparison between “ZKPs at LoA High” and “ZKPs based upon an eID means at LoA High” does not help here.
  o What are the expectations for level substantial and high ? For level substantial, it seems to be assumed in some parts of this document that issuer HSMs would not be needed. If we take as example payments, it is doubtful that it would be high, yet, given the potential systemic impacts of major key related issues, it is to be expected that Issuer HSMs would be required
  o The cybersecurity agencies (at least the main ones) shall clearly express their expectations: how many bits of security / privacy are acceptable for the MMS ? Are some of the MMS to be excluded due to some security considerations already ? Can issuer attestations be considered substantial or high given a particular number of security bits or are other requirements to also be taken into account ? Are there any requirements on the ZKPs for a proof to be considered substantial or high ? This is the only way to clarify the debate and ensure efficient discussions. If they did not answer these questions yet, an official request should come to them through TS14.

• Standardization: it seems that this document is supposed to be a prequel to an ETSI standardization towards an acceptable and recognized standard. This should be properly taken into account for the following aspects:
  o Standardization of new cryptographic components will take some time and it will take years at least before anything final comes out of ETSI as a recognized standard. This is not pedantic nor abusively formalist: standardizing cryptographic elements mainly means analyzing their security along all sorts of aspects, by many people, and with enough time to have a sane perspective on it. Furthermore, given the increasing focus on PQC, it is doubtful that there would be enough time for 2 distinct “phases” with pre-PQC solutions.
  o Skilled people will not spend an unreasonable amount of time standardizing new curves while they’re already busy with PQC topics. Exotic curves like T256 whose standardization has not even started are completely unrealistic as a potential standard target. If this statement is wrong please provide a clear and realistic standardization path for the T256 curve that would make it acceptable for substantial or high.

• The exclusion criteria shall be clearly stated in an unambiguous way. Here are a few proposals, taking into account the previous points:
  o Anything not supporting holder binding (e.g. Anonymous Credentials Light [BL13], SAAC) should simply not be part of the potential targets being considered. The complexity is supporting MMS/AC WITH holder binding. It is well understood how to do either independently, the challenge being to combine them both. Anything not supporting both at the same time is not helping eIDAS 2.0 move forward.
  o In the same way, I think that any cryptographic component that has no real chance of being standardized in a reasonably short term (2 years max) shall be immediately excluded from discussions.

• The “deployment strategy”, “recommendations”, “suggestions” and implicit comparisons are mixed with the problem statement, analysis and solutions and scattered all around the document, many times without an indication of doing so. It should be concentrated in a chapter with justifications after the potential candidates have been properly highlighted and compared based on fact driven criteria. As a reference, here are a few of these occurrences in the current text:
  o Chapter 4.1 “General Considerations for elliptic curve-based MMS Schemes” is particularly rich in these implicit recommendations
  => At the end of 4.1.1, some privileged ways of solving issues related to industrial deployments are recommended with little perspective, including the fact that it would “of course introduce complexity into the system design” as you note elsewhere…
  => 4.1.3 seems to imply that modulo “standard maturity” and “library availability” all solutions are about equal as they are all software. I think that once at scale (that’s the goal of eIDAS 2.0), computing and storage requirements do matter, maybe for performance, and certainly for costs, especially since the solutions discussed in this paper can variate by at least 2 orders of magnitudes in these criteria
  => 4.1.4 is already discussing “strategies” including point 3. which seems to be the main recommendation of this whole document (Appendix A) and lacks documentation (and that’s being slightly laxist here…). Other options are not explored.
  o And this goes on in 4.2 “Pairing-Based MMS Schemes”:
  => In 4.2.1.1 “security level” recommends Appendix A again…
  => In 4.2.2, this recommendation seems strange

“Overall, one must note that PS and BBS should not be opposed.”.

It is latter explained that the protocols have different features, but this is not an academic paper. The question is whether the considered protocols are suitable for eIDAS 2.0 (and not only can but shall be compared), and not whether they have the same features or not. The statement becomes even more peculiar once you consider that one of the main goals of 4.5.1 seems to be to compare them…
=> The chapter 4.3 on “pairing free MMS” is one of the few places (without any clear reason why) where an explicit comparison is done. Unfortunately, it is extremely confusing as it seems to mix up the comparison between pairing based and pairing free MMS with the comparison of multiple sub cases of pairing free solutions.
=> In chapter 4.4, I’m not sure what that sentence

“In their pairing-versions, regardless of the concrete instantiation, they offer performance that can hardly be matched by their competitors.”

is supposed to mean, nor who are the “competitors” but some pairing free versions are arguably performing even better… Furthermore, it gets into “deployment strategies” whereas at this stage, we have no clue what would take how much time nor what the real security expectations are. I also think that this sentence

“There is for example no point in comparing efficiency or features of PS and BBS# as they fit very different scenarios and requirements.”

is taking the problem in the wrong way: before defining strategies and scenarios, solutions should be compared so that the scenarios can be built appropriately with the proper solutions.
=> The “official” comparison block comes in 4.5 but for some reason, the pairing free solutions are not compared between each other in 4.5.2 (acknowledging that part of it as already been done in 4.3 in a confusing document structure) but against pairing based ones !
o In chapter 5.1.1, you mention that

“Therefore, solutions using a dedicated MMS for proofs over attributes and ECDSA only for the device binding part are inherently simpler and lighter than a construction using ECDSA for both.”

, yet this is part of your main recommendation (signing attestations with ECDSA for level high use cases).
o 5.1.2 is praising the benefits of BLS as an efficient “native” holder binding solution for HSMs without disclosing the fact that it is subject to correlation attacks using side channel information such as the time of the HSM signature request and the time of the VP (AKA timing attacks). This sentence is particularly misleading

“It is also the first protocol for BBS signatures that does not require trusting the WSCD for unlinkability and comes with a privacy-preserving variant for remote HSM settings”

as it could let one believe that HSM WSCD would have no way to track the user, which, once again, is wrong due to its susceptibility to timing attacks.

• Finally, two implied requirements require perspective and common sense:
  o [Issuer “high availability”] You mention in chapter 4.3, that in order to be able to answer RP -> issuers requests, issuer must “guarantee high availability”. I’m not too sure what “high availability” means in this case, but what’s sure is that the vast majority of issuers will have an incentive to be online most of the time whatever this group choose or discusses: they simply want people to be able to register and manage their services online 24/7 as, really, any other service. Furthermore, they could, if they want, separate the token consumption service from the issuance service. If the issue is more specifically the availability of Issuer HSMs (and their related private keys) 24/7, I’m not sure where the real issue is given that it is exactly what is happening today in the banking world and in one of the schemes you’re describing in the document ([FHLL25] in chapter 5.1.2) without mentioning anything related to high availability as any sort of disadvantage.
  o [Curve “bridging”] I understand that for the sake of efficiency, not all requirements in the world can be taken into account. However, any serious (and commercially deployable) solution will have to not only allow signature in a privacy respecting and secure (holder binding) way, but also be compatible with revocation, recovery, billing, combined proofs, pseudonyms, optionally non repudiation, etc… So, while it is understandable that all these aspects will not be discussed in details in this document, we should question whether the use of multiple curves that need complex bridging schemes are very reasonable in this kind of environments and whether the performance and scalability / certifiability issues will not compound inextricably.

[ad-Orange]

As mentioned in my previous post, recommendations are very confusing overall. It seems that the main one is hidden in 4.5.2 and states that

“the ECDSA/MMS hybrid approach suggested in Section 4.1.4 might be an alternative that can achieve LoA High on pairing-friendly curves.
Therefore, we suggest further developing that approach in the short term (Phase 1 in the previous section), and switching to HSMs supporting pairing-friendly curves as soon as they become available.”

So to cut a long story short, it means (at least in the short term – whatever it means, cf previous post) applying the idea of Annex A to pairing friendly based BBS attestations. I have some very serious concerns with that:

• This scheme is not formally described anywhere (at least not anywhere linked as part of this TS14 draft and AFAIK, nowhere). Let’s insist on that to be 100% clear: it’s not only that it is not peer-reviewed, it is not even formally scientifically described anywhere linked in something called a “technical specification” and that aims at getting standardized ASAP.
• There is no proof (difficult to prove something that is not defined formally…) for a ZKP that does not look trivial
  o Remember this scheme only applies for level high
• As the BBS attestations would be generated using pairing friendly curves, the holder binding proof that needs to be generated would involve curve bridging for which I still haven’t seen any fully proven scheme and arguably not standardizable in a reasonable time (cf comment on previous post about T256 curve). There is no details on the way to “reuse” the device binding circuits. It is also not clear if it can be performed in parallel with the holder binding part of if the performance issues would compound.

In summary, the recommendation of this draft is a scheme that is:

• Not formally defined (just the main idea is provided)
• As a consequence, not proven
• Needs to perform curve bridging at least once and potentially twice (for holder binding and “issuer binding” – what annex A wants to achieve). This:
  o Has not been demonstrated until now to be standardizable with reasonable efforts (and in my understanding, clearly isn’t)
  o Has at least the same performance impacts as the curve bridging solutions described in the document

This being the main recommendation of this paper is very concerning and raises questions on whether the final version will be come on time with more actionable solutions / recommendations.

As an alternative recommendation, I would suggest to:

• Urgently ask cybersecurity agencies for clear guidance on the security requirements to be taken into account both on the curves and on the schemes
• Identify clear and realistic standardization and deployment paths
• Identify clear requirements related to the subject matter and concentrate on the few remaining solutions and choose no more than 2
• Identify the support needed from the commission and member states to make the deployment happen ASAP

[Kydir]

I must express significant reservations regarding the inclusion of the BBS# scheme in the current Technical Specification (TS).

1. Intellectual Property and Patent Encumbrance There is a notable absence of disclosure regarding existing intellectual property rights, specifically referencing patent WO2025214950A1 and potential satellite patents.

It is a standard expectation that implementers will unlikely allocate resources to a solution devoid of a clear exploitation license, and probably academic institutions will refrain from analyzing a cryptographic scheme that is potentially encumbered by active patents. In contrast, regarding TS13, Google has provided clear, public, and published statements concerning their intellectual property, thereby fostering trust.

Consequently, there is currently no viable opportunity for rigorous public peer review. The reliance on a paper available solely via eprint which has evidently not been subjected to a complete peer review process is insufficient for a standard of this magnitude.

2. Technical Inconsistencies and Lack of Review Preliminary review suggests significant discrepancies that a standard cryptographer would identify, including but not limited to:

• Adversarial Capabilities: In the security experiments, adversaries should be granted access to the issuer public key (pkI​) at every step.

• Anonymity Definitions: There are inconsistencies between the definition of anonymity and the provided security proof; specifically, as is the paper claims a non-negligible advantage in the anonymity game.

3. Required Remediation We require a clear, legally binding declaration from Orange stating that the patent in question is abandoned, under a free license or an equivalent that satisfy legal experts. Without this, we face a dichotomy: either the community ignores the scheme until it is forcefully included in the wallet at which point it may be "open" but unvetted or we proceed with the current unacceptable risk.

Note: Please correct the reference link for BBS# in the TS. While the citation is correct, the hyperlink directs to an unrelated paper (it should be https://eprint.iacr.org/2025/619.pdf).

4. Concerns Regarding PS Signatures Similar due diligence must be applied to PS signatures. Is there an assessment of "patent poisoning" risks regarding EP3729720B1?

Furthermore, the text stating, "More generally, security of PS signatures was initially proven in the generic group model, and later demonstrated using automated tools [ABS16]," is misleading. It implies that automated tools provided proofs in a stronger model, whereas they merely confirmed the original proof within the Generic Group Model (GGM).

5. Security Models and Regulatory Positioning This distinction is critical:

• PS relies on the Generic Group Model (GGM).

To the best of my knowledge, no NCCA has issued a position confirming that 128-bit security in the GGM is equivalent to standard 128-bit security. It has been demonstrated in cryptographic literature that some schemes proven secure in this idealized model can be broken in the standard model, so the equivalence is far from being a given.

Conclusion: I concur with the comments previously stated by "ad-orange." Without explicit guidance and positioning from relevant security agencies, there is no sound basis to proceed productively with these schemes.

[oliviersanders]

Hi,

Thank you for your comment. As a co-author of PS signatures, I may try to answer your questions regarding this scheme.

"4) Concerns Regarding PS Signatures Similar due diligence must be applied to PS signatures. Is there an assessment of "patent poisoning" risks regarding EP3729720B1?"

This patent describes a variant of PS signatures that is not relevant for MMS. It was submitted in 2018, after publication of the PS signatures (2015 on eprint, 2016 at CT-RSA) so I don't see how it could affect PS signatures and their anonymous credential version (described in the eprint paper). Actually, PS signatures have been included in some open-source libraries without any complaints from Orange.

"Furthermore, the text stating, "More generally, security of PS signatures was initially proven in the generic group model, and later demonstrated using automated tools [ABS16]," is misleading. It implies that automated tools provided proofs in a stronger model,"

The text does not mention anything about a "stronger model" and clearly refers to the Ambrona et al paper so that one can directly check the actual result. I am therefore a bit surprised by the implication you mention but would be happy to change the text on [ABS16] if you have suggestion.

To the best of my knowledge, no NCCA has issued a position confirming that 128-bit security in the GGM is equivalent to standard 128-bit security.

I do not know the exact position of NCCA on this topic but since they recommend ECDSA that is only proven (to my knowledge) in the GGM, I guess that they do not see any intrinsic issue with this model.

" It has been demonstrated in cryptographic literature that some schemes proven secure in this idealized model can be broken in the standard model, so the equivalence is far from being a given."

Yes, similar results also exist for the ROM but yet most signature standards (even PQ ones) still massively use it. This is a common problem in cryptography. We would like to only rely on standard model constructions proven under DL but at some point we must be pragmatic. However, a variant of PS signature (https://link.springer.com/chapter/10.1007/978-3-030-55304-3_10 ), with only one additional group element, is proven under the DDH assumption. It retains the very same structure so if proof under standard assumption becomes mandatory, we could simply give up BBS and PS and move to this scheme.

[ad-Orange]

Hello,

As mentioned in a previous post, I don't think that the proper legal framework is available to make any sort of PI claim in this group, which is probably why it was not taken into account in the scope. I have already communicated in written our intentions in this matter to the people who actually need to know about it and whenever it comes to an actual standardization body with proper defined rules (like ISO or ETSI), we will then do what's expected from the community.
Furthermore, for an anonymous account that was created just a few hours before posting, obviously targeting specifically Orange and demanding such claims while claiming nothing on their side (whereas they may represent some alternative solution) is at best questionable.

As for the rest:

Consequently, there is currently no viable opportunity for rigorous public peer review. The reliance on a paper available solely via eprint which has evidently not been subjected to a complete peer review process is insufficient for a standard of this magnitude.

In fact, BBS# has been already peer-reviewed and will appear at SSR 2025. Please note that SSR is on the list of conferences approved by the relevant standardization bodies, such as ISO SC27, which standardize cryptographic mechanisms (For instance, here you can look at ISO SC27 guidelines https://committee.iso.org/sites/jtc1sc27/home/wg2.html and download the document 205 related to the “Process for inclusion and deletion of Cryptographic Mechanisms”, this is in annex B).
Moreover, BBS# has been formally analyzed in [CHLT2025] and [FHLL2025] and is used in the Functional Credentials construction that was recently proposed at ESORICS 2025.
Contrary to what you tacitly suggest, BBS# is not an entirely new construction; it is a straightforward pairing-free variant of BBS that builds on the keyed verification anonymous credentials (KVAC) scheme of Barki et al. (SAC 2016), which has been known and analyzed about a decade ago.

“Technical Inconsistencies”

Regarding the first technical inconsistency (Adversarial Capabilities), you are right, and I will emphasize that the issuer public key (pkI) is public and therefore known to the adversary.
Regarding the second inconsistency (Anonymity Definitions), the advantage of the adversary is in fact negligible; the factor ½ that appears in both Lemma 3 and Game 5 is a typo and should be deleted.

All that being said, your extreme focus on the technologies proposed by Orange in the context of TS14 seems very strange, especially since many of the proposals included in TS14 are not as mature or as thoroughly peer-reviewed, nor do they have a formal description. Yet you focus only on Orange-related technologies. Is there a particular reason for that?

In particular, I am wondering the following related to your post:

• You mentioned the NCCA and asked if they have issued a position on the GGM model. Has it issued a position on pairings and pairing-friendly curves?
• Has the Google solution you mentioned been peer-reviewed?

[Kydir]

I must address the nature of your previous critique, which appears to focus disproportionately on the sole solution within the Technical Specification (TS) that is not affiliated with Orange. Given this context, your remarks regarding my focus on Orange are moot.

The textual composition of the TS strongly suggests direct involvement by Orange. For a representative of that organization to publicly disparage the proposal specifically regarding parts that are not their own Intellectual Property while ignoring similar deficiencies in their own contributions is a questionable tactic. It demonstrates a lack of professional objectivity and raises concerns regarding anti-competitive behavior during the process.

I do not maintain a GitHub account. It is procedurally problematic that commenting on a European Commission initiative necessitates engagement with a U.S.-hosted platform. This raises data sovereignty issues that are a matter for the Ombudsman. Until then, a fresh account is a technical necessity, not an indicator of illegitimacy.

Regardless of your seniority within Orange, informal or "secret" internal assurances are legally insufficient for public commenters. We cannot rely on non-binding promises, especially when we don't even know them.

While it saddens me to go on their side, at least Google issued a clear public statement.

The Google solution also lacks peer review or security proofs, it was already noted in discussions for TS13. So i don't see your point? Should we congratulate you, on not being the worst? It is quite an insufficient standard for a security-critical specification.

NCCAs have examined pairings, but i agree never publicly supported them. You are french though... You should know the French ANSSI reference considerations for their use on page 23 of their guide (referring to Guide des mécanismes cryptographiques: https://messervices.cyber.gouv.fr/documents-guides/anssi-guide-mecanismes_crypto-2.04.pdf, if i am not mistaken couplage = pairing), so they are not toxic.

On the other hand, I am unaware of any NCCA formally analyzing the impact of the Generic Group Model (GGM) on security guarantees.

What i said in my previous comment, but that you apparently cannot fathom is that on this point, we are in agreement: an authoritative statement from the agencies is required before we can productively proceed, one way or the other.

Congratulations for the acceptance of the paper at SSR (Security Standardisation Research). However, for the sake of transparency, one must note its scientific ranking. https://portal.core.edu.au/conf-ranks/?search=Security+Standardisation+Research&by=all&source=CORE2023&sort=atitle&page=1

So, speaking of lack of proper scientific peer-review : Is the version accepted at SSR identical to the eprint version containing the flaws of the eprint ones? (those i mentioned, and the rest?)

This brings us back to the primary objection: You are engaging in a targeted disparagement against the non-Orange solution, while simultaneously failing to provide equivalent rigor for the solution you helped author.
This is more than scientifically dishonest.

And if i were the other people involved in the TS, i would feel that as a betrayal of the compromise that allowed this proposal.

[oliviersanders]

Hi,
I think the discussion is going in the wrong direction. Could we at least agree on the following conclusions?

1. a public statement from NCCAs would be beneficial. But then it should be expected for all TS13 and TS14 solutions. In particular, one cannot rule out a solution because it has not been vetted by NCCAs and yet considers that other solutions would be acceptable without this explicit public validation.

2. More generally, the set of requirements that must be fulfilled by all candidate solutions should be made clear.

On another topic, I understand Kydir's concerns on Github but I really believe it would be better to avoid anonymous comment. For example, when I defend PS signatures it is important that everyone knows that I am one of their authors and that's why I started my comment by providing this information. Antoine has also disclosed his identity so that anyone can identify him as a co-author of BBS#.

[abhvious]

The Google solution also lacks peer review or security proofs, it was already noted in discussions for TS13. So i don't see your point? Should we congratulate you, on not being the worst? It is quite an insufficient standard for a security-critical specification.

Just to correct your mistake here, the original Longfellow paper has security proofs for the main scheme and claims.
There have also been several expert peer review reports---these are substantially higher quality than the type of peer review that you receive at conferences like CCS, Oakland, even Crypto and Eurocrypt---that are published on the project's page. The correctness and security parameters have been carefully verified.

If there is any specific portion of a security analysis that you feel is missing from the record on Longfellow, as a scientific courtesy, we would appreciate that you point specifically to it instead of making imprecise claims.

[b50mc]

On the Algebraic Foundations and Implicit Trust Assumptions in MMS-based Credential Systems

I've been tracking the MMS standardization efforts for a while now, mostly out of academic curiosity since the early BBS formalizations. The recent activity around TS14 caught my attention, and after going through the referenced papers and some of the auxiliary literature, I figured I'd share a few observations that might help frame the discourse.

1. The Homomorphic Gap Problem

The core tension in TS14 stems from what I'd characterize as the homomorphic gap between the algebraic structure of the credential space and the computational model of the verifier.

Let φ: G₁ × G₂ → G_T denote the bilinear pairing. The security of BBS-family schemes fundamentally relies on the assumption that the kernel of the induced homomorphism φ* on the corresponding group algebras remains computationally inaccessible. But this assumption is non-uniform across instantiations.

The discussion conflates two orthogonal concerns:

• Algebraic soundness: whether the scheme's security reduces to well-studied hardness assumptions
• Model adequacy: whether the GGM accurately captures real-world adversarial capabilities

These are not equivalent. A scheme can be algebraically sound yet model-inadequate, and vice versa.

2. On the GGM Dependency

@Kydir raises a valid point regarding the absence of NCCA positioning on GGM-based security claims. I'd refine this though: the issue isn't merely that GGM proofs may not transfer to the standard model (see Dent 2006, Fischlin 2000). The deeper concern is that GGM security is inherently non-composable under arbitrary protocol composition.

For EUDI Wallet deployments, credential presentations will inevitably compose with TLS handshakes (ROM-based), device attestation (hardware-bound assumptions), and revocation checks (potentially interactive). The security semantics become undefined unless we establish a unified computational model encompassing all components. Not a theoretical nicety—a deployment prerequisite.

3. The Curve Bridging Complexity

The Appendix A suggestion on ECDSA/MMS hybrid approaches deserves more scrutiny. Cross-curve proofs necessitate one of:

• Native multi-scalar multiplication across non-isogenous curves (no efficient construction exists)
• Circuit-based bridging via SNARKs/STARKs (recursive proof overhead)
• Trusted setup ceremonies (antithetical to eIDAS 2.0 decentralization ethos)

On the SNARK/STARK point specifically: the arithmetic circuit representation of cross-curve verification requires encoding the target curve's field arithmetic as polynomial constraints over the base curve's scalar field. For non-native field emulation, this means decomposing F_q elements into limbs over F_p and enforcing carry propagation via degree-2 constraint systems.

Concretely, verifying a single BLS12-381 pairing inside a BN254-based SNARK (a likely scenario for ECDSA device binding + BBS attestation) requires expressing the sextic twist isogeny ψ: E'(F_p²) → E(F_p¹²) as R1CS constraints, which induces O(n²) blowup in constraint density due to tower extension arithmetic. The Frobenius endomorphism π_p alone decomposes into ~12k multiplication gates when unrolled.

The document's optimism regarding "reusable device binding circuits" assumes efficient recursive composition—a property that, while theoretically achievable via folding schemes (Nova, Sangria) or accumulation (Halo 2), requires either cycle of curves (Pasta, but not certified) or deferred verification with logarithmic verifier overhead. Neither has been demonstrated at security levels required for LoA High, and the prover complexity remains O(n log n) FFTs over extension fields—prohibitive for constrained mobile environments.

4. Constructive Proposal

Rather than advocating for any particular scheme, the working group should consider a formal criteria matrix:

• Security reduction: standard model or GGM with explicit bounds, peer-reviewed
• IP encumbrance: FRAND or royalty-free with legal attestation
• Implementation maturity: at least 2 independent implementations with public audit
• Composability: defined under UC framework with formal analysis

This transforms the current ad hoc comparison into a deterministic evaluation.

5. On the Procedural Concerns

I echo the sentiment that NCCA guidance would help. But waiting creates a circular dependency: agencies await concrete proposals before issuing opinions, this group awaits opinions before finalizing proposals.

Potential resolution: submit current candidate schemes (BBS, PS, BBS#) as a joint request for comment to ANSSI, BSI, and CCN, explicitly requesting comparative security assessment under specified threat models.

The path forward requires separating the algebraic question (which schemes are sound?) from the engineering question (which schemes are deployable?) from the political question (which schemes are acceptable to regulators?). Conflating these has contributed to the current impasse.

[ad-Orange]

Cryptographers from all around the world are looking at what’s going on here. The commission has allocated you, the experts, precious time to work for the greater good of European citizens into identifying the best compromise to deploy secure and privacy respecting protocols for eIDAS transactions.

Now, after months of work, 3 iterations and multiple warnings, we’re still in the sorry state that, based on recommendation 3, your only recommendation on the most important part of this whole document (the MMS algorithms to use) are for 2 schemes:

• One of which (recommendation 5) depends on an elliptic curve (T256) that has never been seriously investigated and that never will be standardized on time (if ever) to make it into the upcoming ETSI standard
• One of which (Sigpop-like, see chapter 5.1.1) does not respect everlasting privacy / statistical anonymity / unconditional privacy (whatever you want to call it)

Is this for real ? Is the goal of this expert group to self-destruct ?

Once again, it really is a shame that you obviously refused to make a clear technical "fact based comparison" between all the schemes as recommended in one of my previous posts.

Soon, it’s not only cryptographers, but more than 450 millions citizens who will start asking questions. I am one of them. Given the available alternatives, it would be a shame to only have ridiculous excuses like "We did not realize T256 cannot be standardized on time" or "Oh, you cared about everlasting privacy? Really ?" or even worse "You know, everlasting privacy was not in the list of requirements of A.2.3.31 Topic 53 of Annex 2, so we didn't take it into account" to answer their questions on why the work mandated on their behalf was not seriously delivered.

There are lots of other comments to be made on this document. But compared to the fact that you are not including any MMS protocol that can reasonnably be included by ETSI for the upcoming standard (which is exactly your mandate) in your recommendations, they are benign and of negligible importance.

[abhvious]

In S8.3.1: "Note that the positional encoding (index of a value) in multi-message signature schemes always leaks a bit of information unless a static structure that all attestations of that type fit in can be defined."

1. The document is explaining how unlinkability can be violated when using a multi-message signature unless a static approach is used for ALL_ credentials that are issued.

It is important this point be clarified. It is one of the reasons that I consider it unsuitable for deployment at large scale, and why it failed review after review when considered inside Google.

2. TO spell it out more clearly, this document clarifies that an MMS signs an ordered tuple (m1,m2,...).
   IF an issuer mistakingly issues a credential on the tuple (name, dob, age_over_18_flag, ....) to Alice, and then issues a credential on the tuple (name, age_over_18_flag, dob, ...) to Bob, then every RP can break the linkability of the scheme, even though ZKP proofs are used.

It is essentially guaranteed is practice for this to occur, because people upgrade software, the schemas and identity attributes that are included in credentials can change over time, etc. What this is saying is that privacy failures are HIGHLY LIKELY despite the ZKP.

3. In my academic career, we would hardly care about these kinds of things, and I think many of the authors and supporters of the BBS-style schemes willfully ignore this kind of key difficulty. However, practitioners should be keenly aware of this failure mode.

[abhvious]

S3.
"Multi Message Signatures (MMS) are digital signature schemes characterized by two properties:

• they allow the signer to sign tuples of messages of a fixed length (m1,…,mn) in a single signature σ
• they support efficient Zero Knowledge Proofs of knowledge of a signature σ and of the attributes (m1,...,mn) signed in it while possibly selectively disclosing some of them."

--- The Longfellow ZK scheme satisfies this notion. In the latest, it signing a vector (m1,...,m1000) of 1000 bytes, and allows disclosing a fixed number of subranges in less than 100ms, including validation of expiration conditions and range proofs.

Unless a more precise quantitative measure of efficiency, it cannot be ruled out as an MMS according to this document.

[Megaman678]

Two observations on the trusted setup assumption:

TS14's recommended ECDSA/MMS hybrid for LoA High requires SNARK-based curve bridging (as noted in this thread). This reintroduces the same trusted setup assumption that TS13 explicitly excludes. The two specifications are in tension.

An MPC ceremony with Member States as participants (1-of-N honesty, where N=27) is a strictly weaker trust assumption than PID issuance, where each Member State is individually trusted. If we trust a single government to issue identities, we can trust that at least one of twenty-seven will discard a random number.

Has the working group considered whether the TS13 exclusion of trusted setup should be revisited in light of both points?