IBM's homomorphic encryption library
Posted May 12, 2013 1:49 UTC (Sun) by dlang (subscriber, #313)
Posted May 12, 2013 7:21 UTC (Sun) by ras (subscriber, #33059)
No, again not if you do it right. Lets say we have a bucket, and it ends up covering the range 1111-01-01...1111-02-01. Any query that has any part of its range will return every email in that bucket. There may be no emails that actually match in the bucket. What the attacker gets back is effectively a lump of random data. All he knows is that it always the same random data - not that any of the data actually matches his query. The object of the exercise here is to reduce the amount of data that is transferred to something tolerable. A bucket of 100 email-id's would take 5 KB or so. Combining queries with AND's is out of course, but "in this date range OR sender contains 'ABCDEF'" would be fine, and then the back end must calculate the AND to get "find all emails from ABCDEF in this date range".
You are also assuming the attacker knows what you are querying, which he doesn't. What he knows is you have sent some encrypted data to the engine, the engine is applying some homomorphic operation to the payload and what it has stored to yield a result, and in this case the result always returns the same answer. The whole point of homomorphic operation is no one, including CPU executing the operation, as any idea what it means. So neither the CPU doing the operation nor anyone watching knows you are doing a date range query, let alone for what dates. I presume it would be possible to know the homomorphic operation is a range check of some sort - but that is all they know.
I think you may be confusing research showing how it often possible to get information about one specific person out of data that supposedly has been aggregated to prevent that that. You are right to be nervous about that, but it has no relevance here.
Posted May 12, 2013 7:25 UTC (Sun) by dlang (subscriber, #313)
Posted May 12, 2013 8:23 UTC (Sun) by ras (subscriber, #33059)
We would try to ensure only an authenticate entities could ask queries, but it is reasonable to assume the attacker has been clever enough to figure a way around that. And in particular if the attacker is the storage system itself, it does have a way around it.
However "Craft a query" implies to me know what you are asking. The storage has encrypted data, does some homomorphic operations on the data it has and encrypted data it has been sent - ("the query"). This operation yields unencrypted data - which effectively a "yes/no" to send some data it has stored back.
So yes, in the sense that the server can dream up throw random queries at the database and see what it says - it can "craft queries". But since it has no idea what it is asking it is of limited usefulness.
The trigger for my comment is what these people aiming for - a complete and fast set of homomorphic operations, seems like it is a long, long away away. But we don't need that to change the world. All we need are a set of homomorphic operations for querying a database. And even that turns out to be simpler than it sounds - all you need to implement is a homomorphic range query. That sounds plausible to me, so plausible I've made it a personal hobby project.
Posted May 12, 2013 9:57 UTC (Sun) by paulj (subscriber, #341)
Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds