Объяснение доказательств с нулевым разглашением. Часть 2. Неинтерактивные доказательства с нулевым разглашением.

Пример неинтерактивных доказательств с нулевым знанием: судоку и игральные карты


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

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

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

В этой части 2 мы рассмотрим неинтерактивные доказательства с нулевым знанием.

Неинтерактивные доказательства с нулевым разглашением

Причина неинтерактивных доказательств с нулевым знанием состоит в том, чтобы позволить большому количеству наблюдателей эффективно проверить доказательство.

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

Пример неинтерактивных доказательств с нулевым знанием: судоку и игральные карты

Судоку – игра с различной сложностью, но относительно простыми правилами. Каждый из 9 рядов, 9 столбцов и 9 секторов (как указано жирной черной линией) должен содержать каждое число от 1 до 9 ровно один раз.

Представьте себе, что решение головоломки судоку особенно трудно найти, и даже суперкомпьютер вычисляет дни, чтобы вычислить.

Но кто-то (доказатель) утверждает, что нашел решение головоломки и готов продать ее за определенную цену. Как они могут доказать, что у них есть решение – не раскрывая его, – так что проверяющий готов произвести оплату?

Доказательство:

Доказателю нужно 27 игральных карт (любой масти) всего 1-9—243.

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

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

Чтобы доказать, что все закрытые карты находятся в правильном положении (без раскрытия решения), проверяющий должен:

  • Возьмите верхнюю карту с каждого строка и сделать 9 груд
  • Возьмите верхнюю карту с каждого колонка и сделать 9 груд
  • Возьмите оставшиеся карты с каждого сектор и сделать 9 груд

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

Затем каждая куча перемешивается и переворачивается.

Каждое число от 1 до 9 должно появляться в каждой строке, столбце и секторе судоку. Таким образом, если каждая колода карт провайдера (из ряда, столбца и сектора секторов) содержит каждую игральную карту стоимостью 1-9, мы знаем, что у них должно быть решение.

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

Следует признать, что относительно молодая область доказательств с нулевым знанием еще не нашла признания, которого она может заслуживать. Однако они могут оказаться очень ценными.

Многие математические задачи похожи на головоломку судоку (например, задача раскраски графиков). Если мы сможем использовать вышеупомянутый принцип и успешно применить его к различным задачам, мы сможем более эффективно использовать вычислительные ресурсы и математические задачи и обмениваться ими. Или, возможно, решить математические проблемы быстрее.

Престижность Ронену Градволю, Мони Наору, Бенни Пинкасу и Гаю Ротблюму

Kim Martin Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map