4 ms·

> In order to test things, I decided to search the publicly available ImageNet dataset for collisions between semantically different images. I generated NeuralH

> 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).

bawolff 5y ago
ImageNet is a very well-known data set. Are we sure apple didn't test on it when designing this algorithm?
- slg 5y ago
  >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.
  - yeldarb 5y ago
    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-emerge-following-craig-federighi-interview/ https://tidbits.com/2021/08/13/new-csam-detection-details-em...
    - slg 5y ago
      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.
      - javierbyte 5y ago
        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.
  - pfranz 5y ago
    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_for_Children_Frequently_Asked_Questions.pdf https://www.apple.com/child-safety/pdf/Expanded_Protections_...
- robertoandred 5y ago
  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.
SilasX 5y ago
>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.
- dhosek 5y ago
  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.
  - SilasX 5y ago
    >We don't care that any two images have the same hash, Why not?
    - snet0 5y ago
      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.
      - SilasX 5y ago
        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?
- LodeOfCode 5y ago
  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

bawolff 5y ago

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

slg 5y ago
>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.
- yeldarb 5y ago
  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-emerge-following-craig-federighi-interview/ https://tidbits.com/2021/08/13/new-csam-detection-details-em...
  - slg 5y ago
    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.
    - javierbyte 5y ago
      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.
- pfranz 5y ago
  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_for_Children_Frequently_Asked_Questions.pdf https://www.apple.com/child-safety/pdf/Expanded_Protections_...
robertoandred 5y ago
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.

SilasX 5y ago

>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.

dhosek 5y ago
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.
- SilasX 5y ago
  >We don't care that any two images have the same hash, Why not?
  - snet0 5y ago
    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.
    - SilasX 5y ago
      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?
LodeOfCode 5y ago
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