Encryption with keys that form an Abelian group are used in combination with a semi-trusted party that converts queries that are encrypted with the key of a querier to queries that are encrypted with the key of the encrypted database, without knowing the actual keys. In an illustrative embodiment, encryption is done with Bloom filters that employ Pohlig-Hellman encryption. Since the querier's key is not divulged, neither the semi-trusted party nor the publisher of the database can see the original queries. Provision can be made for fourth party “warrant servers”, as well as “censorship sets” that limit the data to be shared.