If the security depends on the person it's supposed to be secure against not trying to break it...

What about doing it all client side? Or perhaps let the user type one or two characters then fetch that from the server for all matches and do the remaining matching client side. There are ways you could truly isolate yourself from the PII.