Scheme (mathematics)

Bandwidth (computing)

Overhead (engineering)

Block size

Computer security

Encryption

Operating system

Variable (mathematics)

Parallel computing

Computer science

Homomorphic encryption

Computer network

Cryptosystem

Mathematics

Block (permutation group theory)

Mathematical analysis

Geometry

Combinatorics

Arithmetic

Key (lock)

Information Sciences

Oblivious RAM (ORAM) is important for applications that require hiding access patterns. Many ORAM schemes have been proposed but most of them support only storing blocks of the same size. For the variable length data blocks, they usually fill them upto the same length before uploading, which leads to an increase in storage space and network bandwidth usage. To develop the first practical ORAM with variable block size, we proposed the "DivORAM" by remodeling the tree-based ORAM structure. It employs an additively homomorphic encryption scheme (Damgård–Jurik cryptosystem) executing at the server side to save the client computing overhead and the network bandwidth cost. As a result, it saves network bandwidth 30% comparing with Ring ORAM and 40% comparing with HIRB ORAM. Experiment results show that the response time of DivORAM is 10 × improved over Ring ORAM for practical parameters.

DivORAM: Towards a practical oblivious RAM with variable block size