Affiliations: [a] Room 226, MIT Lab for Computer Science, 200 Technology Square, Cambridge, MA 02139, USA. E-mail: [email protected] | [b] Microsoft, One Microsoft Way, Redmond, WA 98052, USA. E-mail: [email protected] | [c] Intel Corporation, 2111 NE 25th Ave, Hillsboro, OR 97124, USA. E-mail: [email protected] | [d] aQuery, 100 Fellsway West, Somerville, MA 02145, USA. E-mail: [email protected] | [e] Tower Research Capital, 377 Broadway 11th Floor, New York, NY 10013, USA. E-mail: [email protected] | [f] Room 324, MIT Lab for Computer Science, 200 Technology Square, Cambridge, MA 02139, USA. E-mail: [email protected]
Correspondence:
[*]
Corresponding author.
Abstract: SPKI/SDSI is a novel public-key infrastructure emphasizing naming, groups, ease-of-use, and flexible authorization. To access a protected resource, a client must present to the server a proof that the client is authorized; this proof takes the form of a “certificate chain” proving that the client's public key is in one of the groups on the resource's ACL, or that the client's public key has been delegated authority (in one or more stages) from a key in one of the groups on the resource's ACL. While finding such a chain can be nontrivial, due to the flexible naming and delegation capabilities of SPKI/SDSI certificates, we present a practical and efficient algorithm for this problem of “certificate chain discovery”. We also present a tight worst-case bound on its running time, which is polynomial in the length of its input. We also present an extension of our algorithm that is capable of handling “threshold subjects”, where several principals are required to co-sign a request to access a protected resource.
