CIS Lab Team
Justin Holmgren
Scientist
Publications
- Locally Covert Learning
By Justin Holmgren & Ruta Jawale
ITC 2023
- Nearly Optimal Property Preserving Hashing
By Justin Holmgren, Minghao Liu, LaKyah Tyner & Daniel Wichs
CRYPTO 2022
- Delegation for Search Problems
By Justin Holmgren, Andrea Lincoln & Ron D. Rothblum
ICALP 2022
- Parallel Repetition For All 3-Player Games Over Binary Alphabet
By Justin Holmgren, Uma Girish, Kunal Mittal, Ran Raz & Wei Zhan
CoRR abs 2022
- PPAD is as Hard as LWE and Iterated Squaring
By Justin Holmgren, Nir Bitansky, Arka Rai Choudhuri, Chethan Kamath, Alex Lombardi, Omer Paneth & Ron D. Rothblum
TCC 2022
- Faster Sounder Succinct Arguments and IOPs
By Justin Holmgren & Ron D. Rothblum
CRYPTO 2022
- Time- and Space-Efficient Arguments from Groups of Unknown Order
By Justin Holmgren, Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum & Pratik Soni
CRYPTO 2021
- On the Security of Doubly Efficient PIR
By Justin Holmgren, Elette Boyle, Fermi Ma & Mor Weiss
Cryptology ePrint Archive 2021
- Parallel Repetition for the GHZ Game: A Simpler Proof
By Justin Holmgren, Uma Girish, Kunal Mittal, Ran Raz & Wei Zhan
APPROX/RANDOM 2021
- Error Correcting Codes for Uncompressed Messages
By Justin Holmgren & Ofer Grossman
ITCS 2021
- Counterexamples to the Low-Degree Conjecture
By Justin Holmgren & Alexander S. Wein
ITCS 2021
- Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge)
By Justin Holmgren, Alex Lombardi & Ron Rothblum
Electron. Colloquium Comput. Complex. 2021
- Transparent Error Correcting in a Computationally Bounded World
By Justin Holmgren, Ofer Grossman & Eylon Yogev
TCC 2020
- Public-Coin Zero-Knowledge Arguments with
(almost) Minimal Time and Space OverheadsBy Justin Holmgren, Alexander R. Block, Alon Rosen, Ron D. Rothblum & Pratik Soni
TCC 2020
- On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?
By Justin Holmgren, Marshall Ball, Yuval Ishai, Tianren Liu & Tal Malkin
ITCS 2020
- A Parallel Repetition Theorem for the GHZ Game
By Justin Holmgren & Ran Raz
CoRR abs 2020
- No-Signaling MIPs and Faster-Than-Light Communication, Revisited
By Justin Holmgren
Electron. Colloquium Comput. Complex. 2020
- Transparent Error Correcting in a Computationally Bounded World
- Permuted Puzzles and Cryptographic Hardness
By Justin Holmgren, Elette Boyle & Mor Weiss
TCC 2019
- On the (In)security of Kilian-Based SNARGs
By Justin Holmgren, James Bartusek, Liron Bronfman, Fermi Ma & Ron D. Rothblum
TCC 2019
- On Round-By-Round Soundness and State Restoration Attacks
By Justin Holmgren
IACR Cryptol. ePrint Arch. 2019
- On the Plausibility of Fully Homomorphic Encryption for RAMs
By Justin Holmgren, Ariel Hamlin, Mor Weiss & Daniel Wichs
CRYPTO 2019
- Fully Homomorphic Encryption for RAMs
By Justin Holmgren, Ariel Hamlin, Mor Weiss & Daniel Wichs
Cryptology ePrint Archive 2019
- The Parallel Repetition of Non-signaling Games: Counterexamples and Dichotomy
By Justin Holmgren & Lisa Yang
STOC 2019
- Fiat-Shamir: From Practice to Theory
By Justin Holmgren, Ran Canetti, Yilei Chen, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum & Daniel Wichs
STOC 2019
- Delegating Computations With (Almost) Minimal
Time and Space OverheadBy Justin Holmgren & Ron D. Rothblum
FOCS 2018
- Cryptographic Hashing From Strong One-Way Functions (Or: One-Way Product Functions and Their Applications)
By Justin Holmgren & Alan Lombardi
FOCS 2018
- Fiat-Shamir from Simpler Assumptions
By Justin Holmgren, Ran Canetti, Yilei Chen, Alex Lombardi, Guy N Rothblum & Ron D Rothblum
IACR Cryptol. ePrint Arch. 2018
- Secure Computation on Untrusted Platforms
By Justin Holmgren
Massachusetts Institute of Technology, Cambridge, USA, 2018
- Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings
By Justin Holmgren, Nir Bitansky, Ran Canetti, Sanjam Garg, Abhishek Jain, Huijia Lin, Rafael Pass, Sidharth Telang & Vinod Vaikuntanathan
SIAM J. Comput. 2018
- Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem
By Justin Holmgren & Lisa Yang
Electron. Colloquium Comput. Complex. 2018
- Non-interactive Delegation and Batch NP Verification from Standard Computational Assumptions
By Justin Holmgren, Zvika Brakerski & Yael Tauman Kalai
STOC 2017
- Towards Doubly Efficient Private Information Retrieval
By Justin Holmgren, Ran Canetti & Silas Richelson
TCC 2017
- (A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games
By Justin Holmgren & Lisa Yang
Electron. Colloquium Comput. Complex. 2017
- Fully Succinct Garbled RAM
By Justin Holmgren & Ran Canetti
ITCS 2016
- Watermarking Cryptographic Capabilities
By Justin Holmgren, Aloni Cohen, Ryo Nishimaki, Vinod Vaikuntanathan & Daniel Wichs
STOC 2016
- Adaptive Succinct Garbled RAM or: How to Delegate Your Database
By Justin Holmgren, Ran Canetti, Yilei Chen & Mariana Raykova
TCC 2016
- Non-Interactive RAM and Batch NP Delegation from any PIR
By Justin Holmgren, Zvika Brakerski, & Yael Tauman Kalai
Electron. Colloquium Comput. Complex. 2016
- Multilinear Pseudorandom Functions
By Justin Holmgren & Aloni Cohen
ICALP 2015
- Succinct Adaptive Garbled RAM
By Justin Holmgren, Ran Canetti, Yilei Chen & Mariana Raykova
IACR Cryptol. ePrint Arch. 2015
- On Necessary Padding with IO
By Justin Holmgren
IACR Cryptol. ePrint Arch. 2015
- Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
By Justin Holmgren, Ran Canetti, Abhishek Jain & Vinod Vaikuntanathan
STOC 2015
- Publicly Verifiable Software Watermarking
By Justin Holmgren, Aloni Cohen, & Vinod Vaikuntanathan
IACR Cryptol. ePrint Arch. 2015
- Indistinguishability Obfuscation of Iterated Circuits and RAM Programs
By Justin Holmgren, Ran Canetti, Abhishek Jain & Vinod Vaikuntanathan
IACR Cryptol. ePrint Arch 2014
- Automated Color Selection Using Semantic Knowledge
By Justin Holmgren, Catherine Havasi & Robyn Speer
AAAI Fall Symposium: Commonsense Knowledge 2010
