In this PIR model the server has to read the whole database, otherwise it would be easy on the server to see, that these rows were not accessed and therefore they are not the one the client queried.
In this PIR model the server runtime is O(n) where n is the number of rows.
To keep it practical, we do support sharding the database. Client leaks a few bits of hashed query to pick the right shard, where we process the entire shard. There is a inherent privacy-performance tradeoff: less shards = less leakage vs more shards = better performance & less privacy.
A very simple PIR scheme on top of homomorphic encryption that supports multiplying with a plaintext and homomorphic addition, would look like this:
The client one-hot-encodes the query: Enc(0), Enc(1), Enc(0).
The server has 3 values: x, y, z.
Now the server computes: Enc(0) * x + Enc(1) * y + Enc(0) * z == Enc(y).
Client can decrypt Enc(y) and get the value y. Server received three ciphertexts, but does not know which one of them was encryption of zero or one, because the multiplications and additions that the server did, never leak the underlying value.
This gives some intuition on how PIR works, actual schemes are more efficient.
[Disclosure: I work on the team responsible for the feature]
> The Sensitive Content Analysis framework enables third-party developers to integrate Communication Safety in their apps. The framework allows developers to detect if content that children receive or attempt to send in their apps may contain nudity, and developers can add protections in their apps when sensitive content is detected.
I had phone that could run J2ME but did not have Internet.
I reverse engineered a flash application that showed a map and provided address search. I scraped the map tiles and address to location database. Reimplemented the viewer application as a Java applet and preloaded the tiles and address database to a microSD card connected to the phone. So essentially I built my own offline maps for my not internet connected phone.
Address search required prefix tree because IO was too slow to use binary search on the phone.
Anyway this was done just before I went to a new city to attend university and it was really helpful to find out where I am and where to go. There was no navigation, but it showed the map, gps location and the location where I needed to get to.
So that was my personal project that really had great utility for me.
The encryption is data dependent. The homomorphic computation itself cannot be data dependent. Homomorphic encryption says that even if you see all the intermediate encrypted values, you will not know what the encrypted input or output value is. So side-channels do not matter for the computationally heavy evaluation part. In this paper they attacked the encryption part.
“Alfred Vaino Aho” this a the first time I looked it up in full (with the middle name) it seems like a Finnish or maybe Estonian name. I am wondering if he has Finnish or Estonian heritage.