License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2020.11
URN: urn:nbn:de:0030-drops-121164
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12116/
Go to the corresponding LIPIcs Volume Portal

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

Oblivious Parallel Tight Compaction

pdf-format:
LIPIcs-ITC-2020-11.pdf (0.6 MB)

Abstract

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 Exclusive-Read-Exclusive-Write Parallel-RAM model (i.e., EREW PRAM, 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.

BibTeX - Entry

@InProceedings{asharov_et_al:LIPIcs:2020:12116,
  author =	{Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Enoch Peserico and Elaine Shi},
  title =	{{Oblivious Parallel Tight Compaction}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12116},
  URN =		{urn:nbn:de:0030-drops-121164},
  doi =		{10.4230/LIPIcs.ITC.2020.11},
  annote =	{Keywords: Oblivious tight compaction, parallel oblivious RAM, EREW PRAM}
}

Keywords: Oblivious tight compaction, parallel oblivious RAM, EREW PRAM
Collection: 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Issue Date: 2020
Date of publication: 04.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI