Алгоритмы с открытыми ключами также могут использоваться в протоколах строгой аутентификации. В этом случае доказывающий может продемонстрировать знание секретного ключа одним из следующих способов:

- расшифровать запрос, зашифрованный на открытом ключе;

- подписать запрос проверяющего.

Пара ключей, необходимая для аутентификации, по соображениям безопасности не должна использоваться для других целей (например, для шифрования). Здесь следует предостеречь читателей - выбранная система с открытым ключом должна быть устойчивой к атакам с выборкой зашифрованного текста далее в том случае, если нарушитель попытается получить критичную информацию, выдав себя за проверяющего и действуя от его имени.