Ilan Komargodski

Harry & Abe Sherman Senior Lecturer at the School of Computer Science and Engineering
Hebrew University of Jerusalm
ilank@cs.huji.ac.il
Office: Rothberg A-533

About

I am a faculty member in the School of Computer Science and Engineering at the Hebrew University of Jerusalem. I am interested in various aspects of foundations of computer science with an emphasis on cryptography. Previously, I was a postdoctoral researcher at Cornell Tech, hosted by Prof. Rafael Pass and Prof. Elaine Shi. Priori to that, I completed my Ph.D. at the Weizmann Institute of Science, where I was fortunate to have Prof. Moni Naor as my advisor. I received my M.Sc. from the Weizmann Institute under the guidance of Prof. Ran Raz.

Students & Postdocs

Youlong Ding (M.Sc, January '24 -- ) Shay Gadot (M.Sc, Oct. '23 -- ) Reut Oelbaum (M.Sc, May '23 -- ) Ohad Klein (Postdoc, Sept. '22 -- ) Yuval Gelles (Ph.D, Nov. '22 -- ) Yuval Gelles (M.Sc, Oct. '21 -- Oct. '22) Cody Freitag (Intern, Sept. '21 -- May. '22) Ashrujit Ghoshal (Intern, Jun. '21 -- Dec. '21) Ke Wu (Intern, May. '21 -- Aug. '21) Wei-Kai Lin (Intern, Jun. '20 -- Aug. '20) Aayush Jain (Intern, May. '20 -- Sep. '20) Rex Fernando (Intern, Jan. '20 -- Sep. '20)

Program Committees

ITC 2024 (The 5th Information-Theoretic Cryptography conference) EUROCRYPT 2024 (The 43rd International Conference on the Theory and Applications of Cryptographic Techniques) CRYPTO 2023 (43rd Annual International Cryptology Conference) CT-RSA 2023 (the Cryptographers' Track at the RSA Conference) ASIACRYPT 2022 (the 28th Annual International Conference on the Theory and Application of Cryptology and Information Security) ITC 2022 (The 3st Information-Theoretic Cryptography Conference) PKC 2022 (The 25th International Conference on Practice and Theory of Public-Key Cryptography) TCC 2021 (The 19th Theory of Cryptography Conference) TCC 2020 (The 18th Theory of Cryptography Conference) ITC 2020 (The 1st Information-Theoretic Cryptography Conference) EUROCRYPT 2019 (The 38th International Conference on the Theory and Applications of Cryptographic Techniques) ASIACRYPT 2018 (The 24th Annual International Conference on the Theory and Application of Cryptology and Information Security)

Publications

Memory Checking Requires Logarithmic Overhead
Elette Boyle, Ilan Komargodski, Neekon Vafa
STOC 2024 Optimal Load-Balanced Scalable Distributed Agreement
Yuval Gelles, Ilan Komargodski
STOC 2024 Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election
Rex Fernando, Yuval Gelles, Ilan Komargodski
ITCS 2024 3-Party Secure Computation for RAMs: Optimal and Concretely Efficient
Atsunori Ichikawa, Ilan Komargodski, Koki Hamada, Ryo Kikuchi, Dai Ikarashi
TCC 2023 Distributed-Prover Interactive Proofs
Sourav Das, Rex Fernando, Ilan Komargodski, Elaine Shi, Pratik Soni
TCC 2023 Brief Announcement: Scalable Agreement Protocols with Optimal Optimistic Efficiency
Yuval Gelles, Ilan Komargodski
DISC 2023 FutORAMa: A Concretely Efficient Hierarchical Oblivious RAM
Gilad Asharov, Ilan Komargodski, Yehuda Michelson
CCS 2023 (Distinguished Paper Award) New Bounds on the Local Leakage Resilience of Shamir's Secret Sharing Scheme
Ohad Klein, Ilan Komargodski
CRYPTO 2023 The Cost of Statistical Security in Proofs for Repeated Squaring
Cody Freitag, Ilan Komargodski
ITC 2023 On Distributed Randomness Generation in Blockchains
Ilan Komargodski, Yoav Tamir
CSCML 2023 Optimal Security for Keyed Hash Functions: Avoiding Time-Space Tradeoffs for Finding Collisions
Cody Freitag, Ashrujit Ghoshal, Ilan Komargodski
EUROCRYPT 2023 Maliciously-Secure MrNISC in the Plain Model
Rex Fernando, Aayush Jain, Ilan Komargodski
EUROCRYPT 2023 Fully Adaptive Decentralized Multi-Authority ABE
Pratish Datta, Ilan Komargodski, Brent Waters
EUROCRYPT 2023 log*-Round Game-Theoretically-Fair Leader Election
Ilan Komargodski, Shin'ichiro Matsuo, Elaine Shi, Ke Wu
CRYPTO 2022 Maliciously Secure Massively Parallel Computation for All-but-One Corruptions
Rex Fernando, Yuval Gelles, Ilan Komargodski, Elaine Shi
CRYPTO 2022 Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions
Cody Freitag, Ashrujit Ghoshal, Ilan Komargodski
CRYPTO 2022 On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing
Ashrujit Ghoshal, Ilan Komargodski
CRYPTO 2022
Computational Complexity 2023 Optimal Oblivious Parallel RAM
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, Elaine Shi
SODA 2022 Non-Malleable Time-Lock Puzzles and Applications
Naomi Ephraim, Cody Freitag, Ilan Komargodski, Rafael Pass
TCC 2021 Oblivious RAM with Worst-Case Logarithmic Overhead
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Elaine Shi
CRYPTO 2021
Journal of Cryptology 2023 A Logarithmic Lower Bound for Oblivious RAM (for all parameters)
Ilan Komargodski, Wei-Kai Lin
CRYPTO 2021 Non-Malleable Codes for Bounded Polynomial Depth Tampering
Dana Dachman-Soled, Ilan Komargodski, Rafael Pass
CRYPTO 2021 Decentralized Multi-Authority ABE for DNFs from LWE
Pratish Datta, Ilan Komargodski, Brent Waters
EUROCRYPT 2021 Multiparty Reusable Non-Interactive Secure Computation from LWE
Fabrice Benhamouda, Aayush Jain, Ilan Komargodski, Huijia Lin
EUROCRYPT 2021 Differentially Oblivious Turing Machines
Ilan Komargodski, Elaine Shi
ITCS 2021 Secure Massively Parallel Computation for Dishonest Majority
Rex Fernando, Ilan Komargodski, Yanyi Liu, Elaine Shi
TCC 2020 Oblivious Parallel Tight Compaction
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, Elaine Shi
ITC 2020 Continuous Verifiable Delay Functions
Naomi Ephraim, Cody Freitag, Ilan Komargodski, Rafael Pass
EUROCRYPT 2020 SPARKs: Succinct Parallelizable Arguments of Knowledge
Cody Freitag, Naomi Ephraim, Cody Freitag, Ilan Komargodski, Rafael Pass
EUROCRYPT 2020
Journal of the ACM 2022 OptORAMa: Optimal Oblivious RAM
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, Elaine Shi
EUROCRYPT 2020
Journal of the ACM 2023 Instance Complexity and Unlabeled Certificates in the Decision Tree Model
Tomer Grossman, Ilan Komargodski, Moni Naor
ITCS 2020 Impossibility of Strong KDM Security with Auxiliary Input
Cody Freitag, Ilan Komargodski, Rafael Pass
SCN 2020 On Perfect Correctness without Derandomization
Gilad Asharov, Naomi Ephraim, Ilan Komargodski, Rafael Pass Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge
Cody Freitag, Ilan Komargodski, Rafael Pass
CRYPTO 2019 Distributional Collision Resistance Beyond One-Way Functions
Nir Bitansky, Iftach Haitner, Ilan Komargodski, Eylon Yogev
EUROCRYPT 2019 A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols
Yael Tauman Kalai, Ilan Komargodski, Ran Raz
DISC 2018
Combinatorica 2021 On Distributional Collision Resistant Hashing
Ilan Komargodski, Eylon Yogev
CRYPTO 2018 On the Complexity of Compressing Obfuscation
Gilad Asharov, Naomi Ephraim, Ilan Komargodski, Rafael Pass
CRYPTO 2018
Journal of Cryptology 2022 Non-Trivial Witness Encryption and Null-iO from Standard Assumptions
Zvika Brakerski, Aayush Jain, Ilan Komargodski, Alain Passelègue,, Daniel Wichs
SCN 2018 Another Step Towards Realizing Random Oracles: Non-Malleable Point Obfuscation
Ilan Komargodski, Eylon Yogev
EUROCRYPT 2018 Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions
Ilan Komargodski, Moni Naor, Eylon Yogev
EUROCRYPT 2018 Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari
EUROCRYPT 2018 Evolving Secret Sharing: Dynamic Thresholds and Robustness
Ilan Komargodski, Anat Paskin-Cherniavsky
TCC 2017 Non-Interactive Multiparty Computation Without Correlated Randomness
Shai Halevi, Yuval Ishai, Abhishek Jain, Ilan Komargodski, Amit Sahai, Eylon Yogev
ASIACRYPT 2017 White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing
Ilan Komargodski, Moni Naor, Eylon Yogev
FOCS 2017
Journal of the ACM (J. ACM) 2019 Be Adaptive, Avoid Overcommitting
Zahra Jafargholi, Chethan Kamath, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak, Daniel Wichs
CRYPTO 2017 From Minicrypt to Obfustopia via Private-Key Functional Encryption
Ilan Komargodski, Gil Segev
EUROCRYPT 2017
Journal of Cryptology 2020 How to Share a Secret, Infinitely
Ilan Komargodski, Moni Naor, Eylon Yogev
TCC 2016-B
IEEE Transactions on Information Theory 2017 Leakage Resilient One-Way Functions: The Auxiliary-Input Setting
Ilan Komargodski
TCC 2016-B
Theoretical Computer Science 2018 Threshold Secret Sharing Requires a Linear Size Alphabet
Andrej Bogdanov, Siyao Guo, Ilan Komargodski
TCC 2016-B
Theory of Computing 2020 Multi-Input Functional Encryption in the Private-Key Setting: Stronger Security from Weaker Assumptions
Zvika Brakerski, Ilan Komargodski, Gil Segev
EUROCRYPT 2016
Journal of Cryptology 2017 Cutting-Edge Cryptography Through the Lens of Secret Sharing
Ilan Komargodski, Mark Zhandry
TCC 2016-A
Information and Computation 2018 Communication with Contextual Uncertainty
Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan
SODA 2016
Computational Complexity 2017 Compressing Communication in Distributed Protocols
Yael Tauman Kalai, Ilan Komargodski
DISC 2015 Negation-Limited Formulas
Siyao Guo, Ilan Komargodski
RANDOM 2015
Theoretical Computer Science 2017 Strong Locally Testable Codes with Relaxed Local Decoders
Oded Goldreich, Tom Gur, Ilan Komargodski
CCC 2015
ACM Transactions on Computation Theory (TOCT) 2019 Functional Encryption for Randomized Functionalities in the Private-Key Setting from Minimal Assumptions
Ilan Komargodski, Gil Segev, Eylon Yogev
TCC 2015
Journal of Cryptology 2018 One-Way Functions and (Im)perfect Obfuscation
Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, Eylon Yogev
FOCS 2014 Secret-Sharing for NP
Ilan Komargodski, Moni Naor, Eylon Yogev
ASIACRYPT 2014
Journal of Cryptology 2016 Hardness Preserving Reductions via Cuckoo Hashing
Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor
TCC 2013
Journal of Cryptology 2018 On the Noise Stability of Small De Morgan Formulas
Anat Ganor, Ilan Komargodski, Ran Raz, Troy Lee Improved Average-Case Lower Bounds for DeMorgan Formula Size
Ilan Komargodski, Ran Raz, Avishay Tal
FOCS 2013
SIAM Journal on Computing (SICOMP) 2017 Average-Case Lower Bounds for Formula Size
Ilan Komargodski, Ran Raz
STOC 2013

Teaching

Data Structures (67109): Spring 2022/2023, Spring 2023/2024

Cryptography (67531): Fall 2023/2024

Topics in Cryptography and Secure Computation (67892): Fall 2020/21, Fall 2021/2022

During 2020-2021 I co-organized the Computer Science Colloquium.

I am co-organizing the Theory of Computer Science Seminar since 2020. Please join our mailing list and contact me if you are interested in giving a talk.