Эвристика Fiat – Shamir - Fiat–Shamir heuristic

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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.