Entrusting Private Computation and Data to Untrusted Networks
by Yuriy Brun, Nenad Medvidovic
Abstract:
We present sTile, a technique for distributing trust-needing computation onto insecure networks, while providing probabilistic guarantees that malicious agents that compromise parts of the network cannot learn private data. With sTile, we explore the fundamental cost of achieving privacy through data distribution and bound how much less efficient a privacy-preserving system is than a non-private one. This paper focuses specifically on NP-complete problems and demonstrates how sTile-based systems can solve important real-world problems, such as protein folding, image recognition, and resource allocation. We present the algorithms involved in sTile and formally prove that sTile-based systems preserve privacy. We develop a reference sTile-based implementation and empirically evaluate it on several physical networks of varying sizes, including the globally distributed PlanetLab testbed. Our analysis demonstrates sTile's scalability and ability to handle varying network delay, as well as verifies that problems requiring privacy-preservation can be solved using sTile orders of magnitude faster than using today's state-of-the-art alternatives.
Citation:
Yuriy Brun and Nenad Medvidovic, Entrusting Private Computation and Data to Untrusted Networks, IEEE Transactions on Dependable and Secure Computing (TDSC), vol. 10, no. 4, July/August 2013, pp. 225–238.
Bibtex:
@article{Brun13tdsc,
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun13tdsc.pdf}{Entrusting
  Private Computation and Data to Untrusted Networks}},
  author = {Yuriy Brun and Nenad Medvidovic},
  journal = {IEEE Transactions on Dependable and Secure Computing (TDSC)},
  venue = {TDSC},
  issn = {1545-5971},
  year = {2013},
  doi = {10.1109/TDSC.2013.13},
  month = {July/August},
  pages = {225--238},
  volume = {10},
  number = {4},

  note = {\href{http://dx.doi.org/10.1109/TDSC.2013.13}{DOI:
  10.1109/TDSC.2013.13}},


  abstract = {We present sTile, a technique for distributing trust-needing
  computation onto insecure networks, while providing probabilistic guarantees
  that malicious agents that compromise parts of the network cannot learn
  private data. With sTile, we explore the fundamental cost of achieving privacy
  through data distribution and bound how much less efficient a
  privacy-preserving system is than a non-private one. This paper focuses
  specifically on NP-complete problems and demonstrates how sTile-based systems
  can solve important real-world problems, such as protein folding, image
  recognition, and resource allocation. We present the algorithms involved in
  sTile and formally prove that sTile-based systems preserve privacy. We develop
  a reference sTile-based implementation and empirically evaluate it on several
  physical networks of varying sizes, including the globally distributed
  PlanetLab testbed. Our analysis demonstrates sTile's scalability and ability
  to handle varying network delay, as well as verifies that problems requiring
  privacy-preservation can be solved using sTile orders of magnitude faster than
  using today's state-of-the-art alternatives.},

  fundedBy = {NSF CNS-0937060 to the CRA for the CIFellows Project, NSF CCF-0905665,
	NSF CCF-1117593, Infosys Technologies Ltd},
}