> Citation needed. [0] shows that o(N) lookups are impossible in general with only O(N) space in any private information retrieval scheme. That admittedly does

> Citation needed. [0] shows that o(N) lookups are impossible in general with only O(N) space in any private information retrieval scheme. That admittedly doesn't show that O(log n) lookups are impossible, but it's a similar result. The improvements I'm aware of include (1) storing some extra information, (2) splitting the query into multiple phases to move the bulk of the Ω(N) cost out of the hot path, and (3) reframing the problem (an actual database lookup can't be improved, but similar constructions might still satisfy the end goal, or if you're using a hashmap as a sub-component then the composite algorithm might still be made efficient by never computing those expensive intermediates). [0] https://link.springer.com/content/pdf/10.1007/s00145-004-0134-y.pdf https://link.springer.com/content/pdf/10.1007/s00145-004-013...