Int. J. Inf. Secur. (2005)DOI 10.1007/s10207-005-0076-xSPECIAL ISSUE PAPERGabriel Vanrenen · Sean Smith · John MarchesiniDistributing security-mediated PKIPublished online: 19 July 2005c Springer-Verlag 2005Abstract The security-mediated approach to PKI offersseveral advantages, such as instant revocation and compat-ibility with standard RSA tools. In this paper, we present adesign and prototype that addresses its trust and scalabilityproblems. We use trusted computing platforms linked withpeer-to-peer networks to create a network of trustworthy me-diators and improve availability. We use threshold cryptog-raphy to build a back-up and migration technique which al-lows recovery from a mediator crashing while also avoidinghaving all mediators share all secrets. We then use strongforward secrecy with this migration, to mitigate the damageshould a crashed mediator actually be compromised.Keywords SEM · Peer-to-peer · Trusted computing1 IntroductionThe security-mediated approach to PKI (by Boneh et al.[3, 4]) offers many advantages. However, it has some dis-advantages with regard to trust and scalability: each user de-pends on a mediator that may go down or become compro-mised. In this paper, we apply tools including peer-to-peercomputing and trusted computing platforms to distributethe security-mediated approach to PKI, and thus preserveits advantages while overcoming its scalability, reliability,and trust problems. Section 2 reviews the security-mediatedapproach, and discusses its advantages and disadvantages.Section 3 discusses the tools we apply to this problem.Section 4 discusses the design we build with thesetools. Section 5 discusses our prototype. Section 6 discussessome related approaches. Section 7 discusses some conclu-sions and future work.G. Vanrenen (B) · S. Smith · J. MarchesiniDepartment of Computer Science/PKI Lab, Dartmouth College,Hanover NH 03755, USAE-mail: [email protected],[email protected], [email protected] MotivationBecause it does not require sharing secrets a priori, publickey cryptography can enable a variety of secure commu-nications among parties that have never met. For example,in the case of digital signatures, a keyholder takes an actionwith his private key, and the relying party verifies thisaction against the corresponding public key. However, thecorrectness of the trust decisions a relying party makes,based on this verification, depends on the assumption thatthe entity knowing the matching private key possessescertain properties (e.g., “is student Alice at DartmouthCollege”). In practice, a certificate is a signed assertionbinding a public key to such properties.Public key infrastructure (PKI) refers to the surroundingtechnology and operations necessary for making public keycryptography work in practical applications. A primary roleof PKI is creating certificates to indicate such bindings anddistributing the certificates to relying parties. When the bind-ing that a certificate expresses ceases to hold, this certificateneeds to be revoked, and this revocation information needsto propagate to relying parties, lest they make incorrect trustjudgments regarding that public key.Consequently, fast and scalable certificate revocation hasbeen area of active research in recent years (e.g., [24, 25]).In their Security Mediator1(SEM) approach, Boneh et al. [4]proposed a system that revokes the ability of the keyholderto use a private key, instead of (or in addition to) revokingthe certificate attesting to the corresponding public key. If aprivate key operation cannot take place after the binding hasbeen revoked, then a relying party does not need to checkthe revocation status.2.2 ArchitectureThe SEM approach is based on mediated RSA (mRSA),avariant of RSA which splits the private key of a user into1Also referred to as “semi-trusted mediator.”G. Vanrenen et al.UserSecuritymediator(SEM)Request partial decryptionor partial signatureResults of partial computationCombine SEM resultswith user's resultsFig. 1 In security-mediated RSA, the user has a key pair (as in ordinary RSA). However, the user u’s private exponent is divided into two pieces:one piece, duser,u, is held by the user, and th other, dsem,u, is held by the security mediator. To carry out an operation with the user’s private key,both parties must participatetwo parts. As in standard RSA, each user has a public key(nu, eu) and a private key du,wheren is the product oftwo large primes, gcd(eu,φ(nu)) = 1, and du∗ eu= 1(mod φ(nu)). The public key of a user u is the same asin standard RSA, as is the public-key operation. However,in mediated RSA, we divide the private key duinto two“halves” dsem,uand duser,u,wheredu= dsem,u+ duser,u(mod φ(nu)).In the SEM approach, the half duser,uis held by the userand the half dsem,uis held by the mediator (We note thatdsem,uand duser,uare each statistically unique for each useru.) This division of the private key requires changes to thestandard RSA key setup because a SEM must not knowduser,uand a user must not know dsem,u. So, a trusted party(e.g., a CA) performs key setup by generating a statisticallyunique {pu, qu, eu, du, dsem,u} for a user u. The private keyduis generated in the standard manner, but is communicatedto neither the SEM nor the user. Instead, dsem,uis chosen asa random integer in [0, nu−1],andduser,uis then calculatedas duser,u= du−dsem,u(mod φ(nu)).Because the private key duis split into two pieces, privatekey operations require the participation of both the user andthe SEM: e.g., each party raises the message to its share ofthe exponent, modulo n, and the results are then multiplied,also modulo n (see Fig. 1.) Thus the full private key neverneeds to be reconstructed; also, since the user initiates theseoperations, the SEM does not learn exactly what the user issigning or decrypting.2.3 AdvantagesThe SEM approach provides several advantages. Since theseessentially are standard RSA operations, a SEM PKI iscompatible with most legacy public-key cryptography tools.Since the mediator is not involved in the public key oper-ations (encryption and signature verification), those userswho do not hold SEM-protected private keys do not evenneed to know about these mediators. Because of this, theSEM network can be seamlessly integrated with legacy in-frastructure. Since a full private-key operation can occuronly if the SEM believes the user’s key pair is valid, thenthe system can revoke a key