DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2014.554

Data-Oblivious Data Structures

Authors: John C. Mitchell and Joe Zimmerman

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract

An algorithm is called data-oblivious if its control flow and memory access pattern do not depend on its input data. Data-oblivious algorithms play a significant role in secure cloud computing, since programs that are run on secret data—as in fully homomorphic encryption or secure multi-party computation—must be data-oblivious. In this paper, we formalize three definitions of data-obliviousness that have appeared implicitly in the literature, explore their implications, and show separations. We observe that data-oblivious algorithms often compose well when viewed as data structures. Using this approach, we construct data-oblivious stacks, queues, and priority queues that are considerably simpler than existing constructions, as well as improving constan factors. We also establish a new upper bound for oblivious data compaction, and use this result to show that an "offline" variant of the Oblivious RAM problem can be solved with O(log(n).log(log(n))) expected amortized time per operation - as compared with O(log^2(n)/log(log(n))), the best known upper bound for the standard online formulation.

Cite as

John C. Mitchell and Joe Zimmerman. Data-Oblivious Data Structures. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 554-565, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mitchell_et_al:LIPIcs.STACS.2014.554,
  author =	{Mitchell, John C. and Zimmerman, Joe},
  title =	{{Data-Oblivious Data Structures}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{554--565},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.554},
  URN =		{urn:nbn:de:0030-drops-44876},
  doi =		{10.4230/LIPIcs.STACS.2014.554},
  annote =	{Keywords: Data-oblivious algorithms, Data-oblivious data structures, Oblivious RAM, Secure multi-party computation, Secure cloud computing}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.FSTTCS.2011.6

A Domain-Specific Language for Computing on Encrypted Data (Invited Talk)

Authors: Alex Bain, John Mitchell, Rahul Sharma, Deian Stefan, and Joe Zimmerman

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

In cloud computing, a client may request computation on confidential data that is sent to untrusted servers. While homomorphic encryption and secure multiparty computation provide building blocks for secure computation, software must be properly structured to preserve confidentiality. Using a general definition of secure execution platform, we propose a single Haskell-based domain-specific language for cryptographic cloud computing and prove correctness and confidentiality for two representative and distinctly different implementations of the same programming language. The secret sharing execution platform provides information-theoretic security against colluding servers. The homomorphic encryption execution platform requires only one server, but has limited efficiency, and provides secrecy against a computationally-bounded adversary. Experiments with our implementation suggest promising computational feasibility, as cryptography improves, and show how code can be developed uniformly for a variety of secure cloud platforms, without explicitly programming separate clients and servers.

Cite as

Alex Bain, John Mitchell, Rahul Sharma, Deian Stefan, and Joe Zimmerman. A Domain-Specific Language for Computing on Encrypted Data (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 6-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bain_et_al:LIPIcs.FSTTCS.2011.6,
  author =	{Bain, Alex and Mitchell, John and Sharma, Rahul and Stefan, Deian and Zimmerman, Joe},
  title =	{{A Domain-Specific Language for Computing on Encrypted Data}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{6--24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.6},
  URN =		{urn:nbn:de:0030-drops-33604},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.6},
  annote =	{Keywords: Domain-Specific Language, Secret Sharing, Homomorphic Encryption}
}

Search Results

Documents authored by Zimmerman, Joe

Data-Oblivious Data Structures

Abstract

Cite as

A Domain-Specific Language for Computing on Encrypted Data (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message