* This is part 3 of a series on omission-tolerant integrity
protection and related topics.
See also part 1
and
part
2.
A technical report on the topic is available
on this site and
in the IACR ePrint Archive.
*

When a cryptographic hash is used as a checksum of a bit string,
security depends on the collision resistance of the hash function.
When the root label of a typed hash tree is used as an
omission-tolerant checksum of a set of key-value pairs, security also
depends on the collision resistance of a hash function, in this case
of the hash function that is used to construct the typed hash tree.
(It may also depend on the preimage resistance of the hash function
depending on how the set is encoded, as we shall see in another post
of this series.) The formal proof of security in
the technical report is therefore
based on a formal definition of collision resistance. But, surprising
as this may seem, there is no standard, widely used, formal definition
of collision resistance for the *keyless*, or *unkeyed* hash
functions such as SHA256 that are used in practice.

### Collision resistance is hard to define

The concept of a *hash function collision* is simple and clear
enough: it is a pair of distinct elements of the domain of the hash
function that have the same image. The concept of *collision
resistance*, on the other hand, is difficult to define. The reason
for this, as explained for example by Katz and Lindell in
their *Introduction to Modern Cryptography* (Chapman & Hall/CRC,
2nd edition, 2014, bottom of page 155), is that collisions exist, and
for any collision there exists a trivial algorithm that hardcodes the
collision and outputs it in constant time.