Oblivious RAM with Worst-Case Logarithmic Overhead

Autor:	Elaine Shi, Wei-Kai Lin, Ilan Komargodski, Gilad Asharov
Rok vydání:	2021
Předmět:	Logarithm Computer science Computational security Overhead (computing) Parallel computing Binary logarithm Oblivious ram Constant (mathematics) Block size
Zdroj:	Advances in Cryptology – CRYPTO 2021 ISBN: 9783030842581 CRYPTO (4)
DOI:	10.1007/978-3-030-84259-8_21
Popis:	We present the first Oblivious RAM (ORAM) construction that for N memory blocks supports accesses with worst-case \(O(\log N)\) overhead for any block size \(\varOmega (\log N)\) while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8adee8bc35481397a6898102046a73ce https://doi.org/10.1007/978-3-030-84259-8_21 Zobrazit plný text záznamu