Can homomorphic encryption filter? Often in articles homomorphic encryption is praised as the holy grail of encryption for cloud storage. This is done by suggesting that it can do any computation, and as such could be used for encrypted databases.

Performance issues aside, this makes me very sceptical. If such a database is to be any useful you need to be able to do queries. I understand how these work and how you could do the tricks needed to transform a query into a circuit.

However such a circuit only does a modification on the data, but it does not reduce it's size. In fact, the only way I see you can get the results is by executing the circuit and returning the entire modified database.

So is it possible for homomorphic encryption to actually filter and return a small encrypted subset of a larger encrypted database based on a query?
So is it possible for homomorphic encryption to actually filter and return a small encrypted subset of a larger encrypted database based on a query?


Sure it is. Say we have a database with (encrypted) test scores and student id and want to query the DB for the student with the highest score. Using FHE we can do comparison that for our purposes assume returns either 0 or 1.



students,scores = query()
high_student = encrypt(pk, 0) # encrypt with the public key
high_score = encrypt(pk, 0) # same

for student,score in (students, scores):
  bit = score > high_score
  high_score = bit*score + (1-bit)*high_score
  high_student = bit*student + (1-bit)*high_student

return high_student



This illustrates how you can filter as long as the number of returned results is fixed (not even necessarily fixed to 1). What if you wanted every student with greater than a 90%? I don't think that is possible with out returning something the same size as the entire table. this makes sense as you don't want your FHE to leak any information. That would leak how many values are greater than 90%.