The Taub Faculty of Computer Science Events and Talks

Recently, there is an increase in delegating computations to powerful remote servers. This appearance raises questions of computational integrity and efficient verification. For instance, the server can be unreliable, therefore it may output erroneous results. In other contexts, where preserving information privacy is crucial, as in medical and forensic data, other issues might arise. The veils of secrecy, that are designed to keep the data hidden from the public, may be abused to cover up lies and deceit by institutions entrusted with data, unjustly harming citizens and eroding trust in central institutions. Zero knowledge (ZK) proof systems are an ingenious cryptographic solution to this tension between the ideals of personal privacy and institutional integrity, enforcing the latter in a way that does not compromise the former. For systems to be used with Big Data, it is imperative that the public verification process scale sublinearly in data size. One can use Probabilistically Checkable Proofs (PCP) to verify the correctness of the computations. Furthermore, the verification time is significantly less than the time which would be needed if the client ran the computation by itself. Until recently, however, PCPs have been considered efficient only in theory. Interactive Oracle Proofs (IOP), however, which are interactive versions of PCPs, are more practical. Here we report how to use arithmetization for building programs for these problems. Arithmetization is the encoding of transition functions of computational models as algebraic problems. This technique is used in many theoretical and practical results, and is valuable in making PCPs/IOPs more practical. In order to encode the transition function, we define polynomials over a finite field F such that these polynomials are set to zero if and only if the computation corresponding to that function is executed correctly. The main contribution of our work is in building arithmetizations for real-world problems. We open our discussion with primitive cryptographic functions, e.g. AES or SHA2, and attempt to arithmetize them as optimally as possible. Then, we compare the arithmetizations in terms of fficiency, stemming from algebraic properties of the functions. Afterwards, we progress to more complex data structures e.g. Merkle-Trees or hashchains. We conclude this work by presenting an efficient construction for several real-world problems.