Publications and Preprints

Marshall Ball · DBLP · Google Scholar

A Complexity-Theoretic Approach to Proofs of Space
Marshall Ball, Jiaxin Guan
Preprint, 2026
Strong Pseudorandom Functions in AC⁰[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