Justin Holmgren

According to our database, Justin Holmgren authored at least 48 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Separating Selective Opening Security From Standard Security, Assuming IO.

Justin Holmgren, Brent Waters

IACR Cryptol. ePrint Arch., 2024

Linear-Size Boolean Circuits for Multiselection.

Justin Holmgren, Ron Rothblum

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Locally Covert Learning.

Justin Holmgren, Ruta Jawale

Proceedings of the 4th Conference on Information-Theoretic Cryptography, 2023

2022

Faster Sounder Succinct Arguments and IOPs.

Justin Holmgren, Ron Rothblum

IACR Cryptol. ePrint Arch., 2022

PPAD is as Hard as LWE and Iterated Squaring.

Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Chethan Kamath, Alex Lombardi, Omer Paneth, Ron D. Rothblum

Proceedings of the Theory of Cryptography - 20th International Conference, 2022

Parallel repetition for all 3-player games over binary alphabet.

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Delegation for Search Problems.

Justin Holmgren, Andrea Lincoln, Ron D. Rothblum

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Faster Sounder Succinct Arguments and sfIOPs.

Justin Holmgren, Ron D. Rothblum

Proceedings of the Advances in Cryptology - CRYPTO 2022, 2022

Nearly Optimal Property Preserving Hashing.

Justin Holmgren, Minghao Liu, LaKyah Tyner, Daniel Wichs

Proceedings of the Advances in Cryptology - CRYPTO 2022, 2022

2021

On the Security of Doubly Efficient PIR.

Elette Boyle, Justin Holmgren, Fermi Ma, Mor Weiss

IACR Cryptol. ePrint Arch., 2021

A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof.

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Electron. Colloquium Comput. Complex., 2021

Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge).

Justin Holmgren, Alex Lombardi, Ron D. Rothblum

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Counterexamples to the Low-Degree Conjecture.

Justin Holmgren, Alexander S. Wein

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Error Correcting Codes for Uncompressed Messages.

Ofer Grossman, Justin Holmgren

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Time- and Space-Efficient Arguments from Groups of Unknown Order.

Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, Pratik Soni

Proceedings of the Advances in Cryptology - CRYPTO 2021, 2021

Parallel Repetition for the GHZ Game: A Simpler Proof.

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Proceedings of the Approximation, 2021

2020

A Parallel Repetition Theorem for the GHZ Game.

Justin Holmgren, Ran Raz

Electron. Colloquium Comput. Complex., 2020

No-Signaling MIPs and Faster-Than-Light Communication, Revisited.

Justin Holmgren

Electron. Colloquium Comput. Complex., 2020

Transparent Error Correcting in a Computationally Bounded World.

Ofer Grossman, Justin Holmgren, Eylon Yogev

Proceedings of the Theory of Cryptography - 18th International Conference, 2020

Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads.

Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, Pratik Soni

Proceedings of the Theory of Cryptography - 18th International Conference, 2020

On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?

Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, Tal Malkin

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

On Round-By-Round Soundness and State Restoration Attacks.

Justin Holmgren

IACR Cryptol. ePrint Arch., 2019

Permuted Puzzles and Cryptographic Hardness.

Elette Boyle, Justin Holmgren, Mor Weiss

Proceedings of the Theory of Cryptography - 17th International Conference, 2019

On the (In)security of Kilian-Based SNARGs.

James Bartusek, Liron Bronfman, Justin Holmgren, Fermi Ma, Ron D. Rothblum

Proceedings of the Theory of Cryptography - 17th International Conference, 2019

The parallel repetition of non-signaling games: counterexamples and dichotomy.

Justin Holmgren, Lisa Yang

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fiat-Shamir: from practice to theory.

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On the Plausibility of Fully Homomorphic Encryption for RAMs.

Ariel Hamlin, Justin Holmgren, Mor Weiss, Daniel Wichs

Proceedings of the Advances in Cryptology - CRYPTO 2019, 2019

2018

Secure computation on untrusted platforms.

Justin Lee Holmgren

PhD thesis, 2018

Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings.

Nir Bitansky, Ran Canetti, Sanjam Garg, Justin Holmgren, Abhishek Jain, Huijia Lin, Rafael Pass, Sidharth Telang, Vinod Vaikuntanathan

SIAM J. Comput., 2018

Cryptographic Hashing From Strong One-Way Functions.

Justin Holmgren, Alex Lombardi

IACR Cryptol. ePrint Arch., 2018

Fiat-Shamir From Simpler Assumptions.

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum

IACR Cryptol. ePrint Arch., 2018

Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem.

Justin Holmgren, Lisa Yang

Electron. Colloquium Comput. Complex., 2018

Delegating Computations with (Almost) Minimal Time and Space Overhead.

Justin Holmgren, Ron Rothblum

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and Their Applications).

Justin Holmgren, Alex Lombardi

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

(A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games.

Justin Holmgren, Lisa Yang

Electron. Colloquium Comput. Complex., 2017

Towards Doubly Efficient Private Information Retrieval.

Ran Canetti, Justin Holmgren, Silas Richelson

Proceedings of the Theory of Cryptography - 15th International Conference, 2017

Non-interactive delegation and batch NP verification from standard computational assumptions.

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Non-Interactive RAM and Batch NP Delegation from any PIR.

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2016

Adaptive Succinct Garbled RAM or: How to Delegate Your Database.

Ran Canetti, Yilei Chen, Justin Holmgren, Mariana Raykova

Proceedings of the Theory of Cryptography - 14th International Conference, 2016

Watermarking cryptographic capabilities.

Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, Daniel Wichs

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Fully Succinct Garbled RAM.

Ran Canetti, Justin Holmgren

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

2015

On Necessary Padding with IO.

Justin Holmgren

IACR Cryptol. ePrint Arch., 2015

Publicly Verifiable Software Watermarking.

Aloni Cohen, Justin Holmgren, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2015

Succinct Adaptive Garbled RAM.

Ran Canetti, Yilei Chen, Justin Holmgren, Mariana Raykova

IACR Cryptol. ePrint Arch., 2015

Succinct Garbling and Indistinguishability Obfuscation for RAM Programs.

Ran Canetti, Justin Holmgren, Abhishek Jain, Vinod Vaikuntanathan

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Multilinear Pseudorandom Functions.

Aloni Cohen, Justin Holmgren

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Indistinguishability Obfuscation of Iterated Circuits and RAM Programs.

Ran Canetti, Justin Holmgren, Abhishek Jain, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2014

2010

Automated Color Selection Using Semantic Knowledge.

Catherine Havasi, Robyn Speer, Justin Holmgren

Proceedings of the Commonsense Knowledge, 2010