In Cooperation With
ITC 2024: Program
Wednesday August 14
| 8:45am-9am | Coffee and check-in |
| 9:00am-9:15am | Opening Remarks |
| 9:15am - 11:20am | Session 1: Complexity and Coding Theory
|
| 11:20am - 11:50am | Break |
| 11:50am - 12:40pm | Spotlight Talk 1: Zvika Brakerski (Weizmann Institute of Science)
Title: From Classical to Quantum (Pseudo-) Randomness This talk will survey the effort in the quantum-cryptographic community towards understanding and instantiating pseudorandom quantum objects. A category that includes pseudorandom quantum states and pseudorandom unitaries (quantum operators). This line of work led to a number of constructions of pseudorandom states and very recently also of pseudorandom unitaries. An appealing feature of these constructions is that their main component is information theoretic: constructing the desired object in an idealized model where the construction has access to a random oracle or a random permutation, which are later instantiated computationally. These results therefore shed light on the connection between classical and quantum randomness. |
| 12:40pm - 2pm | Lunch (provided) | 2pm - 4:05pm | Session 2: Cryptographic Protocols
|
| 4:05pm - 4:35pm | Break |
| 4:35pm - 5:25pm | Spotlight Talk 2:Rotem Oshman (Tel-Aviv University)
Title: Distributed Zero-Knowledge Proofs Over Networks A distributed proof is a mechanism for certifying that a network is in a valid state, for example, that the network is connected and the nodes have a valid spanning tree of the network. To do this, each node is given a short certificate, and the nodes then interact with their neighbors in the network to verify the proof. Our goal is to minimize the length of the certificates, as well as the time and communication required for the verification protocol. Typically, no computational restrictions are assumed. In this talk I will describe recent work on distributed proofs, focusing on zero-knowledge proofs. The unique aspect of distributed zero-knowledge proofs over networks is that due to the dual role of the underlying graph in distributed proofs, serving as both the communication topology and the input to the problem, zero-knowledge distributed proofs must protect the communication graph itself. We suggest two definitions for zero-knowledge proofs, reconciling the traditional computational notion of zero-knowledge with the communication-based paradigm of distributed proofs, and show that efficient zero-knowledge distributed proofs can be constructed for fundamental problems such as 3-colorability and spanning tree verification. We also give a generic compiler that takes any non-ZK distributed proof and constructs from it a ZK distributed proof with related parameters. Joint work with Aviv Bick and Gillat Kol. |
Thursday August 15
| 8:45am-9am | Coffee and check-in |
| 9am-11:05am | Session 3: Randomness Extraction and Security
|
| 11:05am - 11:35am | Break |
| 11:35am - 12:25pm | Spotlight Talk 3:Stefano Tessaro (University of Washington)
Title: Information-theoretic Analyses of Block Ciphers Block ciphers, such as AES, are the workhorses of applied cryptography and the standard approach to implementing pseudorandom functions in practice. Their security is inherently computational, but so far, cryptographers have struggled to develop meaningful reduction-based arguments that convincingly validate the security of practical constructions. Instead, our confidence in their security comes from decades of cryptanalysis that have not significantly compromised their security. The next best approach is to provide proofs of security for restricted classes of attacks, and the resulting analyses are inherently information theoretic. This talk will offer an overview of this research area and then focus on recent work aimed at proving that concrete block cipher constructions implement t-wise independent permutations. This property implies resilience to a wide range of statistical attacks considered by cryptanalysts. This talk is based in part on joint works with Tianren Liu, Angelos Pelecanos, and Vinod Vaikunthanathan. |
| 12:25pm - 2pm | Lunch (provided) |
| 2pm - 3:15pm | Session 4: Cryptography and Key-Agreement
|
| 3:15pm - 3:45pm | Break |
| 3:45pm - 4:35pm | Spotlight Talk 4: Mary Wootters (Stanford)
Title: Computing on Top of Error Correction In many settings, one wants to compute a function of data that has been protected with an error correcting code. This flavor of problem has been studied in many different models; one take-away is that encoding data with an error-correcting code can be viewed as useful pre-computation, even in settings where one doesn't care about correcting errors. In this talk, we'll survey coding-theoretic results of this flavor, with an eye towards cryptographic applications. We'll focus in one one such result (low-bandwidth computation of linear functions, joint work with Noah Shutty), and again mention some connections to cryptography. The hope for this talk is that the audience will identify even more cryptographic connections! |
| 4:50pm - ??? | Social time!
|
Friday August 16
| 8:45am-9am | Coffee and check-in |
| 9am - 11:05am | Session 5: Interactive Proofs and Complexity
|
| 11:05am - 11:35am | Break |
| 11:35am - 12:25pm | Spotlight Talk 5: Pasin Manurangsi (Google Research)
Title: Shuffle Differential Privacy: A Survey Traditionally, differential privacy (DP) has been studied under the central model or the local model. The former offers better utility but requires a trusted curator, while the latter often results in large errors but does not require each user to trust any external party. In recent years, several models have been proposed that interpolate between these two extremes. One such model is the shuffle model. In this survey, we will provide the definition of this model and its variants. We will then go over the generic amplification-by-shuffling theorem, and specialized Shuffle DP algorithms. Finally, we will discuss known lower bounds and some open questions. |
| 12:25pm - 2pm | Lunch (provided) |
| 2pm - 3:15pm | Session 6: Cryptographic Security and Protocols
|
| 3:15pm - 3:45pm | Break |
| 3:45pm - 4:35pm | Spotlight Talk 6: Hemanta Maji (Purdue University)
Title: Geometry of Interaction through Lamination Hulls Toward minimizing the overheads of any secure computation task, it is natural to wonder: How do we accomplish it within budgeted resources, if at all? Otherwise, what's the obstruction? Lacking appropriate mathematics, even the decidability of such questions has been unknown for over thirty years. Recently, we opened a wormhole between information complexity and geometry to tackle them. Roughly speaking, the idea is to translate such a question into a set of points and consider its lamination hull -- a generalization of the convex hull. When this hull contains the origin, the task is feasible, and the protocol is also recoverable. Otherwise, the origin is outside the hull, certifying the obstruction. Using this geometric framework, we determined the round and communication complexity of 2-party secure computation, a longstanding open problem. This framework facilitates computer-assisted protocol design and obstruction detection, exploring beyond the purview of human ingenuity and creativity. Fascinatingly, answering several of these information complexity questions motivates building new mathematics, which is of broader interest because lamination hulls find applications in hydrodynamics, operations research, formal languages, and computer graphics, among others. This talk will overview this new mathematical framework at the interface of cryptography and geometry. It is based on my collaborations with Saugata Basu, Hamidreza Amini Khorasgani, and Hai H. Nguyen. |