International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Weighted ORAM, with Applications to Searchable Symmetric Encryption

Authors:
Léonard Assouline , ENS, Paris
Brice Minaud , Inria and ENS, Paris
Download:
DOI: 10.1007/978-3-031-30545-0_15 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
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. 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.
BibTeX
@inproceedings{eurocrypt-2023-32947,
  title={Weighted ORAM, with Applications to Searchable Symmetric Encryption},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30545-0_15},
  author={Léonard Assouline and Brice Minaud},
  year=2023
}