An example apparatus is provided that receives a pseudonym and encrypted identifier, where the pseudonym is of a user's personal data. The pseudonym has been generated using a first secret key, and the encrypted identifier has been generated by encrypting the identifier using a second secret key. The first and second secret keys are known to other user(s) authorized to access the data, and are unknown to the apparatus. The operations also include storing the personal data in a database under the pseudonym, and indexed by the encrypted identifier. The keys used for encryption and pseudorandom generation can be provided by a second apparatus (e.g. an offline security manager), which may employ a proxy re-encryption scheme to provide proper keys to the apparatus based on access policies. Only the authorized users can decrypt the keys with their private keys, thus can query the user records stored in the apparatus.