This invention introduces a new paradigm for outsourcing the transaction processing backend of a multi-client database application to an untrusted service provider. Specifically, the invention enables 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.