WikiDer > Эвристика Fiat – Shamir - Википедия

В криптография, то Эвристика Fiat – Shamir это техника принятия интерактивное подтверждение знаний и создание цифровой подписи на его основе. Таким образом, некоторый факт (например, знание определенного секретного числа) может быть публично доказан без раскрытия основной информации. Техника из-за Амос Фиат и Ади Шамир (1986).^[1]Чтобы метод работал, оригинальное интерактивное доказательство должно иметь свойство быть публичная монета, т.е. случайные монеты проверяющего публикуются на протяжении всего протокола доказательства.

Первоначально эвристика была представлена ​​без доказательства безопасности; потом, Pointcheval и Штерн^[2] доказал свою безопасность против выбранные сообщения атак в случайная модель оракула, то есть в предположении случайные оракулы существовать. Этот результат был обобщен на квантово-доступный случайный оракул (QROM) Дона, Фер, Маженца и Шаффнера,^[3] и одновременно Лю и Чжандри.^[4] В случае, когда случайных оракулов не существует, эвристика Фиата – Шамира оказалась небезопасной. Шафи Гольдвассер и Яэль Тауман Калаи.^[5] Таким образом, эвристика Fiat – Shamir демонстрирует широкое применение случайных оракулов. В более общем плане эвристика Фиат-Шамира может также рассматриваться как преобразование интерактивного доказательства знаний публичной монеты в неинтерактивное доказательство знаний. Если интерактивное доказательство используется в качестве инструмента идентификации, то неинтерактивная версия может использоваться непосредственно как цифровая подпись, используя сообщение как часть входных данных случайному оракулу.

Пример

Для указанного ниже алгоритма читатели должны быть знакомы с законами модульная арифметика, особенно с мультипликативные группы целых чисел по модулю n с премьер п.

Вот интерактивный доказательство знания дискретного логарифма.^[6]

1. Пегги хочет доказать Виктору проверяющему, что она знает ${ displaystyle x}$: дискретный логарифм ${ Displaystyle у = г ^ {х}}$ к базе ${ displaystyle g}$ (мод п).
2. Она выбирает случайный ${ displaystyle v in mathbb {Z} _ {q} ^ {*}}$, вычисляет ${ Displaystyle т = г ^ {v}}$ и отправляет ${ displaystyle t}$ Виктору.
3. Виктор выбирает случайный ${ displaystyle c in mathbb {Z} _ {q} ^ {*}}$ и отправляет его Пегги.
4. Пегги вычисляет ${ displaystyle r = v-cx}$ и возвращается ${ displaystyle r}$ Виктору.
5. Он проверяет, есть ли ${ Displaystyle т эквив г ^ {г} у ^ {с}}$. Это так, потому что ${ displaystyle g ^ {r} y ^ {c} = g ^ {v-cx} g ^ {xc} = g ^ {v} = t}$.

Эвристика Fiat – Shamir позволяет заменить интерактивный шаг 3 на не интерактивный случайный оракул доступ. На практике мы можем использовать криптографическая хеш-функция вместо.^[7]

1. Пегги хочет доказать, что знает ${ displaystyle x}$: дискретный логарифм ${ Displaystyle у = г ^ {х}}$ к базе ${ displaystyle g}$.
2. Она выбирает случайный ${ displaystyle v in mathbb {Z} _ {q} ^ {*}}$ и вычисляет ${ Displaystyle т = г ^ {v}}$.
3. Пегги вычисляет ${ Displaystyle с = Н (г, у, т)}$, куда ${ displaystyle H ()}$ - криптографическая хеш-функция.
4. Она вычисляет ${ displaystyle r = v-cx}$. Полученное доказательство - это пара ${ Displaystyle (т, г)}$. В качестве ${ displaystyle r}$ является показателем ${ displaystyle g}$, рассчитывается по модулю ${ displaystyle q-1}$, не по модулю ${ displaystyle q}$.
5. Кто угодно может использовать это доказательство для вычисления ${ displaystyle c}$ и проверьте, есть ли ${ Displaystyle т эквив г ^ {г} у ^ {с}}$.

Если хеш-значение, используемое ниже, не зависит от (общедоступного) значения у, безопасность схемы снижается, поскольку злоумышленник может затем выбрать определенное значение Икс так что продукт сх известен.^[8]

Расширение этого метода

Пока фиксированный генератор случайных чисел может быть сконструирован с данными, известными обеим сторонам, любой интерактивный протокол может быть преобразован в неинтерактивный.^{[нужна цитата]}

Смотрите также

• Случайная модель оракула
• Неинтерактивное доказательство с нулевым разглашением
• приложение в анонимная сеть вето
• Лемма о разветвлении

Рекомендации