Проверяемая случайная функция
Криптографическая псевдослучайная функция с открытым ключом

В криптографии проверяемая случайная функция ( VRF) — это псевдослучайная функция с открытым ключом , которая предоставляет доказательства того, что ее выходные данные были рассчитаны правильно. Владелец секретного ключа может вычислить значение функции, а также связанное с ним доказательство для любого входного значения. Все остальные, используя доказательство и связанный с ним открытый ключ (или ключ проверки [1] ), могут проверить, что это значение действительно было рассчитано правильно, однако эта информация не может быть использована для нахождения секретного ключа. [2]

Проверяемую случайную функцию можно рассматривать как аналог криптографического хэша с открытым ключом [2] и как криптографическое обязательство по экспоненциально большому числу, казалось бы, случайных битов. [3] Концепция проверяемой случайной функции тесно связана с концепцией проверяемой непредсказуемой функции (VUF), чьи выходные данные трудно предсказать, но не обязательно кажутся случайными. [3] [4]

Концепция VRF была введена Микали , Рабином и Вадханом в 1999 году. [4] [5] С тех пор проверяемые случайные функции нашли широкое применение в криптовалютах, а также в предложениях по разработке протоколов и кибербезопасности.

Конструкции

В 1999 году Микали, Рабин и Вадхан ввели концепцию VRF и предложили первую такую ​​функцию. [4] Первоначальная конструкция была довольно неэффективной: сначала она создает проверяемую непредсказуемую функцию , затем использует хардкорный бит для ее преобразования в VRF; более того, входные данные должны быть сопоставлены с простыми числами сложным образом: а именно, с помощью генератора простых последовательностей, который генерирует простые числа с подавляющей вероятностью, используя вероятностный тест на простоту . [3] [4] Таким образом предложенная проверяемая непредсказуемая функция, которая является доказуемо безопасной, если вариант задачи RSA является сложным, определяется следующим образом: Открытый ключ PK равен , где m — произведение двух случайных простых чисел, r — число, случайно выбранное из , coins — случайно выбранный набор битов, а Q — функция, случайно выбранная из всех полиномов степени над полем . Секретный ключ равен . При наличии входных данных x и секретного ключа SK VUF использует генератор простых чисел для выбора соответствующего простого числа (генератору требуются дополнительные входные данные Q и монеты ), а затем вычисляет и выводит , что легко сделать, зная . [4] ( м , г , В , с о я н с ) {\displaystyle (м,р,Q,монеты)} З м ∗ {\displaystyle \mathbb {Z} _{m}^{*}} 2 к 2 − 1 {\displaystyle 2k^{2}-1} Г Ф ( 2 к ) {\displaystyle GF(2^{k})} ( П К , ϕ ( м ) ) {\displaystyle (ПК,\фи (м))} п х {\displaystyle p_{x}} г 1 / п х ( мод м ) {\displaystyle r^{1/p_{x}}{\pmod {m}}} ϕ ( м ) {\displaystyle \фи (м)}

В 2005 году Додис и Ямпольский предложили эффективную и практичную проверяемую случайную функцию. [3] [6] Когда входные данные поступают из небольшой области (затем авторы расширяют ее до большей области), функцию можно определить следующим образом: х {\displaystyle x}

Ф С К ( х ) = е ( г , г ) 1 / ( х + С К ) и п С К ( х ) = г 1 / ( х + С К ) , {\displaystyle F_{SK}(x)=e(g,g)^{1/(x+SK)}\quad {\mbox{и}}\quad p_{SK}(x)=g^{1/(x+SK)},}

где e (·,·) — это билинейное отображение . Чтобы проверить, было ли вычислено правильно или нет, можно проверить, если и . [3] [6] Чтобы расширить это на большую область, авторы используют конструкцию дерева и универсальную хэш-функцию . [3] Это безопасно, если трудно нарушить «предположение об инверсии q-Диффи-Хелмана», которое гласит, что ни один заданный алгоритм не может вычислить , и «предположение об инверсии q-решения билинейного Диффи-Хелмана», которое гласит, что невозможно для эффективного алгоритма, заданного в качестве входных данных, отличить от случайного в группе . [3] [6] Ф С К ( х ) {\displaystyle F_{SK}(x)} е ( г х П К , п С К ( х ) ) = е ( г , г ) {\displaystyle e(g^{x}PK,p_{SK}(x))=e(g,g)} е ( г , п С К ( х ) ) = Ф С К ( х ) {\displaystyle e(g,p_{SK}(x))=F_{SK}(x)} ( г , г х , … , г х д ) {\displaystyle (г,г^{x},\точки,г^{x^{q}})} г 1 / х {\displaystyle g^{1/x}} ( г , г х , … , г ( х д ) , Р ) {\displaystyle (г,г^{x},\ldots ,г^{(x^{q})},R)} Р = е ( г , г ) 1 / х {\displaystyle R=e(g,g)^{1/x}} Г {\displaystyle \mathbb {G} }

В 2015 году Хофхайнц и Ягер построили VRF, которая является доказуемо безопасной для любого члена «семейства (n − 1)-линейных предположений», которое включает в себя линейное предположение о решении . [7] Это первая такая построенная VRF, которая не зависит от «предположения о сложности Q-типа». [7]

В 2019 году Битанский показал, что VRF существуют, если также существуют неинтерактивные доказательства, неразличимые по свидетелям (то есть более слабые версии неинтерактивных доказательств с нулевым разглашением для проблем NP , которые скрывают только свидетельство, которое использует доказывающая сторона [1] [8] ), неинтерактивные криптографические обязательства и псевдослучайные функции с ограничениями по одному ключу (то есть псевдослучайные функции, которые позволяют пользователю оценивать функцию только с помощью предустановленного ограниченного подмножества возможных входных данных [9] ). [1]

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

В 2020 году Эсгин и др. предложили постквантовую безопасную VRF, основанную на криптографии на основе решеток . [10]

Использование и применение

VRF предоставляют детерминированные предварительные обязательства для входных данных с низкой энтропией, которые должны быть устойчивы к атакам методом перебора прообразов . [11] [ необходим лучший источник ] VRF можно использовать для защиты от атак офлайн-перебора (таких как атаки по словарю ) на данные, хранящиеся в структурах данных на основе хэша. [2]

В разработке протокола

VRF-системы использовались для изготовления:

  • Сбрасываемые доказательства с нулевым разглашением (т.е. такие, которые остаются с нулевым разглашением, даже если злонамеренному проверяющему разрешено сбросить честного доказывающего и снова запросить его [12] ) с тремя раундами в голой модели [3] [7]
  • Неинтерактивные лотерейные системы [3] [7]
  • Проверяемые схемы депонирования транзакций [3] [7]
  • Обновляемые базы данных с нулевым разглашением [7]
  • Электронные деньги [7]

VRF также можно использовать для реализации случайных оракулов . [13]

В сфере интернет-безопасности

DNSSEC — это система, которая не позволяет злоумышленникам вмешиваться в сообщения системы доменных имен , но она также страдает от уязвимости перечисления зон. Предлагаемая система NSEC5, которая использует VRF [ как? ] , доказанно предотвращает этот тип атак. [14] [ важность? ]

Ссылки

  1. ^ abc Bitansky, Nir (2020-04-01). «Проверяемые случайные функции из неинтерактивных доказательств, неразличимых свидетелями». Журнал криптологии . 33 (2): 459–493. doi :10.1007/s00145-019-09331-1. ISSN  1432-1378. S2CID  253636177.
  2. ^ abc Goldberg, Sharon; Vcelak, Jan; Papadopoulos, Dimitrios; Reyzin, Leonid (5 марта 2018 г.). Verifiaible Random Functions (VRF) (PDF) (Технический отчет) . Получено 15 августа 2021 г.
  3. ^ abcdefghij Додис, Евгений; Ямпольский, Александр (16 ноября 2004 г.). "Проверяемая случайная функция с короткими доказательствами и ключами" (PDF) . 8-й международный семинар по теории и практике криптографии с открытым ключом . Международный семинар по криптографии с открытым ключом. Springer, Берлин, Гейдельберг (опубликовано в 2005 г.). стр. 416–431. ISBN 978-3-540-30580-4. Получено 26 августа 2021 г. .
  4. ^ abcde Микали, Сильвио ; Рабин, Майкл О. ; Вадхан, Салил П. (1999). "Проверяемые случайные функции" (PDF) . Труды 40-го симпозиума IEEE по основам компьютерной науки . 40-й ежегодный симпозиум по основам компьютерной науки. стр. 120–130. doi :10.1109/SFFCS.1999.814584. ISBN 0-7695-0409-4.
  5. ^ Поттер, Джон (9 сентября 2021 г.). «Как инвесторы в стоимость могут получить прибыль в экосистеме криптовалют?». finance.yahoo.com . Получено 19 сентября 2021 г. .
  6. ^ abc Nountu, Thierry Mefenza (28 ноября 2017 г.). Псевдослучайные генераторы и псевдослучайные функции: криптоанализ и меры сложности (тезисы докторской диссертации).
  7. ^ abcdefg Хофхайнц, Деннис; Ягер, Тибор (30 октября 2015 г.). Верифицируемые случайные функции из стандартных предположений. Конференция по теории криптографии (опубликовано 19 декабря 2015 г.). стр. 336–362. CiteSeerX 10.1.1.738.9975 . дои : 10.1007/978-3-662-49096-9_14. ISBN  978-3-662-49096-9.
  8. ^ Барак, Вооз; Онг, Шиен Джин; Вадхан, Салил (1 января 2007 г.). «Дерандомизация в криптографии» (PDF) . SIAM Journal по вычислительной технике . 37 (2): 380–400. дои : 10.1137/050641958. ISSN  0097-5397 . Проверено 2 сентября 2021 г.
  9. ^ Boneh, Dan; Waters, Brent (2013). «Ограниченные псевдослучайные функции и их приложения». В Sako, Kazue; Sarkar, Palash (ред.). Advances in Cryptology - ASIACRYPT 2013. Lecture Notes in Computer Science. Vol. 8270. Berlin, Heidelberg: Springer. pp. 280–300. doi : 10.1007/978-3-642-42045-0_15 . ISBN 978-3-642-42045-0. Получено 2 сентября 2021 г. .
  10. ^ Эсгин, Мухаммед Ф.; Кухта, Вероника; Сакзад, Амин; Стейнфельд, Рон; Чжан, Чжэньфэй; Сан, Шифэн; Чу, Шумо (24 марта 2021 г.). «Практическая постквантовая маловременная проверяемая случайная функция с приложениями к Algorand». Архив Cryptology ePrint . Получено 26 августа 2021 г.
  11. ^ Шорн, Эрик (24.02.2020). «Обзор проверяемых случайных функций». NCC Group Research . Получено 04.09.2021 .
  12. ^ Микали, Сильвио; Рейзин, Леонид (2001). «Надежность модели открытого ключа». В Килиан, Джо (ред.). Достижения в криптологии — CRYPTO 2001. Конспект лекций по информатике. Том 2139. Берлин, Гейдельберг: Springer. С. 542–565. doi : 10.1007/3-540-44647-8_32 . ISBN 978-3-540-44647-7.
  13. ^ Додис, Евгений (2002). «Эффективное построение (распределенных) проверяемых случайных функций». В Desmedt, Yvo G. (ред.). Криптография с открытым ключом — PKC 2003. Конспект лекций по информатике. Том 2567. Берлин, Гейдельберг: Springer. стр. 1–17. doi : 10.1007/3-540-36288-6_1 . ISBN 978-3-540-36288-3.
  14. ^ Голдберг, Шарон. «NSEC5: доказуемое предотвращение перечисления зон DNSSEC». www.cs.bu.edu . Получено 26.08.2021 .
Взято с "https://en.wikipedia.org/w/index.php?title=Проверяемая_случайная_функция&oldid=1232893699"