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.
Nice idea, but do I need E2E to identify a song? Seems like a very low threat model for a malicious attacker to know my wife needs that Elton John song.