Криптография на решётках

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

Криптография на решётках — подход к построению алгоритмов асимметричного шифрования с использованием решёток.

Наряду с другими методами постквантовой криптографии, считается перспективным в связи с возможностями квантового компьютера взламывать широко используемые асимметричные системы шифрования, основанные на двух типах задач теории чисел: задачах факторизации целых чисел и задачах дискретного логарифмирования. Сложность взлома алгоритмов, построенных на решётках, крайне велика, самые лучшие алгоритмы могут решить эту задачу с трудом за экспоненциальное время. По состоянию на середину 2010-х годов неизвестно ни одного квантового алгоритма, способного справиться лучше обычного компьютера.





Предпосылки создания

 Данный раздел имеет чрезмерный объём или содержит маловажные подробности.
Если вы не согласны с этим, пожалуйста, покажите в тексте существенность излагаемого материала. В противном случае раздел может быть удалён. Подробности могут быть на странице обсуждения.
Кратко: такой общий раздел был бы уместнее в статье постквантовая криптография.

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

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

В 2001 году группа специалистов IBM продемонстрировала выполнение алгоритма факторизации Шора для числа 15. Число было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами, построенного из 1810 молекул, состоящих из пяти атомов фтора и двух атомов углерода, с записью информации посредством радиосигналов и считыванием методами ядерного магнитного резонанса[1].

Начиная со второй половины 1990-х годов возникла необходимость поиска криптостойких к квантовым компьютерам задач для постквантовой эпохи шифрования, в качестве одного из подходов было предложено использовать решётки в <math>\R^n</math> — дискретные подгруппы вещественного векторного пространства, линейные оболочки которых совпадают с ним:

<math> L = \left\{ \sum_{i=1}^n \lambda_i b_i \mid \lambda_i \in\Bbb{Z} \right\}</math>

Вычислительно сложные задачи

Задача нахождения кратчайшего вектора (SVP, англ. Shortest Vector Problem) — найти в заданном базисе решётки ненулевой вектор по отношению к определённой нормали[2].

Задача нахождения (приблизительно) идеального кратчайшего вектора (ISVP, англ. (approximate) ideal shortest vector problem) не считается NP-сложной. Однако, нет известных решёток, основанных на методе редукции, значительно более эффективных на идеальных структурах, чем на общих[3].

Ещё одна задача нахождения (приблизительно) кратчайшего независимого вектора — SIVP[уточнить], в которой дан базис решётки <math>B</math> и требуется найти <math>n</math> линейно независимых векторов[4].

Задача нахождения ближайшего вектора (CVP, англ. Closest Vector Problem) — нахождение вектора в решётке по заданному базису и некоторому вектору, не принадлежащему решётке, при этом максимально схожего по длине с заданным вектором.

LLL-алгоритм

Все эти задачи разрешимы за полиномиальное время с помощью известного LLL-алгоритма изобретенного в 1982 году Арьеном Ленстрой, Хендриком Ленстрой и Ловасом Ласло[5].

В заданном базисе <math>\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_d \}</math>, с n-мерными целыми координатами, в решётке <math>L</math> из <math>\R^n</math>, где <math> \ d \leq n </math>, LLL-алгоритм находит более короткий (промерно[уточнить]) ортогональный базис за время:

<math>O(d^5n\log^3 B)</math>,

где <math>B</math> — это максимальная длина вектора <math>b_i</math> в этом пространстве.

Основные криптографические конструкции и их стойкость

Шифрование

GGH (англ.)русск. — криптосистема основанная на CVP, а именно на односторонней функции с потайным входом опирающуюся на сложность редукции решётки. Была опубликована в 1997 году. Зная базис, можно сгенерировать вектор близкий к заданной точке, но зная это вектор нам необходим исходный базис, чтобы найти исходную точку. Алгоритм был проверен в 1999 году.

Реализация GGH

GGH состоит из открытого и секретного ключа.

Секретный ключ — это базис <math>B</math> решётки <math>L</math> и унимодулярная матрица <math>U</math>.

Открытый ключ — некоторый базис в решётке <math>L</math> в виде <math>B'=UB</math>.

Для некоторого <math>M</math>, пространство сообщения состоит из вектора <math>(\lambda_1,..., \lambda_n)</math>, где <math>-M <\lambda_i < M</math>.

Шифрование

Задано сообщение <math>m = (\lambda_1,..., \lambda_n)</math>, искажение <math>e</math>, открытый ключ <math>B'</math>:

<math>v = \sum \lambda_i b_i'</math>

В матричном виде:

<math>v=m\cdot B'</math>.

<math>m</math> состоит из целых значений, <math>b'</math> точка решётки, и v также точка решётки. Тогда шифротекст:

<math>c=v+e=m \cdot B' + e</math>
Расшифрование

Для расшифрования необходимо вычислить:

<math> c \cdot B^{-1} = (m\cdot B^\prime +e)B^{-1} = m\cdot U\cdot B\cdot B^{-1} + e\cdot B^{-1} = m\cdot U + e\cdot B^{-1}</math>

Часть <math>e \cdot B^{-1}</math> убирается, из соображений приближения. Сообщение:

<math> m = m \cdot U \cdot U^{-1} </math>
Пример

Выберем решётку <math>L \subset \mathbb{R}^2</math> с базисом <math>B</math>:

<math> B= \begin{pmatrix}
7 & 0 \\ 0 & 3 \\
    \end{pmatrix}</math> and <math>B^{-1}=  \begin{pmatrix}
\frac{1}{7} & 0 \\ 0 & \frac{1}{3} \\
    \end{pmatrix}</math>

где

<math>U = \begin{pmatrix}
        2 & 3 \\ 3 &5\\
       \end{pmatrix}</math> и
<math>U^{-1} = \begin{pmatrix}
        5 & -3 \\ -3 &2\\
       \end{pmatrix}</math>

В результате:

<math>B' = U B = \begin{pmatrix}
           14 & 9 \\ 21 & 15 \\
          \end{pmatrix}</math>

Пусть сообщение <math>m = (3, -7)</math> и вектор ошибки <math>e = (1, -1)</math>. Тогда шифротекст:

<math>c = m B'+e=(-104, -79)</math>.

Для расшифровки необходимо вычислить:

<math>c B^{-1} = \left( \frac{-104}{7}, \frac{-79}{3}\right)</math>.

Округление дает <math>(-15, -26)</math> , восстановим сообщение:

<math>m= (-15, -26) U^{-1} = (3, -7)</math>.

NTRUEncrypt — криптосистема основанная на SVP, является альтернативой RSA и ECC. В вычислении используется кольцо многочленов.

Подпись

Схема подписи GGH впервые предложена 1995 году и опубликована в 1997 году Голдрихом, основана на сложности нахождения ближайшего вектора. Идея заключалась в использовании решёток, для которых «плохой» базис, векторы длинные и почти параллельные, является открытым и «хороший» базис с короткими и почти ортогональными векторами, является закрытым. По их методу, сообщение необходимо хэшировать в пространство, натянутое на решётку, а подпись для данного хэша в этом пространстве является ближайшим узлом решётки. Схема не имела формального доказательства безопасности, и её базовый вариант был взломан в 1999 году Нгуэном (Nguyen). В 2006 году модифицированная версия была снова взломана Нгуэном и Реджевом (Regev).

NTRUSign — специальная, более эффекитивная версия подписи GGH, отличающаяся меньшим ключом и размером подписи. Она использует только решётки подмножества множества всех решёток, связанных с некоторыми полиномиальными кольцами. NTRUSign была предложена на рассмотрение в качестве стандарта IEEE P1363.1.

Напишите отзыв о статье "Криптография на решётках"

Примечания

  1. ↑ Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory & Yannoni, Costantino S. (2001), "[cryptome.org/shor-nature.pdf Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance]", Nature Т. 414 (6866): 883–887, PMID 11780055, doi:[dx.doi.org/10.1038%2F414883a 10.1038/414883a], <cryptome.org/shor-nature.pdf> 
  2. ↑ [www.cs.elte.hu/~lovasz/scans/lll.pdf Factoring polynomials with rational coefficients], <www.cs.elte.hu/~lovasz/scans/lll.pdf> 
  3. ↑ [link.springer.com/content/pdf/10.1007%2F11787006.pdf Generalized compact knapsacks are collision resistant. In:International colloquium on automata, languages and programming], <link.springer.com/content/pdf/10.1007%2F11787006.pdf> 
  4. ↑ [cseweb.ucsd.edu/~daniele/papers/book.bib Complexity of lattice problems: a cryptographic perspective. The Kluwer international series in engineering and computer science], <cseweb.ucsd.edu/~daniele/papers/book.bib> 
  5. ↑ (1982) «Factoring polynomials with rational coefficients». Mathematische Annalen 261 (4): 515–534. DOI:10.1007/BF01457454. hdl:[hdl.handle.net/1887%2F3810 1887/3810].


<imagemap>: неверное или отсутствующее изображение

 Для улучшения этой статьи желательно?:

Отрывок, характеризующий Криптография на решётках

– Какая смелость! По команде подайте. А сами идите, идите… – И он стал надевать подаваемый камердинером мундир.
Ростов вышел опять в сени и заметил, что на крыльце было уже много офицеров и генералов в полной парадной форме, мимо которых ему надо было пройти.
Проклиная свою смелость, замирая от мысли, что всякую минуту он может встретить государя и при нем быть осрамлен и выслан под арест, понимая вполне всю неприличность своего поступка и раскаиваясь в нем, Ростов, опустив глаза, пробирался вон из дома, окруженного толпой блестящей свиты, когда чей то знакомый голос окликнул его и чья то рука остановила его.
– Вы, батюшка, что тут делаете во фраке? – спросил его басистый голос.
Это был кавалерийский генерал, в эту кампанию заслуживший особенную милость государя, бывший начальник дивизии, в которой служил Ростов.
Ростов испуганно начал оправдываться, но увидав добродушно шутливое лицо генерала, отойдя к стороне, взволнованным голосом передал ему всё дело, прося заступиться за известного генералу Денисова. Генерал выслушав Ростова серьезно покачал головой.
– Жалко, жалко молодца; давай письмо.
Едва Ростов успел передать письмо и рассказать всё дело Денисова, как с лестницы застучали быстрые шаги со шпорами и генерал, отойдя от него, подвинулся к крыльцу. Господа свиты государя сбежали с лестницы и пошли к лошадям. Берейтор Эне, тот самый, который был в Аустерлице, подвел лошадь государя, и на лестнице послышался легкий скрип шагов, которые сейчас узнал Ростов. Забыв опасность быть узнанным, Ростов подвинулся с несколькими любопытными из жителей к самому крыльцу и опять, после двух лет, он увидал те же обожаемые им черты, то же лицо, тот же взгляд, ту же походку, то же соединение величия и кротости… И чувство восторга и любви к государю с прежнею силою воскресло в душе Ростова. Государь в Преображенском мундире, в белых лосинах и высоких ботфортах, с звездой, которую не знал Ростов (это была legion d'honneur) [звезда почетного легиона] вышел на крыльцо, держа шляпу под рукой и надевая перчатку. Он остановился, оглядываясь и всё освещая вокруг себя своим взглядом. Кое кому из генералов он сказал несколько слов. Он узнал тоже бывшего начальника дивизии Ростова, улыбнулся ему и подозвал его к себе.
Вся свита отступила, и Ростов видел, как генерал этот что то довольно долго говорил государю.
Государь сказал ему несколько слов и сделал шаг, чтобы подойти к лошади. Опять толпа свиты и толпа улицы, в которой был Ростов, придвинулись к государю. Остановившись у лошади и взявшись рукою за седло, государь обратился к кавалерийскому генералу и сказал громко, очевидно с желанием, чтобы все слышали его.
– Не могу, генерал, и потому не могу, что закон сильнее меня, – сказал государь и занес ногу в стремя. Генерал почтительно наклонил голову, государь сел и поехал галопом по улице. Ростов, не помня себя от восторга, с толпою побежал за ним.


На площади куда поехал государь, стояли лицом к лицу справа батальон преображенцев, слева батальон французской гвардии в медвежьих шапках.
В то время как государь подъезжал к одному флангу баталионов, сделавших на караул, к противоположному флангу подскакивала другая толпа всадников и впереди их Ростов узнал Наполеона. Это не мог быть никто другой. Он ехал галопом в маленькой шляпе, с Андреевской лентой через плечо, в раскрытом над белым камзолом синем мундире, на необыкновенно породистой арабской серой лошади, на малиновом, золотом шитом, чепраке. Подъехав к Александру, он приподнял шляпу и при этом движении кавалерийский глаз Ростова не мог не заметить, что Наполеон дурно и не твердо сидел на лошади. Батальоны закричали: Ура и Vive l'Empereur! [Да здравствует Император!] Наполеон что то сказал Александру. Оба императора слезли с лошадей и взяли друг друга за руки. На лице Наполеона была неприятно притворная улыбка. Александр с ласковым выражением что то говорил ему.
Ростов не спуская глаз, несмотря на топтание лошадьми французских жандармов, осаживавших толпу, следил за каждым движением императора Александра и Бонапарте. Его, как неожиданность, поразило то, что Александр держал себя как равный с Бонапарте, и что Бонапарте совершенно свободно, как будто эта близость с государем естественна и привычна ему, как равный, обращался с русским царем.
Александр и Наполеон с длинным хвостом свиты подошли к правому флангу Преображенского батальона, прямо на толпу, которая стояла тут. Толпа очутилась неожиданно так близко к императорам, что Ростову, стоявшему в передних рядах ее, стало страшно, как бы его не узнали.
– Sire, je vous demande la permission de donner la legion d'honneur au plus brave de vos soldats, [Государь, я прошу у вас позволенья дать орден Почетного легиона храбрейшему из ваших солдат,] – сказал резкий, точный голос, договаривающий каждую букву. Это говорил малый ростом Бонапарте, снизу прямо глядя в глаза Александру. Александр внимательно слушал то, что ему говорили, и наклонив голову, приятно улыбнулся.
– A celui qui s'est le plus vaillament conduit dans cette derieniere guerre, [Тому, кто храбрее всех показал себя во время войны,] – прибавил Наполеон, отчеканивая каждый слог, с возмутительным для Ростова спокойствием и уверенностью оглядывая ряды русских, вытянувшихся перед ним солдат, всё держащих на караул и неподвижно глядящих в лицо своего императора.
– Votre majeste me permettra t elle de demander l'avis du colonel? [Ваше Величество позволит ли мне спросить мнение полковника?] – сказал Александр и сделал несколько поспешных шагов к князю Козловскому, командиру батальона. Бонапарте стал между тем снимать перчатку с белой, маленькой руки и разорвав ее, бросил. Адъютант, сзади торопливо бросившись вперед, поднял ее.
– Кому дать? – не громко, по русски спросил император Александр у Козловского.
– Кому прикажете, ваше величество? – Государь недовольно поморщился и, оглянувшись, сказал:
– Да ведь надобно же отвечать ему.
Козловский с решительным видом оглянулся на ряды и в этом взгляде захватил и Ростова.
«Уж не меня ли?» подумал Ростов.
– Лазарев! – нахмурившись прокомандовал полковник; и первый по ранжиру солдат, Лазарев, бойко вышел вперед.
– Куда же ты? Тут стой! – зашептали голоса на Лазарева, не знавшего куда ему итти. Лазарев остановился, испуганно покосившись на полковника, и лицо его дрогнуло, как это бывает с солдатами, вызываемыми перед фронт.
Наполеон чуть поворотил голову назад и отвел назад свою маленькую пухлую ручку, как будто желая взять что то. Лица его свиты, догадавшись в ту же секунду в чем дело, засуетились, зашептались, передавая что то один другому, и паж, тот самый, которого вчера видел Ростов у Бориса, выбежал вперед и почтительно наклонившись над протянутой рукой и не заставив ее дожидаться ни одной секунды, вложил в нее орден на красной ленте. Наполеон, не глядя, сжал два пальца. Орден очутился между ними. Наполеон подошел к Лазареву, который, выкатывая глаза, упорно продолжал смотреть только на своего государя, и оглянулся на императора Александра, показывая этим, что то, что он делал теперь, он делал для своего союзника. Маленькая белая рука с орденом дотронулась до пуговицы солдата Лазарева. Как будто Наполеон знал, что для того, чтобы навсегда этот солдат был счастлив, награжден и отличен от всех в мире, нужно было только, чтобы его, Наполеонова рука, удостоила дотронуться до груди солдата. Наполеон только прило жил крест к груди Лазарева и, пустив руку, обратился к Александру, как будто он знал, что крест должен прилипнуть к груди Лазарева. Крест действительно прилип.


Источник — «http://wiki-org.ru/wiki/index.php?title=Криптография_на_решётках&oldid=79195202»