A user provides an identification (ID) signal (e.g. a biometric ID signal like a self-snapshot) to a trusted cloud-based provider. When the user attempts to authenticate with the cloud-based provider, a similar ID signal (e.g. another self-snapshot) for the user is captured and provided to the cloud-based provider. The cloud-based provider then obtains a secondary ID signal, or a combination of secondary ID signals, and utilizes the secondary ID signal, or signals, to identify a subset of user records to be searched for the ID signal. The subset of the records, rather than all of the user records, can then be searched for the ID signal. The cloud-based provider can then authenticate the user based on the results of the search of the subset of the user records.