Records in a secure database include attributes. A query homomorphically encrypts indices identifying one record and attribute. A secret key is generated at a certain query count and is divided into randomly generated key shares. A key share sequence is homomorphically encrypted. A table is formed by encrypting the indices, secret key and attributes. The key shares are decrypted sufficient to recover the secret key subject to a non-inference enabling query. In a further embodiment, a query count is maintained. Records in a secure database include attributes, with an attributes set forming inference channels. A data structure includes ciphertext keys. A pseudorandom function seed and non-malleable encryption secret key are chosen. A query provides indices identifying one record and attribute. A secure function evaluation is executed. A table combines the attributes with the pseudorandom function applied to the seed and indices. A table entry for the indices is provided.