Новые конструкции криптографических примитивов, основанные на полугруппах, группах и линейной алгебре тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Санкт-Петербургский Государственный Университет

На правах рукописи

Николенко Сергей Игоревич

I

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

примитивов, основанные на полугруппах, группах и линейной алгебре

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Санкт-Петербург — 2008

003461057

Работа выполнена в Учреждении Российской академии наук Санкт-Петербургском отделении Математического института им. В. А. Стеклова РАН.

Научный кандидат физико-математических наук,

руководитель: доцент Гирш Эдуард Алексеевич

Официальные доктор физико-математических наук оппоненты: Пономаренко Илья Николаевич

(Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН)

кандидат физико-математических наук, доцент Семёнов Андрей Алексеевич (Санкт-Петербургский Государственный Университет)

Ведущая Санкт-Петербургский Государственный Уни-

организация: верситет Аэрокосмического приборостроения

Защита диссертации состоится " ^ " 200? года в час.

на заседании совета Д 212.232.29 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., 28, математико-механический факультет, ауд. 405.

Защита будет проходить в Санкт-Петербургском отделении математического института им. В. А. Стеклова РАН по адресу: 191023, Санкт-Петербург, наб. р. Фонтанки, д. 27, ауд. 311.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан " &п ^Íaf>j> 200 3 года. Учёный секретарь диссертационного совета, доктор физико-математических наук, профессор ^ Нежинский В. М.

овщая характеристика работы

Актуальность темы. В современной криптографии практически нет доказуемо надёжных конструкций. Начиная с первого протокола согласования ключа Диффи-Хеллмана и первой криптосистемы с открытым ключом RSA, не была доказана надёжность ни одного криптографического протокола с открытым ключом (разумеется, существуют надёжные протоколы с секретным ключом, например одноразовые блокноты, но они требуют размера ключа не меньше размера сообщения). Конечно, безусловное доказательство надёжности было бы трудно получить, ведь из него неизбежно следовало бы, что Р ф NP. Но нет и доказательств условных, в естественных структурных предположениях. Недавно постившиеся разработки основанных на решётках криптосистем, связывающих криптографическую надёжность со сложностью в наихудшем случае, в действительности имеют дело не с NP-трудными задачами, а с задачами, чья сложность неизвестна. Поэтому становится актуальной работа над альтернативными определениями и критериями надежности.

Можно рассмотреть более общие криптографические примитивы, такие, например, как односторонние функции (отметим, что односторонняя функция ещё не означает криптосистемы с открытым ключом, для неё нужна функция с секретом, trapdoor function). И действительно, результаты об односторонних функциях оказывается проще доказать. Например, полные односторонние функции (полной, следуя Л. А. Левину, мы называем такую функцию f, что если односторонние функции вообще существуют, то f тоже односторонняя) известны уже достаточно давно, а полные криптосистемы с открытым ключом появились только в последние годы в работах Харника и др. (2005) и Д. Ю. Григорьева и др. (2006). Более того, недавно Л. А. Левин (2003) разработал более или менее естественные конструкции комбинаторных полных односторонних функций.

Другой подход, тоже приводящий к более слабым результатам, заключается в том, чтобы изменить само понятие надёжности. Если рассмотреть более слабые определения надёжности, оказывается возможным построить даже доказуемо надёжные примитивы. Как пример такого подхода можно привести теорию функций, односторонних в слабом смысле (feebly one-way), развитую А. Хильтгеном (1992). В этой теории ослабление достигается за счёт уточнения понятия «вычислительно более сложной задачи», которую для противника должно

/

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

Третий подход также меняет понятие надёжности, но в другом смысле. Он накладывает дополнительные ограничения на противника, которому требуется решить более сложную задачу, чем обычное криптографическое обращение. Например, Эван и Якоби (1980) рассмотрели ситуацию, в которой надёжность определена для противника в наихудшем случае, который должен взламывать криптосистему всегда, для всех сообщений.

Диссертация содержит результаты, касающиеся каждого из вышеописанных подходов. Во-первых, построены новые конструкции полных односторонних функций, следующие подходу Л. А. Левина. Во-вторых, построены новые конструкции криптографических примитивов — семейств функций с секретом, — которые являются надёжными в слабом смысле, по Хильтгену. В-третьих, вводится новое понятие доказуемого взлома, являющееся альтернативным понятием криптографической надёжности, накладывающим дополнительные ограничения на противника; построены новые конструкции криптосистем и протоколов согласования ключа, надёжных относительно доказуемого взлома.

Цели работы.

1. Предложить новые конструкции криптографических примитивов, основанных на полугрупповых задачах. Доказать их полноту.

2. Предложить новые конструкции криптографических примитивов, основанных на задачах линейной алгебры. Доказать их надёжность в слабом смысле.

3. Предложить новые конструкции криптографических примитивов, основанных на задачах теории групп, и доказать надёжность предложенных примитивов относительно ослабленных моделей надёжности.

Общая методика работы. В работе используются методы, традиционные для криптографии и теории сложности доказательств. Полнота построенных примитивов доказывается при помощи моделирования в них задачи вычисления произвольной (достаточно быстро вычислимой) функции; для доказательства одной из теорем применён метод динамического кодирования Гуревича. Надёжность построен-

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

Основные результаты работы.

7. Построены новые односторонние функции, являющиеся полными в смысле Левина: если существуют односторонние функции, то f тоже является односторонней. Построены функции, основанные на задаче достижимости с распределением для полусистем Туэ, задаче Поста и задаче поиска замощения. Доказан более общий результат, позволяющий найти полную одностороннюю функцию в любой комбинаторной задаче, обладающей требуемыми свойствами.

2. Построено семейство линейных функций с секретом, доказуемо надёжных в слабом смысле. Доказано, что в наиболее сильной модели вычисления — схемной сложности в произвольном базисе — обращение этих функций без знания секрета в Ц раза сложнее, чем операции порождения ключей, кодирования и декодирования со знанием секрета. Полученная сложность усилена методом повторения блоков, что позволило получить экспоненциально сильную гарантию надёжности для ещё более ослабленных противников (надёжность порядка 2-с^ для противника, использующего на Сл/п гейтов меньше, чем требуется).

3. Предложено новое определение криптографической надёжности — доказуемый взлом. Построены новые криптосистемы, основанные на инвариантах групп. Доказана надёжность этих криптосистем относительно доказуемого взлома.

Научная новизна. Все основные результаты диссертации являются новыми.

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

свойствами (полнотой).

Апробация работы. Результаты диссертации докладывались на семинаре по дискретной математике ПОМИ РАН, а также на международной конференции «Симпозиум по теоретическим аспектам информатики» (STACS'08, февраль 2008, Бордо, Франция).

Публикации. Основные результаты диссертации изложены в работах [1]-[4], перечисленных в конце автореферата. Статья [1] опубликована в журнале, входящем в перечень ВАК на момент публикации.

Структура и объём диссертации. Диссертация состоит из четырёх глав. Нумерация разделов, формул, примеров, лемм и теорем ведётся отдельно для каждой главы. Текст диссертации изложен на 120 страницах. Список литературы содержит 165 наименований.

Содержание работы

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

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

Определение 1. Функция f : {0,1}* —> {0,1}* называется сильно односторонней, если выполняются следующие условия.

1. Существует детерминированная машина Тьюринга М со входным алфавитом {0,1}, которая за полиномиальное время вычисляет функцию f.

2. Для каждой вероятностной машины Тьюринга М' и каждого многочлена р для всякого достаточно большого и

Pr [M.'(f(x), 1n) G f-1(f(*))] < ^у, где вероятность берётся по случайным битам машины М.' и входу х длины п (оба распределения равномерные).

Определение 2. Функция f: {0,1}* —> {0,1}* называется слабо односторонней, если выполняется условие 1 определения 1, а вместо условия 2 выполнено следующее.

2. Существует такой многочлен р, что для каждой вероятностной машины Тьюринга М.' для всякого достаточно большого n Pr [M'(f(x),ln) £ f-1(f(x))] > ^Ly, где вероятность берётся по случайным битам машины М' и входу х длины п (оба распределения равномерные).

Проще говоря, односторонняя функция — это функция, которую легко вычислить, но трудно обратить. Но для того чтобы построить криптосистему, то есть метод передачи сообщений между двумя участниками, просто односторонних функций недостаточно. Нужно не только чтобы противник не смог расшифровать передаваемый код, но и чтобы второй участник смог это сделать. Поэтому для построения криптосистемы необходимо построить не просто семейство односторонних функций, а семейство функций с секретом (trapdoor functions), для которых существует такая дополнительная информация (секрет, trapdoor), что с её помощью обратить функцию становится просто.

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

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

Определение 3. Пусть функция f : {0,1}* —> {0,1}* такова, что если существует некоторая функция g : {0,1}* —> {0,1}*, являющая-

ся сильно (слабо) односторонней функцией, то f тоже является сильно (слабо) односторонней функцией. Тогда f называется полной сильно (слабо) односторонней функцией.

Рассмотрим конечный алфавит Л. Упорядоченную пару строк {g,h) над алфавитом Л мы будем называть правилом подстановки (rewriting rule). Эти пары записываются как д —> h. и интерпретируются как правила, по которым в других строках производятся подстановки. Достижимость в полусистеме Туэ будем обозначать через и v, ограниченную версию (достижимость за и шагов) — через и v.

Задача 1 (достижимости с распределением для полусистем Туэ). Вход. Полусистема Туэ R = {(gbHi),...,(gm)Hm)}, две битовые строки и и v, натуральное число п. Размер входа, таким образом, равен logn + |u| + |v| + +1^1)• Задача. Верно ли, что и v ?

Распределение. Случайно и независимо выбрать сначала натуральные числа пиши битовую строку х, затем битовые строки ui.vi,...jU^Vm. Числа и строки выбираются по стандартному квазиравномерному распределению, плотность которого пропорциональна ^ для натуральных чисел и ^р- для битовых строк.

Мы вводим ещё одно понятие достижимости в полусистемах Туэ. Для полусистемы Туэ R будем записывать u 4>r v, если u — agb и v = аНЪ для некоторого правила подстановки (д,Н) б R и строк а, Ъ Е Л\ причём не существует никакого другого правила подстановки (д', К') е R, для которого было бы верно, что и = а'д'Ь' и v = a'h'b'

для некоторых a',b' £ Л*. Мы расширяем =4r до своего транзитивно-рефлексивного замыкания =>Rl а также вводим ограниченную версию:

Ln ! * ^

u v, если u =>R v, и соответствующая цепь состоит из не более чем

I *

п шагов. Иначе говоря, и v, если и v, и на каждом шаге этого вывода есть ровно одно применимое правило подстановки. Эта единственность (или, точнее говоря, этот детерминизм) крайне важна для того, чтобы применить метод Левина.

Классическая задача Поста, которая, как и задача достижимости с распределением для полусистем Туэ, является полной для класса DistNP, определяется следующим образом.

Задача 2. Вход. Натуральное число т, пары битовых строк Г = {(ui, vi),..., (um.Vm)}, битовая строка х, натуральное число п. Размер входа, таким образом, равен logn + |х| + ]Г™(|и;| + М).

Задача. Верно ли, что гц,.. .гцк = х^,... Vik для некоторого к < п? Распределение. Случайно и независимо выбрать сначала натуральные числа тт и тп. и битовую строку х, затем битовые строки Числа и строки выбираются по стандартному квазиравномерному распределению, плотность которого пропорциональна для натуральных чисел и ^¡г для битовых строк.

Её детерминированная версия определяется следующим образом:

!

будем говорить, что из х выводится у за один шаг (х Ьр у), если существует не более двух таких пар (р.в), {р', б') е Г, что ру = хв и р'у' = хв' для некоторых строк у, у' (где у ф у', но р может совпадать с р': два разных применения одного и того же правила всё равно приводят к недетерминизму) и, более того, к строке у' непримени-

I *

мо ни одно из содержащихся в Г правил. Как и ранее, через х 1-г у будем обозначать транзитивно-рефлексивное замыкание этого отношения, а также введём ограниченную версию отношения: будем запи-1п ! сывать и Ьг V, если и Ир V за не более чем п шагов.

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

I

х у как х —у с дополнительным ограничением: мы разрешаем добавлять новую плитку в частично замощенный квадрат только в том случае, если во множестве Т есть ровно одна подходящая плитка. Определение 4. Функция замощения — это функция ^ : {0,1}* —> {0,1}*, определённая следующим образом:

— если вход имеет вид (Т, х) для конечного множества плиток Т и строки х, их —^ту, то ¿(Т,х) — (Т,у);

— в противном случае, = (Т,х).

Теорема 1. Если односторонние функции существуют, то функция замощения является (слабо) односторонней функцией. Определение 5. Функция доступности для полусистем Туэ (ФДПТ') — это функция А* Л*, определённая следующим образом:

— если вход имеет вид ({дьИ]),..., (дт.^Цг^х), и в полусисте-

I 1

ме Туэ Г = ((дьТт-1),---.(дтЛт>) верно, что х у, г = |х|2 + 4|х| + 2, в Г нет правил подстановки, которые были бы применимы к у, и |у| = |х|, то f(Г>x) = (Г,у);

— в противном случае, ^Г,х) = (Г,х).

Теорема 2. Если односторонние функции существуют, то ФДПТ является (слабо) односторонней функцией.

Определение 6. Функция преобразования Поста (ФПП) — это функция А* Л*, определённая следующим образом:

— если вход имеет вид

«дъМ,... ,<д ГП) Нт),*). и для системы правил подстановки

Г = ({дьК1),...,{дт,Нт» :

I

верно, что х —у, в Г нет правил подстановки, которые можно было бы применить к у, и |у| = |х|, то ^х) = (Г,у);

— в противном случае, f f(Г)x) = (Г,х).

Теорема 3. Если односторонние функции существуют, то ФПП является слабо односторонней функцией.

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

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

В современной криптографии практически нет доказуемо надёжных конструкций; нет ни безусловных, ни условных (в разумных классических предположениях) доказательств надёжности. Поэтому ценны даже слабые результаты в этом направлении. В 1992 году А. Хильт-ген сконструировал функцию, для которой сумел доказать линейную разницу между сложностью её вычисления и обращения: функцию Хильтгена вдвое труднее обратить, чем вычислить. Его пример является линейной функцией над С?(2) с матрицей, у которой мало ненулевых элементов, в то время как в обратной к ней матрице ненулевых элементов много.

Основной результат третьей главы — конструкция другого слабо надёжного криптографического примитива: семейства функций с секретом. Для получения этого результата доказана нижняя оценка на схемную сложность функций определённого вида; для этого использован метод исключения гейтов (gate elimination), на котором основаны практически все существующие нижние оценки в схемной сложности. Вот определение, которому соответствуют основные конструкции третьей главы.

Определение 6. Зафиксируем функции pi, ti, m, с : N —> N. Семейство кандидатов в функции с секретом представляет собой последовательность троек С = {(Seedn,Evaln)Invn)}£L,, где {Seedn}^, — это семейство схем порождения ключей Seedn : Вп —> Bpl'nl х Btl(n\ {Evaln}^L, —. это семейство вычисляющих функцию схем Evaln : Bpi(nl х Bm(n) Bc(n), a {Invn}~=1 - это семейство обращающих функцию схем Inva : Btl!n) х Вс(п) Bm(n), причём для каждого п, каждого s £ Вп и каждого т G Bm(n' (сообщения) Invn(Seedn,2(s),Evaln(Seedn,i(s},m)) =m, где Seedn,i (s) и Seedn^fs) — первые pi(n) бит («публичная информация», public information) и последние ti(n) бит («секрет», trapdoor information) выхода схемы Seedn(s), соответственно.

Чтобы понять, насколько функция надёжна, нужно ввести понятие взлома функции. В дальнейшем через C(f) обозначается минимальный размер схемы, вычисляющей функцию f, а через — минимальный размер схемы, вычисляющей функцию f G £?n>m на более чем j её входов (длины п.).

Определение 7. Схема N успешно обращает семейство кандидатов в функции с секретом {Seedn,Evaln,Invn} на входах длины п, если для равномерного распределения U, взятого по s € Вп и m € Bm'n' (по начальным числам генератора и входам), Pr(s,m)£u[N(Seeda1i(s),Evaln(Seedn,1(s),m)j = m] > Определение 8. Будем говорить, что семейство кандидатов в функции с секретом С = {(Seedn, Evaln> Invn)}^ имеет порядок надёжности k € R, если для каждой такой последовательности ^»oi. /м V» а *-птп<пт-, м nr-natifun nfjryntuает С "Ао. входах длины

Введены конструкции матриц сложных функций. Основным их составным блоком является матрица А = еп + + для сг =

(1... п). Для анализа сложности был применён метод исключения гей-

тов. Вот главная лемма третьей главы, на которой основаны дальнейшие доказательства.

Лемма 1. Пусть 1:,и > 1. Предположим, что %: Вл,(п) —» Ви — это линейная функция с матрицей X над полем СР(2). Предположим также, что все столбцы X различны, в каждой строке X есть по меньшей мере и ненулевых элементов, и после удаления любых 1 столбцов X в матрице всё ещё останется строка, содержащая по крайней мере два ненулевых элемента. Тогда С(х) > и +1 и, более того, С1/2(х) > и +I.

Она была обобщена на случай блочно-диагональных матриц. Лемма 2. Пусть линейная функция С определяется блочно-диаго-налъной матрицей Х1ФХ2©.. .®Хт, и матрицы X, удовлетворяют условиям леммы 1 с параметрами \ц иЦ, соответственно (матрицы могут быть прямоуголънъши и иметь разный размер). То-

гда С(С) > +tj) и, более того, С1/2(С) > Xj!L,(Uj + ts).

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

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

где А' обозначает матрицу с той же структурой, что и А, но для размерности сш. вместо п. Тогда в терминах определения 6 мы получаем семейство кандидатов в функции с секретом, где входы и выходы функции длиннее начального числа генератора, а также публичной информации и секрета: pi(n) = ti(n) = n, c(n) = m(n) = (1 + a)n. Для а = 2 (точка максимума порядка надёжности) получается следующий результат.

Теорема 4. Существует, семейство функций с секретом, надёжных в слабом смысле, с длиной начального числа генератора pi(n) = ti(n) = п, длинами входа и выхода функций с(п) = т(п) = 3 пи порядком надёжности в слабом смысле Щ.

Классическим методом увеличения сложности удаётся получить конструкцию с суперполиномиальной гарантией надёжности. Теорема 5. Существует семейство надёжных в слабом смысле функций с секретом С = {Seedn, Evaln, Inv^^L, с длиной начального числа генератора pi(n) = ti(n) = п, длинами входа и выхода функций с(п) = m(n) = Зп, схемными сложностями C(Invn) < ^ + 0(1), C(BvaIn) < +0(1), С(Seedn) =п+1 и порядком надёжности в слабом смысле Ц. Более того, для любой константы 5 > 0 ни один противник, располагающий менее чем ^n — ¿6y/ñ гейтами, не способен обратить эти функции с секретом на более чем ¿^v^+oíi/íí) доле их входов.

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

Определение 9. Противник С осуществляет доказуемый взлом криптосистемы (G,E,D), если существует такой многочлен р, что для равномерного распределения по множеству сообщений т и множеству случайных битов всех участвующих в конструкции алгоритмов (где публичный ключ рк порождается G(1n)) Pr[C(E(m,pk,r),pk) = (m,r')] > ¿j, где Е(пцрк,т') = Е(т,рк,т), а п — параметр надёжности.

Определение 10. Противник С осуществляет доказуемый взлом в худшем случае криптосистемы (G, Е, D), если существует такой многочлетр, что для всех сообщений т, всех пар ключей (pk,sk), сгенерированных алгоритмом порождения ключа G(1n), и всех случайных битов алгоритма кодирования Е Pr[C(E(m,pk,r),pk) — (тп,г')] > где E(m,pk,r') — Е(тп,рк,г), п. — параметр сложности, а распределение берётся по множеству случайных битов

взламывающего алгоритма С.

Будем говорить, что криптосистема (G,E,D) надёжна против доказуемого взлома (в худшем случае), если не существует полиномиальной вероятностной машины Тьюринга С, которая бы осуществляла доказуемый взлом (в худшем случае) криптосистемы (G,Е,D).

В пятом разделе описываются основные конструкции, рассматриваемые в этой главе — криптосистемы, основанные на инвариантах групп. В такой криптосистеме качестве секретного ключа Алиса выбирает некоторое множество X и такой инвариант f : Fn —> X, что Vg е G i(gx) = f(x). Она также выбирает заданное базисом подпространство сообщений М С Р; выбирает она его так, чтобы разные сообщения m е М представляли разные орбиты группы G на множестве М: V mi Ф тп.2 € М f(mi) ф f(m.2). Таким образом, криптосистема, основанная на инвариантах, определяется набором (G,f, М). В качестве публичного ключа Алиса передаёт набор образующих группы G (его размер должен быть полиномиален от п) и базис пространства М.

Боб выбирает вектор m е М (где m — сообщение, которое нужно закодировать) и случайный элемент g G G. Затем Боб передаёт Алисе gm.. Алиса может расшифровать сообщение, вычислив известный ей инвариант f(gm) = f(m). Поскольку Алиса выбирала пространство сообщений М трансверсально орбитам, значение инварианта f(m) однозначно позволит ей найти исходное сообщение т. Будем называеть набор (G,f,M) допустимым, если он корректно определяет криптосистему, основанную на инвариантах, т.е. для G, f и М выполняются приведённые в первом абзаце условия.

Первая из конструкций основана на модулярной группе. Рассмотрим в качестве G унимодулярную группу G = {(J f), х £ Z}. В качестве инварианта f мы рассмотрим тривиальный инвариант f (^) = %2» а в качестве пространства сообщений М. — множество векторов М = {('),% G Z}. Боб выбирает случайный элемент g в этой группе, получая его в результате произведения не более чем N образующих. Затем он применяет g к вектору-сообщению тп. и передаёт полученный вектор gm и N. Алиса вычисляет f(gm) и решает, каким был вектор т. Теорема 6. Если существует, противник С, который осуществляет доказуемый взлом в худшем случае описанной выше криптосистемы (G,f,M.) за время, полиномиальное от суммы длин сообщения и публичного ключа, то NP С RP.

В разделах 6 и 7 предложен способ делать криптосистемы, основанные на инвариантах, надёжными и в обычном смысле. Рассмотрим дерево, каждая вершина которого содержит набор (С^, М). Алиса строит это дерево от листьев к корню, на каждом шаге запоминая в, { и М. После создания дерева Алиса берёт криптосистему, получившуюся в корне дерева, и использует её для кодирования вышеописанным способом.

Рассмотрим класс групп 0, замкнутый относительно некоторого множества теоретико-групповых операций О (список операций будет приведён ниже), которые преобразуют допустимые наборы в допустимые наборы. Для множества Оо С С/ (которое является базой конструкции) мы рекурсивно определим класс Т{0о,О) четвёрок (в, ^М,Т) следующим образом.

— База рекурсии: любая четвёрка (С,^ М.,Т), где в € М) является допустимым набором, а Т — дерево из одной вершины, маркированной набором (С, М).

— Шаг рекурсии: для всех наборов четвёрок {(61, Мг,Тг)}?=1 и любой Б-арной операции о е О класс О) содержит четвёрку (С.^М.Т), где С = о^ь...^,), f - М = о(М1,..., М5), а Т — дерево, получающееся из деревьев ~П, г.. ,Т5 добавлением нового корня с меткой о, к которому корни поддеревьев Т),..., Т5 добавляются как потомки.

В качестве шага рекурсии можно рассмотреть такие конструкции, как изменение базового кольца, сопряжение, прямое произведение, сплетение групп, переход к хессиану или якобиану нескольких инвариантов.

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

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

Рассмотрим группу С, и пусть два игрока А и В выбирают некоторые подгруппы С, заданные своими образующими: Сд = (аь • • •) °т), Св = {Ь],...,Ьп). Группа в и элементы сц, 1 < г < ттг, и Ъ^ 1 < ] < п,

выдаются публично. Оба игрока А и В случайно выбирают секретные элементы û g Ga и Ъ g Gb как произведения не более чем n образующих, а затем передают друг другу следующую последовательность:

ХА = {a"1 b¡ q}]L, , Хв = {b"1 щЬ}£,.

У игрока А (соотв. В) изначально имеется представление элемента а (соотв. Ъ) в подгруппе Ga (соотв. Gb), a после этой передачи появляется новый набор образующих Ъ-,сцЬ (соотв. a-1bia), соответствующих исходным civ. Значит, он может вычислить представление элемента Ь~'аЪ (соотв. а_1Ьа), используя элементы последовательности ХА (соотв. Хв). Таким образом, у обоих участников образуется общий ключ, а именно коммутатор аГ'(Ь-1аЬ) = [а,Ъ] = (а-1Ъа)_1Ъ. Очевидное необходимое условие надёжности этого протокола состоит в том, что множество всех коммутаторов элементов a g Ga и Ъ g Gb должно состоять, как минимум из двух элементов. Этот протокол называется протоколом согласования ключа Ашпель-Аншеля-Голдфельда. Теорема 7. Рассмотрим модулярную группу G = SL2(Z). Существуют такие подгруппы Ga<GuGb<G, что если протокол согласования ключа Аншелъ-Аншеля-Голдфелъда для группы G и её подгрупп Ga и Gb подвержен доказуемому взлому в худшем случае, то NP С RP. То же самое верно, если вместо Ga и Gb рассмотреть Ga и Gb, порождённые теми же образующими (си,..., ат) и (bi,..., bn) соответственно, но не как группы, а как полугруппы.

Работы автора по теме диссертации

1. Григорьев Д. Ю., Кожевников А. А., Николенко С. И. Алгебраическая криптография: новые конструкции и их надёжность относительно доказуемого взлома // Алгебра и Анализ. 2008. Т. 20, № 6. С. 119-147.

2. Grigoriev D., Kojevnikov A. A., Nikolenko S. I. Invariant-Based Cryptosystems and Their Security Against Provable Break: Tech. Rep. 158: M ax-Planck-Institut preprints, 2007.

3. Kojevnikov A. A., Nikolenko S. I. New Combinatorial Complete One-Way Functions // Proceedings of the 25^ Symposium on Theoretical Aspects of Computer Science. Bordeaux, Prance, 2008. P. 457-466.

4. Гирш Э. А., Николенко С. И. Надёжная в слабом смысле функция с секретом // Препринты ПОМИ, 16/2008.

Тиражирование и брошюровка выполнены в учреждении

«Университетские телекоммуникации»

197101, Санкт-Петербург, Саблинская ул., 14

Тел. (812) 233 4669 ' объем 1 п.л.

Тираж 100 экз.

1 Введение

1.1 Криптография как раздел информатики

1.2 Модели вычислений.

1.3 Основные определения современной криптографии

2 Новые конструкции полных односторонних функций

2.1 Введение.

2.2 Задача достижимости с распределением для полусистем

2.3 Задача Поста.

2.4 Полная односторонняя функция, основанная на задаче поиска замощения.

2.5 Полная односторонняя функция, основанная на полусистемах Туэ.

2.6 Полная односторонняя функция на базе задачи Поста

2.7 Полные односторонние функции и DistNP-трудные комбинаторные задачи.

2.8 Полные односторонние функции в большей общности

3 Новые конструкции криптографических примитивов, доказуемо надёжных в слабом смысле

3.1 Введение.

3.2 Определения.

3.3 Матрицы сложных функций.

3.4 Исключение гейтов.

3.5 Две конструкции .67

3.6 Семейство функций с секретом, надёжных в слабом смысле

3.7 Функция с секретом с экспоненциальной гарантией надёжности

4 Новые алгебраические конструкции криптографических примитивов

4.1 Алгебраическая криптография.

4.2 Ослабленные результаты современной криптографии

4.3 Доказуемый взлом

4.4 Определения.

4.5 Криптосистемы, основанные на инвариантах групп, и их доказуемый взлом.

4.6 Дерево групп.

4.7 Листья дерева.

4.8 Атаки на криптосистемы, основанные на инвариантах

4.9 Схема согласования ключа Аншель-Аншеля-Голдфельда и её устойчивость против взлома с доказательством

1.1 Криптография как раздел информатики

Классическая криптография, понимаемая как способ передать сообщение так, чтобы противник не сумел его расшифровать, применялась, наверное, с тех самых пор, как люди впервые задумались о том, как передавать друг другу сообщения. Различногр рода шифры, в том числе весьма изящные, применялись ещё в античности. Древние греки (точнее, спартанцы) использовали так называемые скиталы: цилиндры, на которые наматывались узкие полоски пергамента. Затем текст писали на полоске поперёк цилиндра; получался перестановочный шифр, для декодирования которого нужно было снова намотать пергамент на цилиндр такой же толщины [78]. Юлий Цезарь считается изобретателем шифра Цезаря, в котором каждый символ алфавита заменяется на другой, отстоящий от него в алфавите на некоторое фиксированное число позиций (смещение). Краткое руководство по использованию шифров для обмена любовными посланиями содержит даже «Камасутра».

Довольно давно- появились и первые работы, направленные на взлом шифров. Разумеется, если кто-то что-то от кого-то скрывает, значит, это может иметь ценность, и эту ценность порой можно было добыть успешной дешифровкой. Такие, сугубо прикладные работы, конечно, велись с самого появления шифров. Однако появлялись и теоретические исследования. Например, и шифр Цезаря, и большинство других кодов и шифров, использовавшихся в античности и средние века, не были устойчивы против метода частотного анализа, при котором наиболее вероятная расшифровка того или иного символа вычисляется исходя из частоты встречаемости этого символа в закодированном тексте (при известных частотах появления букв алфавита в среднестатистическом тексте на данном языке). Этот метод, судя по всему, впервые рассмотрели Абу Юсуф аль-Кинди и другие арабские учёные (для арабского же языка, разумеется) в IX-X вв. нашей эры [5]. В качестве источников по истории классической криптографии можно порекомендовать [14,74,117].

Современная криптография, которую рассматривают как раздел информатики, — очень молодая наука. Она настолько молода, что даже если начинать изложение её истории раньше её «официального» появления, всё равно за рамки XX века выйти не получится. К началу века относится первый серьёзный теоретический успех: конструкция абсолютно стойкого шифра, так называемой «схемы одноразовых блокнотов» (one-time pad), разработанной Гильбертом Вер-намом и Клодом Моборном [129]. В этой схеме с закрытым ключом в качестве шифра транслируется побитовая сумма (XOR) кодируемого сообщения и случайной битовой строки. При условии надёжной передачи секретного ключа (это, конечно, самое уязвимое место) схему одноразовых блокнотов взломать невозможно [113]; это первый код с таким свойством.

Появление современной криптографии было в значительной степени мотивировано военными нуждами: во время Второй мировой войны надёжная и защищённая связь была крайне ценна. Значительная часть того, что происходило в Влетчли-парке и аналогичных учреждениях, относилась, конечно, ко взлому и разработке конкретных шифров. Но шла и теоретическая работа. Первым математически полным и строгим изложением теории кодирования следует, видимо, считать послевоенные работы Клода Шеннона по теории информации [112,113]. Шеннон заложил математическую базу для криптографических исследований, однако в течение почти тридцати последующих лет исследования в этом направлении либо не проводились вовсе, либо были засекречены.

Прорыв, который мы склонны считать настоящим началом криптографии как раздела информатики, произошёл в середине 1970-х гг. Во-первых, в 1975 году появился первый настоящий криптографический стандарт — DES, Data Encryption Standard — разработанный в IBM и предлагаемый банкам и другим финансовым организациям для обмена секретными данными [43]. DES обладал весьма высокой надёжностью, его криптоанализ не выявил серьёзных дефектов, и взломать DES стало возможным только тогда, когда вычислительных мощностей оказалось достаточно для пусть улучшенных, но всё же атак «грубой силой» [21,34,40].

А главное — в 1976 году появилась работа Уитфилда Диффи и Мартина Хеллмана «New directions in cryptography» [39], в которой была впервые предложена конструкция криптографического примитива (в данном случае — протокола согласования ключа), который по! лагался не на надёжность передачи некоторого секретного ключа или алгоритма дешифровки, как все его предшественники, а на вычислительную сложность решения некоторой задачи, в данном случае — дискретного логарифма (вскоре появился и соответствующий патент, включающий в число авторов оказавшего большое влияние на становление криптографии Ральфа Меркле [68]). В протоколе Диффи-Хеллмана участники (их традиционно называют Алиса и Боб) сначала договариваются (открыто) о том, по какому простому модулю р проводить вычисления и какой первообразный корень д по модулю р использовать. Затем Алиса секретно выбирает натуральное число а и открыто пересылает да mod р. Боб секретно выбирает натуральное число Ъ и открыто пересылает дъ mod р. В результате у участников протокола образуется общий секрет gab mod р, который они могут использовать, например, в криптографических протоколах с секретным ключом. А противнику, для того чтобы получить этот секрет, нужно по д, да и дъ восстановить gab; эта задача считается вычислительно сложной.

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

Эта работа была вскоре продолжена, и появились новые криптографические примитивы, основанные на вычислительно сложных задачах. В 1978 году Ривест, Шамир и Эйдельман предложили криптосистему с открытым ключом RSA [107], которая до сих пор остаётся одним из наиболее успешных примеров таких криптосистем. В криптосистеме с открытым ключом Боб должен передать Алисе сообщение, закодировав его при помощи своего публичного ключа так, чтобы Алиса смогла его дешифровать при помощи своего секретного ключа. Пару (секретный ключ, публичный ключ) генерирует Алиса перед началом обмена сообщениями. В протоколе RSA ключи порождаются следующим образом: Алиса выбирает два простых числа р и q, вычисляет n = pq и ф(тг) = (р — 1)(q — 1), а затем выбирает число 1 < е < ф(п), взаимно простое с ф(п), и вычисляет такое d, что de = 1 (mod ф(п)). Затем Алиса передаёт в качестве публичного ключа пару чисел (п, е). Боб, желая передать число m < тг, кодирует его как с = me mod п и открыто пересылает (чтобы избежать атак, работающих в частных случаях, Боб должен передавать в качестве m не своё сообщение, а его версию, модифицированную при помощи одной из так называемых padding schemes). Алиса теперь может расшифровать это сообщение, вычислив его как m = cd mod п, так как, по малой теореме Ферма, cd = (me)d = med = m (mod n).

Задача взломщика в этой системе была бы простой, если бы число п можно было эффективно разложить на множители; стоит отметить, что обратное неизвестно: взаимоотношения между факторизацией и задачей взлома RSA до конца ещё не установлены [27,29,106]. Уже были разработаны две успешные атаки на RSA, причём обе в том или ином смысле использовали принцип «одним махом перебрать все возможные делители»; одна из них проводится в так называемой unit-cost модели, где разрешено за один шаг делать арифметические операции над числами произвольной длины [110], а другая работает на квантовых компьютерах [116]; однако в классической модели успешно раскладывать числа на множители или решать задачу RSA пока не умеет никто.

Основными источниками по базовым определениям и конструкциям современной криптографии можно считать [50-53,77,89].

1.2 Модели вычислений

Прежде чем давать определения, следует определить модель вычислений, в которой мы будем работать. Долгое время модель вычислений была единственной и естественной, основанной на работах Тьюринга и Поста [99,101,127], которые построили базовые конструкции, эквивалентные друг другу и предположительно реализующие все возможные алгоритмы. Это предположение получило известность как тезис Чёрча-Тьюринга] тезис, выдвинутый самим Чёрчем, касался общерекурсивных функций и функций, вычислимых при помощи Л-исчисления Чёрча [31,33,127]. Поэтому классическая теория сложности изучает алгоритмы, реализуемые на машине Тьюринга [12,49,61,71,96,119,162].

Однако в последние годы значительно возрос интерес к другой модели вычислений, квантовым вычислениям, которые используют схемы, построенные из непрерывных унитарных отображений, производящихся над квантовыми системами [19,41,47,73,86,94,141, 149]. Эта модель не предоставляет принципиально новых вычислимых функций, но вполне возможно, что в ней некоторые задачи можно решить быстрее, чем в классической модели. В частности, популярность квантовой модели вычислений началась с алгоритма Шора, которым можно решить задачу разложения числа на простые множители и задачу дискретного логарифма [116]. Таким образом, и криптосистема RSA, и протокол согласования ключа Диффи-Хеллмана перестают быть надёжными, если противник может использовать квантовые компьютеры. Конечно, квантовые компьютеры не всемогущи — например, NP-трудные задачи вряд ли можно будет решить на квантовых компьютерах за полиномиальное время [16]. Но наиболее популярные задачи классической криптографии, такие, как RSA, квантово решаются достаточно эффективно. Таким образом, оказалось, что для построения криптографических примитивов в квантовой модели вычислений требуются другие, более устойчивые конструкции. Это привело к развитию так называемой квантовой криптографии, которая использует квантовые эффекты для согласования ключа и построения других примитивов [17,18].

В частности, именно квантовые вычисления и алгоритм Шора стали одной из главных мотиваций для исследования некоммутативных криптографических примитивов [8-10,15, 93,95,102,148]. В то время как алгоритм Шора решает задачу факторизации и дискретного логарифма в абелевых группах [79,149], о некоммутативных примитивах ничего подобного не известно. Новые конструкции таких примитивов, описанные в главе 4, являются одним из основных результатов настоящей работы.

В главе 4 мы будем исследовать некоммутативные схемы, но ка' саться квантовой криптографии как таковой не будем. Поэтому здесь мы зафиксируем классическую модель вычислений и приведём лишь базовые классические определения. В определении машины Тьюринга мы следуем классическим источникам [71,162]. Определение 1.1 Машина Тьюринга — это упорядоченная семёрка М = (Q, Г,В, X,7t,s, Н), где

Q — конечное множество состояний машины Тьюринга;

Г — конечный алфавит символов ленты\

В € Г — пустой символ (единственный символ, который может встречаться на ленте бесконечное число раз);

I С Г \ {В} — алфавит символов, подаваемых на вход;

7t:Qxr—>Qxrx{L,R}— функция перехода, описывающая работу машины Тьюринга: L обозначает сдвиг головки влево, R — вправо (существуют также модификации определения, позволяющие головке оставаться на месте); s G Q — начальное состояние машины Тьюринга;

Н С Q — множество конечных состояний.

Нас будут интересовать только машины с единственным конечным состоянием Н = {h}. Неформально говоря, машина Тьюринга состоит из бесконечной в обе стороны ленты и головки, расположенной над одной из ячеек этой ленты. На ленте в начальном состоянии s записан вход, являющийся строкой над L. Машина производит переходы из одного состояния в другое в соответствии с функцией 7г, на вход которой подаётся текущее состояние q е Q и символ а € Г, который на данном шаге находится под головкой. Головка двигается влево или вправо в соответствии с третьей компонентой результата функции я.

Машина Тьюринга М вычисляет функцию f : I* —» (Г* \{В})*, если при запуске М со входом х G I* она заканчивает работу (переходит в состояние Н), оставляя на ленте строку f(x). В дальнейшем мы для простоты не будем делать различий между алфавитами L и Г\{В}. Обозначим через tjvi(x), где tju : I* —> N, количество шагов, которое требуется машине Тьюринга М, чтобы, получив на вход х, перейти в конечное состояние Н. Машина Тьюринга М работает в течение времени Т : N —> N, если

Vtl € N max tM(x) < T(n), x:|x|=n где |x| — длина строки х.

Нам также потребуются недетерминированные и вероятностные машины Тьюринга. Мы не будем давать отдельных определений, а будем считать, что недетерминированная машина Тьюринга — это обычная детерминированная машина Тьюринга с двумя лентами, на которых записаны две части входа: собственно вход и «подсказка»; недетерминированная машина Тьюринга М. вычисляет функцию f : I* —> I*, если для каждого входа х существует такая «подсказка» у б I*, что М.(х,"у) = f(x). Вероятностная машина Тьюринга — это то же самое, что недетерминированная, изменяется только интерпретация: символы подсказки теперь интерпретируются как случайные символы машины; будем говорить, что вероятностная машина Тьюринга вычисляет функцию f на входе х с вероятностью р, если

PryGUm [M.(x,ij) = f(x)] =р, где m — количество случайных символов из L, Um — равномерное распределение на строках длины m из алфавита Z, а у G Um означает «у взято по распределению Um». В дальнейшем обычно I = {0,1}.

В дальнейшем мы будем пользоваться тезисом Чёрча и использовать термины «алгоритм» и «машина Тьюринга» как синонимы; например, «полиномиальный алгоритм» — это алгоритм, реализуемый полиномиальной машиной Тьюринга, т.е. машиной, работающей в течение времени T(n) = cinC2 для некоторых констант ci и С2.

Другой важной для данного исследования моделью вычислений является схемная сложность [109,125,130,137,142,159]. В схемной модели сложность функции определяется как размер минимальной схемы, которая реализует эту функцию. Схемы состоят из гейтов, в качестве которых могут выступать различные булевские функции. Первые работы по схемной сложности относятся, разумеется, к тому же времени, когда Клод Шеннон впервые записал определение булевских схем и начал развивать теорию, позволяющую строить вычисления на основе пропозициональной логики Буля [111,114,115].

Дадим точное определение схемы. Прежде всего обозначим через Bn>m множество всех l™2" функций f : Bn -» Вт, где В = {0,1} — поле из двух элементов.

Определение 1.2 Пусть П — некоторое множество булевских функций f : Bm —> В (m может быть разным для разных f). Тогда О-схема — это ациклический направленный граф с метками, состоящий из вершин двух типов: вершин входящей степени 0 (вершин, в которые не входят рёбра), маркированных одной из переменных xi,., хп, и вершин, маркированных одной из функций f £ П, в которые входит столько рёбер, какова арность этой функции.

Вершины первого типа называются входами, вершины второго типа — гейтами1. Размер схемы — это количество гейтов в ней.

1В русскоязычной литературе встречается термин «вентиль», и лет сорок назад он был общеупотребителен; но мы, пожалуй, не рискнём

Каждый гейт Q-схемы вычисляет некоторую булевскую функцию. Соответственно, схемная сложность функции f : Вп —» Вт в базисе О. обозначается как Co(f) и определяется как размер минимальной Ц-схемы, которая вычисляет функцию f (в которой есть m гейтов, вычисляющих результат применения функции f ко входным битам). Чтобы можно было без оговорок устранить унарные гейты, будем считать, что в гейте вычисляется как сам результат его функции, так и его отрицание. Наша модель вычислений — это булевские схемы с произвольными бинарными гейтами; иными словами, каждый гейт схемы маркируется одной из 16 булевских функций из ®2,1 • В дальнейшем через C(f) будет обозначаться схемная сложность f в базисе ®2,1, состоящем из всех бинарных булевских функций. Мы будем предполагать, что каждый гейт в этой схеме зависит от обоих входов, т.е. нет гейтов, маркированных константами и унарными функциями Ий-1. Это не умаляет общности, потому что такие гейты легко исключить из нетривиальной схемы, не увеличивая её размер.

Стоит отметить, что схемная сложность — одна из немногих моделей вычислений, в которых возможны доказательства конкретных, а не асимптотических оценок сложности. Например, Л. Стокмайер в своей диссертации привёл функцию, любая реализация которой при помощи бинарной булевской схемы на входах размера <616 должна иметь не менее 10123 гейтов [6,123,125].

Основные результаты в классической схемной сложности относятся к 1980-м гг. и раньше; в них значительна заслуга отечественных учёных [24,97,124,125,153-156,158,160,161,163-165]. В последние годы центр усилий в теории схемной сложности переместился на результаты, связанные со схемами ограниченной глубины и/или ограниченным набором вычисляемых в них функций [3,30,48,67,72,103, его использовать.

121,138,140,157]. Однако нам потребуются именно классические результаты, поскольку оценки, которые мы будем доказывать в главе 3, будут выполняться над базисом Вг,1.

1. Advances in Elliptic Curves in Cryptography / Ed. by 1. Blake, G. Seroussi, N. Smart. Cambridge University Press, 2005. Vol. 317 of London Mathematical Society.

2. Agrawal M., Kayal N., Saxena N. PRIMES is in P // Annals of Mathematics. 2004. Vol. 160, N. 2. P. 781-793.

3. Ajtai M. L]-formulae on finite structures // Annals of Pure and Applied Logic. 1983. Vol. 24. P. 1-48.

4. Ajtai M., Dwork C. A public-key cryptosystem with worst-case/average-case equivalence // Proceedings of the 29^ Annual ACM Symposium on Theory of Computing. 1997. P. 284-293.

5. Al-Kadi I. A. The origins of cryptology: The Arab contributions // Cryptologia. April 1992. Vol. 16, N. 2. P. 97-126.

6. Allender E. Circuit Complexity before the Dawn of the New Millennium // Proceedings of the 16^ Conference on Foundations of Software Technology and Theoretical Computer Science. 1996. P. 118.

7. Anshel I., Anshel M., Goldfeld D. An algebraic method for public-key cryptography // Mathematical Research Letters. 1999. Vol. 6. P. 287-291.

8. Anshel I., Anshel M., Goldfeld D. Non-abelian key agreement protocols // Discrete Applied Mathematics. 2003. Vol. 130, N. 1. P. 312.

9. Anshel M. Braid group cryptography and quantum cryptoanalysis // Proceedings of the International Wigner Symposium. 2003. P. 13-27.

10. Apostol Т. M. Modular Functions and Dirichlet Series in Number Theory. Springer, New York, 1990.

11. Arora S., Barak B. Complexity Theory: A Modern Approach. Cambridge University Press. В печати. Черновик свободно доступен по адресу http://www.cs.princeton.edu/theory/complexity/, 2009.

12. Bach E. Explicit bounds for primality testing and related problems // Mathematics of Computation. 1990. Vol. 55, N. 191. P. 355380.

13. Bauer F. L. Decrypted Secrets: Methods and Maxims of Cryptology. Springer, 1997.

14. Benaloh J. Dense Probabilistic Encryption // Proceedings of the 1st Annual Workshop on Selected Areas in Cryptology. 1994. P. 120128.

15. Bennett С. H., Bernstein E., Brassard G., Vazirani U. Strengths and weaknesses of quantum computing // SIAM Journal of Computing. 1997. Vol. 26, N. 5. P. 1510-1523.

16. Bennett С. H., Bessette F., Brassard G., Salvail L., Smolin J. Experimental Quantum Cryptography // Journal of Cryptology. 1992. Vol. 5, N. 1. P. 3-28.

17. Bennett С. H., Brassard G. Quantum Cryptography: Public key distribution and coin tossing // Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. 1984. P. 175.

18. Bennett С. H., Shor P. W. Quantum Information Theory // IEEE Transactions on Information Theory. 1998. Vol. 44, N. 6. P. 27242742.

19. Berger R. The undecidability of the domino problem. 1966. Vol. 66 of Memoirs of the American Mathematical Society.

20. Biham E., Shamir A. Differential Crypt analysis of the Data Encryption Standard. Springer Verlag, 1993.

21. Blake I., Seroussi G., Smart N. Elliptic Curves in Cryptography. Cambridge University Press, 1999. Vol. 265 of London Mathematical Society.

22. Blass A., Gurevich Y. Matrix Transformation is Complete for the Average Case // SI AM Journal of Computing. 1995. Vol. 24, N. 1. P. 3-29.

23. Blum N. A Boolean Function Requiring 3n Network Size // Theoretical Computer Science. 1984. Vol. 28. P. 337-345.

24. Bogdanov A., Trevisan L. On Worst-Case to Average-Case Reductions for NP Problems // Proceedings of the 44t^1 Annual IEEE Symposium on the Foundations of Computer Science. 2003. P. 308317.

25. Bogdanov A., Trevisan L. Average-Case Complexity // Foundations and Trends in Theoretical Computer Science / Ed. by M. Sudan. 2006. Vol. 2.

26. Boneh D., Venkatesan R. Breaking RSA may not be Equivalent to Factoring // Proceedings of the 17^ Annual Eurocrypt Conference, Lecture Notes in Computer Science. Vol. 1233. 1998. P. 59-71.

27. Book R. V., Otto F. String Rewriting Systems. Springer-Verlag, 1993.

28. Brown D. R. L. Breaking RSA May Be as Difficult as Factoring: Tech. Rep. 2005/380: Cryptology ePrint Archive, 2005.

29. Grigoriev D., Hirsch E. A., Pervyshev K. A Complete Public-Key Cryptosystem: Tech. Rep. 006-046: Electronic Colloquium on Computational Complexity. To appear in Groups, Complexity, and Cryptology, 2006.

30. Grigoriev D., Kojevnikov A. A., Nikolenko S. I. Invariant-Based Cryptosystems and Their Security Against Provable Break: Tech. Rep. 158: Max-Planck-Institiit preprints, 2007.

31. Grigoriev D., Ponomarenko I. N. Homomorphic Public-Key Cryptosystems over Groups and Rings // Quaderni di Mathematica. 2004. Vol. 13. P. 305-325.

32. Grigoriev D., Ponomarenko I. N. Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits // Applicable Algebra in Engineering, Communication, and Computing. 2006. Vol. 17. P. 239-255.

33. Gu J., Purdom P. W., Franco J., Wah B. W. Algorithms for the Satisfiability Problem. Cambridge University Press, 2000.

34. Gurari E. An Introduction to the Theory of Computation. Computer Science Press, 1989.

35. Gurevich Y. Complete and incomplete randomized NP problems // Proceedings of the 28^ Annual IEEE Symposium on the Foundations of Computer Science. 1987. P. 111-117.

36. Gurevich Y. Average case completeness // Journal of Computer and System Sciences. 1991. Vol. 42, N. 3. P. 346-398.

37. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity / Ed. by J. van Leeuwen. The MIT Press/Elsevier, 1990.

38. Immerman M. Languages which capture complexity classes // SIAM Journal of Computing. 1987. Vol. 4. P. 760-778.

39. Jaeger G. Quantum Information: An Overview. Berlin: Springer,2006.

40. Katz J., Lindell Y. Introduction to Modern Cryptography. CRC Press, 2007.

41. Kelly T. The myth of the Skytale // Cryptologia. July 1998. P. 244260.

42. Kitaev A. Quantum computations: algorithms and error correction // Russian Mathematical Surveys. 1997. Vol. 52, N. 6. P. 53-112.

43. Koblitz N. Elliptic Curve Cryptosystems // Mathematics of Computation. 1987. Vol. 48. P. 203-209.

44. Kojevnikov A. A., Nikolenko S. I. New Combinatorial Complete One-Way Functions // Proceedings of the 25^ Symposium on Theoretical Aspects of Computer Science. Bordeaux, France, 2008. P. 457466.

45. Lamagna E. A., Savage J. E. On the logical complexity of symmetric switching functions in monotone and complete bases: Tech. rep. Rhode Island: Brown University, July 1973.

46. Lempel A. Cryptography in transition // Computing Surveys. 1979. Vol. 11, N. 4. P. 215-220.

47. Levin L. A. Average Case Complete Problems // SIAM Journal of Computing. 1986. Vol. 15, N. 1. P. 285-286.

48. Levin L. A. One-Way Functions and Pseudorandom Generators // Combinatorica. 1987. Vol. 7, N. 4. P. 357-363.

49. Lo H.-K., Spiller Т., Popescu S. Introduction to Quantum Computation and Information. World Scientific Publishing Company, 1998.

50. Luks E. M. Permutation Groups and Polynomial-Time Computation // DIMACS Series in Discrete Mathematics and Theoretical Computer Science / (DIMACS, 1991). Vol. 11. AMS, 1993. P. 139175.

51. Post E. Recursive Unsolvability of a Problem of Thue // Journal of Symbolic Logic. 1947. Vol. 12. P. 1-11. '

52. Rappe D. K. Algebraisch homomorphe Kryptosysteme. Diplomar-beit, Dem Fachbereich Mathematik der Universitat Dortmund. 2000.

53. Razborov A. A. Bounded arithmetic and lower bounds // Feasible Mathematics II / Ed. by P. Clote, J. Remmel. Birkhauser, 1995. Vol. 13 of Progress in Computer Science and Applied Logic. P. 344-386.

54. Regev O. On lattices, learning with errors, random linear codes, and cryptography // Proceedings of the 37^ Annual ACM Symposium on Theory of Computing. 2005. P. 84-93.

55. Regev O. Lattice-Based Cryptography // Proceedings of the 26^ Annual International Cryptology Conference (CRYPTO'06), Lecture Notes in Computer Science. Vol. 4117. 2006. P. 131-141.

56. Rivest R. L., Kaliski B. RSA Problem // Encyclopedia of Cryptography and Security. Kluwer Publishing House, 2005.

57. Rivest R. L., Shamir A., Adleman L. A Method for Obtaining •Digital Signatures and Public-Key Cryptosystems // Communications of the ACM. 1978. Vol. 21, N. 2. P. 120-126.

58. Ruohonen K. On some variants of Post's correspondence problem // Acta Informatica. 1983. Vol. 19, N. 4. P. 357-367.

59. Savage J. E. The Complexity of Computing. • New York: Wiley, 1976.

60. Shamir A. Factoring Numbers in O(logn) Arithmetic Steps // Information Processing Letters. 1979. Vol. 8, N. 1. P. 28-31.

61. Shannon С. E. A Symbolic Analysis of Relay and Switching Circuits. M. Sc. thesis / Massachusetts Institute of Technology, Dept. of Electrical Engineering. 1940.

62. Shannon С. E. A Mathematical Theory of Communication // Bell System Technical Journal. 1948. Vol. 27, N. 4. P. 379-423, 623-656.

63. Shannon С. E. Communication Theory of Secrecy Systems // Bell System Technical Journal. 1949. Vol. 28, N. 4. P. 656-717.

64. Shannon С. E. The Synthesis of Two-Terminal Switching Circuits // Bell System Technical Journal. 1949. Vol. 28. P. 59-98.

65. Shannon С. E., Riordan J. The Number of Two-Terminal Series-Parallel Networks // Journal of Mathematics and Physics. 1942. Vol. 31. P. 83-93.

66. Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM Journal of Computing. 1997. Vol. 26, N. 5. P. 1484-1509.

67. Singh S. The Code Book: the evolution of secrecy from Mary Queen of Scots to quantum cryptography. New York: Doubleday, 1997.

68. Sipser M. On Relativization and the Existence of Complete Sets // Proceedings of 1С ALP'82, Lecture Notes in Computer Science. Vol. 140. 1982. P. 523-531.

69. Sipser M. Introduction to the Theory of Computation. Course Technology, 2005.

70. Smith L. Polynomial Invariants of Finite Groups. A. K. Peters, Wellesley, Massachusets, 1996. Vol. 6 of Research Notes in Mathematics.

71. Smolensky R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity // Proceedings of the 19^ Annual ACM Symposium on Theory of Computing. 1987. P. 77-82.

72. Solovay R. M., Strassen V. A fast Monte-Carlo test for primality // SIAM Journal of Computing. 1977. Vol. 6, N. 1. P. 84-85.

73. Stockmeyer L. The complexity of decision problems in automata theory and logic: Ph.D. thesis / Massachusetts Institute of Technology. 1974.

74. Stockmeyer L. Oil the combinational complexity of certain symmetric Boolean functions // Mathematical Systems Theory. 1977. Vol. 10. P. 323-326.

75. Stockmeyer L. Classifying the computational complexity of problems // Journal of Symbolic Logic. 1987. Vol. 52. P. 1-43.

76. The Undecidable: Basic Papers on Undecidable Propositions, Un-solvable Problems and Computable Functions / Ed. by M. Davis. Raven Press, New York, 1965.

77. Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. Series 2. 1936. Vol. 42. P. 230-265.

78. Venkatesan R., Rajagopalan S. Average Case Intractability of Matrix and Diophantine Problems // Proceedings of the 24^ Annual ACM Symposium on Theory of Computing. 1992. P. 632-642.

79. Vernam G. S. Cipher Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications // Journal of the IEEE. 1926. Vol. 55. P. 109-115.

80. Vollmer H. Introduction to Circuit Complexity: a Uniform Approach. Springer Verlag, 1999.

81. Wang H. Proving theorems by pattern recognition—II // Bell System Technical Journal. 1961. Vol. 40, N. 1. P. 1-41.

82. Wang J. Random instances of bounded string rewriting are hard // Journal of Computing and Information. 1995. Vol. 1, N. 1. P. 11-23.

83. Wang J. Average-case intractible NP problems // Advances in Languages, Algorithms, and Complexity. 1997. P. 313-378.

84. Wang J. Distributional Word Problem for Groups // SIAM Journal of Computing. 1999. Vol. 28, N. 4. P. 1264-1283.

85. Wang J., Belanger J. On the NP-Isomorphism Problem with Respect to Random Instances // Journal of Computer and System Sciences. 1995. Vol. 50, N. 1. P. 151-164.

86. Washington L. Elliptic Curves: Number Theory and Cryptography. Chapman & Hall / CRC, 2003.

87. Wegener I. The Complexity of Boolean Functions. B. G. Teubner, and John Wiley & Sons, 1987.

88. Yao A. C.-C. Separating the polynomial-time hierarchy by oracles // Proceedings of the 26^ Annual IEEE Symposium on the Foundations of Computer Science. 1985. P. 1-10.

89. Yao A. C.-C. How to Generate and Exchange Secrets // Proceedings of the 27^ Annual IEEE Symposium on the Foundations of Computer Science. 1986. P. 162-187.

90. Yao A. C.-C. On ACC and threshold circuits // Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science. 1990. P. 619-627.

91. Валиев К. А. Квантовая информатика: компьютеры, связь и криптография // Вестник Российской Академии Наук. 2000. Т. 70, № 8. С. 688-695.

92. Верещагин Н. К., Шенъ А. Логические формулы и схемы // Математическое просвещение. Третья серия. 2000. Т. 4. С. 53-80.

93. Всемирное М. А., Гирш Э. А., Данцин Е. Я., Иванов С. В. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности // Записки научных семинаров ПОМИ. 2001. Т. 277. С. 14-46.

94. Гирш Э. А., Николенко С. И. Надежная в слабом смысле функция с секретом // Препринты ПОМИ. 2008. № 16.

95. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. М.: Наука. Физматлит, 2000.

96. Григорьев Д. Ю. Криптография с открытым ключом и теория инвариантов // Записки научных семинаров ПОМИ. 2002. Т. 293. С. 26-38.

97. Григорьев Д. Ю., Кожевников А. А., Николенко С. И. Алгебраическая криптография: новые конструкции и их надёжность относительно доказуемого взлома // Алгебра и Анализ. 2008. Т. 20, № 6. С. 119-147.

98. Григорьев Д. Ю., Пономаренко И. Н. О неабелевых гомоморфных криптосистемах с открытым ключом // Записки научных семинаров ПОМИ. 2002. Т. 293. С. 39-58.

99. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М., МЦНМО, 1999.

100. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦНМО, 2004.

101. Левин Л. А. Универсальные переборные задачи // Проблемы передачи информации. 1973. Т. 9, № 3. С. 265-266.

102. Левин Л. А. Односторонние функции // Проблемы передачи информации. 2003. Т. 39, № 1. С. 92-103.

103. Лупанов О. В. Об одном подходе к синтезу управляющих систем принципе локального кодирования // Проблемы кибернетики. 1965. Т. 14. С. 31-110.

104. Марков А. А. О минимальных контактно-вентильных двухполюсниках для монотонных симметрических функций // Проблемы кибернетики. 1962. Т. 8. С. 117-121.

105. Ненипорук Э. И. Об одной булевской функции // Доклады Академии Наук СССР. 1966. Т. 169, № 4. С. 765-766.

106. Разборов А. А. Нижние оценки монотонной сложности логического перманента // Математические заметки. 1985. Т. 37, № 6. С. 887-900.

107. Разборов А. А. Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения // Математические заметки. 1987. Т. 41, № 4. С. 598-608.

108. Разборов А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами // Математические заметки. 1990. Т. 48, № 6. С. 79-90.

109. Разборов А. А. О сложности вычислений // Математическое просвещение. Третья серия. 1999. Т. 3. С. 127-141.

110. Субботовская В. А. О реализации линейных функций формулами в базисе V, &, // Доклады Академии Наук СССР. 1961. Т. 136, № 3. С. 553-555.

111. Субботовская В. А. О сравнении базисов при реализации функций алгебры логики формулами // Доклады Академии Наук СССР. 1963. Т. 149, № 4. С. 784-787.

112. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М., «Вильяме», 2002.

113. Храпченко В. М. О сложности реализации линейной функции в классе я-схем // Математические заметки. 1971. Т. 9, № 1. С. 36-40.

114. Шоломов Л. А. О реализации недоопределённых булевых функций схемами из функциональных элементов // Проблемы кибернетики. 1969. Т. 21. С. 215-226.

115. Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // Успехи математических наук. 1957. Т. 12, 6. С. 189-196.