[shakna]

Perceptual hashing wouldn't seem to satisfy your second requirement there, either.

[a-dub]

it does, it just works on estimates of percepts rather than bits.

you can think of a perceptual hash as two functions. a perceptual function that maps differing collections of bits that appear the same or similar to the same bits, and then a traditional hash function to ensure that these intermediate values get shuffled.