XML is increasingly becoming the format of choice for information exchange, in such critical areas such as government, finance, healthcare and law, where integrity is of the essence. As this trend grows, one can expect that documents (or collections thereof) may get quite large, and clients may wish to query for specific elements of these documents. In critical applications, clients must be assured that they are getting complete and correct answers to their queries. Existing approaches to signing XML documents don’t support the authentication of answers to queries. Certainly, a server could process queries and certify answers by digitally signing them with an on-line private key; however, the server, and its on-line private key, would be vulnerable to external hacking and insider attacks. We propose a new approach to signing XML documents which allows untrusted servers to answer certain types of path queries and selection queries over XML documents without the need for trusted on-line signing keys. This approach enhances both the security and scalability of publishing information in XML format over the internet. In addition, it provides greater flexibility in authenticating parts of XML documents, in response to commercial or security policy considerations. 1