Onion Ring ORAM - Efficient Constant Bandwidth Oblivious RAM from (Leveled) TFHE
| Autor: | Ling Ren, Hao Chen, Ilaria Chillotti |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Ring (mathematics)
Cryptographic primitive Logarithm business.industry Computer science Homomorphic encryption 0102 computer and information sciences 02 engineering and technology Parallel computing Encryption 01 natural sciences Permutation 010201 computation theory & mathematics Path (graph theory) 0202 electrical engineering electronic engineering information engineering Bandwidth (computing) 020201 artificial intelligence & image processing Oblivious ram business |
| Zdroj: | Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security CCS |
| DOI: | 10.1145/3319535.3354226 |
| Popis: | Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to hide access pattern to its data encrypted and stored at a remote server. Traditionally, ORAM algorithms assume the server acts purely as a storage device. Under this assumption, ORAM has at least log(N) bandwidth blowup for N data entries. After three decades of improvements, ORAM algorithms have reached the optimal logarithmic bandwidth blowup. Nonetheless, in many practical use-cases a constant bandwidth overhead is desirable. To this purpose, Devadas et al. (TCC 2016) formalized the server computation model for ORAM and proposed Onion ORAM which relies on homomorphic computation to achieve constant worst-case bandwidth blowup. This line of work is generally believed to be purely theoretical, due to the large overheads of homomorphic computation. In this paper, we present Onion Ring ORAM, the first efficient constant bandwidth ORAM scheme in the single server model, based on the Onion ORAM construction and the leveled version of the TFHE scheme by Chillotti et al.. We propose a series of improvements, most notably including a more efficient homomorphic permutation protocol. We implement Onion Ring ORAM and show that it can outperform state-of-the-art logarithmic-bandwidth ORAM like Path ORAMs and Ring ORAM when the network throughput is limited. Under one setting, our construction reduces monetary cost per access by 40% and end-to-end latency by 35% over Ring ORAM. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|