  Cryptography often considers the strongest yet plausible attacks in the real
world. Preprocessing (a.k.a. non-uniform attack) plays an important role in
both theory and practice: an efficient online attacker can take advantage of
advice prepared by a time-consuming preprocessing stage.
  Salting is a heuristic strategy to counter preprocessing attacks by feeding a
small amount of randomness to the cryptographic primitive. We present general
and tight characterizations of preprocessing against cryptographic salting,
with upper bounds matching the advantages of the most intuitive attack. Our
result quantitatively strengthens the previous work by Coretti, Dodis, Guo, and
Steinberger (EUROCRYPT'18). Our proof exploits a novel connection between the
non-uniform security of salted games and direct product theorems for memoryless
algorithms.
  For quantum adversaries, we give similar characterizations for property
finding games, resolving an open problem of the quantum non-uniform security of
salted collision resistant hash by Chung, Guo, Liu, and Qian (FOCS'20). Our
proof extends the compressed oracle framework of Zhandry (CRYPTO'19) to prove
quantum strong direct product theorems for property finding games in the
average-case hardness.
