The second ever GTACS @ RUNI will be held at Reichman University, Thu, Oct 19th, 2023 hosted by the Efi Arazi School of Computer Science.
Talks will be held in lecture room A.316, in the Arison School of Business building (#32 on the campus map)
Refreshments & lunch will be in the nearby lounge.
PROGRAM
09:30-10:00 Coffee
10:00-10:45 Eden Aldema Tshuva, Locally Verifiable Distributed SNARGs
10:45-11:15 Coffee break
11:15-12:00 Ran Canetti, Towards general-purpose program obfuscation via local mixing of reversible circuits
12:00-13:30 Lunch
13:00-14:45 Surya Mathialagan, MacORAMa: Optimal Oblivious RAM with Integrity
14:45-15:15 Coffee break
15:15-16:00 Benny Applebaum, The Round Complexity of Statistical MPC with Optimal Resiliency
16:00-16:30 Four o'clock tea
16:30-17:15 Jack Doerner, Sometimes You Can’t Distribute Random-Oracle-Based Proofs
ABSTRACTS
Locally Verifiable Distributed SNARGs
Eden Aldema Tshuva, Tel-Aviv University
Abstract:
The field of distributed certification is concerned with certifying properties of distributed networks, where the communication topology of the network is represented as an arbitrary graph; each node of the graph is a separate processor, with its own internal state. To certify that the network satisfies a given property, a prover assigns each node of the network a certificate, and the nodes then communicate with one another and decide whether to accept or reject. We require soundness and completeness: the property holds if and only if there exists an assignment of certificates to the nodes that causes all nodes to accept. Our goal is to minimize the length of the certificates, as well as the communication between the nodes of the network. Distributed certification has been extensively studied in the distributed computing community, but it has so far only been studied in the information-theoretic setting, where the prover and the network nodes are computationally unbounded.
In this work we introduce and study computationally bounded distributed certification: we define locally verifiable distributed SNARGs (LVD-SNARGs), which are an analog of SNARGs for distributed networks, and are able to circumvent known hardness results for information-theoretic distributed certification by requiring both the prover and the verifier to be computationally efficient (namely, PPT algorithms).
We give two LVD-SNARG constructions: the first allows us to succinctly certify any network property in P, using a global prover that can see the entire network; the second construction gives an efficient distributed prover, which succinctly certifies the execution of any efficient distributed algorithm. Our constructions rely on non-interactive batch arguments for NP (BARGs) and on RAM SNARGs, which have recently been shown to be constructible from standard cryptographic assumptions.
Based on joint work with Elette Boyle, Ran Cohen, Tal Moran and Rotem Oshman.
The Round Complexity of Statistical MPC with Optimal Resiliency
Benny Applebaum, Tel-Aviv University
Abstract:
In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model.
Our main result shows that every functionality can be realized in only four rounds of interaction which is known to be optimal. This completely settles the round complexity of statistical actively-secure optimally-resilient MPC, resolving a long line of research. Along the way, we construct the first round-optimal statistically-secure verifiable secret sharing protocol (Chor, Goldwasser, Micali, and Awerbuch; STOC 1985), show that every single-input functionality (e.g., multi-verifier zero-knowledge) can be realized in 3 rounds, and prove that the latter bound is optimal. The complexity of all our protocols is exponential in the number of parties, and the question of deriving polynomially-efficient protocols is left for future research.
Our main technical contribution is a construction of a new type of statistically-secure signature scheme whose existence was open even for smaller resiliency thresholds. We also describe a new statistical compiler that lifts up passively-secure protocols to actively-secure protocols in a round-efficient way via the aid of protocols for single-input functionalities. This compiler can be viewed as a statistical variant of the GMW compiler (Goldreich, Micali, Wigderson; STOC, 1987) that originally employed zero-knowledge proofs and public-key encryption.
Joint work with Eliran Kachlon and Arptia Patra.
MacORAMa: Optimal Oblivious RAM with Integrity
Surya Mathialagan, MIT
Abstract:
Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM `96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size N, well-known lower bounds show that a multiplicative overhead of Omega(log N) in the number of RAM queries is necessary assuming O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO `21) with O(log N) worst-case overhead and O(1) client storage. However, this optimal ORAM is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.
In this work, we construct the first maliciously secure ORAM with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the Omega(log N) lower bound, our construction is asymptotically optimal. To attain this overhead, we develop techniques to intricately interleave online and offline memory checking for malicious security. Furthermore, we complement our positive result by showing the impossibility of a generic overhead-preserving compiler from honest-but-curious to malicious security, barring a breakthrough in memory checking.
Sometimes You Can’t Distribute Random-Oracle-Based Proofs
Jack Doerner, Technion and Reichman University
Abstract:
We investigate the conditions under which straight-line extractable NIZKs in the random oracle model (i.e. without a CRS) permit multiparty realizations that are black-box in the same random oracle. We show that even in the semi-honest setting, any MPC protocol to compute such a NIZK cannot make black-box use of the random oracle or a hash function instantiating it if security against all-but-one corruptions is desired, unless the size of the NIZK grows with the number of parties. This presents a fundamental barrier to constructing efficient protocols to securely distribute the computation of NIZKs (and signatures) based on MPC-in-the-head, PCPs/IOPs, and sigma protocols compiled with transformations due to Fischlin, Pass, or Unruh.
When the adversary is restricted to corrupt only a constant fraction of parties, we give a positive result by means of a tailored construction, which demonstrates that our impossibility does not extend to weaker corruptions models in general.
Joint work with Yashvanth Kondi and Leah Namisa Rosenbloom
Towards general-purpose program obfuscation via local mixing of reversible circuits
Ran Canetti, Boston University
Abstract:
We explore the possibility of obtaining indistinguishability obfuscation for all circuits by way of making only simple, local, functionality preserving random perturbations in the circuit structure. Towards this goal, we use the additional structure provided by reversible circuits, but no additional algebraic structure.
We start by formulating an intermediate (and relatively weak) obfuscation task regarding the ability to obfuscate random circuits of bounded length. We call such obfuscators random input & output (RIO) obfuscators. We then show how to construct inditinguishability obfuscators for all (unbounded length) circuits given only a RIO obfuscator --- under a conjecture made by Gowers (Comb. Prob. Comp. '96) regarding the pseudorandomness of bounded-size random reversible circuits, plus a new assumption regarding the hardness of distinguishing certain (not efficiently generatable) distributions over reversible circuits.
We then investigate the possibility of constructing RIO obfuscators using local, functionality preserving perturbations. Our approach is rooted in statistical mechanics and can be thought of as locally ``thermalizing'' a circuit while preserving its functionality. We also provide a framework for analyzing the security of such strategies, as well as some initial evidence for their plausible security.
Given the power of program obfuscation, viability of the proposed approach would provide an alternative route to realizing almost all cryptographic tasks under hardness assumptions that are potentially plausible, yet very different from standard ones. Furthermore, our specific candidate obfuscators are relatively efficient: the obfuscated version of an n-wire, m-gate reversible circuit has n wires and as few as ~O(n)m gates. We hope that these initial results will motivate further study of this alternative path to cryptography.
Joint work with Claudio Chamon, Eduardo R. Mucciolo and Andrei E. Ruckenstein.