Secure systems are not easy to implement, even for experts. But security is becoming an issue for more and more applications. For example, an e-mail client may need to obtain cryptographic keys to send private mail, or a web server may need to authenticate page requests to protect corporate data. Usually the programmers who write these applications are not security experts, and cannot be expected to build a secure system from cryptographic primitives (signing and verifying signatures, encryption and decryption).

The goal of the SD3 project is to make it easy for applications to define security policies in a distributed system. SD3 is a trust management system: it provides a high-level, application independent language for authentication and access control. An application uses SD3 by writing a security policy in this language. SD3 then handles all of the details needed to authenticate user requests and check whether access should be granted according to the policy, including retrieval of digital certificates and verification of signatures.

SD3 provides an API that lets applications query a daemon process that maintains security policies. Each application defines a security policy in SD3's high-level language, and uses the SD3 daemon to maintain the policy. When an application needs to consult its policy, it queries the SD3 daemon in the high-level policy language. The SD3 daemon performs all of the security-critical computation needed to answer the query. This includes such things as verifying signatures on locally cached digital certificates, and exchanging encrypted messages with remote SD3 daemons (commonly needed in networks with centralized administration of security policies). Application writers thus only need to know how to write SD3 security policies, and do not have to be experts in cryptography. The SD3 daemon handles all of the cryptography transparently to the application.

The figure below shows how an application typically uses SD3.

SD3 diagram

In the first step (1), the SD3 daemon is started and configured with a local policy file. Once this initial configuration is finished, the application can query the daemon about the policy as necessary. Typically, an application does so when it receives a request from a user. (2) The user may supply some certificates to the application along with the request, as proof that the request should be granted. (3) Instead of looking at the certificates, the application forwards them along with the request to the SD3 daemon. The SD3 daemon will examine the certificates and the local policy, verify signatures, and decide whether the request should be granted. (4,5) If the local policy depends on a remote policy (as in the case of a centrally administered system), the SD3 daemon will communicate with a remote data source (an SD3 daemon, LDAP directory, etc.) to check the request. (6) Finally, SD3 sends the application the answer to its query.


Authentication in SD3 is based on a digital signature scheme, in which a user's signature is verified through their public cryptographic key. The difficulty is in distributing a user's public key to all of the applications that the user must access, over an untrusted network -- the public key distribution problem.

In SD3, the public keys are distributed under the control of a policy in a high-level language. For example, here is a typical SD3 policy file:

    AliceKey =  Principal(DSA("P: 6e+1xVU3D5d..."));
    BobKey =    Principal(DSA("P: vO3gkdeTc0E..."));

    PKD("alice",AliceKey):- ;
    PKD("bob",BobKey)    :- ;
    PKD(user,key)        :- AliceKey$PKD(user,key);
The policy file defines two public keys: AliceKey and BobKey (the key is a large number, truncated here to save space). It also defines a policy, PKD, that associates keys with user names. Traditionally, this sort of policy is called a public key directory, since it can be used to look up a user's key, much as a phone directory can be used to look up someone's phone number. For example, the policy says that the key of the user "alice" is AliceKey, and the key of "bob" is BobKey. The last line of the policy is the most interesting: it says that PKD(user,key) holds if AliceKey$PKD(user,key) holds. AliceKey$PKD is the public key directory defined by Alice (every user is allowed to define their own, distinct public key directory). The policy says that whenever Alice's policy says that a user has a particular key, we will believe that as well.

Once an application has set up a public key directory, it can query the SD3 daemon to extract keys. For example, an e-mail application could get the key of a user "claire" by asking SD3 the following query:

   (k) :- PKD("claire",k);
Intuitively, this can be read, "return all keys k such that PKD("claire",k) holds."

SD3 will evaluate the query by asking Alice for Claire's key. Alice will have her own SD3 server and a policy defining her PKD, so this amounts to a query/response protocol between two SD3 servers. A server signs its own messages and verifies the signature on messages that it receives, so that messages cannot be tampered with on the untrusted Internet. Alternately, the SD3 server might have a certificate signed by AliceKey that gives Claire's key; for example, Claire could have included her key certificate in e-mail. In this case, SD3 can verify the key certificate and safely get Claire's key without contacting Alice's SD3 server; in fact, Alice can be entirely offline. The decision to use a certificate to short-circuit network communication is made automatically by SD3.

SD3 policies can also express access control. For example, the policies below define groups and permissions in SD3:

  Group("wheel","alice")    :- ;
  Group("employee","alice") :- ;
  Group("employee","bob")   :- ;

  Perms("bob","file /etc/hosts","modify") :- ;
  Perms(user,"file /etc/motd","read") :- Group("employee",user);
  Perms(user,resource,op) :- PKD("alice",k), k$Perms(user,resource,op);

The first policy says that Alice is in the groups "wheel" and "employee", while Bob is only an employee. The second policy says that Bob has permission to modify /etc/hosts, that any employee can read /etc/motd, and that Alice is trusted to add to the permissions policy. Once the policy is defined, an application can query SD3 regarding the policy, for example:

  • What users are employees?
                    (user) :- Group("employee",user)
  • What resources can Bob modify?
                    (resource) :- Perms("bob",resource,"modify")
  • What is the access control list of /etc/motd, i.e., who can perform what operations on the file?
                    (user,op) :- Perms(user,"file /etc/motd",op)
SD3 is designed to express the security policies of a wide range of applications. It also incorporates a variety of policy retrieval mechanisms (including signed query/response protocols, "pushed" certificates, revocation mechanisms, and offline signing protocols) to accomodate tradeoffs in availability and security.


For a more detailed introduction to SD3, including a description of how SD3 can be used to build a public key infrastructure similar to DNSSEC, see:
SD3: A Trust Management System with Certified Evaluation. Trevor Jim. IEEE Symposium on Security and Privacy, May 2001. (Abstract, PDF)

Another paper describes the theoretical foundation of SD3:

Dynamically Distributed Query Evaluation. Trevor Jim and Dan Suciu. ACM Symposium on Principles of Database Systems, May 2001. (PDF)

Previous work

Many of the ideas used in SD3 were developed in my previous trust management system, QCM. In particular, QCM was the first distributed trust management system, and the first based on a declarative query language. Technically, SD3 can be seen as an extension of QCM to handle recursive queries and to do certified evaluation.