May 2024 - Colo - huji-cs listserver

CS Colloquium (03/06): Orr Dunkelman (University of Haifa)
by Sagie Benaim 03 Jun '24

03 Jun '24

Dear all, Next week, we have the pleasure of having Prof. Orr Dunkelman give a talk in the colloquium. The seminar will be held on Monday, June 3rd at 14:00. Location: C221. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* The Hunt for High Probability Statistical Impurities in Cryptographic Primitives *Abstract:* Computer security relies on cryptographic primitives such as block ciphers and hash functions. The security of these primitives is usually not proved in a reduction-style proof, but rather argued based on claims of the form - this block cipher has no statistical property of some type (e.g., differential) with high enough probability. However, how do we know that there are no such statistical properties in a given n-bit cryptographic primitive? When *n* is small (e.g., an 8-bit S-box), this is easy to do. However, for large values of *n*, the only practical way to find such statistical properties was to exploit the internal structure of the primitive and to speed up the search with a variety of heuristic rules of thumb. However, such bottom-up techniques can miss many properties, especially in cryptosystems which are designed to have hidden trapdoors. In this work we consider the top-down version of the problem in which the cryptographic primitive is given as a structureless black box, and reduce the complexity of the best known techniques for finding all its significant differential and linear properties by a large factor of 2^{n/2}. Our main new tool is the idea of using *surrogate differentiation*. In the context of finding differential properties, it enables us to simultaneously find information about all the differentials of the form f(x) \oplus f(x \oplus \alpha) in all possible directions by differentiating *f* in a single randomly chosen direction \gamma (which is unrelated to the \alpha’s). In the context of finding linear properties, surrogate differentiation can be combined in a highly effective way with the Fast Fourier Transform. For 64-bit cryptographic primitives, this technique makes it possible to automatically find in about 2^64 time all their differentials with probability larger than 2^{-32} and all their linear approximations with bias larger than 2^{-16}; previous algorithms for these problems required at least 2^{96} time. This is a joint work with Itai Dinur, Nathan Keller, Eyal Ronen, and Adi Shamir. *Bio*: Orr Dunkelman is a full professor in the Computer Science Department at the University of Haifa. He has held post-doctoral research positions at the Weizmann Institute of Science, Ecole Normale Superieure, and Katholieke Universiteit Leuven. He earned his Ph.D. from the Technion under the supervision of Prof. Eli Biham.

1 2

CS Colloquium (27/05): Hagit Attiya (Technion)
by Sagie Benaim 27 May '24

27 May '24

Dear all, Next week, we have the pleasure of having Prof. Hagit Attiya give a talk in the colloquium. The seminar will be held on Monday, May 27th at 14:00. Location: C220. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Preserving Hyperproperties when Using Concurrent Objects *Abstract:* Linearizability, a consistency condition for concurrent objects, is known to preserve trace properties. This suffices for modular usage of concurrent objects in applications, deriving their safety properties from the abstract object they implement. However, other desirable properties, like average complexity and information leakage, are not trace properties. These hyperproperties are not preserved by linearizable concurrent objects, especially when randomization is used. This talk will discuss formal ways to specify concurrent objects that preserve hyperproperties and their relation with verification methods. We will show that certain concurrent objects cannot satisfy such specifications, and describe ways to mitigate these limitations. This is a joint work with Constantin Enea and Jennifer Welch. *Bio*: Hagit Attiya is a professor at the department of Computer Science at the Technion, Israel Institute of Technology, and holds the Harry W. Labov and Charlotte Ullman Labov Academic Chair. She received all her academic degrees, in Computer Science, from the Hebrew University of Jerusalem, and was a post-doctoral fellow at MIT.

1 1

CS Colloquium (20/05): Elchanan Mossel (MIT)
by Sagie Benaim 20 May '24

20 May '24

Dear all, Next week, we have the pleasure of having Prof. Elchanan Mossel give a talk in the colloquium. The seminar will be held on Monday, May 20th at 14:00. Location: C220. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Why depth? Some new perspectives on the advantages of depth in inference *Abstract:* Can theory help explain the success of deep nets on real data? One avenue to explore this question is to ask if we can find 1. Natural data models where: 2. Inference is computationally and statistically efficient, 3. Inference requires depth (or some other measure of complexity) and 4. The inference procedure can be learned efficiently from data As proving lower bounds in theoretical computer science for explicit objects is hard, perhaps the most difficult task is to establish 3. I will discuss some recent works that try to establish 1-4 for the broadcast model on the tree and where the inference procedure is belief propagation. Based on: https://arxiv.org/pdf/2402.13359 https://dl.acm.org/doi/abs/10.1145/3564246.3585155 https://proceedings.neurips.cc/paper_files/paper/2022/hash/77e6814d32a86b76… https://proceedings.mlr.press/v125/moitra20a.html https://arxiv.org/pdf/1612.09057 *Bio*: Elchanan Mossel is a professor of mathematics at the Massachusetts Institute of Technology. His primary research fields are probability theory, combinatorics, and statistical inference.

1 1

CS Colloquium (06/05): Gil Cohen (Tel Aviv University)
by Sagie Benaim 06 May '24

06 May '24

Dear all, We are resuming the colloquium with the start of the new semester. Next week, we have the pleasure of having Prof. Gil Cohen give a talk in the colloquium. The seminar will be held on Monday, May 6th at 14:00. Location: C220. The title, abstract and bio appear below. Looking forward to seeing you, Sagie and Liat *Title:* Tight Bounds for the Zig-Zag Product *Abstract:* In this talk, we will explore the Zig-Zag product, a pivotal concept in pseudorandomness introduced over two decades ago by Reingold, Vadhan, and Wigderson. We will utilize methods from free probability theory and analytic combinatorics to establish a tight bound on the spectral expansion when Zig-Zag-ing with a (vertex-transitive) graph H. Our bound incorporates H's entire spectrum, deviating from the classical, combinatorial, bound. This talk is designed for a broad audience; no prior knowledge of free probability, analytic combinatorics, or expanders for that matter, is required. This work is a collaboration with Itay Cohen and Gal Maor. *Bio*: Gil Cohen is a faculty member at the Department of Computer Science at Tel Aviv University. He is working on pseudo-randomness and derandomization, explicit constructions, and coding theory. Of particular interest are randomness extractors, derandomization of space-bounded computation, spectral graph theory, tree codes, locally decodable codes, and algebraic-geometric codes.

1 1

2024

2023

Colo May 2024

2024

2023

Colo May 2024 ----- 2024 ----- November 2024 October 2024 September 2024 August 2024 July 2024 June 2024 May 2024 April 2024 March 2024 February 2024 January 2024 ----- 2023 ----- December 2023 November 2023

Colo May 2024