Возможно, там k-анонимность применяется.

Я не знаю, как устроен конкретно этот сервис, но в менеджере паролей в Firefox она точно используется. При использовании k-анонимности, серверу передаётся лишь такая часть инфы, которая не позволяет идентифицировать пользователя, но зато позволяет локально на клиентской машине определить, есть ли почта пользователя в утечке. Я плохо объясню это своими словами - посмотрите, хотя бы, статью в англовики, а уже в ней есть ссылки на научные работы по теме.