4 ms·
> except in some (exciting!) new theoretical constructions Sorry if this is too much of a tangent, but I would love to know what these are!
by teraflop 4y ago
> except in some (exciting!) new theoretical constructions
Sorry if this is too much of a tangent, but I would love to know what these are!
- sangel 4y agoThey are called PIR with sublinear online computation or offline/online PIR. Key idea is the client issues a query that is independent of what they really want. This is the “offline” query. This query is linear (unavoidable) and the client gets some hints as a result Then later, the client can issue one or more queries for elements they want and those queries can be sublinear in terms of computation. The client uses hints to make that happen. Some papers on this are: https://eprint.iacr.org/2019/1075.pdf https://eprint.iacr.org/2019/1075.pdf https://eprint.iacr.org/2021/1438 https://eprint.iacr.org/2021/1438 https://eprint.iacr.org/2022/081.pdf https://eprint.iacr.org/2022/081.pdf
- blintz 4y agoSure! This paper has people really excited from a theoretical standpoint: https://eprint.iacr.org/2022/081.pdf https://eprint.iacr.org/2022/081.pdf. It’s a bit far from practical for single-server, but I’m sure people are working on it.