To join the email distribution list of the cs colloquia, please visit the list subscription page.
Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.
Academic Calendar at Technion site.
Linear Prover IOPs in Log Star Rounds
Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover can interact with the verifier over multiple rounds, where in each round the prover sends a long message, from which the verifier only queries a few symbols.
State-of-the-art IOPs achieve a linear-size prover and a poly-logarithmic verifier but require a relatively large, logarithmic, number of rounds. While the Fiat-Shamir heuristic can be used to eliminate the need for actual interaction, in modern highly-parallelizable computer architectures such as GPUs, the large number of rounds translates into a major bottleneck for the prover (since it needs to alternate between computing the IOP messages and the Fiat-Shamir hashes).
Motivated by this fact, in this work we study the round complexity of linear-prover IOPs.
Our main result is an IOP for a large class of Boolean circuits, with only O(log*(S)) rounds, where log* denotes the iterated logarithm function (and S is the circuit size). The prover has linear size O(S) and the verifier runs in time polylog(S) and has query complexity O(log*(S)).
The protocol is both conceptually simpler, and strictly more efficient, than prior linear prover IOPs for Boolean circuits.
Debugging into Existence with Program Synthesis
Room 601
When modifying an existing codebase to handle new functionality, programmers will often debug the program until the insertion point for the new code.
This method, termed Debugging into Existence, helps programmers familiarize themselves with the surrounding code and runtime state. Despite its real-world usage, it is limited by the inability to test potential code past the first time the location is called, since added functionality would change the future state making it irrelevant.
Prior work has pioneered Live Execution over partial programs, with extensions using the provided values for synthesis by Programming by Example. In this work, we present DeSynt, a debugger extension that integrates live execution and program synthesis to extend the Debugging into Existence interaction model. DeSynt grants programmers meaningful run-time information across many executions, by allowing them to manipulate program state according to the desired functionality. Based on the state provided by the programmer, DeSynt then synthesizes programs that capture this functionality. We evaluated DeSynt in a between-subjects study on 10 users, and found that in tasks that do not involve complex fault localization, DeSynt reduces time to completion and concentrates programmer effort into fewer code locations. In addition, we found that users that used DeSynt spent more of their task time debugging, indicating DeSynt supports Debugging into Existence for those that already use it.
Combinatorially Homomorphic EncryptionHomomorphic encryption enables public computation over encrypted data. In the past few decades, homomorphic encryption has become a staple of both the theory and practice of cryptography.
Nevertheless, while there is a general loose understanding of what it means for a scheme to be homomorphic, to date there is no single unifying minimal definition that captures all schemes. In this work, we propose a new definition, which we refer to as combinatorially homomorphic encryption, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption and draws a clear line between trivial and nontrivial homomorphism.
Our notion relates the ability to accomplish some task when given a ciphertext, to accomplishing the same task without the ciphertext, in the context of communication complexity.
Thus, we say that a scheme is combinatorially homomorphic if there exists a communication complexity problem f(x, y) (where x is Alice’s input and y is Bob’s input) which requires communication c, but can be solved with communication less than c when Alice is given in addition also an encryption Ek(y) of Bob’s input (using Bob’s key k).
We show that this definition indeed captures pre-existing notions of homomorphic encryption and (suitable variants are) sufficiently strong to derive prior known implications of homomorphic encryption in a conceptually appealing way. These include constructions of (lossy) public-key encryption from homomorphic private-key encryption, as well as collision-resistant hash functions and private information retrieval schemes.