4.3.3 Схемы, в которых подделка подписи может быть доказана

Пусть обозначает параметр безопасности, и  -- соответственно секретный и открытый ключи подписывающего, а и  -- алгоритмы генерации и проверки подписей соответственно (см. подраздел 4.6.1). Предположим, что некоторая одноразовая схема электронной подписи удовлетворяет следующим условиям (см. [HP]):     1. Для любых , и сообщения мощность множества всех секретных ключей , соответствующих и таких, что , экспоненциальна от . Кроме того, для любого сообщения при      пренебрежимо мала.

    2. Существует полиномиальный алгоритм, вычисляющий по , , сообщению и допустимой подписи для сообщения некоторую информацию, доказывающую, что подпись поддельная.

    3. Никакой полиномиально ограниченный подписывающий не может вычислить с не пренебрежимо малой вероятностью допустимую подпись для данного сообщения и информацию, доказывающую ее поддельность.

Неформально эти условия означают следующее. Если противник, имея открытый ключ законного подписывающего и его подпись для некоторого сообщения , каким-либо образом подделал подпись для другого сообщения (например, нашел некоторый секретный ключ , соответствующий , и вычислил ), то ввиду условия 1 эта поддельная подпись с большой вероятностью будет отличаться от подписи законного подписывающего. В этом случае законный подписывающий может доказать поддельность , воспользовавшись алгоритмом из условия 2. В поддельности могут убедиться также проверяющий или арбитр, получив от подписывающего его секретный ключ. Таким образом, условия 1 и 2 обеспечивают безопасность подписывающего, защищая его от действий противника (даже обладающего неограниченными вычислительными возможностями). Условие же 3 обеспечивает безопасность проверяющего, защищая его от действий нечестного подписывающего, который ввиду этого условия не может отказаться от своей подписи, сославшись на ее поддельность. Отметим, что безопасность подписывающего (доказуемость подделки) носит безусловный (теоретико-информационный) характер, а безопасность проверяющего -- теоретико-сложностной.

Схема электронной подписи, удовлетворяющая условиям 1-3, названа в работе ван Хейста и Педерсена [HP] схемой, останавливаемой при сбоях (fail-stop signature scheme). Название связано с тем, что подписывающий, обнаружив и доказав подделку подписи, может остановить использование схемы. Однако первая такая схема была предложена Вайднером и Пфитцман [WP], в более поздней работе которых вместе с Блоймером [BPW] она была названа схемой, в которой подделка подписи может быть доказана (scheme where forgery can be proved). Нам представляется, что второе название более точно отражает сущность этих схем.

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

Как уже отмечалось, первая схема электронной подписи, в которой подделка может быть доказана, предложена Вайднером и Пфитцман в [WP]. А именно, в этой работе было замечено, что схема Лампорта (см. п. 4.6.2.2) является таковой, если в ней функция удовлетворяет следующим условиям:     1) для некоторой (достаточно большой) константы и для любого имеет не менее прообразов;

    2) нахождение коллизий функции (т. е. таких пар , что и ) является вычислительно трудной задачей для подписывающего. Действительно, в этом случае легко проверить истинность условий 1-3 (в качестве информации, доказывающей поддельность подписи, выступает коллизия функции ). Авторы [WP] при некотором криптографическом предположении строят односторонние функции, удовлетворяющие условиям 1) и 2). Дальнейшее развитие этого подхода предлагается в работе Блоймера, Пфитцман и Вайднера [BPW].

Однако в вышеописанной схеме сообщения подписываются побитово, поэтому длина подписи очень велика. В работе ван Хейста и Педерсена [HP] предлагается более эффективная схема электронной подписи, в которой подделка может быть доказана. Приведем ее описание. Пусть и -- большие простые числа такие, что делит , а и  -- элементы порядка в группе . Предполагается, что , , и известны как подписывающему, так и проверяющему, но ни тому, ни другому не известен дискретный логарифм по основанию (т. е. такое , что ). Секретный ключ подписывающего имеет вид

     б) для любого сообщения и любой допустимой подписи для существует единственный секретный ключ , удовлетворяющий условию п. а) и такой, что ;

     в) если известны , и некоторая допустимая подпись для сообщения , то можно эффективно вычислить дискретный логарифм по основанию . Из этих утверждений легко вытекает истинность условий 1 и 2 (если и  -- случайный элемент, удовлетворяющий условию п. а), то ввиду а) и б), а в качестве информации, доказывающей поддельность подписи, выступает дискретный логарифм по основанию ). Условие же 3 будет истинным, если дискретные логарифмы в (единственной) подгруппе порядка группы вычисляются сложно.

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