Paper 2020/125

Oblivious Parallel Tight Compaction

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi


In tight compaction, one is given an array of balls some of which are marked 0 and the rest are marked 1. The output of the procedure is an array that contains all of the original balls except that now the 0-balls appear before the 1-balls. In other words, tight compaction is equivalent to sorting the array according to 1-bit keys (not necessarily maintaining order within same-key balls). Tight compaction is not only an important algorithmic task by itself, but its oblivious version has also played a key role in recent constructions of oblivious RAM compilers. We present an oblivious deterministic algorithm for tight compaction such that for input arrays of $n$ balls requires $O(n)$ total work and $O(\log n)$ depth. Our algorithm is in the EREW Parallel-RAM model (i.e., the most restrictive PRAM model), and importantly we achieve asymptotical optimality in both total work and depth. To the best of our knowledge no earlier work, even when allowing randomization, can achieve optimality in both total work and depth.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Information-Theoretic Cryptography (ITC) 2020
oblivious algorithmsinformation theoretic cryptography
Contact author(s)
Gilad Asharov @ biu ac il
ilan komargodski @ ntt-research com
wklin @ cs cornell edu
enoch @ dei unipd it
runting @ gmail com
2020-04-06: revised
2020-02-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Enoch Peserico and Elaine Shi},
      title = {Oblivious Parallel Tight Compaction},
      howpublished = {Cryptology ePrint Archive, Paper 2020/125},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.