Secure computation on untrusted platforms

In this thesis, we present two lines of research developing tools that, in addition to being of independent theoretical interest, yield improved protocols for secure out-sourcing of computation: Succinct Garbling Schemes. A garbling scheme is a way to encode a program P and input x as P̃̃ and x̃ such that P̃ can be evaluated on i to obtain P(x), but (P̃, x̃) reveals nothing more than P(x). We devise an efficient garbling scheme, based on the recent notion of indistinguishability obfuscation, in which the RAM running time and space usage of P on x are each the same as for P̃ on ,x̃. No-Signaling Multi-Prover Interactive Proofs. A multi-prover interactive proof (MIP) is a protocol by a which a "verifier" can ascertain the truth of a mathematical statement by interacting with two or more "provers" that cannot communicate with each other. We devise an MIP that achieves better efficiency and stronger soundness guarantees than previous constructions. In terms of efficiency, our MIP allows proving many statements with roughly the same (small) communication complexity as is required to prove a single statement. The soundness guarantee is that the verifier cannot be fooled even by malicious provers that can, in a very limited sense, collude in their messages to the verifier. The latter guarantee crucially enables an application to delegation of computation. Specifically, we obtain a protocol by which a weak device can outsource expensive computations to a powerful but untrusted server, while being assured that the computation is performed correctly.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Holmgren, Justin Lee

Advisor dc:contributor.advisor

• Shafi Goldwasser.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/118082

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/118082