Hello, would someone mind explaining to me the "combinatorial explosion problem"? Specifically, there is one aspect where I think I'm going off-roads, or have not been paying enough attention:
As I see it, we have a bunch of traditional schemes, say T1 up to Tn. We are now proposing to create "composites" MLDSA+T1 up to MLDSA+Tn. Now we are worried that the ecosystem will not, to a sufficient extend, interoperate in the sense that a client and a server will implement distinct subsets of these composites. A reasonable objection I would have here is that if most implementations and most CA supporting one set of signatures Ti would, by implementing MLDSA and adding the few-line combiner code for each [0], support the entire set of MLDSA+Ti composites. But if that is the case, then a client and server supporting distinct sets of composites would imply (logically) that they supported distinct sets of traditional schemes. So why is this not a problem today? ---------- Perhaps the discussion is not around lack of interoperability between MLDSA-composites, but between MLDSA-composites and other composites (or traditional schemes). But to me this seems equally contrived, since if we consider several PQ signature schemes PQ1 to PQm and consider that any implementation is likely to implement the cross product between all Ti and PQj schemes it supports [see 0], we can deduce from distinct sets of composites that a particular pair of client and server either did not agree on a PQ scheme or on a T scheme. So why is this not a problem either today or once we have standardized several PQ-only schemes? ---------- Thanks in advance, -- TBB [0] The few-line combiner code can be extremely simple. The most complicated part, which potentially scales with the number of combiners (n*m) rather than the number of underlying schemes (n+m) or the one-time combiner logic is a map from combiner codepoints to pairs of schemes (and associated parameters like signature length so it is clear where to serialize each). Even that could be done in O(n+m) LOC, if the code points are sufficiently structured, which seems like more of an engineering task to me.
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ TLS mailing list -- [email protected] To unsubscribe send an email to [email protected]
