You are looking at a specific version 20200409:171145 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAMcombinatorial optimizationbootstrap percolation
Contact author(s)
samuel dittmer @ gmail com,rafail @ cs ucla edu
History
2020-06-08: last of 2 revisions
2020-04-02: received
See all versions
Short URL
https://ia.cr/2020/377
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.