В 1978 г. Рабин предложил следующий способ подписи. Пусть E - функция шифрования некоторой криптосистемы, (k_i, 1 <= i <= 2r) - последовательность случайно выбранных ключей, которые отправитель A держит в секрете. Пользователь B получает список параметров проверки (X_i,U_i) (1 <= i <= 2r), где

E(X_i,k_i) = U_i (1 <= i <= 2r).

Эти параметры хранятся в доступном для всех месте.

Предположим, что A хочет подписать сообщение m. Его подписью будет цепочка S = S₁S₂..S_2r, для каждого i (1<=i<=2r) S_i =E(m,k_i). B делает следующее. Сначала он выбирает случайным образом r ключей, которые A должен ему предъявить: k_i1 , k_i2 ,..,k_ir. При получении этих ключей от A он проверяет:

E(m,k_i1) = S_i1, E(X_i1,k_i1) = U_i1

и далее для всех индексов i₂, i₃ ,.., i_r . Он считает действительной подпись от A только в том случае, когда выдерживаются все проверки. Безопасность получателя зависит от его уверенности в том, что только отправитель, знающий секретный ключ, может послать так подписанное сообщение. Что касается A, то предположим, что он отказывается от сообщения, которое по утверждению B он подписал. Тогда протокол для A следующий: он должен предъявить судье свои секретные ключи k₁,k₂,..,k_2r, и в присутствии обеих сторон делается 2r проверок:

E(m,k_i)=S_i, E(X_i,k_i)=U_i.

Рассмотрим, что это означает в трех возможных случаях.

1. Корректными являются менее r проверок. Тогда B не должен был принимать подписанное сообщение.
2. Выдерживается точно r проверок, то есть при формировании ключей B выбрал именно это подмножество из r ключей. Вероятность, что он угадает это подмножество, равна
   p_r = (C_2r ^r)^-1,
   для r=18, p_r примерно равно 10^-10.
3. Выдерживается r+1 и более проверок: отказ абонента A не принимается.