Posted by Pavel Kankovsky on Apr 10
You always need Omega(l) operations to check a value where l is the
number of its significant bits (i.e. of the cert's serial number).
It cannot be less than Omega(l) because you need to read and consider
every of those significant bits (they would not be really significant if
you did not have to do that).
Any set of values having (at most) l significant bits can be represented
by a bitwise trie whose depth is (at most) l. The presence of…
Source: Re: how would browser vendors deal with $O(10^k)$ fake certs?
