Many of the patents blocking the use of good ideas in cryptography are spurious. Micali's Tree based revocation scheme is one of the rare examples of a scheme that was not completely obvious.
A digital certificate is a signed assertion that is used to make claims about the holder of a public key. Digital certificates are used in the WebPKI to provide a browser connecting to a Web site with the public key to use with the TLS encryption protocol. They are also used in the S/MIME end to end secure email system and in banking.
In the PKIX standard that governs use of digital certificates on the Internet, certificates are issued by a party known as a Certificate Authority which has various legal and technical responsibilities. One of the legal responsibilities is to verify that the claims made by the keyholder are valid. Another is to manage the status of the certificate, revoking it if certain conditions are met.
Changing the status of the certificate is the easy part, reporting the status change in an efficient manner is rather difficult. At the time Micali's scheme was proposed, the standard way a CA would do revocation was to issue a list of serial numbers of revoked certificates. These Certificate Revocation Lists (CRLs) would quickly become long and unmanageable.
A variant of Micali's scheme was discovered independently by Paul Kocher and a company, Valicert started to offer services based on the scheme. Micali's scheme was commercialized by a company called NovoModo. Neither company had any success in selling their proprietary certificate validation services but Valicert did end up offering a certificate status service based on the OCSP scheme Michael Moore, Warwick Ford and myself had developed at VeriSign.
Like blockchain, Micali's revocation scheme is based on a one way function that is easy to compute in one direction and hard to compute in the other. It is logically an extension of a scheme called S/Key that was developed by Leslie Lamport (the same Lamport who wrote LaTeX).
S/Key is an authentication system based on a chain of hashes calculated as follows:
The last value of sn calculated is sent to the server to use as the authentication test value. The values s0 ... sn-1 are used for authentication in the reverse order to the order in which they were calculated. So the first value presented for authentication is sn-1 and the last value used is s0.
The server keeps track of the last authentication value presented. Each time the user makes a login attempt, they present the previous value. If the function is genuinely one way, the server can verify the value but not generate it.
So if Alice is setting up an S/Key chain to authenticate to a server every day for a year, she generates a random number as her initial seed, calculates the SHA-2-512 digest of the seed to get the first link in the chain, then takes the digest of that to get the next and so on 365 more times. She sends the 366th value to the server to use as the authentication basis. The first authentication value she presents will be the 365th, the next the 364th and so on.
Like OCSP, Micali's scheme does not report certificate status, it reports that a certificate is valid. This is important as it means that a certificate is assumed to be invalid unless there is proof to the contrary.
To use the simplest form of Micali revocation to provide daily status updates on a certificate valid for a year, the CA would calculate a hash chain with 365 links and embed link value 365 in the certificate as an attribute. The next day, the CA would publish link value 364, the day after that link 363 and so on.
The revocation chain approach requires the least amount of data to revoke a certificate but requires an increasing amount of effort to verify each link. On the last day that the certificate is valid, the verifier has to calculate 365 hash values.
As with variations on the use of blockchain to notarize documents, we can use the Merkle tree scheme to achieve a tradeoff, in this time between the amount of processing time required and the size a certificate validation proof. If we use a simple Merkle tree with 9 layers, we will need 10 hash values and 9 operations to validate. If we use only 3 layers we will need 4 hash values and 48 operations to validate.
We can also use a shorter hash value. Since we are only interested in providing a re-affirmation of the status of a certificate already issued, a Work factor of 2128 is arguably sufficient. We can truncate the hash value to 128 bits without concern.
While we are on the subject of S/Key, it is worth noting that the same scheme can be applied to payments. The first time I saw this was in a paper by Ron Rivest and Adi Shamir that demonstrated two payment schemes based on the use of one-way digest functions. One was the Payword scheme I describe here, the other was MicroMint, a scheme that might be thought as a very early ancestor of BitCoin.
Rivest had asked me to review the paper to see if I had seen anything similar in the payments area, I hadn't. A few days after the preprint was released, Torben Pedersen replied that he had developed the same idea calling it the Phone Tick modus and the CAFE project he had developed it for was in the process of patenting it.
We can apply the S/Key chain and its Merkle tree variant in a wide range of protocols. As a general rule it is a useful tool for the protocol designer's toolbox that allows us to perform one public key signature operation to make an assertion and then re-affirm the continued validity of that assertion without having to create a new signature.
In the 1990s, it was generally applied to re-affirm assertions with a validity lasting a year or more. In new protocol designs, it is more likely that we would be seeking to apply the technique to much finer grain re-validation at the granularity of hours minutes or even seconds.