Mildly-lossy reductions, which lose information only on sparse uniform inputs, are shown to imply one-way functions (and quantum one-way state generators) unless they run in near-optimal worst-case time.
Tomoyuki Morimae and Takashi Yamakawa
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CR 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond
Mildly-lossy reductions, which lose information only on sparse uniform inputs, are shown to imply one-way functions (and quantum one-way state generators) unless they run in near-optimal worst-case time.