On the Pitfalls of Modeling Individual Knowledge

The concept of knowledge has been central in cryptography, especially within cryptographic proof systems. Traditionally, research in this area considers an abstract prover defending a claim that it knows a message M . Recently, a stronger concept-termed "individual" (Dziembowski et al., CRYPTO'23) or "complete" (Kelkar et al., CCS'24) knowledge-has emerged. This notion ensures the prover physically stores M on a machine that it controls. As we argue in the paper, this concept also appears in earlier work on "non-outsourceable puzzles" (Miller et al., CCS'15), which implicitly assumes that performing quickly complex computation on a string M implies storing it on a single machine. In this line of work, the authors typically rely on the algorithms whose computation requires a massive number of queries to a hash function H. This paper highlights a subtle issue in the modeling used in some of these papers, more concretely, the assumption that H can be modeled as an atomic random oracle on long messages. Unfortunately, this does not correspond well to how the hash functions are constructed in practice. For example, the real-world hash functions (e.g., Merkle-Damgård or sponge-based) allow partial evaluation on long inputs, violating this assumption. Another example is the hashing used in Bitcoin mining, which permits similar precomputation. This undermines some protocols relying on individual knowledge. We demonstrate practical attacks against Miller et al.'s and Kelkar et al.'s schemes based on this observation, and discuss secure alternatives. Our alternative constructions, which are modifications of the original ones, avoid reliance on the random oracle behavior of hash functions on long messages. In the full version of this paper, we will provide their formal security analysis in the individual cryptography model of Dziembowski et al. (CRYPTO'23).