Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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%.

share|improve this answer
1  
However, using methods similar to those in your answer, it would be possible to query e.g. for "the first 50 students with scores higher than 90%" (with null values returned if there weren't that many matching records). –  Ilmari Karonen Nov 28 '13 at 18:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.