Можно ли перепроектировать схему в zk-SNARK?

Мы неправильно поняли ваш вопрос, но схема не нуждалась в обратном проектировании. Это общеизвестно и передается верификатору в открытом виде. Однако в вашем примере x не будет частью описания схемы, это свидетель, то есть * вход * схемы.

Спасибо, @Maeher. Я имел в виду, что x не должен быть свидетелем, так как мы также не хотим, чтобы доказывающий знал x. Возможно ли получить доказательство, в котором никто не знает x, но может проверить, является ли HMAC(x, свидетель) = s?

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

Нет, zk-SNARK — это своего рода NIZK, который может гарантировать, что свидетель, например, секрет x, не будет раскрыт, кроме доказательства $\pi$ и утверждения s. Итак, для HMAC компилятор сначала преобразует его в арифметическую схему и, наконец, генерирует экземпляр QAP/QSP. Дуэт с QAP жесткий, потом трудно реверсировать, чтобы получить информацию свидетелей.

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

Вы имеете в виду, что доказывающий, у которого есть только пара подписей $(s, msg)$, но секретный ключ подписи $x$, должен просто доказать, что он/она владеет действительной подписью, сгенерированной из какой-то общедоступной схемы? Если это так, то это просто проверяемая вычислительная задача, а не задача с нулевым разглашением. Кроме того, ваш вопрос должен быть абстрактным: как доказать, что результат правильно сгенерирован из некоторой публичной функции? Публичную функцию можно рассматривать как HMAC($x, \cdot$), которую, безусловно, можно преобразовать в арифметическую схему. В этом случае злоумышленник, получивший схему, может легко изменить секретное значение $x$.

Правильно; `x` предназначен только для подтверждения права собственности на действительную подпись и не должен быть известен никому, кроме того, кто выдал подпись. Процесс подписания не является публичным, но проверка доступна. Таким образом, вопрос заключается в том, как провести публичную проверку подписи HMAC, не сообщая публике «x».

Если общедоступной функцией является $HMAC(k, x)$, где $k$ — фиксированный ключ, а $x$ — вход, то с помощью технологии zkSNARKs $HMAC(k, x)$ можно преобразовать в экземпляр QAP во-первых. Однако на этом этапе злоумышленник также может восстановить секретное значение $k$, если степень полиномов равна $poly(\cdot)$ размеру. Затем, поместив полиномы в основание экспоненты $g$, например, $g^{l_i(y)}$, где $y$ — случайное значение, это может сохранить $k$ в секрете из-за сложности задачи DL. Наконец, опубликуйте $vk$ и $ek$ как для доказывающего, так и для проверяющего.

Для доказывающего он может вычислить $s=HMAC(k,msg)$ и, следовательно, соответствующие значения переменных ${w_i}, i \in [n]$. Эти значения {$w_i$} можно рассматривать как свидетели. Следовательно, доказывающая выполняет алгоритм доказательства и выводит доказательство $\pi$ и ${s,msg}$ проверяющей стороне. Описанный выше процесс непроверен, особенно метод сохранения $k$ в секрете.

Этот вопрос на других языках: