Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Фон [ править ]

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

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

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

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

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

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

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

Генерация «малых» многочленов. [ редактировать ]

Сигнатура RLWE использует многочлены, которые считаются «маленькими» по отношению к мере, называемой « бесконечной нормой ». Бесконечная норма для многочлена просто по величине абсолютного значения коэффициентов многочлена , когда эти коэффициенты рассматриваются как целые числа в Z , а не Z д . [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 по модулю 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) должен быть выбран способом « ничего в рукаве », например, односторонним хешированием выходных данных генератора случайных чисел с истинным шумом (TRNG) или с использованием цифрового расширения хорошо известных математических констант, таких как пи или е. Все подписывающие и проверяющие подписи будут знать 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) отклонить подпись, в противном случае принять подпись как действительную.

Заметь:

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

= a (x) · y 1 (x) + z 2 (x) - e (x) · c (x)

= a (x) y 1 (x) + e (x) · c (x) + y 2 (x) - e (x) · c (x)

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

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

Дальнейшее развитие [ править ]

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

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

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

Ссылки [ править ]

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