Updating encrypted XML documents on untrusted machines

With XML and other data types becoming increasingly used in distributed systems, we have a need to update this data in a way that preserves privacy and integrity. Prior work has developed ways of encrypting XML documents for privacy, and adding integrity codes to ensure that the data is not tampered with. In this paper we present an algorithm that allows XML documents, or other tree-structured data, to be updated without decrypting them. In our model of a distributed system, several trusted machines have access to the decrypted form of a document and may request changes to it. These change requests are encrypted and sent to an untrusted update machine for processing. The update machine is able to take the original encrypted document, apply the encrypted changes, and produce an updated encrypted document. In addition, an integrity code is produced that proves the untrusted machine performed the update correctly. In practice, our algorithm allows trusted machines in a distributed system to send incremental updates to a storage server, even if that server is not allowed access to the clear text.