Preimage Awareness in Linicrypt
Zahra Javar, Bruce M. Kapron · 2023
We extend the analysis of collision-resistant hash functions in the Linicrypt model presented by McQuoid, Swope & Rosulek (TCC 2019) in order to characterize preimage awareness, a security property defined by Dodis, Ristenpart & Shrimpton (Eurocrypt 2009), who also demonstrate its utility in the construction of indifferentiable hash functions. We present a simple and efficiently-checkable property of Linicrypt programs which characterizes preimage awareness. Finally, we show that this characterization may be efficiently automated and as an example, use it to enumerate all preimage-aware compression functions which use two calls to the random oracle. This includes several functions shown to be preimage aware by Dodis et. al. using hand-crafted proofs.