On the Structure of Unconditional UC Hybrid Protocols Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/w0892g49n

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Two parties, Alice and Bob, hold inputs x and y respectively. They wish to compute a function f of their inputs. In an ideal world, f(x, y) could be calculated by sending the inputs to a trusted third party. In the absence of such a third party, Alice and Bob are required to communicate directly. Alice would like the real-world computation of f to reveal no more about her input x to Bob than he could have deduced from the ideal-world interaction. In addition, Alice would like this guarantee to hold even if Bob cheats at the protocol. Bob would like the computation to have the same properties with regards to security against malicious Alice.If both parties have unlimited computation power, such a feat is impossible for all but the simplest f . We introduce a trusted third party that can compute for Alice and Bob a different function g. If f can be computed in this modified model, we say that f reduces to g. Some g, which we call complete, have a special structural property that allows all f to reduce to g. These reductions are well-studied. Unfortunately, if g does not have this structural property, we do not fully understand reductions to g. This thesis describes our work in characterizing this landscape.In particular, we show that if f reduces to g by some deterministic protocol or by a randomized protocol with a strict sub-logarithmic bound in the number of communication rounds, then we can shorten these protocols to use only a single call to g. In addition, we give a combinatorial property of f and g that is present if and only if this single-call protocol is possible. We also show an example of f and g where a randomized and potentially super-logarithmic protocol is required for f to reduce to g. This example hints at a direction for future investigation towards the complete characterization of these reductions.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Keyword
Rights Statement
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Steven Van Tuyl(steve.vantuyl@oregonstate.edu) on 2017-06-27T21:22:36Z (GMT) No. of bitstreams: 2license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5)ShirleyMorganF2017.pdf: 437189 bytes, checksum: d169738145698ab86b77065a469faeea (MD5)
  • description.provenance : Made available in DSpace on 2017-06-27T21:22:36Z (GMT). No. of bitstreams: 2license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5)ShirleyMorganF2017.pdf: 437189 bytes, checksum: d169738145698ab86b77065a469faeea (MD5) Previous issue date: 2017-06-07
  • description.provenance : Submitted by Morgan Shirley (shirlemo@oregonstate.edu) on 2017-06-08T19:31:51ZNo. of bitstreams: 2license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5)ShirleyMorganF2017.pdf: 437189 bytes, checksum: d169738145698ab86b77065a469faeea (MD5)
  • description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 2017-06-22T19:13:58Z (GMT) No. of bitstreams: 2license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5)ShirleyMorganF2017.pdf: 437189 bytes, checksum: d169738145698ab86b77065a469faeea (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items