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, particularly from underrepresented backgrounds.
Papers
Publications- 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
- (Nondeterministic) Hardness vs. Non-Malleability
Marshall Ball, Dana Dachman-Soled, Julian Loss
CRYPTO 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-Malleablility
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 Wost-Case Assumptions
Marshall Ball, Prashant Vasudevan, Alon Rosen, Manuel Sabin
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