Can homomorphic encryption filter?
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%.