The Binomial Ladder Frequency Filter and its Applications to Shared Secrets

We introduce the binomial ladder filter: a data structure used to examine a stream of values to identify those that occur frequently, while keeping the identity of infrequent values private. Password-protected services may use the filter when users choose passwords, to isolate the common (weak) passwords and forbid their use—without storing or revealing infrequent (likely-strong) passwords. Similarly, when users login, they may filter the stream of passwords from failed login attempts to isolate frequent incorrect passwords, which result when attackers guess a password they believe to be common against many user accounts. The filter would ignore passwords from users’ failed logins, which exhibit errors that are broadly distributed and infrequent (even if collectively more frequent). Among the features of the binomial ladder filter are that it protects the privacy both of the frequency of values in a stream and the identity of the values themselves; its size does not grow with the number of elements in the stream or the number of possible values any element can represent; it does not need to be replaced or re-initialized with age; and with small modifications it can be implemented efficiently in highly-distributed systems with minimal coordination.