Рейтинг:4

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

флаг mx

Свойство Groth16 (https://eprint.iacr.org/2016/260, стр. 8) неинтерактивный аргумент с нулевым разглашением основан на существовании симулятора $\text{Сима}$ создание «поддельных» доказательств для действительных утверждений $(\фи, ш) \в R$ без ведома свидетеля $w$ для заявления $\фи$.

У меня вопрос, существует ли для Groth16 симулятор $\text{Сим}'$ генерировать «фальшивые» доказательства для недействителен заявления $\фи'$, для которого нет свидетелей $w'$ с $(\фи', ш') \in R$ существуют. Формально удовлетворяет ли Groth16 следующему понятию?

Поддельное нулевое знание: Для всех $\lambda \in \mathbb{N}, (R, z) \gets \mathcal{R}(1^\lambda), (\phi, w) \in R$, все $\фи'$, и все противники $\mathcal{А}$: $Pr[(\sigma, \tau) \gets \text{Setup}(R); \pi \gets \text{Докажите}(R, \sigma, \phi, w): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1] = Pr[(\sigma, \tau) \gets\text{Setup}(R); \pi \gets \text{Sim}'(R, \tau, \phi'): \mathcal{A}(R, z, \sigma, \tau, \pi) = 1]$

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

(Я пытаюсь сконструировать доказательство безопасности, где создание таких поддельных доказательств кажется необходимым. Я никогда не видел приведенного выше понятия, но мне кажется, что $\text{Сим}'$ должны существовать для некоторых схем.)

Рейтинг:3
флаг cn

«Фальшивое нулевое знание» всегда следует из сочетания двух свойств:

  • Стандартное нулевое разглашение: существует Сим-симулятор, который может генерировать доказательства (неотличимые от честных доказательств) для действительных утверждений, и

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

Комбинация вышеизложенного дает «правильное» понятие «фальшивого нулевого разглашения»: выборка истинного утверждения и построение для него честного NIZK неотличимы от выборки ложного утверждения и имитации для него NIZK.

Примечание 1

Понятие фальшивого нулевого знания в вашем вопросе другое (оно не ссылается на алгоритм выборки для языка): вы говорите, что для Любые истинное утверждение $(\фи, ш)$ и Любые ложное заявление $\фи'$, честные НИЗКи с $(\фи,ш)$ должны быть неотличимы от моделируемых НИЗК с $\фи'$. Это слишком сильно, и это никогда не удержится. Причина в том, что алгоритм атаки $\mathcal{А}$ может иметь $\фи, \фи'$ жестко запрограммированы в его описании (поскольку свойство для всех $\фи,\фи'$ и все противники $\mathcal{А}$) а можно просто попробовать алгоритм проверки на НИЗК. Теперь, поскольку алгоритм проверки принимает $\фи$ (или же $\фи'$) в качестве входных данных, противник всегда будет различать две ситуации (если проверка пройдет с $\фи'$, это было поддельное доказательство, иначе это было настоящее доказательство; обратите внимание, что в силу достоверности проверка реального доказательства, сгенерированного честным доказывающим, не может быть успешной в отношении недействительного утверждения. $\фи'$, поэтому только что описанная различительная атака сработает с подавляющей вероятностью).

Заметка 2

Жесткое членство в подмножестве необходимо для «фальшивого нулевого разглашения»: если нетрудно отличить истинные утверждения от неправильных, мы не можем сформулировать какое-либо полезное и нетривиальное понятие фальшивого нулевого разглашения. Но это верно для большинства интересующих криптографических языков — обычно мы заинтересованы в создании NIZK для утверждений, которые верификатор все равно не смог бы проверить самостоятельно.

Anakin Charles avatar
флаг mx
Спасибо, я понимаю, почему моя предложенная идея слишком сильна. Как вы говорите, «всегда следует»: есть ли ссылка, показывающая, что стандартное-zk + жесткое-подмножество-членство позволяет моделировать доказательства поддельных утверждений?
Geoffroy Couteau avatar
флаг cn
Я не могу придумать стандартную ссылку на макушку, это скорее прямое наблюдение фольклора. Если вы напишете определение жесткого членства в подмножестве и нулевого знания, то сразу последует «фальшивое нулевое знание», последовательно применяя и то, и другое: начните с честного доказательства истинного утверждения, сначала примените нулевое знание, чтобы заменить доказывающего симулятором, затем примените жесткое членство в подмножестве, чтобы неразличимо переключить истинное утверждение на ложное утверждение (что можно сделать на этом этапе, потому что Sim не требует свидетеля).
Anakin Charles avatar
флаг mx
Я понимаю. Да, такое доказательство игрового перехода должно быть легко построено. Спасибо!

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

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