Justin Holmgren

holmgren at alum dot mit dot edu
head shot

Until July 2024, I was a scientist at NTT Research. Prior to that, I was a Google Research Fellow at the Simons Institute in Berkeley, and a Postdoctoral Research Associate at Princeton University with Professors Ran Raz and Mark Zhandry. I obtained my PhD in Computer Science at MIT under the wonderful supervision of Professor Shafi Goldwasser.

I'm broadly interested in theoretical cryptography and complexity theory, with a focus on delegation of computation.

Selected Publications

By reverse chronological ordering of publication date. Authorship on all papers is alphabetical.
  1. Locally Covert Learning
    with Ruta Jawale
    ITC 2023
    Presented at Charles River Crypto Day, May 2023. [slides] [with build slides]
  2. Nearly Optimal Property-Preserving Hashing
    with Minghao Liu, LaKyah Tyner, and Daniel Wichs.
    CRYPTO 2022
  3. Faster Sounder Succinct Arguments and IOPs
    with Ron Rothblum.
    CRYPTO 2022
  4. Delegation for Search Problems
    with Ron Rothblum.
    ICALP 2022
  5. Parallel repetition for all 3-player games over binary alphabet.
    with Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan
    STOC 2022
  6. PPAD is as Hard as LWE and Iterated Squaring
    with Nir Bitansky, Arka Rai Choudhuri, Chethan Kamath, Alex Lombardi, Omer Paneth, and Ron Rothblum.
    TCC 2022
  7. Parallel Repetition for the GHZ Game: A Simpler Proof
    with Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan.
    APPROX/RANDOM 2021
  8. Time- and Space-Efficient Arguments from Groups of Unknown Order
    with Alex Block, Alon Rosen, Ron Rothblum, and Pratik Soni.
    CRYPTO 2021
  9. Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge)
    with Alex Lombardi and Ron Rothblum.
    STOC 2021
    Oded's Choices #300
  10. A Parallel Repetition Theorem for the GHZ Game
    with Ran Raz.
    QIP 2021
  11. Counterexamples to the Low-Degree Conjecture
    with Alex Wein
    ITCS 2021
  12. Error Correcting Codes for Uncompressed Messages
    with Ofer Grossman
    ITCS 2021
    Oded's Choices #285. Auxiliary source code here.
  13. Transparent Error Correcting in a Computationally Bounded World.
    with Ofer Grossman and Eylon Yogev.
    TCC 2020
  14. Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads
    with Alexander Block, Alon Rosen, Ron Rothblum, and Pratik Soni.
    TCC 2020
  15. On the Complexity of Decomposable Randomized Encodings, or: How Friendly Can a Garbling-Friendly PRF be?
    with Marshall Ball, Yuval Ishai, Tianren Liu, and Tal Malkin
    ITCS 2020
  16. Permuted Puzzles and Cryptographic Hardness
    with Elette Boyle and Mor Weiss
    TCC 2019
  17. On the (In)security of Kilian-Based SNARGs
    with James Bartusek, Liron Bronfman, Fermi Ma, and Ron D. Rothblum.
    TCC 2019
  18. Fully Homomorphic Encryption for RAMs
    with Ariel Hamlin, Mor Weiss, and Daniel Wichs.
    CRYPTO 2019
  19. Fiat-Shamir: From Practice to Theory
    (merge of Fiat-Shamir From Simpler Assumptions and Non-Interactive Zero Knowledge and Correlation Intractability from Circular-Secure FHE)
    with Ran Canetti, Yilei Chen, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs.
    STOC 2019
  20. The Parallel Repetition of Non-Signaling Games: Counterexamples and Dichotomy
    with Lisa Yang
    STOC 2019 and QIP 2019,
  21. Cryptographic Hashing from Strong One-Way Functions
    with Alex Lombardi
    FOCS 2018
  22. Delegation With (Nearly) Optimal Time/Space Overhead
    with Ron D. Rothblum
    FOCS 2018
  23. Towards Doubly-Efficient Private Information Retrieval
    with Ran Canetti and Silas Richelson
    TCC 2017
  24. Non-Interactive RAM and Batch NP Delegation from any PIR
    with Zvika Brakerski and Yael Kalai
    STOC 2017
  25. Succinct Adaptive Garbled RAM
    with Ran Canetti, Yilei Chen, and Mariana Raykova.
    TCC 2016-B
  26. Fully Succinct Garbled RAM
    with Ran Canetti
    ITCS 2016
  27. Watermarking Cryptographic Capabilities
    with Aloni Cohen and Vinod Vaikuntanathan (Merged with Ryo Nishimaki and Daniel Wichs)
    STOC 2016
  28. Multilinear Pseudorandom Functions
    with Aloni Cohen
    ICALP 2015
  29. Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
    with Ran Canetti, Abhishek Jain, Vinod Vaikuntanathan
    STOC 2015

Manuscripts

  1. No-Signaling MIPs and Faster-Than-Light Communication, Revisisted (2020)
  2. On Round-By-Round Soundness and State Restoration Attacks (2019)
  3. On Necessary Padding with IO (2015)

Teaching

In Fall 2016, I co-taught Advanced Topics in the Theory of Cryptography with Aloni Cohen, Sunoo Park, and Adam Sealfon.

In Spring 2014, I was a TA for 6.857: Computer and Network Security, taught by Ron Rivest. See the notes for a lecture I prepared on Bitcoin.