2 ms·
If you say a malicious server can't determine which article was retrieved, is that private information retrieval (PIR)? Something must be different here. I th
by throwaway81523 4y ago
If you say a malicious server can't determine which article was retrieved, is that private information retrieval (PIR)? Something must be different here. I thought there was a theorem that for single-server PIR to work, the client has to download the entire DB, which is the right way to read Wikipedia privately anyway.
- blintz 4y agoThis is PIR. You do have to download the whole database for information-theoretic security, but not for computational security. If you assume the hardness of some problem (in this case, lattices, but it is also possible from RSA, ECC, etc) it is possible to do much better than simply downloading the entire database.
- throwaway81523 4y agoDoes the server have to scan the whole database on every query? If not, doesn't the disk access pattern tell you what the query was? I had thought you had to download the whole DB even for computational PIR, but hmm, maybe not in some cases where there is only 1 client with a secret.
- blintz 4y agoYes, the whole database is scanned to answer a single query.