karulont

Edit: it is now free

Run SHA256 on the keyword, truncate the hash and take the modulus with number of shards.

Basically the server does not know, it just computes with every possible value. And the result turns out to be what the client was interested in.

“Cheddar: A Swift Fully Homomorphic Encryption Library for CUDA GPUs” - https://arxiv.org/pdf/2407.13055

We were a little worried, but quickly discovered that they used Swift as an adjective not as a programming language.

[Disclosure: I work on the team responsible for the feature]

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.

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 point is that the proprietary client software was not used.

Can you tell us more about that?

https://www.apple.com/child-safety/

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.

At one point they were handing out T-shirts saying 9 out of 10 PHDs

But when things go wrong they run to the FBI and FTC both run by the government.

Might be a better place to start reading about it.

The presence of _unsafe_ is okay, it just means that this is a part of code, that the compiler cannot verify itself. Usually the unsafe part (verified by human) is wrapped in a API that is safe to use.

PS: You can still have memory leaks in GC-d languages by reference cycles.

Part 2 is at: https://medium.com/privacy-technology/ios14s-privacy-labels-...

The way how bots were done, was that you had to write tools that try to fingerprint interesting variables by their usage patterns in the bytecode. This was by no means an easy task. But with the frequent client updates manual reverse engineering only helped to understand the codebase, but to actually keep up with the client updates you needed to automate that work.

Disclaimer, never tried those myself.