Welcome to the resource topic for 2020/377
Title:
Oblivious tight compaction in O(n) time with smaller constant
Authors: Samuel Dittmer, 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.
ePrint: https://eprint.iacr.org/2020/377
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .