Comment by blintz
3 years ago
This 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.
Does 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.
Yes, the whole database is scanned to answer a single query.