Probabilistic Identity Filter for Offline, Privacy-Preserving, Contact-Based Nearby Device Discovery
Abstract
A core component of offline, private, contact-based discovery is requiring the two devices to perform a cryptographic protocol known as private set intersection (PSI) between a list of identifiers stored at a first device and the address book of known contacts stored at a second device. However, PSI is computationally expensive. This disclosure describes a probabilistic identity filter for devices. A device can encode a set of identities using this filter that enables other devices to check if their identity belongs in this filter with no false negatives and only small false positive probabilities, while ensuring that other devices cannot extract the exact identities placed into the filter. Devices that participate in contact-based discovery can first use the probabilistic identity filter to check if their identity is part of the filter. If not, such devices can safely terminate the discovery process without performing the expensive PSI protocol. This can substantially improve the efficiency in the majority of interactions where contact-based discovery is attempted.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
McCloskey, Dave; Krahn, Darren; Seo, Joon Young; and Yeo, Kevin, "Probabilistic Identity Filter for Offline, Privacy-Preserving, Contact-Based Nearby Device Discovery", Technical Disclosure Commons, (October 23, 2025)
https://www.tdcommons.org/dpubs_series/8772