Private and Oblivious Set and Multiset Operations

Master's Thesis


With the recent advent of cloud computing and the constant maturing of computation outsourcing techniques, incentives for the adoption of such technologies have reached an all-time high. Today, more than ever, companies can easily cut costs by simply offloading their storage and computing needs. However, ensuring that all sensitive data remains private to its owner remains as a major concern. Among the several privacy-preserving operations available, a group that can be made considerably useful to the described scenario is that of set operations, in particular set intersection, which can be used by multiple parties to jointly determine if their private datasets share common items while not revealing any information about the portion of that data that is unique to them. Despite the very large body of literature devoted to this topic, the majority of the proposed solutions are two-party protocols and are not composable. This work describes the design and implementation of a comprehensive suite of multi-party protocols for set and multiset operations that are composable and optimized to have small interactive round complexities, making this approach highly suitable to secure outsourcing. Furthermore, all protocols are secure in the information theoretic sense and have communication and computation complexity of O(m log m) for sets or multisets of size m, which compares favorably with prior work.


Attribute NameValues
  • etd-07182012-130119

Author Everaldo Marques de Aguiar Jr.
Advisor Dr. Marina Blanton
Contributor Dr. Raul Santelices, Committee Member
Contributor Dr. Haitao Wang, Committee Member
Contributor Dr. Marina Blanton, Committee Chair
Degree Level Master's Thesis
Degree Discipline Computer Science and Engineering
Degree Name MSCSE
Defense Date
  • 2012-07-16

Submission Date 2012-07-18
  • United States of America

  • private set and multiset operations

  • secure multi-party computation and outsourcing

  • oblivious sorting

  • secret sharing

  • University of Notre Dame

  • English

Record Visibility Public
Content License
  • All rights reserved

Departments and Units


Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.