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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

^ Фиат, Амос; Шамир, Ади (1987). «Как проявить себя: практические решения проблем идентификации и подписи». Достижения в криптологии - CRYPTO '86. Конспект лекций по информатике. Springer Berlin Heidelberg. 263: 186–194. Дои:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.
^ Поинтшеваль, Дэвид; Стерн, Жак (1996). «Доказательства безопасности для схем подписи». Достижения в криптологии - EUROCRYPT '96. Конспект лекций по информатике. Springer Berlin Heidelberg. 1070: 387–398. Дои:10.1007/3-540-68339-9_33. ISBN 978-3-540-61186-8.
^ Дон, Джелле; Фер, Серж; Майенз, Кристиан; Шаффнер, Кристиан (2019). «Безопасность преобразования Фиат-Шамира в квантовой модели случайного оракула». Достижения в криптологии - CRYPTO '19. Конспект лекций по информатике. Springer Cham. 11693: 356–383. arXiv:1902.07556. Bibcode:2019arXiv190207556D. Дои:10.1007/978-3-030-26951-7_13. ISBN 978-3-030-26950-0.
^ Лю, Ципэн; Жандры, Марк (2019). «Возвращаясь к постквантовому Фиат-Шамиру». Достижения в криптологии - CRYPTO '19. Конспект лекций по информатике. Springer Cham. 11693: 326–355. Дои:10.1007/978-3-030-26951-7_12. ISBN 978-3-030-26950-0.
^ Goldwasser, S .; Калаи, Ю. Т. (октябрь 2003 г.). «О (Не) безопасности парадигмы Фиат-Шамир». 44-й ежегодный симпозиум IEEE по основам компьютерных наук, 2003. Труды.: 102–113. Дои:10.1109 / SFCS.2003.1238185. ISBN 0-7695-2040-5.
^ Камениш, Ян; Стадлер, Маркус (1997). "Системы доказательства общих утверждений о дискретных логарифмах" (PDF). Департамент компьютерных наук, ETH Zurich.
^ Белларе, Михир; Rogaway, Филипп (1995). «Случайные оракулы практичны: парадигма для разработки эффективных протоколов». ACM Press: 62–73. CiteSeerX 10.1.1.50.3345. Цитировать журнал требует | журнал = (помощь)
^ Бернхард, Дэвид; Перейра, Оливье; Варински, Богдан. «Как не проявить себя: подводные камни эвристики Fiat-Shamir и приложения к Helios» (PDF). В Ван, Сяоюнь; Сако, Казуэ (ред.). Достижения в криптологии - ASIACRYPT 2012. С. 626–643.

[1] Фиат, Амос; Шамир, Ади (1987). «Как проявить себя: практические решения проблем идентификации и подписи». Достижения в криптологии - CRYPTO '86. Конспект лекций по информатике. Springer Berlin Heidelberg. 263: 186–194. Дои:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.

[2] Поинтшеваль, Дэвид; Стерн, Жак (1996). «Доказательства безопасности для схем подписи». Достижения в криптологии - EUROCRYPT '96. Конспект лекций по информатике. Springer Berlin Heidelberg. 1070: 387–398. Дои:10.1007/3-540-68339-9_33. ISBN 978-3-540-61186-8.

[3] Дон, Джелле; Фер, Серж; Майенз, Кристиан; Шаффнер, Кристиан (2019). «Безопасность преобразования Фиат-Шамира в квантовой модели случайного оракула». Достижения в криптологии - CRYPTO '19. Конспект лекций по информатике. Springer Cham. 11693: 356–383. arXiv:1902.07556. Bibcode:2019arXiv190207556D. Дои:10.1007/978-3-030-26951-7_13. ISBN 978-3-030-26950-0.

[4] Лю, Ципэн; Жандры, Марк (2019). «Возвращаясь к постквантовому Фиат-Шамиру». Достижения в криптологии - CRYPTO '19. Конспект лекций по информатике. Springer Cham. 11693: 326–355. Дои:10.1007/978-3-030-26951-7_12. ISBN 978-3-030-26950-0.

[5] Goldwasser, S .; Калаи, Ю. Т. (октябрь 2003 г.). «О (Не) безопасности парадигмы Фиат-Шамир». 44-й ежегодный симпозиум IEEE по основам компьютерных наук, 2003. Труды.: 102–113. Дои:10.1109 / SFCS.2003.1238185. ISBN 0-7695-2040-5.

[6] Камениш, Ян; Стадлер, Маркус (1997). "Системы доказательства общих утверждений о дискретных логарифмах" (PDF). Департамент компьютерных наук, ETH Zurich.

[7] Белларе, Михир; Rogaway, Филипп (1995). «Случайные оракулы практичны: парадигма для разработки эффективных протоколов». ACM Press: 62–73. CiteSeerX 10.1.1.50.3345. Цитировать журнал требует | журнал = (помощь)

[8] Бернхард, Дэвид; Перейра, Оливье; Варински, Богдан. «Как не проявить себя: подводные камни эвристики Fiat-Shamir и приложения к Helios» (PDF). В Ван, Сяоюнь; Сако, Казуэ (ред.). Достижения в криптологии - ASIACRYPT 2012. С. 626–643.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]