Алгоритми з відкритими ключами також можуть використовуватися в протоколах строгої аутентифікації. У цьому випадку доводить може продемонструвати знання секретного ключа одним із таких способів:

- Розшифрувати запит, зашифрований на відкритому ключі;

- Підписати запит перевіряючого.

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