Techniques are disclosed for using a false positive-prone data structure to store normalization data for use in an encrypted search context. A file host server in a cloud provider network may provide search functionality for a user's encrypted data by use of a search index. In updating the search index, the server consolidates common identities of the user on different web services (e.g., an e-mail service or a social media service) into a normalized identifier. These normalization values are stored in the false positive-prone data structure (e.g., a colliding hash table, a Bloomier filter, etc.). Consequently, the data structure may return false positives after a search operation. The server may filter out these false positives before returning search results.