1 Blocked Hash-Tree Status and Entitlement System

This paper describes a new technology for fast, lightweight, and secure confirmation of information related to digital certificates. With the continued rapid expansion of Internet and wireless services, there is a growing need for enhanced public key infrastructure (PKI) services, including more efficient ways to confirm certificate revocation status and related entitlements. In a wireless environment, (a) messages must be small, due to low baud rates, and (b) the computation to verify them must be minimal, due to the reduced computing resources in many hand held devices. The blocked hash tree (BHT) technology uses a Merkle tree (M-tree) to encode a table of attribute values, with the M-tree’s root then embedded in a certificate extension. The attribute table is public, so for each certificate, each value is preceded by a different secret “blocker ” nonce value (e.g., 160 bits). Only upon release of the blocker value can a given leaf of the M-tree be verified down to the embedded root value. To notify potential relying parties regarding certificate revocation or suspension, for a given certificate, the attribute table will contain one leaf for each validity period, so the release of that leaf