Применение задачи обучения с ошибками в постквантовой криптографии

Размещено на http://www.allbest.ru/

ФГБОУ ВО «Оренбургский государственный университет»

ПРИМЕНЕНИЕ ЗАДАЧИ ОБУЧЕНИЯ С ОШИБКАМИ В ПОСТКВАНТОВОЙ КРИПТОГРАФИИ

Фадеев С.В.

Обучение с ошибками (LWE) - концепция, подразумевающая намеренное введение ошибки в простые вычисления с целью затруднения их решения известными методами. Была представлена Одедом Регев в 2005 году и сразу вызвала интерес как основа для построения криптографических средств, устойчивых к криптоанализу с использованием квантовых компьютеров. Такая устойчивость обусловлена сведением задачи обучения с ошибками к проблеме решеток, являющейся одним из основных направлений постквантовой криптографии.

Описание задачи

Определяется параметр , модуль и распределение вероятности ошибки ч на .

Пусть -- соотношение векторов на , полученное случайным выбором вектора , выбором ошибки в соответствии с ч и полученным выражением

, (1)

где

(2)

и сложение производится по модулю q. Алгоритм решает задачу , если для любого секрета , имея произвольное число независимых соотношений из он с высокой вероятностью выдаст .

Пример: найти вектор .

, (3)

где каждое уравнение верно до некоторой ошибки . Ответ: . Если бы в примере отсутствовала ошибка, можно было бы восстановить за полиномиальное время. Например, алгоритм исключения Гаусса принимает линейные комбинации уравнений, тем самым усиливая погрешность до неуправляемых уровней, не оставляя по существу никакой информации в полученных уравнениях.

Отметим, что можно рассматривать LWE как проблему декодирования из случайных линейных кодов или как задачу случайного ограниченного расстояния для декодирования. Кроме того, было доказано, что задача обучения с ошибками может быть сведена к задачам, относящимся к теории решеток, являющихся NP-сложными, что сразу повлекло разработку криптографических приложений.

Теория решеток

Решеткой называется множество точек в -мерном пространстве с периодической структурой, заданное -линейно независимыми векторами , называемыми базисом решетки:

. (4)

Криптосистемы на решетках строятся исходя из предположения, что не существует полиномиального квантового алгоритма, который аппроксимирует решетчатые задачи с точностью до полиномиальных факторов.

Базис может быть представлен матрицей , имеющей базисные векторы в виде столбцов. Используя матричную запись, решетка, порожденная матрицей , может быть определена как

, (5)

где - обычное умножение матрицы на вектор.

Если U - унимодулярная матрица (т. е. целочисленная квадратная матрица с определителем ± 1), то B и BU порождают одну и ту же решетку. Т.о., любая решетка допускает множество оснований, и этот факт лежит в основе многих криптографических приложений. Определителем решетки является абсолютная величина определителя базисной матрицы:

. (6)

Значение детерминанта не зависит от выбора базиса и геометрически соответствует обратному значению плотности точек решетки в .

Проблемы, основанные на решетках:

- Задача Нахождения Кратчайшего Вектора (SVP): заданный базис решетки, найти самый короткий ненулевой вектор в .

- Ближайшая Векторная Задача (CVP): заданный решеточный базис и целевой вектор (не обязательно в решетке), найдите ближайшую к точку решетки.

- Задача Нахождения Независимого Вектора (SIVP): задан базис решетки , найти линейно независимых решеточных вектора

, (7)

где ),

минимизируя величину

(8)

В криптографии на основе решеток обычно рассматривается аппроксимационный вариант этих задач, который обозначается дополнительным индексом г, указывающим коэффициент аппроксимации. Например, в SVPг цель состоит в том, чтобы найти вектор, норма которого не более, чем в г раз больше, чем у кратчайшего ненулевого вектора.

В 2005 году Одед Регев доказал, что задача обучения с ошибками сводится к модификациям задачи нахождения кратчайшего вектора и задачи нахождения независимого вектора, а в 2009 Крис Пейкер смог свести ее к одной задаче нахождения кратчайшего вектора в отношении стойкости к классическому и квантовому криптоанализу.

Квантовый криптоанализ

Квантовый криптоанализ - взлом криптосистем, подразумевающий использование для этих целей квантового компьютера и квантовых алгоритмов. Квантовый компьютер, ввиду своего быстродействия, позволяет решать множество вычислительно сложных задач за приемлемое время, что стимулировало поиск криптосистем с доказанной математической стойкостью.

В основе работы квантового компьютера лежат принципы квантовой механики, в частности квантовая суперпозиция - понятие, подразумевающее нахождение системы в некотором состоянии, объединяющем несколько взаимоисключающих состояний.

Математически суперпозиция представляется как сумма произведений базисных состояний на их комплексные амплитуды:

, (9)

где суперпозиция;

комплексная амплитуда;

базисное состояние.

Квантовый параллелизм: при вычислении суперпозиции осуществляются операции одновременно над всеми базисными состояниями. Таким образом, обеспечивается значительный рост производительности систем, построенных на квантовых принципах. Некоторые трудности возникают при извлечении данных из базисных состояний. Ввиду этого в архитектуре квантовых вычислительных систем выделяют два представления, в которых может находиться квантовое состояние:

- операция - это последовательность унитарных операций (квантовых вентилей), осуществляемых над состоянием;

- измерение - это присвоение состоянию суперпозиции некоторого его базисного состояния в соответствии с вероятностью, определяемой комплексной амплитудой.

Квантовая запутанность - это явление наличия между парой элементарных частиц определенной связи: обе находятся в противоположных состояниях при выходе из суперпозиции, при измерении одной из них соответственно изменяется и другая, независимо от расстояния между ними.

Основой квантовых компьютеров являются кубиты - разряды для хранения информации, принимающие значения: одно из двух противоположных или их суперпозицию, то есть:

, (10)

где .

Применение кубитов и обуславливает высокую производительность (экспоненциальную) квантовых компьютеров, так как использование L таких кубитов в регистре равносильно наличию в системе 2^L классических состояний.

Значительными препятствиями в разработке квантовых систем являются некоторые слабо изученные механизмы квантовой механики, такие, например, как редукция фон Неймана - мгновенное изменение квантового состояния объекта, происходящее при измерении. Таким образом, создаются множественные ошибки в регистрах. Противодействием этому является применение охлаждения жидким гелием, что существенно усложнит конструкцию и затруднит эксплуатацию перспективных квантовых компьютеров. Большую роль играет и организация управления каждым кубитом индивидуально. Подобные задачи требуют прецизионно выполненного управляющего компонента. Эти, а также многие другие проблемы, затрудняют масштабируемость многих проектов квантовых компьютеров. квантовый компьютер криптографический ошибка

Технологиями, пригодными для квантовых компьютеров на данный момент, считаются:

1) твердотельные квантовые точки на полупроводниках: в качестве логических кубитов используются зарядовые состояния или направление электронного, или ядерного спина, управление внешними потенциалами или лазерным импульсом;

2) сверхпроводящие элементы: присутствие/отсутствие куперовской пары в определённой области пространства, управление: внешний потенциал или магнитный поток;

3) ионы в вакуумных ловушках Пауля или атомы в оптических ловушках, в качестве логических кубитов используются основное или возбуждённое состояния внешнего электрона в ионе, управлением служат колебательные моды ионного ансамбля или лазерные импульсы;

4) смешанные технологии: использование заранее приготовленных запутанных состояний фотонов для управления атомными ансамблями или как элементы управления классическими вычислительными сетями.

За последнее время было представлено значительное количество новых разработок.

1) 14 июля 2017 года в Гарварде был представлен 51 кубитный квантовый компьютер разработки группы Михаила Лукина, работающий на основе применения холодных атомов рубидия в случайном состоянии в оптических ловушках.

2) 13 ноября 2017 года представлен 50 кубитный компьютер IBM. Квантовые эффекты обеспечиваются использованием сверхпроводников, время устойчивой суперпозиции составляет до 90 миллисекунд.

3) 29 ноября 2017 года университет Мерилэнда представил 53 кубитный компьютер Кристофера Монро, применяющий ионы иттербия-171 в оптических ловушках, используя в качестве значений направления их спинов

4) 6 марта 2018 года представлен 72 кубитный компьютер компании Google, основанный на сверхпроводящих элементах, выстроенных в две противолежащие матрицы 6*6. Подчеркивается рекордно высокая надежность: вероятность возникновения ошибки однокубитного вентиля в 0,1%, двухкубитного - в 0,6%.

5) Компания Intel, совместно с Нидерландами, работает в двух направлениях: в январе 2018 года представлен 49 кубитный чип Tangle Lake, на сверхпроводящих элементах; в июне 2018 представлен чип на спиновых кубитах рекордно малого размера - до 50 нм, использующий технологии, производные от производства транзисторов.

Уже сейчас квантовые компьютеры позволяют работать в направлениях квантовой химии и изучения квантовой механики, криптоанализ же требует значений разрядности квантовых чипов в несколько сотен тысяч кубитов, но при этом она является одной из ключевых задач создания квантовых компьютеров, что выражается в объемах спонсирования программ со стороны соответствующих управлений государств. Экспертные оценки, с учетом доказанной в настоящее время возможности масштабируемости квантовых компьютеров, позволяют предполагать появление таких компьютеров к середине-концу следующего десятилетия. Показательным также является урезание в этой связи расходов на переход инфраструктуры с RSA на считавшуюся перспективной эллиптическую криптографию.

Квантовый компьютер не способен решать новые типы задач, отличные от решаемых классическими компьютерами, но, благодаря применению кубитов, достигнут существенный рост производительности вычислений обычных. Это позволяет проектировать алгоритмы, в наибольшей степени использующих данную особенность.

Такие перспективы стимулировали появление квантовых алгоритмов, одним из которых являлся алгоритм Шора - алгоритм решения задачи факторизации, а затем и задачи дискретного логарифмирования (основных проблем, на которых базируется криптография с открытым ключом). Представленный в 1994 году, он спровоцировал интерес к развитию отрасли. Будучи основан на квантовом преобразовании Фурье (расширение дискретного преобразования Фурье на использование квантового компьютера), он стал первым квантовым алгоритмом криптоанализа. В 2001 году была практически продемонстрирована возможность факторизации числа 15 на 7 кубитном компьютере этим алгоритмом.

Последовавший затем алгоритм Гловера, осуществляющий поиск в базах данных за квадратичное время, продемонстрировал возможность взлома и симметричных криптосистем.

Применение проблемы обучения с ошибками в ЭЦП

Проблема LWE находит применение в конструировании криптоалгоритмов симметричного и ассиметричного шифрования, протоколов распределения ключей, хэш-функций и схем электронно-цифровой подписи. Схема ЭЦП на этой проблеме была впервые представлена Любашевским в 2011 году и пережила несколько модернизаций.

Алгоритм:

Операции производятся в конечном поле , где нечетное простое число. Случайным образом задается полином вида: .

Генерация ключей:

1) создаются два полинома, служащие закрытым ключом, с коэффициентами, выбранными равномерно из множества .

2) вычисляется открытый ключ:

(11)

Создание подписи:

1) создаются два полинома, с коэффициентами, выбранными равномерно из множества .

2) вычисляется:

. (12)

3) переводится в битовое представление .

4) вычисляется хэш-функция , принимающая на вход битовую строку, выдающую полином из коэффициэнтов, из которых ненулевые и меньше значения диапазона выбора коэффициентов полиномов.

. (13)

5) вычисляется:

. (14)

6) вычисляется:

= · c (x) + . (15)

До тех пор, пока равномерные нормы (т.е., значение наибольшего коэффициента полинома) и ? в (т.е. разность диапазона выборки и числа ненулевых коэффициентов), осуществляется переход к первому шагу.

Под подписью понимается тройка многочленов: , и .

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

1) проверяется, что равномерные нормы и ? в.

2) вычисляется

+ (16)

3) переводится в битовое представление

4) вычисляется:

. (17)

Если - подпись действительна и можно удостовериться в целостности, авторстве и неотказуемости от авторства, если нет - недействительна.

В сравнении с другими постквантовыми алгоритмами ЭЦП (основанными на хэш-функциях, кодах исправления ошибок и многомерных квадратичных системах), схемы на основе задачи обучения с ошибками демонстрируют малые размеры открытого ключа при относительно небольшой длине подписи. Множество приложений, математическая доказуемость, преимущества перед другими ЭЦП и приемлемость создания реализаций позволяют расценивать ЭЦП на основе задачи обучения с ошибками как очень перспективное направление.

Список литературы

1 Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring // SFCS '94 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, November 20 - 22, 1994, IEEE Computer Society Press. 1994 - С.124-134.

2 Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen, Post-Quantum Cryptography / Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen; Springer-Verlag. Berlin, 2009. C. 245. ISBN: 978-3-540-88701-0.

3 Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography// STOC '05 Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, Baltimore, MD, USA -- May 22 - 24, 2005, - С. 84-93. - ISBN:1-58113-960-8.

4 Oded Regev, The Learning with Errors Problem// 2012 IEEE 27th Conference on Computational Complexity (2010), - Boston, Massachusetts, June 9-12, 2010, - ISBN: 978-0-7695-4060-3.

5 Vadim Lyubashevsky, Chris Peikert, Oded Regev, A Toolkit for Ring-LWE Cryptography// Extended abstract appears in Eurocrypt 2013, Springer, Berlin, Heidelberg, - 16 May 2013, - C. 35-54, - ISBN 978-3-642-38347-2.

6 Cryptology ePrint Archive [Электронный ресурс].: Johannes Buchmann, Carlos Coronado, Martin Doring, Daniela Engelbert, Christoph Ludwig, Raphael Overbeck, Arthur Schmidt, Ulrich Vollmer, Ralf-Philipp Weinmann, Post-Quantum Signatures, 2004 - Режим доступа: http://eprint.iacr.org/2004/297.pdf/. 20.09.2018.

Размещено на Allbest.ru