Graduate Thesis Or Dissertation

 

On the Structure of Unconditional UC Hybrid Protocols Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/w0892g49n

Descriptions

Attribute NameValues
Creator
Abstract
  • 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
DOI
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Conference Name
Conference Section/Track
Conference Location
Academic Affiliation
Non-Academic Affiliation
Keyword
Rights Statement
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • 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)
  • 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 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
Embargo reason

Relationships

Parents:

This work has no parents.

Items