Кольцевое обучение с подписью ошибок - Ring learning with errors signature

Цифровые подписи являются средством защиты цифровая информация от преднамеренного изменения и для аутентификации источника цифровой информации. Криптография с открытым ключом предоставляет богатый набор различных криптографических алгоритмов для создания цифровых подписей. Однако используемые в настоящее время первичные подписи с открытым ключом (ЮАР и Сигнатуры эллиптических кривых) станет совершенно небезопасным, если ученым когда-либо удастся построить здание среднего размера. квантовый компьютер.[1] Пост квантовая криптография - это класс криптографических алгоритмов, устойчивых к атакам квантовой криптографии. Несколько алгоритмов пост-квантовой цифровой подписи, основанных на сложных проблемах в решетках, заменяют обычно используемые ЮАР и подписи эллиптических кривых. Подмножество этих решетчатых схем основано на проблеме, известной как Кольцевое обучение с ошибками. Кольцевое обучение с использованием цифровых подписей на основе ошибок входит в число пост-квантовых подписей с наименьшими размерами открытого ключа и подписи

Фон

События в квантовые вычисления За последнее десятилетие и оптимистичные перспективы реальных квантовых компьютеров в течение 20 лет начали угрожать базовой криптографии, обеспечивающей безопасность Интернета.[2][3] Относительно небольшой квантовый компьютер способный обрабатывать всего десять тысяч бит информации, легко сломал бы все широко используемые открытый ключ алгоритмы криптографии, используемые для защиты конфиденциальности и цифровой подписи информации в Интернете.[1][4]

Один из наиболее широко используемых алгоритмов открытого ключа, используемых для создания цифровые подписи известен как ЮАР. Его безопасность основана на классической сложности разложения произведения двух больших и неизвестных простых чисел на составляющие простые числа. В проблема целочисленной факторизации считается трудноразрешимым на любом обычном компьютере, если простые числа выбраны случайным образом и достаточно велики. Однако, если разложить произведение двух n-битных простых чисел на множители, квантовый компьютер с примерно 6n битами логической кубит память и способна выполнять программу, известную как Алгоритм Шора легко выполнит поставленную задачу.[5] Алгоритм Шора также может быстро взламывать цифровые подписи на основе того, что известно как дискретный логарифм проблема и более эзотерический дискретный логарифм эллиптической кривой проблема. Фактически, относительно небольшой квантовый компьютер, на котором работает алгоритм Шора, может быстро взломать все цифровые подписи, используемые для обеспечения конфиденциальности и целостности информации в Интернете сегодня.

Несмотря на то, что мы не знаем, когда появится квантовый компьютер для взлома RSA и других алгоритмов цифровой подписи, в последнее десятилетие проводились активные исследования по созданию криптографических алгоритмов, которые остаются безопасными, даже когда злоумышленник имеет ресурсы квантового компьютера в своих руках. утилизация.[1][6] Эта новая область криптографии называется Пост квантовый или же Квантовый сейф криптография.[1][6] Эта статья посвящена одному классу этих алгоритмов: цифровым подписям, основанным на проблеме кольцевого обучения с ошибками. Использование общего Обучение с ошибками Проблема в криптографии была предложена Одедом Регевым в 2005 году и послужила источником нескольких криптографических разработок.[7]

Создатели криптографии, основанной на кольцевом обучении с ошибками (RLWE), считают, что важной особенностью этих алгоритмов, основанных на кольцевом обучении с ошибками, является их доказуемое сокращение до известных сложных проблем.[8][9] Подпись, описанная ниже, имеет доказуемое сокращение до Кратчайшая векторная задача в идеальная решетка.[10] Это означает, что если атака может быть обнаружена на криптосистеме Ring-LWE, то целый класс предполагаемых сложных вычислительных проблем будет иметь решение.[11]

Первая подпись на основе RLWE была разработана Любашевским в его статье «Фиат-Шамир с прерываниями: приложения к подписям на основе решеток и факторинга».[12] и доработана в "Решетчатых подписях без лазеек" в 2011 году.[13] За этим последовал ряд уточнений и вариантов. В этой статье освещается фундаментальная математическая структура подписей RLWE и следует оригинальная работа Любашевского и работа Гунейсу, Любашевского и Попплеманна (GLP ).[10] Эта презентация основана на обновлении схемы GLP 2017 года под названием GLYPH.[14]

RLWE-SIG работает в частном кольцо многочленов по модулю многочлена Φ (x) степени n с коэффициентами конечное поле Zq для нечетного простого числа q (т. е. кольца Zq[x] / Φ (x)).[13] Умножение и сложение многочленов будет работать обычным образом с результатами приведенного умножения по модулю Φ (x). Для этого представления типичный многочлен выражается как:

Поле Zq имеет свои репрезентативные элементы в множестве {- (q-1) / 2, ...- 1, 0, 1, ... (q-1) / 2}. Когда n является степенью двойки, многочлен Φ (x) будет круговым многочленом xп + 1. Возможны и другие варианты n, но соответствующие циклотомические многочлены более сложны или их безопасность не так хорошо изучена.

Генерация «малых» многочленов.

Сигнатура RLWE использует многочлены, которые считаются «маленькими» по отношению к мере, называемой «бесконечная норма ". бесконечная норма для полинома - это просто наибольшее абсолютное значение коэффициентов полинома, когда эти коэффициенты рассматриваются как целые числа в Z, а не Zq .[10] Алгоритм подписи будет создавать случайные многочлены, которые малы по отношению к определенной границе нормы бесконечности. Это легко сделать путем случайной генерации всех коэффициенты полинома (а0, ..., ап-1) способом, который гарантированно или с большой вероятностью будет меньше или равен этому пределу. В литературе по кольцевому обучению с ошибками есть два распространенных способа сделать это:[13]

  • С помощью Равномерная выборка - Коэффициенты малого полинома равномерно выбираются из набора малых коэффициентов. Пусть b - целое число, намного меньшее q. Если мы случайным образом выберем полиномиальные коэффициенты из набора: {-b, -b + 1, -b + 2. ... -2, -1, 0, 1, 2, ..., b-2, b-1, b} бесконечная норма полинома будет ≤ (b).
  • Использование дискретной гауссовой выборки - для нечетного целого числа q коэффициенты выбираются случайным образом путем выборки из набора {- (q-1) / 2 до (q-1) / 2} в соответствии с дискретным гауссовым распределением со средним 0 и распределением параметр σ. Ссылки предоставляют более подробную информацию об этом методе.

В сигнатуре RLWE GLYPH, используемой в качестве примера ниже, коэффициенты для "малых" многочленов будут использовать единообразный отбор проб метода и значение b будет намного меньше, чем значение q.[10]

Хеширование до "маленького" многочлена

Для большинства алгоритмов подписи RLWE также требуется способность криптографически хэш произвольные битовые строки в маленькие полиномы в соответствии с некоторым распределением. В приведенном ниже примере используется хеш-функция POLYHASH (ω), которая принимает битовую строку ω в качестве входных данных и выводит полином с n коэффициентами, так что ровно k из этих коэффициентов имеют абсолютное значение больше нуля и меньше целочисленной границы b. (см. выше).

Отбор проб

Ключевой особенностью алгоритмов подписи RLWE является использование метода, известного как отбраковка.[13][12] В этой технике, если бесконечная норма сигнатурного полинома превышает фиксированную границу, β, этот многочлен будет отброшен, и процесс подписания начнется снова. Этот процесс будет повторяться до тех пор, пока бесконечная норма сигнатурного полинома не станет меньше или равна границе. Выборка отклонения гарантирует, что выходная подпись не будет коррелировать с использованием секретных ключей подписывающей стороны.

В следующем примере оценка β, будет (b - k), где b - это диапазон однородной выборки, описанной выше, а k - количество ненулевых коэффициентов, разрешенных в "принятом" полиноме.[10]

Прочие параметры

Согласно GLYPH и как отмечалось выше, максимальная степень многочленов будет n-1 и, следовательно, иметь n коэффициентов.[10] Типичные значения n - 512 и 1024.[10] Коэффициенты этих полиномов будут из поля Fq где q - нечетное простое число, конгруэнтное 1 по модулю 4. Для n = 1024 GLYPH устанавливает q = 59393, b = 16383 и k количество ненулевых коэффициентов в выводе Polyhash равным 16.[14] Количество ненулевых коэффициентов k, созданных хеш-функцией, равно 32 для обоих случаев.[10] Безопасность схемы подписи тесно связана с относительными размерами n, q, b и k. Подробную информацию о настройке этих параметров можно найти в ссылках 5 и 6 ниже.[13][10][14]

Как отмечалось выше, многочлен Φ (x), который определяет кольцо используемых многочленов, будет xп + 1. Наконец, a (x) будет случайно выбранным и фиксированным многочленом с коэффициентами из множества {- (q-1) / 2 до (q-1) / 2}. Полином a (x) следует выбрать в "Ничего в рукаве "таким образом, как одностороннее хеширование выходной сигнал генератора случайных чисел с истинным шумом (TRNG) или с использованием цифрового разложения хорошо известных математических констант, таких как пи или е. Все подписывающие и проверяющие подписи будут знать n, q, b, k, Φ (x), a (x) и β = б-к.

Генерация открытого ключа

Субъект, желающий подписать сообщения, генерирует свой открытый ключ, выполнив следующие действия:

  1. Сгенерируйте два малых полинома s (x) и e (x) с коэффициентами, выбранными равномерно из набора {-b, ...- 1, 0, 1, ..., b}
  2. Вычислить t (x) = a (x) · s (x) + e (x)
  3. Распределить t (x) как открытый ключ объекта

Многочлены s (x) и e (x) служат закрытым ключом, а t (x) - соответствующим открытым ключом. Безопасность этой схемы подписи основана на следующей проблеме. Для многочлена t (x) найдите малые многочлены f1(x) и f2(x) такая, что: a (x) · f1(x) + f2(х) = т (х)

Если эту проблему решить сложно, то схему подписи будет сложно подделать. [См. Статью в Википедии о Кольцевое обучение с ошибками или же Идеальная решетчатая криптография для более подробной информации о теоретической сложности этой проблемы]

Генерация подписи

Следуя GLYPH,[14] чтобы подписать сообщение m, выраженное в виде битовой строки, подписывающий объект выполняет следующие действия:

  1. Сгенерируйте два маленьких многочлена y1(x) и y2(x) с коэффициентами из множества {-b, ..., 0, ...., b}
  2. Вычислить w (x) = a (x) · y1(х) + у2(Икс)
  3. Отображение w (x) в битовую строку ω
  4. Вычислить c (x) = POLYHASH (ω | m) (это многочлен с k ненулевыми коэффициентами. «|» Обозначает конкатенацию строк)
  5. Вычислить z1(х) = s (x) · c (x) + y1(Икс)
  6. Вычислить z2(х) = е (х) · с (х) + у2(Икс)
  7. До бесконечности нормы z1(x) и z2(х) ≤ β = (B - k) переходите к шагу 1. (Это этап отбора пробы, указанный выше)
  8. Сигнатура - это тройка многочленов c (x), z1(x) и z2(Икс)
  9. Передайте сообщение вместе с c (x), z1(x) и z2(x) верификатору.

Подтверждение подписи

Следуя GLYPH,[14] для проверки сообщения m, выраженного в виде битовой строки, проверяющий объект должен обладать открытым ключом подписывающей стороны (t (x)), подписью (c (x), z1(х), z2(x)), а сообщение m. Верификатор делает следующее:

  1. Проверить, что бесконечные нормы z1(x) и z2(х) ≤ β , если не отклоняю подпись.
  2. Вычислить w '(x) = a (x) · z1(х) + г2(х) - t (х) с (х)
  3. Преобразуйте w '(x) в битовую строку ω'
  4. Вычислить c '(x) = POLYHASH (ω' | m)
  5. Если c '(x) ≠ c (x) отклонить подпись, в противном случае принять подпись как действительную.

Заметь:

а (х) · г1(х) + г2(х) - t (x) c (x) = a (x) · [s (x) · c (x) + y1(x)] + z2(х) - [а (х) · s (х) + е (х)] с (х)

= а (х) · у1(х) + г2(х) - е (х) · с (х)

= а (х) у1(х) + е (х) · с (х) + у2(х) - е (х) · с (х)

= а (х) у1(х) + у2(x) = w (x) (как определено выше)

Этот краткий вывод показывает, что процесс проверки будет иметь c '(x) = c (x), если подпись не была изменена.

Дальнейшие разработки

Схема подписи GLYPH, описанная в этом документе, во многом повторяет работу Любашевского, Гунесю и Попплемена в 2011 и 2012 годах. Есть ряд других вариаций их работы. К ним относятся:

  • Задокументированная работа Бая и Гэлбрейта над короткими подписями здесь.[15]
  • Работа Аклейлека, Бинделя, Бухмана, Крамера и Марсона по доказательствам безопасности для подписи с меньшим количеством предположений безопасности и документирована здесь.[16]

Другой подход к подписям на основе решеток над кольцами - это вариант запатентованного семейства NTRU решетчатой ​​криптографии. Основным примером этого подхода является подпись, известная как схема подписи бимодальной решетки (BLISS). Он был разработан Дукасом, Дурмасом, Лепойнтом и Любашевским и задокументирован в их статье «Решеточные подписи и бимодальные гауссианы».[17] Видеть Схема подписи BLISS

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

  1. ^ а б c d Дамен-Люисье, Сабина. «ETSI - Quantum-Safe Cryptography». ETSI. Получено 2015-07-05.
  2. ^ Шах, Агам. «Заявление IBM о прорыве в области квантовых вычислений». Получено 2015-06-01.
  3. ^ Марков, Джон (04.03.2015). «Исследователи сообщают о вехе в развитии квантового компьютера». Нью-Йорк Таймс. ISSN  0362-4331. Получено 2015-07-05.
  4. ^ Бекман, Дэвид; Chari, Amalavoyal N .; Девабхактуни, Шрикришна; Прескилл, Джон (1996). «Эффективные сети для квантового факторинга». Физический обзор A. 54 (2): 1034–1063. arXiv:Quant-ph / 9602016. Bibcode:1996ПхРвА..54.1034Б. Дои:10.1103 / PhysRevA.54.1034. ISSN  1050-2947. PMID  9913575. S2CID  2231795.
  5. ^ Смолин, Джон А .; Смит, Грэм; Варго, Александр (11 июля 2013 г.). «Упрощение квантового факторинга». Природа. 499 (7457): 163–165. arXiv:1301.7007. Bibcode:2013Натура.499..163С. Дои:10.1038 / природа12290. ISSN  0028-0836. PMID  23846653. S2CID  4422110.
  6. ^ а б "Вступление". pqcrypto.org. Получено 2015-07-05.
  7. ^ «Проблема обучения с ошибками» (PDF). www.cims.nyu.edu. Получено 2015-05-24.
  8. ^ Любашевский, Вадим; Пайкерт, Крис; Регев, Одед (2010). «Об идеальных решетках и обучении с ошибками по кольцам». В Proc. EUROCRYPT, том 6110 LNCS: 1–23. CiteSeerX  10.1.1.297.6108.
  9. ^ «Что« поучительная история »GCHQ означает для решетчатой ​​криптографии?». www.cc.gatech.edu. Архивировано из оригинал на 2015-07-06. Получено 2015-07-05.
  10. ^ а б c d е ж грамм час я Гюнесу, Тим; Любашевский, Вадим; Пёппельманн, Томас (2012). «Практическая криптография на основе решеток: схема подписи для встроенных систем». В Проффе, Эммануэль; Шаумон, Патрик (ред.). Криптографическое оборудование и встроенные системы - CHES 2012. Конспект лекций по информатике. 7428. Springer Berlin Heidelberg. С. 530–547. Дои:10.1007/978-3-642-33027-8_31. ISBN  978-3-642-33026-1.
  11. ^ Микчанчо, Даниэле (1998). «Кратчайший вектор в решетке трудно аппроксимировать с точностью до некоторой константы». В Proc. 39-й симпозиум по основам компьютерных наук: 92–98.
  12. ^ а б Любашевский, Вадим (01.01.2009). «Фиат-Шамир с прерываниями: приложения к подписям на основе решеток и факторинга». В Мацуи, Мицуру (ред.). Достижения в криптологии - ASIACRYPT 2009. Конспект лекций по информатике. 5912. Springer Berlin Heidelberg. С. 598–616. Дои:10.1007/978-3-642-10366-7_35. ISBN  978-3-642-10365-0.
  13. ^ а б c d е Любашевский, Вадим (2011). "Решетчатые подписи без лазеек". Цитировать журнал требует | журнал = (помощь)
  14. ^ а б c d е Чопра, Арджун (2017). «GLYPH: новая реализация схемы цифровой подписи GLP». Архив электронных отпечатков Международной ассоциации криптографических исследований. Архивировано из оригинал (PDF) 26 августа 2017 г.. Получено 26 августа 2017.
  15. ^ «Архив Cryptology ePrint: отчет 2013/838». eprint.iacr.org. Получено 2016-01-17.
  16. ^ «Архив Cryptology ePrint: отчет 2015/755». eprint.iacr.org. Получено 2016-01-17.
  17. ^ «Архив Cryptology ePrint: отчет 2013/383». eprint.iacr.org. Получено 2016-01-17.