Paper 2024/831

Tight Characterizations for Preprocessing against Cryptographic Salting

Fangqi Dong, Tsinghua University
Qipeng Liu, University of California, San Diego
Kewen Wu, University of California, Berkeley
Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Keywords
SaltingNon-uniform Attacks
Contact author(s)
dongfangqi77 @ gmail com
qipengliu0 @ gmail com
shlw_kevin @ hotmail com
History
2024-05-31: approved
2024-05-28: received
See all versions
Short URL
https://ia.cr/2024/831
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/831,
      author = {Fangqi Dong and Qipeng Liu and Kewen Wu},
      title = {Tight Characterizations for Preprocessing against Cryptographic Salting},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/831},
      year = {2024},
      url = {https://eprint.iacr.org/2024/831}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.