Cryptology ePrint Archive: Report 2020/858

Client-oblivious OPRAM

Gareth T. Davies and Christian Janson and Daniel P. Martin

Abstract: Oblivious Parallel RAM (OPRAM) enables multiple clients to synchronously make read and write accesses to shared memory (more generally, any data-store) whilst hiding the access patterns from the owner/provider of that shared memory. Prior work is best suited to the setting of multiple processors (or cores) within a single client device, and consequently there are shortcomings when applying that work to the multi-client setting where distinct client devices may not trust each other, or may simply wish to minimise for legal reasons or otherwise the volume of data that is leaked to other client devices. In prior constructions, obliviousness from the storage provider is achieved by passing accesses between the clients in one or more sorting networks, both before and after the logical access is made to the shared memory: this process inherently leaks the contents of the accesses to those other clients. In this paper we address this issue by introducing the notion of client obliviousness for OPRAM, which asks that clients should only learn as much as is necessary for the scheme to function correctly. We provide an instantiation using established tools, with careful analysis to show that our new notion and regular OPRAM security are met. This introduces several subtleties which were not previously apparent, and we further discuss the implications of using the OPRAM model in the context of outsourced storage.

Category / Keywords: cryptographic protocols / oblivious parallel RAM, client obliviousness, outsourced storage security

Original Publication (with major differences): ICICS 2020

Date: received 9 Jul 2020

Contact author: davies at uni-wuppertal de,christian janson@cryptoplexity de

Available format(s): PDF | BibTeX Citation

Note: A preliminary version of this paper appears in the proceedings of ICICS 2020. This is the full version.

Version: 20200712:125002 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]