Ph.D Student | Weiss Mor |
---|---|

Subject | Secure Computation and Probabilistic Checking |

Department | Department of Computer Science |

Supervisor | Professor Yuval Ishai |

Full Thesis text |

In the past few decades, probabilistic checking techniques were shown to yield dramatic efficiency improvements in verifying proofs and approximating distance from error-correcting codes. Concurrently, so-called "side channel" attacks launched on physical devices resulted in major security breaches, and have led to a surge of interest in "leakage-resilient" hardware. In this thesis we study "zero-knowledge" variants of probabilistic checking techniques, and generalizations of leakage-resilient hardware, and apply them towards improving the efficiency, and generalizing the scope, of cryptographic protocols. Our contributions lie in two main areas.

Primarily, we study "zero-knowledge"
variants of three probabilistic checking techniques. First, Probabilistically
Checkable Proofs (PCPs), which are proofs that allow a randomized verifier with
oracle access to a purported proof to probabilistically verify an input
statement of the form "*x* is in *L*", by querying only few
proof bits. Second, PCPs of Proximity (PCPPs) which have the additional feature
of allowing the verifier to query only few bits of the *input* *x*
and a purported proof, where if the input is accepted then the verifier is
guaranteed that (with high probability) *x* is *close* to some *x'*
in* L*. Thirdly, Locally Testable Codes (LTCs) which are error correcting
codes that allow a tester to probabilistically test membership in the code by
probing few symbols of a purported code word. Zero-knowledge PCPs are PCPs with
the additional guarantee that the view of any (possibly malicious) verifier
reading a large portion of the proof can be simulated given *x* alone. We
introduce the notion of zero-knowledge PCPPs and zero-knowledge LTCs, which
possess the property that even a large portion of the input and proof, or the
purported code word, reveals no information about the encoded input or message.
We construct zero-knowledge variants of PCPs, PCPPs, and LTCs, and apply them
to design communication-efficient protocols for various cryptographic tasks,
such as verifying a shared secret, flipping a common random coin, and
zero-knowledge proofs in the two-party and multiparty setting.

Second, we investigate
generalizations of leakage-resilient circuit-compilers (LRCCs), which compile
any circuit into a new circuit that operates on encoded inputs, and withstands
side-channel attacks in the sense that these reveal nothing about the (properly
encoded) input, other than what follows from the output. We construct LRCCs
that guarantee correctness of the computation *even when the input to the
compiled circuit may not be properly encoded*, namely the compiled circuit
emulates the original circuit on some set of inputs (determined by the possibly
ill-formed encodings given to the compiled circuit). Additionally, we use LRCCs
to design a *single* leaky (but otherwise trusted) stateless hardware
device that allows *m>0* mutually distrusting parties to jointly compute
a function of their inputs, while preserving input secrecy, and the correctness
of the outputs, in the presence of active corrupted parties that may also
obtain leakage on the internals of the device.