Comment by criticaltinker | Hacker News Reader

Comment by criticaltinker | Hacker News Reader

Parent Full thread

> In order to test things, I decided to search the publicly available ImageNet dataset for collisions between semantically different images. I generated NeuralHashes for all 1.43 million images and searched for organic collisions. By taking advantage of the birthday paradox, and a collision search algorithm that let me search in n(log n) time instead of the naive n^2, I was able to compare the NeuralHashes of over 2 trillion image pairs in just a few hours.

> This is a false-positive rate of 2 in 2 trillion image pairs (1,431,168^2). Assuming the NCMEC database has more than 20,000 images, this represents a slightly higher rate than Apple had previously reported. But, assuming there are less than a million images in the dataset, it's probably in the right ballpark.

It's great to see the ingenuity and attention this whole debacle is receiving from the community. Maybe it will lead to advances in perceptual hashing (and also advances in consumer awareness of tech related privacy issues).

>2 in 2 trillion image pairs

Reporting the collision rate per image pair feels misleading. What you really want to know is the number of false positives per image in the relevant set, not image pair, as that's the figure that indicates how frequently you'll hit a false positive.

In fact, I'd argue that the collision rate per image pair is overestimating the collision rate. It's the flip side of the birthday paradox. We don't care that any two images have the same hash, we care about any image having the same hash as one in the set that we're testing against.

>We don't care that any two images have the same hash,

Why not?

Based on the pigeonhole principle alone, it will always be the case that collisions exist. The size of the digest is very likely smaller than the size of any given image.

How is that relevant to whether “per image” or “Per image pair” is the right metric?

Heck, how is it relevant to anything given that hash functions avoid collisions in practice, even given the pigeonhole principle?

Those should only differ by a factor of 2 [the collision rate for an image is the number of collisions it has divided by the number of other images, so the average collision rate is the total collisions divided by n(n-1) vs. n(n-1)/2 pairs] which isn't particularly relevant at this scale

You care about the total number of collisions, not collisions for a specific image, so they differ by a square -- hence the 1 in a trillion vs million difference.

ImageNet is a very well-known data set. Are we sure apple didn't test on it when designing this algorithm?

>This is a false-positive rate of 2 in 2 trillion image pairs (1,431,168^2). Assuming the NCMEC database has more than 20,000 images, this represents a slightly higher rate than Apple had previously reported. But, assuming there are less than a million images in the dataset, it's probably in the right ballpark.

Apple reported a pretty similar collision rate so maybe they did.

Their reported collision rate was against their CSAM hash database[1].

> In Apple’s tests against 100 million non-CSAM images, it encountered 3 false positives when compared against NCMEC’s database. In a separate test of 500,000 adult pornography images matched against NCMEC’s database, it found no false positives.

[1] https://tidbits.com/2021/08/13/new-csam-detection-details-em...

I don't follow the point you are making here. The goal of the algorithm is to match images so I would expect similar collision rates regardless of what image was matched against what set of hashes. The exact rate of collision will obviously vary slightly.

I think the point is that if Apple did optimize the algorithm using ImageNet then they and we are seeing the same best case scenario.

The only number I've heard from Apple is, "the likelihood that the system would incorrectly identify any given account is less than one in one trillion per year."[1] Which I read as enough false hits to flag an account that year (some interview said that threshold was around 30). That depends on the average number of new photos uploaded to iCloud, the size of the NCMEC database, the threshold for flagging the account, and the error rate of the match. Without knowing most of those numbers it's hard to gauge how close it is.

https://www.apple.com/child-safety/pdf/Expanded_Protections_...

Nah, the consensus online seems to be that Apple hires naive, inept script kiddies and that any rando on GitHub can prove without question that Apple’s solution is flawed.

Reply on news.ycombinator.com