Рейтинг:1

Схема ZK на основе Шнорра

флаг cn

TL;DR: Это АБСОЛЮТНО не работает и представляет огромный риск для безопасности.В любом случае публикую это на случай, если есть другие угрозы, которые я пропустил, или чтобы отговорить любого другого человека, которому придет в голову эта идея.

Привет! Я новичок в криптографии. Я начинаю рисковать схемами ZK. Для своего небольшого проекта, с помощью которого я намерен применить на практике то, что я узнал до сих пор, я придумал протокол, и я хотел бы знать, хорош ли он (т. е. безопасный, действительно неинтерактивный и ZK , и т.д). Это в значительной степени повторное использование протокола построения и проверки подписи Шнорра.

Настраивать

  • Игроки Алиса, Боб и Толпа людей.
  • Все игроки договариваются об использовании криптографически стойкой циклической подгруппы некоторой эллиптической кривой с генератором $G$.
  • У Боба есть пара открытый/закрытый ключ ($b$,$B=bG$).

Задача

Алиса имеет секрет $s$, к чему она публично заявляет, объявив $S$ (построен как $S=sG$).

Боб хочет доказать любому члену Толпы, что он знает $s$, но ничего не раскрывая о $s$ (ЗК). Кроме того, он хочет, чтобы его доказательство было неинтерактивным и могло использоваться повторно любым скептиком из толпы.

Протокол

  1. Алиса публично объявляет $S$.
  2. Боб утверждает, что знает $s$ и представляет доказательство $p=s-b$.
  3. Толпа принимает это как действительное доказательство, если и только если $pG+B=S$.

Обоснование

  1. Чтобы Боб мог построить правильный $p=s-b$ по желанию он обязан знать $s$. Он знает, что проверка включает удаление $-b$ часть, так что не зная $s$ значит не в состоянии закончить $S$ в конце.
  2. Боб не выдает никакой информации о $s$ потому что он маскируется добавлением с $-b$. Поскольку никто другой не знает $b$, он по существу равномерно рандомизирует значения.
  3. Толпа знает, что Боб на самом деле знает, потому что для создания доказательства нужно знать $b$ а также $s$ по аналогичному принципу с первым пунктом. Если бы кто-то знал $s$ но нет $b$, они не смогли вычесть правильную сумму $-b$ который восстанавливается в процессе проверки, и конечный результат этого не будет $S$.

Вопросы

  • Является ли это допустимой неинтерактивной схемой ZK?
  • Хороший ли он, если да?
  • Есть ли какие-либо преимущества использования zkSNARK по сравнению с такой схемой, с доказываемой функцией, например, что пользователь знает хэш слова и хеш слова, объединенного с их собственным открытым ключом?

Предупреждение

Это абсолютно не работает. Это очень рискованно, так как любой доказывающий (в данном случае Боб) может получить утечку своего секретного ключа: любой другой игрок, знающий $s$ (Алиса в этом случае и любой другой, кто получил $s$ любыми средствами) мог бы просто сделать $б = с - р$. В схеме подписи Шнорра есть фактор, сопровождающий $b$. Но этот фактор общеизвестен, так как он используется в протоколе проверки и поэтому не защищает $b$ в таком случае. Ключевой вывод, который я рад усвоить в качестве урока, заключается в том, что в протоколе Шнорра крайне важно соблюдать $к$ Безопасно.

knaccc avatar
флаг es
Я предполагаю, что в части вашего вопроса о zkSNARKs «слово» - это секрет $s$? Если это слово, то его нельзя квалифицировать как высокоэнтропийное. Я не уверен, как это поможет доказать не только знание хэша $s$, но и хеш $s$, объединенный с открытым ключом Боба $B$. zkSNARK намного сложнее, поэтому эта часть вашего вопроса, вероятно, заслуживает другого вопроса о crypto.stackexchange, если вы хотите изучить его более подробно.
флаг cn
Да, это не слово, это высокоэнтропийный секрет (может быть, и слово, но смешанное с достаточно высокоэнтропийным одноразовым номером). Причина привлечения B к доказательству заключается в том, что я хочу, чтобы доказательство было уникальным для Боба, чтобы ни один сторонний Чарли не мог также утверждать, что знает ответ с таким же доказательством. Но, конечно, я еще немного подумаю и задам правильный отдельный вопрос, которого он заслуживает :)
knaccc avatar
флаг es
Если я правильно понимаю ваш вариант использования, то на всякий случай это не очевидно: Боб может просто предоставить любую обычную подпись для открытого ключа $S$ в сообщении, которое включает личность Боба или открытый ключ. Это предотвратило бы повторное использование подписи другой стороной, которая также хотела бы заявить о знании $s$.
флаг cn
Я не знаю, полностью ли я понял, как вы говорите, что можете избежать повторного использования доказательства. Однако я также пытаюсь минимизировать размер полного доказательства. Идея состоит в том, чтобы иметь это в блокчейне, поэтому проверка правильного доказательства zkSNARK дешевле, чем доказательство zkSNARK + подпись. Я действительно не возражаю против усложнения доказываемой функции zkSNARK.
knaccc avatar
флаг es
Тип доказательства, который вы указали в исходном вопросе, привяжет доказательство к открытому ключу Боба. Однако для метода, упомянутого в только что сделанном мной комментарии, обычная подпись не будет связывать доказательство с Бобом как автором, если вы также не включите личность Боба как часть подписываемого сообщения.Поэтому я говорю, что вы можете избежать необходимости создавать какой-либо пользовательский механизм подписи, а вместо этого просто использовать обычные подписи для открытого ключа S и включать личность Боба в сообщение, чтобы предотвратить копирование подписи кем-то еще в качестве доказательства. они также знают $s$.
флаг cn
Я не понимаю, как вы предлагаете Бобу доказать знание $s$ способом привязки к его открытому ключу, просто подписав что-то, связанное с $S$. Я понимаю, что такие схемы, как подписи Шнорра, в этом случае связывают подпись с Бобом, потому что протокол доказательства и проверки использует H(m|B). Однако в этом случае, что именно подписывает Боб, чтобы показать, что он знает секрет? Извините, если это просто, и я пропустил это
knaccc avatar
флаг es
Допустим, Боб подписывает пустое сообщение, используя знание $s$. Ева может просто скопировать и вставить эту подпись и заявить, что именно она продемонстрировала знание $s$. Но если Боб подписывает сообщение «Это Боб, мой открытый ключ 01234…», используя закрытый ключ $s$, то Ева не может утверждать, что оно исходит от нее. Весь смысл подписи в том, что сообщение не поддается изменению.
флаг cn
Ага, понятно. Я понимаю, я просто не могу придумать содержание сообщения для подписи, которое показывает знание $s$ без утечки информации о нем.
knaccc avatar
флаг es
Правильно, вы не можете поместить $s$ в сообщение. Вместо этого вы создаете обычную подпись и подписываетесь так, как если бы вы были человеком, чей открытый ключ был $S$, и это доказывает знание $s$. Но затем внутри сообщения вы включаете свою настоящую личность $B$.
флаг cn
Супер, теперь понял! Используйте подпись Шнорра с S в качестве подписавшего (Боб знает $s$) и B в качестве сообщения (без повторного использования, привязывает доказательство к Бобу). Это чисто! Спасибо
Рейтинг:0
флаг es

Рассмотрим эквивалентный вариант обычной подписи Шнорра, которой подписывается сообщение $м$. Я предполагаю, что $s$ является достаточно высокоэнтропийным секретом, и поэтому $S$ не может быть грубой силой.

Подпись будет пара $(B=bG,\ p=c\cdot s-b)$. Это можно было бы проверить, проверив, что $B\overset{?}{=}cS-pG$, куда $c = H(B \mathbin\| m)$.

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

Таким образом, у вас есть пара $(B=bG,\ p=s-b)$, а проверка $pG\overset{?}{=}S-B$.

Задача также была частью эвристики Fiat-Shamir, которая предотвратила $В$ от расчета после соревнование $с$ был выбран. Поэтому возникает проблема, если Боб может объявить свой открытый ключ $В$ после $S$ было объявлено. Боб мог просто выбрать случайный $р$ стоимость, определить $B=S-pG$, и заявить, что его открытый ключ $В$. Это можно решить двумя способами: 1. Боб должен объявить $В$ до $S$ объявляется. 2. Боб должен предоставить подпись, подтверждающую знание $b$ такой, что $B\overset{?}{=}bG$.

Предположим, что открытый ключ Боба был объявлен до $S$ будучи объявленным, у вас есть действительный способ доказать знание $s$. Как вы указали, Алиса может тривиально узнать закрытый ключ Боба. $b$. Следовательно, это не соответствует определению нулевого знания, которое требует «без раскрытия самой информации или любая дополнительная информация".

Таким образом, ваша конструкция аналогична по определению "подпись адаптера", потому что "схема подписи адаптера может аутентифицировать сообщения, но одновременно раскрывает секрет определенным сторонам". Ваша схема не подписывает сообщения, но подтверждает знание $s$ при достоверной утечке $b$ Алисе.

Обратите внимание, что также могут быть проблемы с вашей схемой, где есть второй секрет. $s'$, и почему-то $s'-s$ становится известным.

флаг cn
Это было очень тщательно, спасибо! 1) В пункте 2 должна быть подпись (B, p=c.s-b) вместо этого? В любом случае, в свою схему я не включил этот фактор, потому что меня интересует только доказательство знаний, а не подписание. 2) Очень понравился второй вектор атаки с объявлением Б после С.В моем случае это не было бы проблемой, потому что игроки взаимодействуют таким образом, что им необходимо знать свои закрытые ключи. Но я нашел это очень умным! 3) Спасибо за информацию о подписи адаптера, обязательно посмотрю!
knaccc avatar
флаг es
@GastonMaffei ой, да, спасибо, я забыл $c$. Я изменил ответ.

Ответить или комментировать

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