Beschreibung:
<jats:p>
We introduce a new practical mechanism for remote data storage with
<jats:italic>access pattern privacy</jats:italic>
and
<jats:italic>correctness</jats:italic>
. A storage client can deploy this mechanism to issue encrypted reads, writes, and inserts to a potentially curious and malicious storage service provider, without revealing information or access patterns. The provider is unable to establish any correlation between successive accesses, or even to distinguish between a read and a write. Moreover, the client is provided with strong correctness assurances for its operations—illicit provider behavior does not go undetected. We describe a practical system that can execute an unprecedented several queries per second on terabyte-plus databases while maintaining full computational privacy and correctness.
</jats:p>