Cryptology ePrint Archive: Report 2020/377

Oblivious tight compaction in O(n) time with smaller constant

Samuel Dittmer and Rafail Ostrovsky

Abstract: Oblivious compaction is a crucial building block for hash-based oblivious RAM. Asharov et al. recently gave a O(n) algorithm for oblivious tight compaction. Their algorithm is deterministic and asymptotically optimal, but it is not practical to implement because the implied constant is $\gg 2^{38}$. We give a new algorithm for oblivious tight compaction that runs in time $< 16014.54n$. As part of our construction, we give a new result in the bootstrap percolation of random regular graphs.

Category / Keywords: cryptographic protocols / Oblivious RAM, combinatorial optimization, bootstrap percolation

Date: received 1 Apr 2020, last revised 8 Jun 2020

Contact author: samuel dittmer at gmail com,rafail@cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20200608:171541 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]