[ArVID220u]

Scaling is definitely why this hasn't been done before — it is hard! Recent research in private information retrieval shows that we can do it for 1 million people (see e.g. https://www.usenix.org/conference/osdi21/presentation/ahmad and https://www.cs.utexas.edu/~dwu4/spiral.html). All of the recent advances still scale as n^2 with the number of users, which becomes prohibitive after 1 million people, but we are working on a paper that shows how we can scale subquadratically (n^{1+1/k}*c^k for a fixed c and any k). With an n^1.33 scheme, 1 billion people suddenly becomes feasible.