The Blind Stone Tablet: Outsourcing Durability to Untrusted Parties

This paper introduces a new paradigm for outsourcing the durability property of a multi-client transactional database to an untrusted service provider. Specifically, the authors enable untrusted service providers to support transaction serialization, backup and recovery for clients, with full data confidentiality and correctness. Moreover, providers learn nothing about transactions except their size and timing, thus achieving read and write access pattern privacy.