[Download postscript version]

Requirements for Hash Visualization Algorithms

 

In order for HVAs to be useful for secure applications, we illustrate a variety of desired properties for HVAs. A HVA that is used in a particular application will only need to satisfy a subset of the properties. We will give several examples of these applications and their usage of the HVAs in the later section.

Near-one-way property

We define two images $I$₁ and $I$₂ to be near, denoted as $I$₁ I₂, if the two images are perceptually indistinguishable.

1. Near preimage resistance: for any pre-specified output image $y$, it is computationally infeasible to find the input $x$ such that $h$_I(x) y.
2. Near 2nd-preimage resistance: given any input $x$, it's computationally infeasible to find $x\text{'}$ such that $h$_I(x') h_I(x).
3. Near collision resistance: it is computationally infeasible to find any two distinct inputs $x,\; x\text{'}$ which hash to the same output, $h$_I(x) h_I(x').

It is difficult to devise an algorithm which can judge automatically whether two images are near since that depends on the person comparing the images. But in general, we can find some similarity-metric function $\delta :\; I\; I\; \to R$ and a threshold $\beta$ such that if $\delta (I$₁, I₂) ≥β, then the two images $I$₁ and $I$₂ are not near. Finding a good function for $\delta$ is an active area of research in image retrieval and is not in the scope of this paper.

Regularity property

Humans are good at identifying geometric objects (such as circles, rectangles, triangles, and lines), and shapes in general. We call images, which contain mostly recognizable shapes, regular images. If an image is not regular, i.e. does not contain identifiable objects or patterns, or is too chaotic (such as white noise), it is difficult for humans to compare or recall it.

We suggest two ways for testing the regularity of an image automatically.

1. We can use a compression algorithm to compress the image. If the image is chaotic, such as white noise, the compression factor will be very small since almost every pixel is random. Therefore we can show that an image is regular if the compression factor is above a certain threshold.
2. Non-regular images tend to have wide frequency spectra. Noisy images contain a high percentage of the energy in high frequencies. Hence we can transform an image to the Fourier domain and compute the magnitude spectrum. If the magnitude spectrum does not have too much energy in the high frequencies, $\sum$f>f_thresh | F(f) | < const, then the image is regular.

To illustrate how to use energy in the magnitude spectrum of the Fourier transform in order to decide regularity, we show in figure 1 white noise along with the Fourier transform.

       
Figure 1: White noise and photograph

Minimum complexity property

Since the image might be presented in many different ways, i.e., printed in a newspaper, displayed on a color LCD display, or on a TV screen, the result of comparing two images needs to be robust with respect to resolution and color changes: if two inputs $x$₁ and $x$₂ are different, then the two outputs $h$_I(x₁) and $h$_I(x₂) should not be near with any resolution and color configuration that could occur in the secure system; similarly, if two inputs $x$₁ and $x$₂ are equal, then the outputs $h$_I(x₁) and $h$_I(x₂) should be near with any resolution and color configuration that could occur in the secure system.

An immediate implication of this property is that an image can not be too simplistic in shapes and patterns, or rely on subtle color differences. Just like for to the regularity property, we could use compression or the frequency spectrum to detect images that are simplistic. For example, compressing an image which has all pixels set to a unique color, should result in a very short file. Also, the frequency spectrum of such a simplistic picture has all the energy in the lowest frequency components.