Marshall Ball
marshall.ball at cs.nyu.edu
Department of Computer Science
Courant Institute of Mathematical Sciences
New York University
I am an Assistant Professor of Computer Science at NYU Courant.
My research is in theoretical computer science, particularly the foundations of cryptography and computational complexity.
I completed my PhD at Columbia University, where I was fortunate enough to be advised by Tal Malkin. In the midst of my doctoral studies, I spent two and half years visiting the FACT Center at IDC Herzliya, Israel. After graduating, I was a postdoctoral scholar at the University of Washington, supported by a NSF/CRA Computing Innovation Fellowship, under the guidance of Huijia Lin and Stefano Tessaro.
I'm currently looking for creative and motivated students.
Papers
Publications and PreprintsSee also Google Scholar and DBLP.
- A Complexity-Theoretic Approach to Proofs of Space
Marshall Ball, Jiaxin Guan
Preprint, 2026 - Strong Pseudorandom Functions in AC0[2] in the Bounded-Query Setting
Marshall Ball, Clément Ducros, Saroja Erabelli, Lisa Kohl, Nicolas Resch, Peter Scholl
TCC 2026 (to appear) - Permissionless Consensus from a Common Random String
Damiano Abram, Marshall Ball, Juan Garay, Aggelos Kiayias
CRYPTO 2026 - Fair Multiparty Coin Tossing from Minimal Assumptions
Marshall Ball, Miranda Christ, Yevgeniy Dodis, Rachit Garg
EUROCRYPT 2026 - How to Use Nondeterminism in Cryptography
Marshall Ball, Peter Crawford-Kahrl
ITCS 2026 - Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)
Marshall Ball, Lijie Chen, Roei Tell
CCC 2025 - Uniform Black-Box Separations via Non-Malleable Extractors
Marshall Ball, Dana Dachman-Soled
CRYPTO 2025 - (Inefficient Prover) ZAPs from Hard-to-Invert Functions
Marshall Ball, Dana Dachman-Soled
EUROCRYPT 2025 - Extractors for Samplable Distributions with Low Min-Entropy
Marshall Ball, Ronen Shaltiel, Jad Silbak
STOC 2025 - Towards Permissionless Consensus in the Standard Model via Fine-Grained Complexity
Marshall Ball, Juan Garay, Peter Hall, Aggelos Kiayias, Giorgos Panagiotakos
CRYPTO 2024 - Non-Malleable Codes with Optimal Rate for Poly-Size Circuits
Marshall Ball, Ronen Shaltiel, Jad Silbak
EUROCRYPT 2024 - Secure Stateful Aggregation: A Practical Protocol with Applications in Differentially-Private Federated Learning
Marshall Ball, James Bell-Clark, Adrià Gascón, Peter Kairouz, Sewoong Oh, Zhiye Xie
IACR ePrint 2024 - Immunizing Backdoored PRGs
Marshall Ball, Yevgeniy Dodis, Eli Goldin
TCC 2023 - Towards Topology-Hiding Computation from Oblivious Transfer
Marshall Ball, Alex Bienstock, Lisa Kohl, Pierre Meyer
TCC 2023 - Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement
Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass
FOCS 2023 - Extracting Randomness from Samplable Distributions, Revisited
Marshall Ball, Dana Dachman-Soled, Eli Goldin, Saachi Mutreja
FOCS 2023 - Experimental evaluation of digitally verifiable photonic computing for blockchain and cryptocurrency
Sunil Pai, Taewon Park, Marshall Ball, Bogdan Penkovsky, Michael Dubrovsky, Nathnael Abebe, Maziyar Milanizadeh, Francesco Morichetti, Andrea Melloni, Shanhui Fan, Olav Solgaard, David AB Miller
Optica 10 (5) - New Ways to Garble Arithmetic Circuits
Marshall Ball, Hanjun Li, Huijia Lin, Tianren Liu
EUROCRYPT 2023 - Non-malleable Code in the Split-State Model
Divesh Aggarwal, Marshall Ball, Maciej Obremski
Entropy 24 (8) - (Nondeterministic) Hardness vs. Non-Malleability
Marshall Ball, Dana Dachman-Soled, Julian Loss
CRYPTO 2022 - A Note on the Complexity of Private Simultaneous Messages with Many Parties
Marshall Ball, Tim Randolph
ITC 2022 - Randomness Extraction from Somewhat Dependent Sources
Marshall Ball, Oded Goldreich, Tal Malkin
ITCS 2022 - Linear Threshold Secret-Sharing with Binary Reconstruction
Marshall Ball, Alper Cakan, Tal Malkin
ITC 2021 - Communication Complexity with Defective Randomness
Marshall Ball, Oded Goldreich, Tal Malkin
CCC 2021 -
Topology-Hiding Communication from Minimal Assumptions
Marshall Ball, Elette Boyle, Ran Cohen, Lisa Kohl, Tal Malkin, Pierre Meyer, Tal Moran
TCC 2020 - New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, interaction, and trust
Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni
CRYPTO 2020 (video) - Non-Malleability against Polynomial Tampering
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan
CRYPTO 2020 - Cryptography from Information Loss
Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Nalini Vasudevan
ITCS 2020 - Limits to Non-Malleability
Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin
ITCS 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
ITCS 2020 (video) - Is Information-Theoretic Topology-Hiding Computation Possible?
Marshall Ball, Elette Boyle, Ran Cohen, Tal Malkin, Tal Moran
TCC 2019 - Non-Malleable Codes for Decision Trees
Marshall Ball, Siyao Guo, Daniel Wichs
CRYPTO 2019 (video) - Garbled Neural Networks are Practical
Marshall Ball, Brent Carmer, Tal Malkin, Mike Rosulek, Nichole Schimanski.
Presented at PPML 2019 (CRYPTO) & PPML 2019 (CCS) - Non-Malleable Codes Against Bounded Polynomial Time Tampering
Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, Tal Malkin
EUROCRYPT 2019 (video) - Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan
FOCS 2018 - Proofs of Work from Worst-Case Assumptions
Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan
CRYPTO 2018 (video) - Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering
Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin
EUROCRYPT 2018 - Exploring the Boundaries of Topology-Hiding Computation
Marshall Ball, Elette Boyle, Tal Malkin, Tal Moran
EUROCRYPT 2018 - Average-Case Fine-Grained Hardness
Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan
STOC 2017 - Garbling Gadgets for Boolean and Arithmetic Circuits
Marshall Ball, Tal Malkin, Mike Rosulek
CCS 2016 (video) - Non-Malleable Codes for Bounded Depth, Bounded Fan-In Circuits
Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin
EUROCRYPT 2016
- On Resilience to Computable Tampering
Marshall Ball
Teaching
Students and Alumni
- Alex Bienstock (Ph.D. 2023; joint with Yevgeniy Dodis). Senior Research Scientist at J.P. Morgan AI Research.
- Peter Hall (joint with Yevgeniy Dodis)
- Eli Goldin (joint with Yevgeniy Dodis)
- Peter Crawford-Kahrl
- Saroja Erabelli (joint with Nir Bitansky)
- Justin Kim (joint with Yevgeniy Dodis and Nir Bitansky)