ТЛ, ДР: союз простых $\Сигма$-протоколы могут доказать это составное утверждение с нулевым разглашением. Однако доказательство несколько велико.
Во-первых, давайте разобьем ваше составное утверждение на более простые утверждения. Обратите внимание, что по существу вы хотите доказать с нулевым разглашением для $C_1=м^е$ и $C_2=г^м$ что следующее соотношение $\mathcal{R}(x,\omega)$ ($х$ является общедоступным параметром и $\омега$ является свидетелем) содержит: $$\mathcal{R}=\{((C_1,C_2),(m,l)):m\in QR_{N}\land C_1=m^e\bmod{N}\land C_2=g^m \bmod{p}\},$$
куда $л$ это квадратный корень из $м\bmod{N}$, то есть свидетелем является $(м,л)$ пара. Для простоты будем использовать следующие обозначения для элементарных утверждений: $$\mathcal{R}_1=\{((C_1,C_2),(m,l)):m\in QR_{N}\},$$
$$\mathcal{R}_2=\{((C_1,C_2),(m,l)): C_1=m^e\bmod{N}\},$$
$$\mathcal{R}_3=\{((C_1,C_2),(m,l)):C_2=g^m\bmod{p}\}. $$
Обратите внимание, что оба элементарных оператора $\mathcal{R}_2$ и $\mathcal{R}_3$ легко доказать с помощью $\Сигма$-протоколов, так как оба соотношения доказывают знание прообраза при гомоморфизме групп (т.е. $w$ удовлетворяющий $х=\фи(ш)$). В случае $\mathcal{R}_2$ групповой гомоморфизм $\фи(\омега)=\омега^е$, пока в $\mathcal{R}_3$, гомоморфизм $\фи(\омега)=г^{\омега}$. Это вполне стандартные утверждения, и вы можете найти, как доказать прообраз гомоморфизма в Бангертер и др. или в Книга Боне-Шоупа, среди многих других.
Чтобы доказать $\mathcal{R}_1$ немного сложно на первый взгляд, так как $м$ должно храниться в секрете, и мы хотим доказать, что $м$ является квадратичным вычетом, т. е. $м\в QR_N$. Почти во всех развертываниях криптосистемы RSA $е$ нечетно (я предполагаю, что это также имеет место в вашем приложении), поэтому $C_1=m^e\in QR_{N} \ тогда и только тогда, когда m\in QR_{N}$. Я также предполагаю, что шифровальщик знает $л$, один из квадратных корней $м$, так как факторизация неизвестна. Если шифровальщик не знает такого $л$, то он не может доказать, что это квадратичный вычет, потому что он не знает факторизации. Учитывая это обсуждение, теперь $\mathcal{R}_1$ по существу влечет за собой доказательство следующего утверждения: $$\mathcal{R}_1=\{((C_1),(l)):C_1=l^{2e}\bmod{N}\},$$
что снова является доказательством знания прообраза гомоморфизма групп. Мы знаем, как доказать это утверждение.
Чтобы объединить все это, чтобы получить доказательство с нулевым разглашением для составного утверждения $\mathcal{R}$, верификатору просто нужно отправить один и тот же случайный вызов для всех элементарных операторов (хотя случайный запрос отличается при повторении протокола!).
Каков размер доказательства? За $\Сигма$-протоколы в группах неизвестного порядка, погрешность корректности велика, поэтому нужно повторять $\Сигма$-протокол много раз, чтобы получить разумные уровни надежности. В каждом повторении ошибка правильности уменьшается на $\примерно 1/2$. Следовательно, протокол должен повторяться последовательно, чтобы получить достаточно малую ошибку знания (например, $80$ требуются последовательные повторения, чтобы получить ошибку знания $1/2^{80}$). Это привело бы к доказательству, состоящему из $2*2*80=320$ групповые элементы для $3$ элементарные операторы (2 оператора встречаются в группе RSA, поэтому нам нужно повторять много раз).
Чтобы обойти это ограничение эффективности, вам нужно использовать общую ссылочную строку, чтобы уменьшить размер доказательства. Видеть Бангертер и др.
Надеюсь, это поможет! Дайте мне знать, если я оставил какую-либо серую область в ответе!
