Пусть $(\mathcal G,\mathcal S,\mathcal V)$ — протокол электронной подписи. Пусть также $n\in\mathbb N$ — параметр стойкости. Тогда $w\in\{0,1\}^*$ называется допустимой подписью для сообщения $m$ относительно открытого ключа $v$, если всегда выполняется равенство $\mathcal V(1^n,v,m,w)=1$ (означающее, что подпись принята). См. также протокол электронной подписи.