Abstract
Simple Public Key Infrastructure (SPKI) was designed as a decentralized alternative to hierarchical identity-based infrastructures like X.509. While SPKI introduced innovative concepts such as local name spaces and tuple reduction, its original specification relied on informal rules for authorization. This paper provides a formal logical foundation for SPKI, introducing the language $L_{SPKI}$. By modeling certificates and revocation within a monotonic logic, the authors prove the soundness of SPKI's reduction rules and identify the conditions necessary for logical completeness.
Introduction
In the late 1990s, the Simple Public Key Infrastructure (SPKI) emerged, eventually merging with the Simple Distributed Security Infrastructure (SDSI). Unlike traditional Public Key Infrastructures (PKIs) that rely on global directories and hierarchical Certificate Authorities, SPKI/SDSI focused on decentralized authorization. Its core innovation was the use of "local names," allowing users to define their own namespaces (e.g., "Alice's Joe") rather than relying on a single global identity.
To determine if a specific request is authorized, SPKI utilizes a mechanism known as "tuple reduction." However, the original standard described these rules informally, leaving significant questions regarding their mathematical soundness and completeness. Furthermore, the security community debated whether features like certificate revocation necessitated nonmonotonic logic—a complex reasoning framework where new information can invalidate previous conclusions. This research seeks to resolve these ambiguities by constructing a rigorous logical model of SPKI.
Formalizing the Logic: $L_{SPKI}$
The authors develop $L_{SPKI}$, a formal language that extends the Logic of Local Name Containment (LLNC). To capture the dynamic nature of a security infrastructure, the model incorporates several key technical components:
- Temporal Semantics: The logic introduces the concept of a "run"—a function of time that models the lifecycle of certificates, including their issuance and expiration.
- Minimal Interpretations: To prevent the accidental "hallucination" of permissions, the authors employ a closed semantics approach. In this model, a name binding or authorization is only considered true if it is explicitly necessitated by the issued certificates.
- Refining Tuple Reduction: The authors translate the informal SPKI reduction rules into formal logical inference rules (labeled R1, R2, and R3). They further propose extensions (R0, R2', R3', and R4) to handle more sophisticated reasoning regarding name bindings and sets of authorized actions.
The Monotonicity of Revocation
One of the paper's most significant insights concerns the nature of certificate revocation. Conventionally, revocation is viewed as a nonmonotonic process: if a certificate is revoked, a previously valid authorization becomes invalid.
However, the authors demonstrate that SPKI’s implementation of revocation can be modeled using purely monotonic logic. In SPKI, a revocable certificate is only considered "applicable" if there is positive evidence—specifically a Certificate Revocation List (CRL) or a revalidation—covering the current time interval that does not list the certificate as revoked. Consequently, adding more CRLs to a knowledge base only increases the set of verifiable certificates. This insight simplifies the formal reasoning required for SPKI, as it avoids the complexities inherent in nonmonotonic systems.
Soundness, Completeness, and the "Small World" Problem
The formalization allows for a rigorous evaluation of the standard SPKI reduction rules:
- Soundness: The authors prove that the SPKI tuple reduction rules are sound. Any authorization derived through these rules is guaranteed to be valid according to the logic's underlying semantics.
- Weak Completeness: The standard rules (R1–R3) are shown to be complete for "concrete" queries—specifically, determining if a specific key is authorized for a specific action at a specific time.
- The Small World Problem: The researchers identified a unique edge case where logical validity depends on the size of the key space ($K$). In a "small world" with very few possible keys, one might logically conclude that two names are identical simply because no other keys exist for them to point to.
- Almost Completeness: By incorporating the authors' proposed extended rules (R2', R3', and R4), the system achieves "almost completeness." This means the rules can derive any valid conclusion provided the number of possible public keys is significantly larger than the number of issued certificates—a condition that is universally met in real-world cryptographic applications.
Limitations and Future Directions
While this reconstruction provides a solid foundation for SPKI, certain areas remain for future exploration. The current model simplifies SPKI by excluding "threshold subjects" (e.g., $M$-of-$N$ multi-signature requirements). While the authors suggest $L_{SPKI}$ could be extended to accommodate these, the formal proof has yet to be established. Additionally, while the logic defines what can be derived, it does not address the computational complexity of "certificate chain discovery"—the algorithmic efficiency of finding a valid path of authorized tuples in a large network. Finally, a full axiomatization of the $L_{SPKI}$ language remains a goal for future theoretical work.
Conclusion
By providing a formal logical semantics for SPKI, this work moves the standard from an informal set of heuristics to a mathematically grounded framework. The discovery that SPKI revocation is monotonic and the identification of the "small world" constraint provide essential clarity for both the theoretical study and the practical implementation of decentralized authorization systems.
Summary updated