Верифицируемая случайная функция

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

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

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

Конструкции

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

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

F_{SK}(x)=e(g,g)^{1/(x+SK)}\quad {\mbox{and}}\quad p_{SK}(x)=g^{1/(x+SK)},

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

В 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]^{[ важность? ]}

Ссылки

^ Jump up to: ^а ^б ^с Битанский, Нир (01.04.2020). «Проверяемые случайные функции на основе неинтерактивных свидетелей-неотличимых доказательств» . Журнал криптологии . 33 (2): 459–493. дои : 10.1007/s00145-019-09331-1 . ISSN 1432-1378 . S2CID 253636177 .
^ Jump up to: ^а ^б ^с Голдберг, Шэрон; Вчелак, Ян; Пападопулос, Димитриос; Рейзин, Леонид (5 марта 2018 г.). Верифицируемые случайные функции (VRF) (PDF) (Технический отчет) . Проверено 15 августа 2021 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Додис, Евгений; Ямпольский, Александр (16 ноября 2004 г.). «Проверяемая случайная функция с короткими доказательствами и ключами» (PDF) . 8-й международный семинар по теории и практике криптографии с открытым ключом . Международный семинар по криптографии с открытым ключом. Springer, Берлин, Гейдельберг (опубликовано в 2005 г.). стр. 416–431. ISBN 978-3-540-30580-4 . Проверено 26 августа 2021 г.
^ Jump up to: ^а ^б ^с ^д ^и Микали, Сильвио ; Рабин, Майкл О .; Вадхан, Салил П. (1999). «Проверяемые случайные функции» (PDF) . Материалы 40-го симпозиума IEEE по основам информатики . 40-й ежегодный симпозиум по основам информатики. стр. 120–130. дои : 10.1109/SFCS.1999.814584 . ISBN 0-7695-0409-4 .
^ Поттер, Джон (9 сентября 2021 г.). «Как стоимостные инвесторы могут получить прибыль от крипто-экосистемы?» . финансы.yahoo.com . Проверено 19 сентября 2021 г.
^ Jump up to: ^а ^б ^с Нунту, Тьерри Мефенса (28 ноября 2017 г.). Псевдослучайные генераторы и псевдослучайные функции: криптоанализ и меры сложности (Тезисы докторской диссертации).
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Хофхайнц, Деннис; Ягер, Тибор (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 .
^ Барак, Вооз; Онг, Шиен Джин; Вадхан, Салил (1 января 2007 г.). «Дерандомизация в криптографии» (PDF) . SIAM Journal по вычислительной технике . 37 (2): 380–400. дои : 10.1137/050641958 . ISSN 0097-5397 . Проверено 2 сентября 2021 г.
^ Боне, Дэн; Уотерс, Брент (2013). «Ограниченные псевдослучайные функции и их приложения» . В Сако, Казуэ; Саркар, Палаш (ред.). Достижения в криптологии — ASIACRYPT 2013 . Конспекты лекций по информатике. Том. 8270. Берлин, Гейдельберг: Springer. стр. 280–300. дои : 10.1007/978-3-642-42045-0_15 . ISBN 978-3-642-42045-0 . Проверено 2 сентября 2021 г.
^ Эсгин, Мухаммед Ф.; Кухта, Вероника; Сакзад, Амин; Стейнфельд, Рон; Чжан, Чжэньфэй; Сунь, Шифэн; Чу, Шумо (24 марта 2021 г.). «Практическая постквантовая маловременно проверяемая случайная функция с приложениями к алгоритму» . Архив электронной печати по криптологии . Проверено 26 августа 2021 г.
^ Шорн, Эрик (24 февраля 2020 г.). «Обзор проверяемых случайных функций» . Исследования группы компаний NCC . Проверено 4 сентября 2021 г.
^ Микали, Сильвио; Рейзин, Леонид (2001). «Надежность модели открытого ключа». В Килиане, Джо (ред.). Достижения криптологии — КРИПТО 2001 . Конспекты лекций по информатике. Том. 2139. Берлин, Гейдельберг: Springer. стр. 542–565. дои : 10.1007/3-540-44647-8_32 . ISBN 978-3-540-44647-7 .
^ Додис, Евгений (2002). «Эффективное построение (распределенных) проверяемых случайных функций». В Десмедте, Иво Г. (ред.). Криптография с открытым ключом — PKC 2003 . Конспекты лекций по информатике. Том. 2567. Берлин, Гейдельберг: Springer. стр. 1–17. дои : 10.1007/3-540-36288-6_1 . ISBN 978-3-540-36288-3 .
^ Голдберг, Шэрон. «NSEC5: Доказуемое предотвращение перечисления зон DNSSEC» . www.cs.bu.edu . Проверено 26 августа 2021 г.

[:9-1] Jump up to: ^а ^б ^с Битанский, Нир (01.04.2020). «Проверяемые случайные функции на основе неинтерактивных свидетелей-неотличимых доказательств» . Журнал криптологии . 33 (2): 459–493. дои : 10.1007/s00145-019-09331-1 . ISSN 1432-1378 . S2CID 253636177 .

[:0-2] Jump up to: ^а ^б ^с Голдберг, Шэрон; Вчелак, Ян; Пападопулос, Димитриос; Рейзин, Леонид (5 марта 2018 г.). Верифицируемые случайные функции (VRF) (PDF) (Технический отчет) . Проверено 15 августа 2021 г.

[:7-3] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Додис, Евгений; Ямпольский, Александр (16 ноября 2004 г.). «Проверяемая случайная функция с короткими доказательствами и ключами» (PDF) . 8-й международный семинар по теории и практике криптографии с открытым ключом . Международный семинар по криптографии с открытым ключом. Springer, Берлин, Гейдельберг (опубликовано в 2005 г.). стр. 416–431. ISBN 978-3-540-30580-4 . Проверено 26 августа 2021 г.

[:8-4] Jump up to: ^а ^б ^с ^д ^и Микали, Сильвио ; Рабин, Майкл О .; Вадхан, Салил П. (1999). «Проверяемые случайные функции» (PDF) . Материалы 40-го симпозиума IEEE по основам информатики . 40-й ежегодный симпозиум по основам информатики. стр. 120–130. дои : 10.1109/SFCS.1999.814584 . ISBN 0-7695-0409-4 .

[:11-5] Поттер, Джон (9 сентября 2021 г.). «Как стоимостные инвесторы могут получить прибыль от крипто-экосистемы?» . финансы.yahoo.com . Проверено 19 сентября 2021 г.

[:1-6] Jump up to: ^а ^б ^с Нунту, Тьерри Мефенса (28 ноября 2017 г.). Псевдослучайные генераторы и псевдослучайные функции: криптоанализ и меры сложности (Тезисы докторской диссертации).

[:2-7] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Хофхайнц, Деннис; Ягер, Тибор (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] Боне, Дэн; Уотерс, Брент (2013). «Ограниченные псевдослучайные функции и их приложения» . В Сако, Казуэ; Саркар, Палаш (ред.). Достижения в криптологии — ASIACRYPT 2013 . Конспекты лекций по информатике. Том. 8270. Берлин, Гейдельберг: Springer. стр. 280–300. дои : 10.1007/978-3-642-42045-0_15 . ISBN 978-3-642-42045-0 . Проверено 2 сентября 2021 г.

[:10-10] Эсгин, Мухаммед Ф.; Кухта, Вероника; Сакзад, Амин; Стейнфельд, Рон; Чжан, Чжэньфэй; Сунь, Шифэн; Чу, Шумо (24 марта 2021 г.). «Практическая постквантовая маловременно проверяемая случайная функция с приложениями к алгоритму» . Архив электронной печати по криптологии . Проверено 26 августа 2021 г.

[11] Шорн, Эрик (24 февраля 2020 г.). «Обзор проверяемых случайных функций» . Исследования группы компаний NCC . Проверено 4 сентября 2021 г.

[12] Микали, Сильвио; Рейзин, Леонид (2001). «Надежность модели открытого ключа». В Килиане, Джо (ред.). Достижения криптологии — КРИПТО 2001 . Конспекты лекций по информатике. Том. 2139. Берлин, Гейдельберг: Springer. стр. 542–565. дои : 10.1007/3-540-44647-8_32 . ISBN 978-3-540-44647-7 .

[13] Додис, Евгений (2002). «Эффективное построение (распределенных) проверяемых случайных функций». В Десмедте, Иво Г. (ред.). Криптография с открытым ключом — PKC 2003 . Конспекты лекций по информатике. Том. 2567. Берлин, Гейдельберг: Springer. стр. 1–17. дои : 10.1007/3-540-36288-6_1 . ISBN 978-3-540-36288-3 .

[14] Голдберг, Шэрон. «NSEC5: Доказуемое предотвращение перечисления зон DNSSEC» . www.cs.bu.edu . Проверено 26 августа 2021 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]