AguiarE072012T.pdf (1.51 MB)
Private and Oblivious Set and Multiset Operations
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-05Research Director(s)
Dr. Marina BlantonCommittee Members
Dr. Raul Santelices Dr. Haitao WangDegree
- Master of Science in Computer Science and Engineering
Degree Level
- Master's Thesis
Language
- English
Alternate Identifier
etd-07182012-130119Publisher
University of Notre DameProgram Name
- Computer Science and Engineering
Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC