  Significant amounts of data are currently being stored and managed on
third-party servers. It is impractical for many small scale enterprises to own
their private datacenters, hence renting third-party servers is a viable
solution for such businesses. But the increasing number of malicious attacks,
both internal and external, as well as buggy software on third-party servers is
causing clients to lose their trust in these external infrastructures. While
small enterprises cannot avoid using external infrastructures, they need the
right set of protocols to manage their data on untrusted infrastructures. In
this paper, we propose TFCommit, a novel atomic commitment protocol that
executes transactions on data stored across multiple untrusted servers. To our
knowledge, TFCommit is the first atomic commitment protocol to execute
transactions in an untrusted environment without using expensive Byzantine
replication. Using TFCommit, we propose an auditable data management system,
Fides, residing completely on untrustworthy infrastructure. As an auditable
system, Fides guarantees the detection of potentially malicious failures
occurring on untrusted servers using tamper-resistant logs with the support of
cryptographic techniques. The experimental evaluation demonstrates the
scalability and the relatively low overhead of our approach that allows
executing transactions on untrusted infrastructure.
