1. Set up something like a bloom filter, tuned to give lots of false positives.
2. Fill the list with the 100,000 most common passwords.
3. Every time someone proposes a password, see if it hits. If so, goto 3. If not, let them use the password and insert it into the list.
I think you probably want to scrypt[1] the passwords first. If someone gets the list, they can rule out that no one has certain passwords. I'm not sure how much of a failure that is.
[1] EDIT: I mean scrypt without a hash, which might be nonsense. Or the same hash for everyone. Yes, this sucks for storing individual passwords, but it helps you build the "master list." I'm not sure there is a way around this paradox if you want to have a master list, but the bloom filter will throw a lot of noise into the mix.
1. Set up something like a bloom filter, tuned to give lots of false positives.
2. Fill the list with the 100,000 most common passwords.
3. Every time someone proposes a password, see if it hits. If so, goto 3. If not, let them use the password and insert it into the list.
I think you probably want to scrypt[1] the passwords first. If someone gets the list, they can rule out that no one has certain passwords. I'm not sure how much of a failure that is.
[1] EDIT: I mean scrypt without a hash, which might be nonsense. Or the same hash for everyone. Yes, this sucks for storing individual passwords, but it helps you build the "master list." I'm not sure there is a way around this paradox if you want to have a master list, but the bloom filter will throw a lot of noise into the mix.