This is awesome but with a mere 1000-song database it would be simpler just to run the whole thing on the client. How well could the approach scale? (eg. To a billion song DB?)
Yes for now, it's 1000 song, which is already awesome if you think about it, no? As it's like 300 ms, one can increase the DB size by a few order of magnitude, certainly. It will scale to billions of songs thanks to hardware accelerators, which are coming. One can google and see that there is a bunch of companies (small or large) working on accelerating FHE computations.
If you have a Google Pixel phone running the stock OS, you already have this! https://support.google.com/pixelphone/answer/7535326?hl=en#z...