Кольцевое обучение с подписью ошибок

Цифровые подписи — это средство защиты цифровой информации от преднамеренного изменения и аутентификации источника цифровой информации. Криптография с открытым ключом предоставляет богатый набор различных криптографических алгоритмов для создания цифровых подписей. Однако используемые в настоящее время первичные подписи с открытым ключом ( подписи RSA и эллиптические кривые) станут совершенно небезопасными, если ученые когда-нибудь смогут построить квантовый компьютер среднего размера . ^[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 была разработана Любашевским в его статье «Фиат-Шамир с прерываниями: приложения к подписям на основе решеток и факторингов». ^[12] и уточнен в «Решетчатых подписях без люков» в 2011 году. ^[13] Последовал ряд усовершенствований и вариантов. В этой статье освещается фундаментальная математическая структура сигнатур RLWE и следует оригинальная работа Любашевского и работа Гунейсу, Любашевского и Попплеманна ( GLP ). ^[10] Эта презентация основана на обновленной схеме GLP 2017 года под названием GLYPH. ^[14]

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

$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 ^н + 1. Возможны и другие варианты n, но соответствующие круговые полиномы более сложны или их безопасность не так хорошо изучена.

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

В сигнатуре RLWE используются полиномы, которые считаются «малыми» по отношению к мере, называемой « нормой бесконечности ». Норма бесконечности для многочлена — это просто наибольшее абсолютное значение коэффициентов многочлена, когда эти коэффициенты рассматриваются как целые числа от Z, а не от Z _q . ^[10] Алгоритм подписи будет создавать случайные полиномы, малые по отношению к определенной границе нормы бесконечности. Это легко сделать путем случайной генерации всех коэффициентов полинома (a ₀ , ..., 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]

Другие параметры

Следуя ГЛИФУ и как отмечалось выше, максимальная степень полиномов будет равна 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 ^н + 1. Наконец, a(x) будет случайно выбранным и фиксированным полиномом с коэффициентами из набора от { -(q-1)/2 до (q-1)/2 }. Полином a(x) следует выбирать по принципу « ничего в рукаве », например, одностороннее хеширование выходных данных генератора случайных чисел с истинным шумом (TRNG) или использование цифрового расширения хорошо известных математических констант, таких как пи или е. Все подписывающие и проверяющие подписи будут знать n, q, b, k, Φ(x), a(x) и β = bk.

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

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

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

Полиномы s(x) и e(x) служат закрытым ключом, а t(x) — соответствующим открытым ключом. Безопасность этой схемы подписи основана на следующей проблеме. Учитывая многочлен t(x), найдите малые многочлены f ₁ (x) и f ₂ (x) такие, что: a(x) · f ₁ (x) + f ₂ (x) = t(x)

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

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

Следуя ГЛИФУ, ^[14] Чтобы подписать сообщение m, выраженное в виде битовой строки, подписывающий объект делает следующее:

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

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

Следуя ГЛИФУ, ^[14] Чтобы проверить сообщение m, выраженное в виде битовой строки, проверяющий объект должен обладать открытым ключом подписавшего (t(x)), подписью (c(x), z ₁ (x), z ₂ (x)), а также сообщение м. Верификатор делает следующее:

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

Обратите внимание:

a(x)·z ₁ (x) + z ₂ (x) - t(x)c(x) = a(x)·[s(x)·c(x) + y ₁ (x)] + z ₂ (x) - [a(x)·s(x) + e(x)]c(x)

= a(x) y ₁ (x) + z ₂ (x) - e(x) c(x)

= a(x)y ₁ (x) + e(x)·c(x) + y ₂ (x) - e(x)·c(x)

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д Дамен-Люисье, Сабина. «ETSI — квантово-безопасная криптография» . ЕТСИ . Проверено 5 июля 2015 г.
^ Шах, Агам. «Заявление IBM о прорыве в области квантовых вычислений» . Архивировано из оригинала 23 сентября 2015 г. Проверено 1 июня 2015 г.
^ Маркофф, Джон (04 марта 2015 г.). «Исследователи сообщают о важной вехе в разработке квантового компьютера» . Нью-Йорк Таймс . ISSN 0362-4331 . Проверено 5 июля 2015 г.
^ Бекман, Дэвид; Чари, Амалавоял Н.; Девабхактуни, Шрикришна; Прескилл, Джон (1996). «Эффективные сети для квантового факторинга». Физический обзор А. 54 (2): 1034–1063. arXiv : Quant-ph/9602016 . Бибкод : 1996PhRvA..54.1034B . дои : 10.1103/PhysRevA.54.1034 . ISSN 1050-2947 . ПМИД 9913575 . S2CID 2231795 .
^ Смолин, Джон А.; Смит, Грэм; Варго, Александр (11 июля 2013 г.). «Чрезмерное упрощение квантового факторинга». Природа . 499 (7457): 163–165. arXiv : 1301.7007 . Бибкод : 2013Natur.499..163S . дои : 10.1038/nature12290 . ISSN 0028-0836 . ПМИД 23846653 . S2CID 4422110 .
^ Jump up to: ^а ^б "Введение" . pqcrypto.org . Проверено 5 июля 2015 г.
^ «Проблема обучения с ошибками» (PDF) . www.cims.nyu.edu . Проверено 24 мая 2015 г.
^ Любашевский Вадим; Пейкерт, Крис; Регев, Одед (2010). «Об идеальных решетках и обучении с ошибками в кольцах». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2010 . Конспекты лекций по информатике. Том. 6110. стр. 1–23. CiteSeerX 10.1.1.297.6108 . дои : 10.1007/978-3-642-13190-5_1 . ISBN 978-3-642-13189-9 .
^ «Что означает «предостерегающая история» GCHQ для решетчатой криптографии?» . www.cc.gatech.edu . Архивировано из оригинала 6 июля 2015 г. Проверено 5 июля 2015 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Гюнейсу, Тим; Любашевский Вадим; Пёппельманн, Томас (2012). «Практическая решетчатая криптография: схема подписи для встраиваемых систем». В Пруффе, Эммануэль; Шаумонт, Патрик (ред.). Криптографическое оборудование и встраиваемые системы – CHES 2012 . Конспекты лекций по информатике. Том. 7428. Шпрингер Берлин Гейдельберг. стр. 530–547. дои : 10.1007/978-3-642-33027-8_31 . ISBN 978-3-642-33026-1 .
^ Миччанчо, Даниэле (1998). «Кратчайший вектор в решетке трудно аппроксимировать с точностью до некоторой константы» . В Proc. 39-й симпозиум по основам информатики : 92–98.
^ Jump up to: ^а ^б Любашевский, Вадим (01.01.2009). «Фиат-Шамир с прерываниями: приложения к подписям на основе решетки и факторинга». В Мацуи, Мицуру (ред.). Достижения в криптологии – ASIACRYPT 2009 . Конспекты лекций по информатике. Том. 5912. Шпрингер Берлин Гейдельберг. стр. 598–616. дои : 10.1007/978-3-642-10366-7_35 . ISBN 978-3-642-10365-0 .
^ Jump up to: ^а ^б ^с ^д ^и Любашевский, Вадим (2011). «Решетчатые подписи без люков» . Архив электронной печати по криптологии .
^ Jump up to: ^а ^б ^с ^д ^и Чопра, Арджун (2017). «ГЛИФ: новый вариант схемы цифровой подписи GLP» (PDF) . Архив электронных изданий Международной ассоциации криптографических исследований . Архивировано из оригинала 28 августа 2017 года . Проверено 26 августа 2017 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
^ «Архив криптологии ePrint: отчет 2013/838» . eprint.iacr.org . Проверено 17 января 2016 г.
^ «Архив криптологии ePrint: отчет 2015/755» . eprint.iacr.org . Проверено 17 января 2016 г.
^ «Архив криптологии ePrint: отчет 2013/383» . eprint.iacr.org . Проверено 17 января 2016 г.

Внешние ссылки

[:2-1] Jump up to: ^а ^б ^с ^д Дамен-Люисье, Сабина. «ETSI — квантово-безопасная криптография» . ЕТСИ . Проверено 5 июля 2015 г.

[2] Шах, Агам. «Заявление IBM о прорыве в области квантовых вычислений» . Архивировано из оригинала 23 сентября 2015 г. Проверено 1 июня 2015 г.

[3] Маркофф, Джон (04 марта 2015 г.). «Исследователи сообщают о важной вехе в разработке квантового компьютера» . Нью-Йорк Таймс . ISSN 0362-4331 . Проверено 5 июля 2015 г.

[4] Бекман, Дэвид; Чари, Амалавоял Н.; Девабхактуни, Шрикришна; Прескилл, Джон (1996). «Эффективные сети для квантового факторинга». Физический обзор А. 54 (2): 1034–1063. arXiv : Quant-ph/9602016 . Бибкод : 1996PhRvA..54.1034B . дои : 10.1103/PhysRevA.54.1034 . ISSN 1050-2947 . ПМИД 9913575 . S2CID 2231795 .

[5] Смолин, Джон А.; Смит, Грэм; Варго, Александр (11 июля 2013 г.). «Чрезмерное упрощение квантового факторинга». Природа . 499 (7457): 163–165. arXiv : 1301.7007 . Бибкод : 2013Natur.499..163S . дои : 10.1038/nature12290 . ISSN 0028-0836 . ПМИД 23846653 . S2CID 4422110 .

[:4-6] Jump up to: ^а ^б "Введение" . pqcrypto.org . Проверено 5 июля 2015 г.

[7] «Проблема обучения с ошибками» (PDF) . www.cims.nyu.edu . Проверено 24 мая 2015 г.

[8] Любашевский Вадим; Пейкерт, Крис; Регев, Одед (2010). «Об идеальных решетках и обучении с ошибками в кольцах». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2010 . Конспекты лекций по информатике. Том. 6110. стр. 1–23. CiteSeerX 10.1.1.297.6108 . дои : 10.1007/978-3-642-13190-5_1 . ISBN 978-3-642-13189-9 .

[9] «Что означает «предостерегающая история» GCHQ для решетчатой криптографии?» . www.cc.gatech.edu . Архивировано из оригинала 6 июля 2015 г. Проверено 5 июля 2015 г.

[:0-10] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Гюнейсу, Тим; Любашевский Вадим; Пёппельманн, Томас (2012). «Практическая решетчатая криптография: схема подписи для встраиваемых систем». В Пруффе, Эммануэль; Шаумонт, Патрик (ред.). Криптографическое оборудование и встраиваемые системы – CHES 2012 . Конспекты лекций по информатике. Том. 7428. Шпрингер Берлин Гейдельберг. стр. 530–547. дои : 10.1007/978-3-642-33027-8_31 . ISBN 978-3-642-33026-1 .

[11] Миччанчо, Даниэле (1998). «Кратчайший вектор в решетке трудно аппроксимировать с точностью до некоторой константы» . В Proc. 39-й симпозиум по основам информатики : 92–98.

[:5-12] Jump up to: ^а ^б Любашевский, Вадим (01.01.2009). «Фиат-Шамир с прерываниями: приложения к подписям на основе решетки и факторинга». В Мацуи, Мицуру (ред.). Достижения в криптологии – ASIACRYPT 2009 . Конспекты лекций по информатике. Том. 5912. Шпрингер Берлин Гейдельберг. стр. 598–616. дои : 10.1007/978-3-642-10366-7_35 . ISBN 978-3-642-10365-0 .

[:1-13] Jump up to: ^а ^б ^с ^д ^и Любашевский, Вадим (2011). «Решетчатые подписи без люков» . Архив электронной печати по криптологии .

[:3-14] Jump up to: ^а ^б ^с ^д ^и Чопра, Арджун (2017). «ГЛИФ: новый вариант схемы цифровой подписи GLP» (PDF) . Архив электронных изданий Международной ассоциации криптографических исследований . Архивировано из оригинала 28 августа 2017 года . Проверено 26 августа 2017 г. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[15] «Архив криптологии ePrint: отчет 2013/838» . eprint.iacr.org . Проверено 17 января 2016 г.

[16] «Архив криптологии ePrint: отчет 2015/755» . eprint.iacr.org . Проверено 17 января 2016 г.

[17] «Архив криптологии ePrint: отчет 2013/383» . eprint.iacr.org . Проверено 17 января 2016 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]