Paper 2025/1060
Uniform Black-Box Separations via Non-Malleable Extractors
, New York University, University of Maryland, College ParkAbstract
We construct $t$-non-malleable extractors---which allow an attacker to tamper with a source $t$ times---for high min-entropy sources samplable by poly-time hierarchy circuits and for tampering classes corresponding to poly-time hierarchy functions from derandomization-type assumptions. We then show an application of this new object to ruling out constructions of succinct, non-interactive, arguments (SNARGs) secure against \emph{uniform} adversaries from \emph{uniform} falsifiable assumptions via a class of black-box reductions that has not been previously considered in the literature. This class of black-box reductions allows the reduction to arbitrarily set the \emph{coins}, as well as the input, of the uniform adversary it interacts with. The class of reductions we consider is restricted in allowing only non-adaptive queries to the adversary.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. CRYPTO 2025
- Keywords
- non-malleable extractorsblack-box separationsSNARGssamplable distributionssamplable sourcesderandomization
- Contact author(s)
-
marshall @ cs nyu edu
danadach @ umd edu - History
- 2025-06-09: approved
- 2025-06-06: received
- See all versions
- Short URL
- https://ia.cr/2025/1060
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1060,
author = {Marshall Ball and Dana Dachman-Soled},
title = {Uniform Black-Box Separations via Non-Malleable Extractors},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1060},
year = {2025},
url = {https://eprint.iacr.org/2025/1060}
}
