University of Notre Dame
Browse
AguiarE072012T.pdf (1.51 MB)

Private and Oblivious Set and Multiset Operations

Download (1.51 MB)
thesis
posted on 2012-07-18, 00:00 authored by Everaldo Marques de Aguiar Jr.
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.

History

Date Modified

2017-06-05

Research Director(s)

Dr. Marina Blanton

Committee Members

Dr. Raul Santelices Dr. Haitao Wang

Degree

  • Master of Science in Computer Science and Engineering

Degree Level

  • Master's Thesis

Language

  • English

Alternate Identifier

etd-07182012-130119

Publisher

University of Notre Dame

Program Name

  • Computer Science and Engineering

Usage metrics

    Masters Theses

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC