@operator & /operator | building future.news | BCI, bioinformatics, search, chaos, decentralized AI

PIR has been around for a bit, with schemes varying from naive (just send the whole database, which is obviously useless), to the naive LWE construction (O(sqrt(N) of database size), to the more recent SimplePIR and DoublePIR (https://eprint.iacr.org/2022/949), which EXO is using SimplePIR. The "trick" here, is that the server has a preprocessed hint payload that the client must download, which is 4*(sqrt(N)) the size of the database, and a relatively high per-request payload (~242kB). For something Google scale, this is unusable. DoublePIR reduces the hint database size to a much more manageable size, but increases communication overhead, making it also unusable for something Google scale. What they're doing is very cool though, however it seems their Wikipedia remark is not true – they had a random article fetch for their PIR server, but they removed it, probably because it was not using PIR at all: https://github.com/exo-explore/private-search/commit/ba3b8c686f7074fcfe50f19f93ab03d9afa6b85e

at some point i really should try to get past the first problem set

@operator & /operator | BCI, bioinformatics, search, chaos, decentralized AI

her christmas challenges were fun but yeah it sucks/hard