P. Devanbu, M. Gertz, A. Kwong, C. Martel, G. Nuckolls, and S.G. Stubblebine,
Flexible Authentication of XML documents, to appear in the 8th ACM
Conference on Computer and Communications Security, 2001. 


Summary:

The authors have developed a scheme for allowing clients to validate
the answers to certain queries from untrusted publishers.  This
includes both path queries and selection queries.  The main focus of
the paper is on non-recursive DTD's, although the authors claim their
method can also be extended to recursive DTD's.  The method presented
on the paper is dependent on three main facts: (1) there are only a
finite number of paths in a non-recursive DTD, (2) XML documents (and
subtrees) can be securly hashed using DOMHASHes (which are hard to
forge), and (3) using a Merkle hash, groups of hashes can be combined
into a single digital signature which can be used to verify and link
the individual hashes. The authors present a basic version of their
algorithms along with an extension based on a new data structure
called an 'xtrie' that stores the set of possible paths based on a
given DTD.

We discussed whether XML queries are just a special case of general
queries and decided this paper might just have well been entitle
"Flexible Authentication of Tree-based Structures".  We discussed the
value of the xtrie extension, and also covered Merkle hashes in
general.  We also attempted to clarify how this approach would extend
to non-recursive DTD's.


Pros (by Adam Slagell):

- It is a good model to try and avoid requiring trust of all the
servers that may carry out queries.

- It is good, and most likely should be expected, that they provide
empirical data.  However, I think they should have collected empirical
data on more than just size comparisons of xtries to tables. Things
such as algorithm speeds and benchmark results from an actual
full-fledged implementation of the entire system would be appropriate.

- They not only designed a working system, but they also made many
enhancements and revisions to make it more efficient and practical.

- They were clear to state their limitations, namely with recursive
DTDs.  However 63 out of 100 being non-recursive hardly seems
sufficient data to indicate that most DTDs are non-recursive, and in
no way does it indicate that non-recursive DTDs is a trend for the
future.


Cons (by Kan-yuan Mark Lee):

- No specific description of recursive DTD's - must enumerate all
paths in document.  Document can be extremely large, percentage of
DTD's that are non-recursive is also large.

- No benchmarks characterizing performace of XML documents with
  authentication - building trees and digests searches takes
  processing power

- Abstract and intro have identical first three sentences

- Would require changes to database implementation - should discuss
  current XML database software

- Should compare against existing forms of authentication w/o using
  XML -- benchmarks