The ability to enforce policies on online access to data is a crucial ingredient of any viable Web technology. Recently, several elaborate schemes for fine-grained control of access to published Extensible Markup Language (XML) documents were developed. Instead of producing many versions of the same data for each potential user group, these policies avoid data duplication by relying on cryptography. For example, these policies allow users to publish medical records as XML documents so that only authorized users can see their contents.

In 2003, Miklau and Suciu developed a policy query language that implements fine-grained access policies on XML documents and a corresponding logical model based on the concept of protection [1]. They showed how to translate consistent policies into protections and how to subsequently implement protections through XML encryption. Their analysis, however, does not address the question of whether the used cryptographic keys and encryption techniques correctly implement the abstract notion of protection. In this paper, Abadi and Warinschi address and bridge this crucial gap. They replace Miklau and Suciu’s informal concept of data secrecy with a strong cryptographic definition.

The authors use the following notion of security: assume that an adversary is given an arbitrary set of keys and the ability to select two instantiations for the data in all nodes that occur in an XML document; these two instantiations must coincide on the nodes to which the adversary has rightful access according to its keys, but may differ elsewhere. Given the partially encrypted document that corresponds to one of its two documents, the adversary must now decide which of the two instantiations was used in generating the partially encrypted document. Security means that the adversary cannot do much better than picking at random. Using a more formal version of this notion of security, the authors are able to prove that the encryption-based techniques suggested by Miklau and Suciu secure XML data.

After a short introduction in Section 1, the paper reviews XML access control with protections in Section 2. In Section 3, the authors introduce a formal language to represent cryptographic expressions. The main result, showing that protections are secure, is presented in Section 4. Section 5 discusses some extensions, and the conclusions are presented in Section 6.

I highly recommend this well-written paper. It makes a significant contribution, since its approach may serve as a blueprint for other researchers in their attempts to bridge the gap between the design and implementation of online security on one hand, and a strong guarantee of online security on the other.