Somewhat similar to Signed Certificate Timestamps (SCTs) in Certificate Transparency, an MTC CA could sign an assertion before it's published, promising to include it. Dissimilar to CT, we'd want to MTC CA to also commit to the index within the batch.
This doesn't require direct sequencing if we allow empty assertions within batches. Indeed: the MTC CA could divvy out intervals of consecutive indicies within the coming batch to different signers. Those signers could assign assertions as required without hassle of synchronisation (until they run out).
These post-quantum promises would be relatively big using a general purpose post-quantum signature scheme. In the case of MTC, we could make them relatively small by using stateful hash-based signatures where the index of the final tree matches the index of the promised point of inclusion within the batch. Using a stateful hash-based signature with two levels of subtrees: one for the batches and one for the promises within the batch, we're looking at about a 1.3kB signature with n=16, w=256.
The hard problem is how to ensure these pinky promises are kept.
Somewhat similar to Signed Certificate Timestamps (SCTs) in Certificate Transparency, an MTC CA could sign an assertion before it's published, promising to include it. Dissimilar to CT, we'd want to MTC CA to also commit to the index within the batch.
This doesn't require direct sequencing if we allow empty assertions within batches. Indeed: the MTC CA could divvy out intervals of consecutive indicies within the coming batch to different signers. Those signers could assign assertions as required without hassle of synchronisation (until they run out).
These post-quantum promises would be relatively big using a general purpose post-quantum signature scheme. In the case of MTC, we could make them relatively small by using stateful hash-based signatures where the index of the final tree matches the index of the promised point of inclusion within the batch. Using a stateful hash-based signature with two levels of subtrees: one for the batches and one for the promises within the batch, we're looking at about a 1.3kB signature with n=16, w=256.
The hard problem is how to ensure these pinky promises are kept.