CA's and PKI's with multiple signature algorithms

[Trevor Freeman <trevorf@xxxxxxxxxxxxx>]

There seems to be a significant overhead for CA's and PKI's in general
which support multiple signature algorithms. PKI's cannot make
assumptions about the capabilities of a certificate user, therefore
users with only one signature algorithm must be catered for.
CA's and PKI's must ensure that a certification path exists for each
signature algorithm they use. It seems unreasonable for a path to force
a switch of algorithms. This introduces the concept that a CA is
operating in an algorithm qualified name space.
There seems to be at least two solutions to this problem

1. CA's maintain multiple certificate hierarchies independently and in
parallel. This would also include CRL's distribution point for each
algorithm. This is in effect maintaining multiple PKI's with all the
management overhead that would entail. As the CA hierarchy for each
algorithm qualified name space is independent, they can have different
structures. This may be a benefit??. However users with multiple
signature algorithms are being artificially constrained by this option
since they can cross algorithms name spaces. 

2 Certificates could optionally carry multiple signatures thus
permitting their use by either algorithm user community. This is then a
singe PKI for all algorithms. I cannot however see how to do this
without a change in the certificate structure.

Any enlightened solutions?

Dr Trevor Freeman
Senior Consultant
Microsoft Consulting Services
Microsoft Ltd ECU
> Tel:  UK(+44) 1734 270412 
Fax: UK(+44) 1734 270435