Make sure to not do it automatically, but on user interaction (like new Safari password fills). Otherwise you leak usernames and tie them to browser sessions which can be fingerprinted.
I think this is addressed by the use of k-anonymity which is described in the section of the article titled “Enabling Anonymous Searches with k-Anonymity”.