Shadow Block: Accelerating ORAM Accesses with Data Duplication

摘要

Oblivious RAM (ORAM) is a cryptographic primitive designed to hide memory access patterns. To achieve this objective, the intended data block is loaded and evicted back together with other data blocks and dummy blocks in each ORAM access. To further protect the timing pattern, extra dummy ORAM accesses are triggered periodically. Such designs lead to huge memory access overheads. Many techniques have been proposed to mitigate this problem by reducing the total number of ORAM accesses and the number of blocks per access. However, the impact of the access order of intended data block in an ORAM access is not addressed yet. In this work, we argue that higher performance can be achieved by advancing the access to the intended data block in ORAM accesses. However, changing the access order of blocks directly compromises the ORAM security. To solve this problem, we propose a duplication method to advance the access to the intended data blocks without compromising the ORAM security. The method leverages dummy blocks to store extra copies of data blocks, to facilitate early access of intended data blocks. These dummy blocks with valid data duplications are called Shadow blocks in this work. We further introduce two data duplication techniques, called RD-Dup and HD-Dup, to reorder the data block access for different purposes. In addition, we propose ORAM space partitioning to make RD-Dup and HD-Dup cooperate with each other efficiently. Compared with state-of-the-art ORAMs, our design can achieve a 32% reduction in system execution time on average, with negligible hardware overheads.