Graduate Thesis Or Dissertation

 

On the Structure of Unconditional UC Hybrid Protocols Público Deposited

Contenido Descargable

Descargar 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
Fecha Disponible
Fecha de Emisión
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Declaración de derechos
Publisher
Peer Reviewed
Language
Replaces

Relaciones

Parents:

This work has no parents.

En Collection:

Elementos