A first version of a database is accessed. The first version includes the identities of items of information included in the database. A second version of the database is generated. The second version includes changed identities created by applying a function to the identities of the first version. In response to a query that seeks to determine whether a particular item is in the first version, the function is applied to the particular item to generate a changed identity for the particular item. Verification information is provided to demonstrate that the changed identity for the particular item was determined using the same function used to create the changed identities in the second version. A determination is made whether or not the particular item is in the second version and hence in the first version of the database, without requiring a release of the identities in the first version.