ФЭНДОМ


В криптографии Доказательство с нулевым разглашением (информации) (англ. Zero-knowledge proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, prover).

Доказательство с нулевым разглашением должно обладать тремя свойствами:

  1. Полнота: если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
  2. Корректность: если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
  3. Нулевое разглашение: если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.

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

Пример Править

Назовем проверяющую сторону Петей, а доказывающую сторону Димой (в англоязычной литературе обычно используются пары Alice и Bob). Допустим Диме известен Гамильтонов цикл в большом графе G. Пете известен граф G, но он не знает гамильтонова цикла в нем. Дима хочет доказать Пете, что он знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нем (возможно Петя хочет купить этот гамильтонов цикл у Димы, но перед этим удостовериться, что он у Димы действительно есть).

Для этого Петя и Дима совместно выполняют несколько раундов протокола:

  • Вначала Дима создает граф H, изоморфный G. Преобразовывание гамильтонов цикла между изоморфными графами - тривиальная задача, поэтому если Диме известен гамильтонов цикл в G, то он также знает гамильтонов цикл в H.
  • Дима передает граф H Пете.
  • Петя выбирает случайный бит b ← {0,1}
    • Если b=0, то Петя просит Диму доказать изоморфизм G u H, то есть предоставить соответствие вершин этих двух графов. Петя может проверить, действительно ли G u H изоморфны.
    • Если b=1, то Петя просит Диму показать гамильтонов цикл в H. Изоморфизм графов - NP-полная задача, поэтому будем здесь считать, что невозможно из гамильтонова цикла в H вычислить гамильтонов цикл в G.

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

Если же у Димы нету гамильтонова цикла в G и он хочет обмануть Петю, то Дима может в каждом раунде либо создать H изоморфный G, либо найти гамильтонов цикл к фальшивому графу H' . В таком случае вероятность того, что Дима все-таки обманет Петю после n раундов равна 1/2n, а это в криптографии считается пренебрежимо малой вероятностью.da:Vidensløst bevis de:Zero Knowledge en:Zero-knowledge proof fr:Preuve à divulgation nulle de connaissance ko:영지식 증명 he:הוכחה באפס ידע ja:ゼロ知識証明 pl:Dowód z wiedzą zerową

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики