Search Results

Documents authored by Persiano, Giuseppe

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.104
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing

Authors: Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, and Or Zamir

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We present a simple and provably optimal non-adaptive cell probe data structure for the static dictionary problem. Our data structure supports storing a set of n key-value pairs from [u]× [u] using s words of space and answering key lookup queries in t = O(lg(u/n)/lg(s/n)) non-adaptive probes. This generalizes a solution to the membership problem (i.e., where no values are associated with keys) due to Buhrman et al. We also present matching lower bounds for the non-adaptive static membership problem in the deterministic setting. Our lower bound implies that both our dictionary algorithm and the preceding membership algorithm are optimal, and in particular that there is an inherent complexity gap in these problems between no adaptivity and one round of adaptivity (with which hashing-based algorithms solve these problems in constant time). Using the ideas underlying our data structure, we also obtain the first implementation of a n-wise independent family of hash functions with optimal evaluation time in the cell probe model.
Cite as

Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, and Or Zamir. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 104:1-104:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{larsen_et_al:LIPIcs.ICALP.2024.104,
  author =	{Larsen, Kasper Green and Pagh, Rasmus and Persiano, Giuseppe and Pitassi, Toniann and Yeo, Kevin and Zamir, Or},
  title =	{{Optimal Non-Adaptive Cell Probe Dictionaries and Hashing}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{104:1--104:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.104},
  URN =		{urn:nbn:de:0030-drops-202471},
  doi =		{10.4230/LIPIcs.ICALP.2024.104},
  annote =	{Keywords: non-adaptive, cell probe, dictionary, hashing}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.161
CacheShuffle: A Family of Oblivious Shuffles

Authors: Sarvar Patel, Giuseppe Persiano, and Kevin Yeo

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider oblivious two-party protocols where a client outsources N blocks of private data to a server. The client wishes to access the data to perform operations in such a way that the access pattern does not leak information about the data and the operations. In this context, we consider oblivious shuffling with a focus on bandwidth efficient protocols for clients with small local memory. In the shuffling problem, the N outsourced blocks, B_1,...,B_N, are stored on the server according to an initial permutation pi. The client wishes to reshuffle the blocks according to permutation sigma. Oblivious shuffling is a building block in several applications that hide patterns of data access. In this paper, we introduce a generalization of the oblivious shuffling problem, the K-oblivious shuffling problem, and provide bandwidth efficient algorithms for a wide range of client storage requirements. The task of a K-oblivious shuffling algorithm is to shuffle N encrypted blocks that were previously randomly allocated on the server in such a way that an adversarial server learns nothing about either the new allocation of blocks or the block contents. The security guarantee must hold when an adversary has partial information on the initial placement of a subset of K <=N revealed blocks. The notion of oblivious shuffling is obtained for K=N. We first study the N-oblivious shuffling problem and start by presenting CacheShuffleRoot, that is tailored for clients with O(sqrt{N}) blocks of memory and uses approximately 4N blocks of bandwidth. CacheShuffleRoot is a 4x improvement over the previous best known N-oblivious shuffle for practical sizes of N. We then generalize CacheShuffleRoot to CacheShuffle that can be instantiated for any client memory size S and requires O(N log_S N) blocks of bandwidth. Next, we present K-oblivious shuffling algorithms that require 2N + f(K,S) blocks of bandwidth for all K and a wide range of S. Any extra bandwidth above the 2N lower bound depends solely on K and S. Specifically, for clients with O(K) blocks of memory, we present KCacheShuffleBasic that uses exactly 2N blocks of bandwidth. For clients with memory S <= K, we present KCacheShuffle, that requires 2N + O(K log_S K) blocks of bandwidth. Finally, motivated by applications to ORAMs, we consider the case where the server stores D dummy blocks whose contents are irrelevant in addition to the N real blocks. For this case, we design algorithm KCacheShuffleDummy that shuffles N+D blocks with K revealed blocks using O(K) blocks of client storage and approximately D+2N blocks of bandwidth.
Cite as

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. CacheShuffle: A Family of Oblivious Shuffles. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 161:1-161:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{patel_et_al:LIPIcs.ICALP.2018.161,
  author =	{Patel, Sarvar and Persiano, Giuseppe and Yeo, Kevin},
  title =	{{CacheShuffle: A Family of Oblivious Shuffles}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{161:1--161:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.161},
  URN =		{urn:nbn:de:0030-drops-91651},
  doi =		{10.4230/LIPIcs.ICALP.2018.161},
  annote =	{Keywords: Shuffling, Data-Oblivious Algorithms}
}
Document
DOI: 10.4230/DagSemRep.345
Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251)

Authors: Evripidis Bampis, Klaus Jansen, Giuseppe Persiano, Roberto Solis-Oba, and Gordon T. Wilfong

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Evripidis Bampis, Klaus Jansen, Giuseppe Persiano, Roberto Solis-Oba, and Gordon T. Wilfong. Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251). Dagstuhl Seminar Report 345, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{bampis_et_al:DagSemRep.345,
  author =	{Bampis, Evripidis and Jansen, Klaus and Persiano, Giuseppe and Solis-Oba, Roberto and Wilfong, Gordon T.},
  title =	{{Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{345},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.345},
  URN =		{urn:nbn:de:0030-drops-152265},
  doi =		{10.4230/DagSemRep.345},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact