Протоколы аутентификации, обладающие свойством доказательства с нулевым знанием
Одна из уязвимостей протоколов простой аутентификации заключается в том, что после того, как доказывающий передаст проверяющему свой пароль, проверяющий может, используя данный пароль, выдать себя за проверяемого, Немногим лучше обстоит дело с протоколами строгой аутентификации. Дело в том, что А, отвечая на запросы В, обязан продемонстрировать знание секретного ключа, пусть даже и одноразово; при этом передаваемая информация не может быть напрямую использована В. Тем не менее некоторая ее часть поможет В получить дополнительную информацию о секрете А. Например, В имеет возможность так сформировать запросы, чтобы передаваемые ответы анализировались на предмет содержания дополнительной информации.
Протоколы доказательства с нулевым знанием были разработаны специально для решения данной проблемы. Этой цели можно добиться при помощи демонстрации знания секрета, однако проверяющий должен быть лишен возможности получать дополнительную информацию о секрете доказывающего. Если сформулировать эту мысль в более строгой форме, то протоколы доказательства с нулевым знанием (далее - ZK-протоколы) позволяют установить истинность утверждения и при этом не передавать какой-либо дополнительной информации о самом утверждении.
ZK-протоколы являются примером систем интерактивного доказательства, в которых проверяющий и доказывающий обмениваются многочисленными запросами и ответами, обычно зависящими от случайных чисел (в идеальном случае зависимость может реализовываться в виде подбрасывания монеты), которые позволяют сохранить секрет в тайне. Цель доказывающего - убедить проверяющего в истинности утверждения. Проверяющий же принимает или отклоняет доказательство. Необходимо отметить, что доказательство носит скорее вероятностный, нелсели абсолютный характер.
Интерактивное доказательство, использующееся для идентификации, может быть сформулировано как доказательство знания. А владеет некоторым секретом s и с помощью последовательных ответов на вопросы (при наличии согласованных входных данных и функций) пытается убедить В в знании s. Заметим, что доказательство знания s отличается от доказательства того факта, что s существует. Например, доказательство знания простых множителей п (основания в RSA) отличается от доказательства того, что п является составным. Интерактивное доказательство может быть названо доказательством знания в том случае, если выполнены свойства стойкости и целостности.
Интерактивный протокол обладает свойством целостности, если только доверенные стороны смогут успешно закончить протокол (когда проверяющий принимает доказательство).
Интерактивный протокол является стойким при условии, что не существует алгоритма М, работающего за полиномиальное время и обладающего следующим свойством: если злоумышленник, пытающийся выдать себя за А, может с малой вероятностью успешно закончить протокол с участником В, тогда М в ходе работы протокола может использоваться для получения дополнительных знаний о секрете А, которые с высокой вероятностью позволяют успешно выполнить некоторые шаги протокола (в худшем случае весь протокол).
Несмотря на то что в основе построения ZK-протоколов лежат те же математические идеи, что и в протоколах, построенных на открытой криптографии, между ними есть некоторые отличия. Прежде всего они касаются:
• уменьшения эффективности в ходе использования. Протоколы доказательства с нулевым знанием не уменьшают свою эффективность даже при повторных передачах и соответственно являются стойкими к атаке с выборкой открытого текста. Данное свойство в некоторых случаях позволяет предпочесть использование ZK-протоколов;
• использования шифрования. Многие ZK-протоколы поволяют избегать употребления шифрования явным образом, что дает несомненные преимущества, например в случае экспортных ограничений;
• эффективности. Коммуникационная и вычислительная эффективность в ZK-протоколах основана прежде всего на том факте, что они по своей природе являются интерактивными протоколами доказательства.
Среди сходств данных протоколов можно отметить следующие:
• наличие недоказумых предположений. ZK-протоколы, так же как и протоколы, основанные на открытой криптографии, напрямую используют недоказуемые предположения (например, доказуемая стойкость к факторизации);
• доказуемость обладания свойством ZK. На практике достаточно сложно доказать наличие данного свойства у протокола.
Для практического рассмотрения концепции построения протоколов, обладающих свойством ZK, приведем оригинальную версию протокола Фиата и Шамира (Fiat-Shamir). Целью данного протокола является демонстрация знания секрета s доказывающей стороной, при этом информация о самом секрете не раскрывается проверяющему и он не имеет предварительно распределенных сведений. Безопасность протокола основана на сложности извлечения квадратного корня по модулю п (имеет то же значение, что и в RSA), не зная разложения п. Опишем общую структуру протоколов данного класса: А доказывает знание секрета s В при помощи t-шагов по три сообщения в каждом.