Oregon State University

Can’t find an event? We’re busy migrating to a new event calendar. Try looking at the new calendar



Event Details

MS Final Examination – Morgan Shirley

Wednesday, June 7, 2017 9:00 AM - 11:00 AM

On the Structure of Unconditional UC Hybrid Protocols
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 most simple 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 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, understanding of reductions to g is incomplete. 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.

Major Advisor: Mike Rosulek
Committee: Glencora Borradaile
Committee: Amir Nayyeri
GCR: Cleyton Petsche

Kelley Engineering Center (campus map)
Calvin Hughes
1 541 737 3168
Calvin.Hughes at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: