Что означает для g и h быть независимыми в обязательствах Педерсена?

я смотрю на Научно-исследовательская работа о небезопасности конкретного (неправильного) использования обязательств Педерсена.

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

Мое понимание обязательств Pedersen

Во-первых, мы говорим, что Боб хочет, чтобы Алиса зафиксировала сообщение, поэтому он генерирует два простых числа. п и д.

p <--- случайное простое число q <--- случайное простое число

Затем Боб генерирует генератор г, что имеет порядок д и есть в группе $Z_{p}^*$.

г <--- $\in Z_{q}^*$

Затем он выбирает секретное значение Икс в $Z_{q} $:

х <--- $\in Z_{q} $

x — это секретный ключ, который он использует для получения открытого ключа:

$h = g^{x} по модулю p $

Теперь Алиса хочет зафиксировать конкретное сообщение и имеет доступ к открытому и секретному ключу Боба. Она первая выбирает сообщение м и случайное целое р, а затем вычисляет ее обязательство с:

с = $ г ^ {м} * ч ^ {г} $

Теперь Алиса может отправить обязательство Бобу. Когда Алиса хочет показать свое обязательство, она отправляет м и `r``к Бобу. Теперь Боб может выполнить те же вычисления и сравнить.

Применение в голосовании и вопрос о независимости

В упомянутой ранее статье схема используется для подтверждения целостности набора перетасованных голосов. В этом контексте список н зашифрованные голоса обозначаются $ m_{1},...,m_{n} $. Обязательство Педерсена для списка голосов затем вычисляется следующим образом:

$ c = G_{1}^{m_1} ... G_{n}^{m_n} * H^{r}$

А потом в газете так говорится о ценностях г и ЧАС (может быть некоторая путаница в обозначениях, так как я привык использовать строчные g и h для генератора для генератора и PK, в то время как в статье используются заглавные буквы). Но затем в документе указывается следующая проблема, которая может возникнуть:

«Если нарушается независимость между H и одним единственным значением Gi, то расширенное обязательство c может быть открыто для любого вектора альтернативных сообщений m²1,..., m²n. Если это произойдет, то весь аргумент доказательства перетасовки рухнет. , т. е. можно построить ложное доказательство неправильной тасовки».

Я немного смущен тем, что это значит для значений $G_{я}$ и H быть «независимыми», и что это, вероятно, означает, когда у нас есть несколько версий г, поэтому у меня два вопроса:

1

если у нас есть n G, значит ли это, что группа, в которой мы работаем, должна иметь n генераторов?

2 Как может быть один Н, а образующих несколько? если ЧАС вычисляется с использованием г, то какой г используется для вычисления открытого ключа ЧАС. Может быть, я неправильно понимаю что-то основное в конструкции, изложенной в документе?

Я немного смущен тем, что это значит для значений $G_i$ и $Ч$ быть «независимым»,

Собственно, в статье дано довольно приличное определение:

Независимость означает, что соответствующие дискретные логарифмы $ч = \log_G Ч$ и $g = \log_HG$ всем неизвестны.

То есть никто не должен знать решения $х$ к $ G ^ х = Н $

Однако, поскольку мы работаем с несколькими генераторами, оказывается, что нам нужно более сильное утверждение: никто не знает нетривиального решения. $(а_1, а_2, ..., а_n, б)$ для отношения $G_1^{a_1} \cdot G_2^{a_2} \cdot ... \cdot G_n^{a_n} \cdot H^b = 1$, где тривиальное решение $a_1 \equiv a_2 \equiv ... \equiv a_n \equiv b \equiv 0$.

Однако применима та же идея.

если у нас есть $n$ $G$, значит ли это, что группа, в которой мы работаем, должна иметь $n$ генераторы?

Да. На самом деле их гораздо больше, если мы имеем дело с группой размером $q$ куда $q$ является простым, то будет $q-1$ генераторы. Потому что нам нужно $q$ быть не менее 256 бит (чтобы усложнить задачу дискретного журнала), это означает, что у нас есть огромный количество доступных нам генераторов.

Как может быть один $Ч$, и несколько генераторов? если $Ч$ вычисляется с использованием $G$,

На самом деле мы не вычисляем $Ч$ с использованием $G$, подбираем самостоятельно.

Теперь, если вы вернетесь к оригинальной статье Педерсена, он предложил верификатору выбрать $Ч$ (и, следовательно, может сделать этот выбор, выбрав случайное значение $ч$ и вычисления $Ч = Г^ч$, и давая $Ч$ (но нет $ч$) доказывающему); таким образом верификатор мог быть уверен, что проверяющий не знает дискретный журнал.

Однако в настоящее время мы производим $G$ и $Ч$ независимо (так что буквально никто не знает отношения) - этот подход, очевидно, распространяется на несколько $G$ ценности.