טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentWeiss Mor
SubjectSecure Computation and Probabilistic Checking
DepartmentDepartment of Computer Science
Supervisor Professor Yuval Ishai
Full Thesis textFull thesis text - English Version


Abstract

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.