Просмотр кода страницы Подпись на основе обучения с ошибками в кольце

'''Подпись при обучении с ошибками в кольце''' ({{lang-en|Ring learning with errors signature}}) — один из классов [[Криптосистема с открытым ключом|криптосистем с открытым ключом]], основанный на задаче [[обучение с ошибками в кольце|обучения с ошибками в кольце]]<ref name=":6">{{статья|автор=Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded|заглавие=On ideal lattices and learning with errors over rings|год=2010|язык=en|издание=In Proc. Of EUROCRYPT, Volume 6110 of LNCS|тип=journal|страницы=1—23|citeseerx=10.1.1.297.6108}}</ref>, который заменяет используемые алгоритмы подписи [[RSA]] и [[ECDSA]]. В течение последнего десятилетия проводились активные исследования по созданию криптографических алгоритмов, которые остаются безопасными, даже если у злоумышленника есть ресурсы [[Квантовый компьютер|квантового компьютера]]<ref name=":2" /><ref name=":4">{{Cite web|url=http://pqcrypto.org/|title=Introduction|website=pqcrypto.org|accessdate=2015-07-05|archive-date=2011-07-17|archive-url=https://web.archive.org/web/20110717174032/http://pqcrypto.org/|deadlink=no}}</ref>. Подпись при обучении с ошибками в кольце относится к числу [[пост-квантовая криптография|пост-квантовых]]<ref name=":2" /><ref name=":4" /> подписей с наименьшим открытым ключом и размерами подписи. Использование общей проблемы [[Обучение с ошибками|обучения с ошибками]] в криптографии было введено Одедом Регевым в 2005 году и послужило источником нескольких криптографических разработок<ref>{{Cite web|url=http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|title=The Learning with Errors Problem|website=www.cims.nyu.edu|accessdate=2015-05-24|archive-date=2015-09-23|archive-url=https://web.archive.org/web/20150923203529/http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf|deadlink=no}}</ref>. Основоположники криптографии при [[обучение с ошибками в кольце|обучении с ошибками в кольце]] (англ. Ring learning with errors, RLWE), считают, что особенностью этих алгоритмов, основанных на обучении с ошибками, является доказуемое сокращение известных сложных задач<ref name=":6" /><ref>{{Cite web|url=http://www.cc.gatech.edu/~cpeikert/soliloquy.html|title=What does GCHQ's "cautionary tale" mean for lattice cryptography?|website=www.cc.gatech.edu|accessdate=2015-07-05|archiveurl=https://web.archive.org/web/20150706150530/http://www.cc.gatech.edu/~cpeikert/soliloquy.html|archivedate=2015-07-06}}</ref>. Данная подпись имеет доказуемое сокращение до [[Задачи теории решёток|задачи нахождения кратчайшего вектора]] в области [[Криптография на решётках|криптографии на решётках]]<ref name=":0">{{книга |заглавие=Cryptographic Hardware and Embedded Systems – CHES 2012 |doi=10.1007/978-3-642-33027-8_31 |часть=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems |страницы=530—547 |том=7428 |серия=Lecture Notes in Computer Science |isbn=978-3-642-33026-1 |издательство=[[Springer Science+Business Media|Springer Berlin Heidelberg]] |ref=Güneysu |язык=en |автор=Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas |ответственный=Prouff, Emmanuel; Schaumont, Patrick |год=2012}}</ref>. Это означает, что если можно обнаружить атаку на криптосистему RLWE, то целый класс предполагаемых сложных вычислительных проблем будет иметь решение<ref>{{статья|ссылка=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.7305|автор=Micciancio, Daniele|заглавие=The shortest vector in a lattice is hard to approximate to within some constant|год=1998|язык=en|издание=In Proc. 39th Symposium on Foundations of Computer Science|тип=journal|страницы=92—98|archivedate=2015-07-05|archiveurl=https://web.archive.org/web/20150705181513/http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.7305}}</ref>. Первая подпись на основе RLWE была разработана Вадимом Любашевским<ref name=":5">{{книга |издательство=[[Springer Science+Business Media|Springer Berlin Heidelberg]] |isbn=978-3-642-10365-0 |страницы=598—616 |серия=Lecture Notes in Computer Science |doi=10.1007/978-3-642-10366-7_35 |заглавие=Advances in Cryptology – ASIACRYPT 2009 |том=5912 |часть=Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures |ref=Lyubashevsky |язык=und |автор=Lyubashevsky, Vadim |ответственный=Matsui, Mitsuru |день=1 |месяц=1 |год=2009}}</ref> и уточнена в 2011 году<ref name=":1">{{статья|ссылка=http://eprint.iacr.org/2011/537|автор=Lyubashevsky, Vadim|заглавие=Lattice Signatures Without Trapdoors|год=2011|язык=und|archivedate=2016-09-03|archiveurl=https://web.archive.org/web/20160903120542/http://eprint.iacr.org/2011/537}}</ref>. Данная статья освещает фундаментальные математические основы RLWE и основана на схеме под названием GLYPH<ref name=":3">{{Cite web|url=https://eprint.iacr.org/2017/766.pdf|title=GLYPH: A New Instantiation of the GLP Digital Signature Scheme|first=Arjun|last=Chopra|website=International Association of Cryptographic Research eprint Archive|date=2017|archive-url=https://web.archive.org/web/20170828012937/https://eprint.iacr.org/2017/766.pdf|archive-date=2017-08-28|access-date=2017-08-26|deadlink=no}}</ref>.

== Предпосылки ==
Цифровая [[Электронная подпись|подпись]] является средством защиты информации и средством проверки подлинности источника информации. [[Криптография с открытым ключом]] предоставляет богатый набор различных криптографических алгоритмов для создания цифровых подписей. Тем не менее, подписи с открытым ключом, используемые в настоящее время, станут совершенно небезопасными после появления квантовых компьютеров<ref name=":2">{{Cite web|title = ETSI - Quantum-Safe Cryptography|url = http://www.etsi.org/technologies-clusters/technologies/quantum-safe-cryptography|website = ETSI|accessdate = 2015-07-05|first = Sabine|last = Dahmen-Lhuissier|archive-date = 2015-06-21|archive-url = https://web.archive.org/web/20150621013126/http://www.etsi.org/technologies-clusters/technologies/quantum-safe-cryptography|deadlink = no}}</ref><ref>{{Cite web|title = Quantum computing breakthrough claim from IBM|url = http://www.cio.co.uk/news/r-and-d/quantum-computing-breakthrough-claim-from-ibm-3609914/|accessdate = 2015-06-01|first = Agam|last = Shah|archive-date = 2015-09-23|archive-url = https://web.archive.org/web/20150923203728/http://www.cio.co.uk/news/r-and-d/quantum-computing-breakthrough-claim-from-ibm-3609914/|deadlink = no}}</ref><ref>{{Cite news|title = Researchers Report Milestone in Developing Quantum Computer|url = https://www.nytimes.com/2015/03/05/science/quantum-computing-nature-google-uc-santa-barbara.html|newspaper = The New York Times|date = 2015-03-04|issn = 0362-4331|first = John|last = Markoff|archivedate = 2019-08-26|archiveurl = https://web.archive.org/web/20190826001237/https://www.nytimes.com/2015/03/05/science/quantum-computing-nature-google-uc-santa-barbara.html|access-date = 2019-11-08}}</ref>.Потому как даже относительно небольшой квантовый компьютер, способный обрабатывать только лишь десять тысяч битов информации, сможет легко взломать все широко используемые алгоритмы [[шифрование с открытым ключом|шифрования с открытым ключом]], используемые для защиты конфиденциальности и [[цифровая подпись|цифровой подписи]] в [[Интернет]]е<ref name=":2" /><ref>{{статья |заглавие=Efficient Networks for Quantum Factoring |издание=[[Physical Review|Physical Review A]] |issn=1050-2947 |страницы=1034—1063 |том=54 |номер=2 |doi=10.1103/PhysRevA.54.1034 |arxiv=quant-ph/9602016 |bibcode=1996PhRvA..54.1034B |язык=en |автор=Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John |год=1996 |тип=journal}}</ref>. [[RSA]], как один из наиболее широко используемых алгоритмов с открытым ключом для создания [[цифровая подпись|цифровых подписей]], также становится уязвимым благодаря квантовым компьютерам, так как его безопасность основана на классической сложности задач факторизации{{sfn|Bakhtiari, Maarof|2012|p=175}} . А квантовый компьютер, обладающий примерно 6n [[кубит]]ами памяти и способный выполнять [[алгоритм Шора]], легко может произвести факторизацию произведения двух n-разрядных простых чисел, а также взломать цифровые подписи на основе задач [[дискретный логарифм|дискретного логарифма]] и [[Эллиптическая криптография|дискретного логарифма эллиптической кривой]]<ref>{{source|Q42308003|ref=Shor|ref-year=1994}} <!-- Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on --></ref> за обозримое время<ref name=":11">{{статья |заглавие=Oversimplifying quantum factoring |ссылка=http://www.nature.com/nature/journal/v499/n7457/full/nature12290.html |издание=Nature |issn=0028-0836 |страницы=163—165 |том=499 |номер=7457 |doi=10.1038/nature12290 |pmid=23846653 |arxiv=1301.7007 |bibcode=2013Natur.499..163S |язык=en |автор=Smolin, John A.; Smith, Graeme; Vargo, Alexander |число=11 |месяц=7 |год=2013 }}</ref>. Предпосылки к появлению таких компьютеров имеются уже сейчас. Так, например, 20 сентября 2019 Financial Times сообщила: «Google утверждает, что достигла [[Квантовое превосходство|квантового превосходства]] на массиве из 54 кубитов, из которых 53 были функциональными и использовались для выполнения вычислений за 200 секунд, на что обычному суперкомпьютеру потребовалось бы около 10 000 лет»<ref>{{Cite news|title=Google claims to have reached quantum supremacy|author=|url=https://www.ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17|website=[[The Financial Times]]|date=2019-09-21|lang=en|accessdate=2019-10-23|archivedate=2021-04-29|archiveurl=https://web.archive.org/web/20210429173358/https://www.ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17}}</ref>. Таким образом, относительно небольшой квантовый компьютер, используя алгоритмом Шора, может быстро взломать все цифровые подписи, используемые для обеспечения конфиденциальности и целостности информации в Интернете сегодня<ref name=":11" />.

== Введение ==
Криптографические примитивы, основанные на сложных [[Задачи теории решёток|задачах теории решёток]], играют ключевую роль в области постквантовых криптографических исследований. Во 2 раунде внесения представлений о постквантовой криптографии, названных [[Национальный институт стандартов и технологий|NIST]]<ref>{{Cite web|title = Round 2 Submissions|url = https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions|access-date = 2019-11-21|archive-date = 2019-11-14|archive-url = https://web.archive.org/web/20191114010029/https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions|deadlink = no}}</ref>, 12 из 26 основаны на решётках и большинство из них основаны на проблеме [[Обучение с ошибками|обучения с ошибками]] (англ. Learning With Errors, LWE) и её вариантах. Было предложено огромное количество криптографических примитивов на основе LWE, таких как шифрование с открытым ключом, протоколы обмена ключами, цифровые подписи, семейства псевдослучайных функций и другие<ref name=":12">{{статья |заглавие=Module-LWE versus Ring-LWE, Revisited |ссылка=https://eprint.iacr.org/2019/930 |язык=und |автор=Wang, Yang; Wang, Mingqiang |год=2019 |archivedate=2022-05-29 |archiveurl=https://web.archive.org/web/20220529093637/https://eprint.iacr.org/2019/930 }}</ref>. Криптографические протоколы, основой которых служит задача LWE, являются такими же безопасными, как и протоколы, основывающиеся на [[задачи теории решёток|задачах теории решёток]], которые на сегодняшний день полагаются чрезвычайно сложными. Тем не менее, криптографические примитивы, основанные на задаче LWE страдают от больших размеров ключей, следовательно, они обычно являются неэффективными<ref name=":12"/>.Этот недостаток стимулировал людей к развитию более эффективных вариантов LWE, таких как [[обучение с ошибками в кольце]](англ. Ring Learning with errors, RLWE)<ref name=":6"/>. Было показано, что задача RLWE также вычислительно трудна, как и наисложнейшие задачи теории решёток над специальными классами идеальных решёток<ref name=":6"/>, и криптографические приложения RLWE обычно имеют большую эффективность по сравнению с обычными LWE, особенно в циклотомическом полиномиальном кольце, приведённым по модулю многочлена, степень которого является спепенью 2<ref name=":12"/>.

== Задача RLWE ==
{{основная статья|Обучение с ошибками в кольце}}
Подпись RLWE работает в [[Кольцо многочленов|кольце многочленов]] по модулю многочлена <math>\Phi (x)</math> степени <math>n</math> с коэффициентами в конечном поле <math>Z_q</math> для нечётного простого числа <math>q</math>. Множество многочленов над [[Конечное поле|конечным полем]] с операциями сложения и умножения образует бесконечное полиномиальное кольцо <math>F_q[x]</math><ref name=":1" />. Умножение и сложение полиномов будет работать как обычно с результатом, приведённым по модулю <math>\Phi (x)</math>(то есть кольцо <math>F_q[x] / \Phi(x)</math>). Типичный многочлен выражается как:

<math>a(x) = a_0 + a_1x + a_{2}x^2 + \ldots + a_{n-3}x^{n-3} + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>

Поле <math>Z_q</math> имеет свои элементы в наборе <math> \{ -(q-1)/2, ...-1, 0, 1, ... (q-1)/2 \} </math>. Если <math>n </math> — это степень двух, то многочлен <math> \Phi (x)</math> будет [[Круговой многочлен|круговым многочленом]] <math>x^n + 1</math>. Возможны другие варианты выбора <math>n </math>, но соответствующие круговые многочлены являются более эффективными<ref name=":1" />.

Существуют две различных постановки задачи обучения с ошибками в кольце первый вариант — «''поиск''», второй вариант — «''решение''»<ref name=":6" />.

''Положим'': <math>a_i(x)</math> — множество случайных, но известных полиномов из <math>Z_q[x]/\Phi(x)</math> с различными коэффициентами для всех <math>F_q</math>, <math>e_i(x)</math> — множество малых случайных и неизвестных полиномов относительно границы <math>b</math> в кольце <math>Z_q[x]/\Phi(x)</math>, <math>s(x)</math> — малый неизвестный полином относительно границы <math>b</math> в кольце <math>Z_q[x]/\Phi(x)</math>, <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math>.

''Поиск'': найти полином <math>s(x)</math> по списку полиномиальных пар <math>( a_i(x), b_i(x) )</math>

''Решение'': данный список полиномиальных пар <math>( a_i(x), b_i(x) )</math> определяет были ли полиномы <math>b_i(x)</math> построены как <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math> или были сгенерированы случайным образом из <math>Z_q[x]/\Phi(x)</math> с коэффициентами из всех <math>F_q</math>.

Сложность данной задачи заключается в выборе фактор-полинома <math>\Phi(x)</math> степени <math>n</math>, над полем <math>F_q</math> и границей <math>b</math>. Во многих алгоритмах, основывающихся на RLWE, закрытый ключ будет парой «малых» полиномов <math>s(x)</math> и <math>e(x)</math>. Тогда соответствующий ему открытый ключ будет парой полиномов <math>a(x)</math>, выбранный случайно из <math>Z_q[x]/\Phi(x)</math>, и полинома <math>t(x)= (a(x)\cdot s(x)) + e(x)</math>. Данные <math>a(x)</math> и <math>t(x)</math> полиномы должны быть вычислительно неразрешимы для задачи восстановления полинома <math>s(x)</math><ref name=":6" /><ref name=":0" />.

== Циклотомический класс ==
Циклотомическим классом над полем <math>\mathbb{F}_q,\;q=p^s</math>, порождённым некоторым элементом <math>\alpha\in\mathbb{F}_Q,\;Q=p^S</math> называется [[множество]] всех различных элементов <math>\mathbb{F}_Q</math>, являющихся <math>q</math>-ми степенями <math>\alpha</math>{{sfn|Сагалович|2014|с=105}}.

Если <math>\alpha</math> — ''[[Примитивный элемент конечного поля|примитивный элемент]]''{{sfn|Блейхут|1986|с=99}} (такой элемент, что <math>\alpha^{Q-1}=1</math> и <math>\alpha^k\neq 1</math> при <math>0<k<Q-1</math>) поля <math>\mathbb{F}_Q,\;Q=q^m</math>, то циклотомический класс <math>C=\{\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}\}</math> над полем <math>\mathbb{F}_q</math> будет иметь ровно <math>m</math> элементов. Любой элемент из циклотомического класса может порождать этот и только этот класс, а, следовательно, и принадлежать только ему.

'''Пример 1.''' Пусть <math>q=2</math>, <math>Q=2^3=8</math> и <math>\alpha</math> — примитивный элемент поля <math>\mathbb{F}_8</math>, то есть <math>\alpha^7=1</math> и <math>\alpha^i\neq 1</math> при <math>i<7</math>. Учитывая также, что <math>\alpha^8=\alpha</math>, можно получить разложение всех ненулевых элементов поля <math>\mathbb{F}_8</math> на три циклотомических класса над полем <math>\mathbb{F}_2</math>:

: <math>\begin{matrix} 
\{1\}, \\
\{\alpha,\;\alpha^2,\;\alpha^4\}, \\
\{\alpha^3,\;\alpha^6,\;\alpha^5\}.
\end{matrix}</math>

'''Пример 2.''' Аналогично можно построить классы на поле <math>\mathbb{F}_{16}</math> над полем <math>\mathbb{F}_4</math>, то есть <math>q=4,\;Q=q^2=16</math>. Пусть <math>\alpha</math> — примитивный элемент поля <math>\mathbb{F}_{16}</math>, значит <math>\alpha^{15}=1,\;\alpha^{16}=\alpha</math>.

: <math>\begin{matrix} 
\{1\}, \\
\{\alpha,\;\alpha^4\},\;\{\alpha^2,\;\alpha^8\}, \\
\{\alpha^3,\;\alpha^{12}\},\;\{\alpha^5\},\;\{\alpha^{10}\}, \\
\{\alpha^6,\;\alpha^9\},\;\{\alpha^7,\;\alpha^{13}\}, \\
\{\alpha^{11},\;\alpha^{14}\}.
\end{matrix}</math><br>

== Генерация «небольших» полиномов ==
Подпись RLWE использует многочлены, которые считаются «малыми» по отношению к [[равномерная норма|равномерной норме]]. [[Равномерная норма]] для полинома является просто наибольшим абсолютным значением коэффициентов полинома, и эти коэффициенты рассматриваются как целые числа в <math>Z</math>, а не в <math>Z_q</math><ref name=":0" />.Алгоритм подписи создаёт случайные многочлены, равномерная норма которых мала по отношению к конкретной границе. Это легко сделать путём случайной генерации всех [[Коэффициент|коэффициентов полинома]] <math> a_0, ..., a_{n-1} </math> так, чтобы гарантировать с большой вероятностью норму меньше или равную этой границе. Имеется два распространённых способа сделать это<ref name=":1" />:

* ''Используя [[Дискретное равномерное распределение|равномерное распределение]]'': коэффициенты малого полинома равномерно выбираются из набора коэффициентов. Пусть <math>b</math> будет [[Целое число|целым числом]], которое намного меньше, чем <math>q</math>. Если мы случайным образом выберем полиномиальные коэффициенты из множества <math> \{-b, -b+1, -b+2, ... -2, -1, 0, 1, 2, ... , b-2, b-1, b\} </math>, то норма многочлена будет <math> \leqslant b </math>.
* ''Используя дискретную гауссову выборку'': для нечётного целого числа <math>q</math>, коэффициенты выбираются случайным образом путём выборки из набора <math> \{ -\frac{q-1}{2}, ... 0, ... \frac{q-1}{2} \} </math> в соответствии с дискретным распределением Гаусса со средним <math>0</math> и дисперсией <math>\sigma^2</math>.

В подписи RLWE GLYPH, используемой в качестве примера ниже, для коэффициентов «малых» многочленов будет использоваться метод с [[Дискретное равномерное распределение|равномерным распределением]], и значение <math>b</math> будет намного меньше значения <math>q</math><ref name=":0" />.

== Хэширование «небольших» полиномов ==
Большинство алгоритмов подписи RLWE также требуют способности [[Криптографическая хэш-функция|криптографического хэширования]] произвольных битовых строк в небольшие полиномы в соответствии с некоторым распределением<ref name=":0" /><ref name=":3" />. В приведённом ниже примере используется хеш-функция <math>\mathsf{POLYHASH} (\omega )</math>, которая принимает битовую строку <math> \omega </math> в качестве входных данных и выводит полином с <math>n</math> коэффициентами, так что ровно <math>k</math> из этих коэффициентов имеет абсолютное значение больше нуля и меньше целочисленной границы <math>b</math><ref name=":3" />.

== Выборка с отклонением ==
Ключевой особенностью алгоритмов подписи RLWE является использование метода, известного как [[выборка с отклонением]]<ref name=":1" /><ref name=":5" />. В этом методе, если [[равномерная норма]] полинома подписи превышает фиксированную границу <math>\beta</math>, то этот полином будет отброшен, и процесс генерации подписи начнётся снова. Этот процесс будет повторяться до тех пор, пока равномерная норма полинома не станет меньше или равна границе. Выборка с отклонением гарантирует, что выходная подпись не может эксплуатироваться с использованием значений секретного ключа подписывающего лица<ref name=":3" />.

В данном примере граница <math>\beta</math> будет равна <math>(b - k)</math>, где <math>b</math> — это диапазон равномерной выборки, а <math>k</math> — количество ненулевых коэффициентов, связанных с разрешённым полином<ref name=":0" />.

== Другие примеры ==
Согласно GLYPH<ref name=":3" />, максимальная степень многочленов будет <math>n-1</math> и, следовательно, иметь <math>n</math> коэффициентов<ref name=":0" />.Типичные значения для <math>n</math> являются 512 и 1024<ref name=":0" />. Коэффициенты этих многочленов будут элементами поля <math>F_q</math> , где <math>q</math> — нечётное простое число, соответствующее <math>1\bmod 4</math>. Для <math>n=1024</math>, GLYPH определяет <math>q = 59393, b=16383</math> и <math>k</math> — количество ненулевых коэффициентов на выходе <math>\mathsf{POLYHASH}</math> равное <math>16</math><ref name=":3" />.Безопасность схемы подписи тесно связана с относительными размерами <math>n, q, b, k</math>.

Как отмечено выше, многочлен <math> \Phi (x)</math>, который определяет кольцо используемых многочленов, будет равняться <math>x^n + 1</math>. Наконец, <math>a(x)</math> будет случайно выбранным и фиксированным полиномом с коэффициентами из множества <math> \{-b, ...  0, ... , b\} </math>. Все подписывающие и проверяющие сущности будут знать <math>n, q, b, k, \Phi (x), a (x) </math> и <math>\beta =  b-k </math><ref name=":3" />.

== Генерация открытого ключа ==
Согласно GLYPH<ref name=":3" />, открытый ключ для подписи сообщения <math> M </math> генерируется посредством следующих шагов:

# Генерация двух небольших полиномов <math> s(x) </math> и <math> e(x) </math> с коэффициентами, выбранными случайно с равномерным распределением из множества <math> \{-b, ...- 1, 0, 1, ..., b\} </math>
# Вычисление <math> t(x) = a(x) s(x) + e(x) </math>
# Распределение <math> t(x) </math> как открытого ключа объекта
Полиномы <math> s(x) </math> и <math> e(x) </math> служат закрытым ключом, а <math> t(x) </math> — соответствующим открытым ключом. Безопасность этой схемы подписи основана на следующей проблеме: для заданного полинома <math> t(x) </math> необходимо найти малые полиномы <math> f_1(x) </math> и <math>f_2(x) </math>, такие что: <math> a(x)f_1(x) + f_2 (x) =t (x)</math>. Если эту задачу трудно решить, то схему подписи будет трудно подделать.

== Генерация подписи ==
Согласно GLYPH<ref name=":3"/>, чтобы подписать сообщение <math> M </math>, выраженное в виде битовой строки, необходимо произвести следующие операции:
# Генерация двух небольших полиномов <math> y_1(x) </math> и <math> y_2(x) </math> с коэффициентами из множества <math> \{-b, ...- 1, 0, 1, ..., b\} </math>
# Вычисление <math> w(x) = a(x)y_1(x) + y_2(x) </math>
# Отображение <math> w(x) </math> в битовую строку <math> \omega </math>
# Вычисление <math> c(x) =  \mathsf{POLYHASH} (\omega | M )</math> (Это многочлен с k ненулевыми коэффициентами. Символ "|" обозначает конкатенацию строк)
# Вычисление <math> z_1(x) = s(x)c(x) + y_1(x) </math>
# Вычисление <math> z_2(x) = e(x)c(x) + y_2(x) </math>
# Если <math>\|z_1(x)\|</math> и <math>\|z_2(x)\| >  \beta  = (b - k) </math>, то повторять пункты 1-6 (Норма <math>\|\cdot\|</math> — [[равномерная норма]])
# Подпись — это тройка полиномов <math>c(x), z_1(x)</math> и <math> z_2(x)</math>

== Проверка подписи ==
Согласно GLYPH<ref name=":3"/>, для проверки сообщения <math> M </math>, выраженного в виде битовой строки, необходимо использовать публичный ключ автора данного сообщения <math> t(x) </math> и цифровую подпись (<math>c(x), z_1(x), z_2(x)</math>):
# <math>\|z_1(x)\|</math>, и <math>\|z_2(x)\| \leqslant  \beta </math>, иначе подпись не принята
# Вычисление <math> w'(x) = a(x)z_1(x) + z_2(x) - t(x)c(x) </math>
# Отображение <math> w'(x) </math> в битовую строку <math> \omega ' </math>
# Вычисление <math> c'(x) =  \mathsf{POLYHASH} (\omega' | M )</math>
# Если <math> c'(x) = c(x) </math>, подпись считается действительной
Не сложно показать корректность проверки:<br><math>a(x)z_1(x) + z_2(x) - t(x)c(x) =  a(x)[s(x)c(x) + y_1(x)] + z_2(x) - [a(x)s(x) + e(x)]c(x) = </math><br><math> =  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)=</math><br><math> =  a(x)y_1(x) + y_2(x) = w(x)</math>

== Возможные атаки ==
В работе Любошевского<ref name=":6" /> много внимания уделяется безопасности алгоритма, однако, чтобы осветить данные свойства задачи и доказать их полное соответствие заявленным, следует провести ряд прямых атак на RLWE. Атака определяется выбором числового поля <math>K</math> и простого числа <math>q</math>, называемого модулем, наряду с распределением ошибок.

Дукас и Дурмус предложили недвойственный вариант RLWE в циклотомической постановке и доказали, что сложность нового и прежнего варианта идентичны<ref>{{Статья|автор=Ducas, L., Durmus, A|заглавие=Ring-LWE in polynomial rings|ссылка=|язык=|издание=Springer|тип=|год=2012|месяц=|число=|том=|номер=|страницы=34—51|issn=}}</ref>. Этот вариант RLWE порождает распределение ошибки как дискретная [[гауссова функция]] в кольце целых чисел <math>R</math> при каноническом вложении, а не в изображении двойственного идеала. Двойственный и недвойственные варианты эквиваленты вплоть до распределения ошибок<ref name=":7">{{Статья|автор=Hao Chen, Kristin Lauter, Katherine E. Stange|заглавие=Attacks on the Search-RLWE problem with small errors|ссылка=https://arxiv.orgpdf/1710.03739.pdf|язык=|издание=|тип=|год=|месяц=|число=|том=|номер=|страницы=|issn=}}{{Недоступная ссылка|date=Апрель 2020 |bot=InternetArchiveBot }}</ref>. Для недвойственного варианта RLWE авторы<ref name=":8">{{Статья|автор=Yara Elias, Kristin E. Lauter, Ekin Ozman, Katherine E. Stange|заглавие=Provably Weak Instances of Ring-LWE|ссылка=https://eprint.iacr.org/2015/106.pdf|язык=|издание=|тип=|год=|месяц=|число=|том=|номер=|страницы=|issn=|archivedate=2019-06-08|archiveurl=https://web.archive.org/web/20190608143134/https://eprint.iacr.org/2015/106.pdf}}</ref> предложили атаку на версию «решение» RLWE. При атаке используется модуль <math>q</math> степени вычетов 1, дающий кольцевой гомоморфизм <math>p:R</math>→ <math >F_q </math>. Атака работает, когда с подавляющей вероятностью распределение ошибок RLWE при наборе пар <math display="inline">p</math> принимает значения только в малом подмножестве <math>F_q </math>. Затем авторы<ref name=":8" /> дают целое семейство примеров, уязвимых для атак. Однако, уязвимые числовые поля не являются полями Галуа, поэтому теорема сведения версии «поиск» к версии «решение» не применима и атака не может быть прямо использована для варианта «поиск» задачи RLWE, на что собственно была нацелена представленная работа<ref name=":8" />.

Однако позже в другой работе<ref name=":7" />, эта атака была обобщена на некоторые числовые поля Галуа и модули более высокой степени. В ней же была представлена её реализация для конкретных экземпляров RLWE, включая вариант сведения «''поиска''» к «''решению''». Основным её принципом было то, что гомоморфизм в кольце рассматривался в виде <math display="inline">R</math>→<math>F_q^f </math>(где, <math>f</math> — это степень <math>q</math>) для <math>f > 1</math>, и то, что распределение ошибок отличается от случайного, используя статистический [[критерий хи-квадрат]] вместо того, чтобы полагаться на значения многочлена ошибок. Авторы акцентируют внимание также на том, что ими была проведена атака на вариацию RLWE с простыми циклотомическими кольцами при определённых предположениях о модуле и частоте ошибок, которая успешно выполняется с высокой вероятностью. А именно, они показали атаку на недвойственный вариант RLWE, когда модуль равен уникальному и простому <math display="inline">p</math>.К примеру, если размерность n = 808, можно атаковать вариацию RLWE в циклотомическом кольце <math display=>Q</math>(ζ809) за 35 секунд, где модуль равен 809. Возникает тогда вопрос о том, безопасны ли циклотомические поля для криптографии в принципе, в зависимости от того, можно ли использовать большие модули (которые используются на практике) вместо тех, что были рассмотрены в примере статьи. В дополнение, авторами статьи была осуществлена ещё одна атака на двойственную RLWE версии «решение» в <math>p</math>-ом циклотомическом поле с произвольным модулем <math display="inline">q</math>, предполагая, что ширина распределения ошибок составляет значение около <math>1/\sqrt{p}</math>.

== Примечания ==
{{примечания|30em}}

== Литература ==
* {{Публикация|книга
 | автор        = Сагалович Ю. Л.
 | заглавие     = Введение в алгебраические коды
 | издание      = Review of General Psychology
 | издательство = ИППИ РАН
 | год          = 2014
 | страниц      = 310
 | ссылка       = http://iitp.ru/upload/content/790/algebcodes.pdf
 | ref          = Сагалович
}}
* {{Публикация|книга
 | автор        = Блейхут Р. Э.
 | заглавие     = Теория и практика кодов, контролирующих ошибки
 | издательство = Мир
 | год          = 1986
 | страниц      = 576
 | ссылка       = http://en.bookfi.net/book/467135
 | ref          = Блейхут
}}
* {{Публикация|книга
 | автор        = Bakhtiari M., Maarof M. A.
 | заглавие     = Serious Security Weakness in RSA Cryptosystem
 | издательство = IJCSI
 | год          = 2012
 | allpages     = 175
 | язык         = en
 | ссылка       = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.402.6882&rep=rep1&type=pdf
 | ref          = Bakhtiari, Maarof
}}

{{Криптосистемы с открытым ключом}}
[[Категория:Криптография с открытым ключом]]