I thought I understood one core principle of encryption: You take clear text, encrypt it, and now that encrypted gibberish can’t be worked with until it is decrypted again. THIS IS WRONG.
There is a concept called homomorphic encryption, which turns this assumption on its head: You can actually work with the encrypted data and do mathematical calculations on it, and those calculations also happened on the clear text.
Let me try to explain this in the most basic way:
Our clear numbers are 4 and 9. Now let’s assume our “encryption algorithm” consists of multiplying these numbers with another secret number 5.
So if we encrypt our clear data, we end up with two encrypted data sets: 20 (=4*5) and 45 (=9*5). This encrypted data has homomorphic properties. So we can now give these numbers to a third person (a server) and say, “Add these two for me.”. And we get back the result 65 (=20+45).
Now we “decrypt” this again by dividing by our secret 13 (=65/5) which is exactly the same as if we sum up the two clear data numbers 4+9=13 …yaay.
So we now have a way to offload calculations to a server, which has no chance of ever knowing the original secret.
Be aware that in the real world, this is a lot more complex, to be secure. Our example would be easily hackable by finding the Greatest Common Factor for our numbers. (GCF of 20 and 45 is 5). But the principle is kind of the same: Do some encryption magic, and then you can do calculations on the encrypted data, which reflects in the original data.
This week’s paper discusses the idea of using homomorphic encryption for private information retrieval. Basically, building a Google/Wikipedia that is proven privacy-friendly (it actually exists: spiralwiki.com)
Software exists to create business value
I am Simon Frey, the author of the Weekly CS Paper Newsletter. And I have great news: You can work with me
As CTO as a Service, I will help you choose the right technology for your company, build up your team and be a deeply technical sparring partner for your product development strategy.
Checkout my website simon-frey.com to learn more or directly contact me via the button below.
Abstract:
We explore the limits of single-server computational private information retrieval (PIR) for the purpose of preserving client access patterns leakage. We show that deployment of non-trivial single server PIR protocols on real hardware of the recent past would have been orders of magnitude less
time-efficient than trivially transferring the entire database. We stress that these results are beyond existing knowledge of mere “impracticality” under unfavorable assumptions. They rather reflect an inherent limitation with respect to modern hardware, likely the result of a communication-cost centric protocol design. We argue that this is likely to hold on non-specialized traditional hardware in the foreseeable future. We validate our reasoning in an experimental setup on modern off-the-shelf hardware. Ultimately, we hope our results will stimulate practical designs.
Download Link:
https://zxr.io/research/sion2007pir.pdf
Additional Links:
- Private information retrieval using homomorphic encryption (explained from scratch) This article is a lot less mathematically and ACTUALLY made me understand how this works :’D