> What stops the feds from brute-force querying the whole database?

What if the encryption was such that it took a computer ~ five minutes to decrypt the name?

That’s still a speed up over the current system, but makes brute forcing impractical as decrypting 100 million records would take about a thousand years of compute. It would also enable auditing of who is doing the decrypting and who is being decrypted.