Кольцевое обучение с сигнатурой ошибок

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

Фон

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

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

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

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

Первая подпись на основе RLWE была разработана Любашевским в его статье «Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures» [12] и усовершенствована в «Lattice Signatures Without Trapdoors» в 2011 году. [13] За этим последовало несколько усовершенствований и вариантов. В этой статье освещается фундаментальная математическая структура подписей RLWE, и она следует оригинальной работе Любашевского и работе Гунейсу, Любашевского и Попплемана (GLP). [10] Эта презентация основана на обновлении схемы GLP 2017 года под названием GLYPH. [14]

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

а ( х ) = а 0 + а 1 х + а 2 х 2 + … + а н − 3 х н − 3 + а н − 2 х н − 2 + а н − 1 х н − 1 {\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}

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

Генерация «маленьких» полиномов.

Сигнатура RLWE использует полиномы, которые считаются «малыми» по отношению к мере, называемой « нормой бесконечности ». Норма бесконечности для полинома — это просто наибольшее абсолютное значение коэффициентов полинома, когда эти коэффициенты рассматриваются как целые числа в Z, а не Z q . [10] Алгоритм подписи создаст случайные полиномы, которые малы по отношению к определенной границе нормы бесконечности. Это легко сделать, случайным образом сгенерировав все коэффициенты полинома (a 0 , ..., a n-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] Коэффициенты этих многочленов будут из поля F q , где q — нечетное простое число, сравнимое с 1 mod 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 n + 1. Наконец, a(x) будет случайно выбранным и фиксированным полиномом с коэффициентами из набора { -(q-1)/2 до (q-1)/2 }. Полином a(x) должен быть выбран способом " Nothing Up My Sleeve ", например, односторонним хешированием выходных данных генератора случайных чисел с истинным шумом (TRNG) или с использованием цифрового расширения известных математических констант, таких как pi или e. Все подписывающие и проверяющие подписи будут знать n, q, b, k, Φ(x), a(x) и β = bk.

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

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

  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) найдите малые полиномы f 1 (x) и f 2 (x) такие, что: a(x)·f 1 (x) + f 2 (x) = t(x)

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

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

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

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

Проверка подписи

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

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

Обратите внимание, что:

а(х)·z 1 (х) + z 2 (х) - t(х)с(х) = а(х)·[s(х)·c(х) + y 1 (х)] + z 2 (х) - [а(х)·s(х) + е(х)]с(х)

= а(х)·y1 ( х) + z2 ( х) - е(х)·с(х)

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

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

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

Дальнейшее развитие событий

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

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

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

Ссылки

  1. ^ abcd Дамен-Люиссье, Сабина. «ETSI - Квантово-безопасная криптография». ЕТСИ . Проверено 5 июля 2015 г.
  2. ^ Шах, Агам. "Заявка IBM о прорыве в области квантовых вычислений". Архивировано из оригинала 2015-09-23 . Получено 2015-06-01 .
  3. ^ Маркофф, Джон (2015-03-04). «Исследователи сообщают о важной вехе в разработке квантового компьютера». The New York Times . ISSN  0362-4331 . Получено 2015-07-05 .
  4. ^ Бекман, Дэвид; Чари, Амалавойал Н.; Девабхактуни, Шрикришна; Прескилл, Джон (1996). «Эффективные сети для квантовой факторизации». Physical Review A. 54 ( 2): 1034– 1063. arXiv : quant-ph/9602016 . Bibcode : 1996PhRvA..54.1034B. doi : 10.1103/PhysRevA.54.1034. ISSN  1050-2947. PMID  9913575. S2CID  2231795.
  5. ^ Смолин, Джон А.; Смит, Грэм; Варго, Александр (11 июля 2013 г.). «Упрощение квантовой факторизации». Nature . 499 (7457): 163– 165. arXiv : 1301.7007 . Bibcode :2013Natur.499..163S. doi :10.1038/nature12290. ISSN  0028-0836. PMID  23846653. S2CID  4422110.
  6. ^ ab "Введение". pqcrypto.org . Получено 2015-07-05 .
  7. ^ "Проблема обучения с ошибками" (PDF) . www.cims.nyu.edu . Получено 24.05.2015 .
  8. ^ Любашевский, Вадим; Пейкерт, Крис; Регев, Одед (2010). «Об идеальных решетках и обучении с ошибками в кольцах». В Gilbert, Henri (ред.). Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp.  1– 23. CiteSeerX 10.1.1.297.6108 . doi :10.1007/978-3-642-13190-5_1. ISBN  978-3-642-13189-9.
  9. ^ «Что означает «предостерегающая история» GCHQ для решетчатой ​​криптографии?». www.cc.gatech.edu . Архивировано из оригинала 2015-07-06 . Получено 2015-07-05 .
  10. ^ abcdefghi Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems". В Prouff, Emmanuel; Schaumont, Patrick (ред.). Cryptographic Hardware and Embedded Systems – CHES 2012. Lecture Notes in Computer Science. Vol. 7428. Springer Berlin Heidelberg. pp.  530– 547. doi :10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1.
  11. ^ Micciancio, Daniele (1998). «Кратчайший вектор в решетке трудно аппроксимировать с точностью до некоторой константы». В Proc. 39th Symposium on Foundations of Computer Science : 92–98 .
  12. ^ ab Любашевский, Вадим (2009-01-01). "Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures". В Matsui, Mitsuru (ред.). Advances in Cryptology – ASIACRYPT 2009. Lecture Notes in Computer Science. Vol. 5912. Springer Berlin Heidelberg. pp.  598– 616. doi :10.1007/978-3-642-10366-7_35. ISBN 978-3-642-10365-0.
  13. ^ abcde Любашевский, Вадим (2011). "Решетчатые подписи без лазеек". Архив Cryptology ePrint .
  14. ^ abcde Chopra, Arjun (2017). "GLYPH: A New Instantiation of the GLP Digital Signature Scheme" (PDF) . Архив электронной печати Международной ассоциации криптографических исследований . Архивировано из оригинала 28 августа 2017 года . Получено 26 августа 2017 года .{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )
  15. ^ "Архив Cryptology ePrint: Отчет 2013/838". eprint.iacr.org . Получено 17.01.2016 .
  16. ^ "Архив Cryptology ePrint: Отчет 2015/755". eprint.iacr.org . Получено 2016-01-17 .
  17. ^ "Архив Cryptology ePrint: Отчет 2013/383". eprint.iacr.org . Получено 17.01.2016 .
Получено с "https://en.wikipedia.org/w/index.php?title=Кольцевое_обучение_с_ошибками_подписью&oldid=1245868531"