Paper 2023/350

Weighted Oblivious RAM, with Applications to Searchable Symmetric Encryption

Leonard Assouline, École Normale Supérieure - PSL, French National Centre for Scientific Research, French Institute for Research in Computer Science and Automation
Brice Minaud, École Normale Supérieure - PSL, French National Centre for Scientific Research, French Institute for Research in Computer Science and Automation
Abstract

Existing Oblivious RAM protocols do not support the storage of data items of variable size in a non-trivial way. While the study of ORAM for items of variable size is of interest in and of itself, it is also motivated by the need for more performant and more secure Searchable Symmetric Encryption (SSE) schemes. In this article, we introduce the notion of weighted ORAM, which supports the storage of blocks of different sizes. In a standard ORAM scheme, each data block has a fixed size $B$. In weighted ORAM, the size (or weight) of a data block is an arbitrary integer $w_i \in [1,B]$. The parameters of the weighted ORAM are entirely determined by an upper bound $B$ on the block size, and an upper bound $N$ on the total weight $\sum w_i$ of all blocks\textemdash regardless of the distribution of individual weights $w_i$. During write queries, the client is allowed to arbitrarily change the size of the queried data block, as long as the previous upper bounds continue to hold. We introduce a framework to build efficient weighted ORAM schemes, based on an underlying standard ORAM satisfying a certain suitability criterion. This criterion is fulfilled by various Tree ORAM schemes, including Simple ORAM and Path ORAM. We deduce several instantiations of weighted ORAM, with very little overhead compared to standard ORAM. As a direct application, we obtain efficient SSE constructions with attractive security properties.

Note: Full version of a paper to appear in EUROCRYPT2023

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
Keywords
ORAMSSE
Contact author(s)
leonard assouline @ ens fr
brice minaud @ ens fr
History
2023-03-15: approved
2023-03-10: received
See all versions
Short URL
https://ia.cr/2023/350
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/350,
      author = {Leonard Assouline and Brice Minaud},
      title = {Weighted Oblivious {RAM}, with Applications to Searchable Symmetric Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/350},
      year = {2023},
      url = {https://eprint.iacr.org/2023/350}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.