авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |   ...   | 5 |

«Российская академия наук САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМЕНИ В.А. СТЕКЛОВА РАН УДК 510.6 ГРНТИ 27.03.19 Инв. ...»

-- [ Страница 2 ] --

/ Чтобы показать важность этой проблемы и ее нетривиальность для эвристических алгоритмов рассмотрим конкретный пример, в ко тором f является псевдослучайным генератором.

Определение 4.24 (см. также [28, Section 3]). Пусть функция f : {0, 1} {0, 1} вычислима за полиномиальное время и |f(r)| = |r| + для всех r {0, 1}. Функция f называется псевдослучайным генерато ром, если для каждого полиномиального вероятностного алгоритма A и для любого полинома p:

Pr [A(f(x)) = 1] Pr n0 n n0 [A(x) = 1].

p(n) xU xU n n+ Известно, что инъективный псевдослучайный генератор суще ствует, если существует псевдослучайная функция [28].

Предложение 4.7 ( [39, Theorem 5.2]). Если f является псевдослу чайным генератором, то не существует вероятностного эвристического алгоритма для задачи (Im f, U) со временем работы, которое полино Im f.

миально ограничено на Определение 4.25. Будем называть оценщиком алгоритм Estimate(A, x, S, v,, T ), который получая на вход  алгоритм A (т.е. его Геделев номер), который может быть как – 59 – вероятностным, так и детерминированным,  вход x {0, 1}n,  функцию S : {0, 1}n {0, 1}n (оракул),  значение v {0, 1},  рациональное число (0;

1),  целое число T, запускает на время, полиномиально ограниченное от T, n, и и выдает рациональное число, такое что Pr Pr );

A[AT (y) = v], yS(Un где внешняя вероятность берется по внутренним случайным битам ал Estimate и по распределению x {0, 1}n.

горитма Замечание 4.6. На первый взгляд может показаться, что выход алго Estimate не зависит от x, и следовательно, Estimate не требует ритма подавать на вход x. Однако, мы увидим позже, что в детерминиро ванном случае вход x является источником псевдослучайности и, сле довательно, это имеет смысл для детерминированных эвристических оценщиков. В вероятностном случае x можно игнорировать.

Замечание 4.7. В дальнейшем мы будем использовать оценщиков для двух видов функций: тождественная функция и функция S, которая обрезает последний бит входа и применяет инъективную функцию f, чей образ мы пытаемся распознать, к первым n 1 битам входной строки чтобы получить строку длины n, равномерно распределенную Im f {0, 1}n.

на 4.6 Основная конструкция оптимального алгоритма В этой части мы опишем “главный” алгоритм Opt для распределенной задачи (Im f, U), который мы используем в обоих случаях (в детер минированном и в вероятностном). Этот алгоритм использует пере – 60 – числитель A• для алгоритмов конкретного типа (т.о., Ai это машина Тьюринга с Геделевым номером i, и она может быть как вероятност ной так и детерминированной в зависимости от типа перечислителя), Estimate для того же типа алгоритмов. Мы предполагаем, и оценщик что A0 это детерминированный переборный алгоритм для проверки Im f, который работает за время 2cn для c 1 (от принадлежности к Im f может быть принято за время O(2n · p(n)), где p(n) метим, что это сложность функции f).

Opt похож на оптимальный алгоритм Левина для за Алгоритм дач поиска из NP [52]. Он запускает параллельно все алгоритмы Ai.

Когда алгоритм Ai останавливается с ответом v, ответ проверяется в том же параллельном процессе;

если верификация проходит успешно, Opt останавливает все параллельные процессы и выдает полученный ответ. Однако, процедура верификации сильно отличается от вери фикации в алгоритме Левина (отметим, что ответ состоит всего из одного бита). Проверка зависит от ответа: если v = 0, то мы проверя Im f с ем, что Ai возвращает 0 на случайно выбранных элементах из пренебрежимо малой вероятностью. Это достигается генерированием Im f и вычислением частоты ответа 0 (отметим, что равно элементов мерное распределение на Im f можно генерировать за полиномиальное время используя саму функцию f). Если v = 1, то мы проверяем, что Ai возвращает 1 на случайно выбранных входах из равномерного рас Im f с пренебрежимо малой вероятностью.

пределения на дополнении Однако, равномерное распределение на Im f может быть трудным для генерации. Вместо этого мы сводим эту задачу к задаче оценки двух PrxU [... ] = 2 PrxU (Im f)[... ] + 1 PrxU (Im f)[... ].

вероятностей: n n n Алгоритм 4.3. Opt(A•, Estimate, x, d) 1. Положить d = 20cn2 d.

2. Для всех i {0, 1,..., n}, запустить параллельно следующий про – 61 – цесс:

 Запустить Ai (x, d ).

 Если i = 0 и A0 выдает v {0, 1}, то остановить все процессы и выдать v.

 Если i 0 и Ai (x, d ) выдает v {0, 1} за T шагов, то запу Test(v, Estimate, Ai, 2 log T, x, d ). Если Test принимает стить вход, то завершить все процессы и выдать v.

Test(v, Estimate, A, T, x, d ) Алгоритм 4.4.

1. Положить и A (x) = A(x, d ).

= d 2. Если v = 0:

(a) Вычислить = Estimate(A, x, S, 0,, T ), где S(y b) = f(y) для y {0, 1}|x|1, b {0, 1}.

(b) Если 2, принять;

иначе отклонить.

3. Если v = 1:

(a) Вычислить = Estimate(A, x, S, 1,, T ).

(b) Вычислить = Estimate(A, x, id, 1,, T ).

(c) Принять, если 2 4 ;

иначе отклонить.

2 В дальнейшем будем считать, что d = 20cn2 d и 10cn2 d, = = d как в алгоритме выше.

Лемма 4.5. Для алгоритма A, обозначим = PrxUn (Im f);

A [AT (x, d ) = 1]. Пусть и будут случайными переменными вычисленными на Test(1, Estimate, A, T, x, d ). Тогда Pr[| (2 )| шаге 3 алгоритма 3 ]2.

Доказательство. Пусть Prxf(U PrxU (Im f);

A[AT (x, d) = 1] [AT (x, d) = 1] = a= n1 );

A n PrxU ;

A[AT (x, d) = 1]. Можно заметить, что = 2b a. По иb= n определению оценщика Pr[|a | ] и Pr[|b | ].

– 62 – Используя неравенство треугольника получаем Pr[|(2ba)(2)| 3 ]2.

Opt(A•, Estimate, x, d) является корректным Теорема 4.8. Алгоритм эвристическим алгоритмом для (Im f, U) (детерминированным или ве роятностным в зависимости от того, что перечисляет A• ).

Доказательство. Так как A0 всегда выдает корректный ответ, то достаточно доказать, что Ai (x, d ) выдает 0 или 1 за T 2 шагов cn Pr ;

Test Ai(x, d ) = (Im f)(x) 1.

dn xUn ;

Ai log T, x, d ) = Test(v, Estimate, Ai, Так как A0 работает за 2cn шагов, то никакой другой алгоритм Ai не может работать дольше. Таким образом мы можем разбить каждый алгоритм на cn “частей”: A1, A2, A4,... и этого будет достаточно, i i i чтобы доказать, что k A2 (x, d ) {0, 1} i Pr Ai (x, d ) = (Im f)(x) 1.

2k cdn xUn ;

Ai ;

Test Test(v, Estimate, Ai, 2k, x, d ) = Эта вероятность может быть разбита на две части в зависимости от правильного ответа:

Pr );

A [A2k (x, d ) = 0...]+ 1 · Pr [A2k (x, d ) = 1...].

· 2 xf(Un1 i i 2 xUn (Im f);

Ai i Дабы ограничить первую часть заметим, что если Prxf(U );

A [A2 (x, d ) = 0] 3, то по определению алгорит k i n1 i мов Estimate и Test мы имеем Pr[Test(0, Estimate, Ai, 2k, x, d ) = 1].

Следовательно, первая часть вероятности меньше, чем.

Мы рассматриваем случай, когда x Un (Im f). По лемме 4.5, Pr[A2 (x, d ) = 1] 7 Pr[Test(1, Estimate, Ai, 2k, x, d ) = 1] k если, то i 2. Следовательно, вторая часть вероятности меньше, чем. В итоге 3 7 получаем (по определению и d ).

+ cdn 2 – 63 – Лемма 4.6. Пусть A является корректный эвристическим алгоритмом для (Im f, U). Тогда для каждого целого числа T и любого v {0, 1}, Pr [Test(v, Estimate, A, T, x, d ) = 0] 2.

xUn ;

Test Test от Доказательство. Рассмотрим случай v = 0. В этом случае Pryf(U [AT (y, d ) = 0] клоняет вход с вероятностью =.

n1 );

A d Рассмотрим теперь случай По лемме 4. v = 1.

PrxU (Im f);

A[AT (y, d ) Test, отклоняет вход с ве = 1] = d n роятностью меньше, чем 2.

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

Алгоритм 4.5. Estimate-Random(A, x, S, v,, T )  Пусть s = ln(2/ ) + 1.

 Для i = 1, 2,..., s, выполнить:

1. Сгенерировать y S(Un ).

2. Запустить AT (y);

присвоить ui = 1, если ответ равен v, иначе присвоить ui = 0.

s  Вывести i=1 ui.

s Лемма 4.7. Алгоритм Estimate-Random является оценщиком для ве роятностных алгоритмов.

Доказательство. По оценкам Чернова(см., к примеру, [56]), Pr PryS(Un ),A [AT (y) = v] s 2e2 s.

i=1 ui s Замечание 4.8. В действительности выполняется немного более стро гое утверждение. А именно, вероятность может браться только по слу чайным битам, т.е. не учитывая вероятность по входам, как это дела ется в определении оценщика.

– 64 – Теорема 4.9. Для любого случайного эври стического алгоритма для задачи B (Im f, U), 1/ tOpt (A•, Estimate-Random, x, d), где A• перечисляет все ве tB роятностные алгоритмы.

Доказательство. Пусть B Ai. Чтобы показать асимпто = тическую оценку, достаточно рассмотреть |x| i. Тогда Ai Opt.

выполняется внутри алгоритма Так как Estimate-Random не использует x, из леммы 4.6 следует, что для любых x, PrTest[Test(v, Estimate-Random, Ai, T, x, d ) = 0] меньше, чем 2. Для каждого x алгоритм Opt останавливается за время полиномиальное от n, d и медианного времени tAi (x, d ) с вероятностью не менее 2 2.

Следствие 4.7. Три запущенные параллельно копии Opt(A•, Estimate-Random, x, 3d) (выполнение заканчивается как только одна из копий принимает или отклоняет вход) формируют оптимальный вероятностный эвристический алгоритм для (Im f, U) 4.8 Оптимальный детерминированный эвристический алго ритм Для того, чтобы дерандомизировать конструкцию оптимального эври стического алгоритма, мы используем следующий результат Голдрей ха и Вигдерсона.

целое число и 2n, где Теорема 4.10 ( [29]). Пусть n некото рая положительная константа. Тогда существует семейство функций F, каждая из которых отображает {0, 1}n в себя, удовлетворяющее следующим свойствам.

 Сжатость: существует биекция между {0, 1}l() и F, где l() = O(log ). Пусть обозначает функцию из F соответствующую – 65 – {0, 1}n. Это свойство означает, что семейство F содержит полиномиальное от число функций.

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

{0, 1}l(), строку x {0, 1}n и возвращает (x).

 Перемешивание: для любых двух подмножеств A, B {0, 1}n су ществует FA,B, F, такой что |FA,B, | (1 )|F | и для всех функций FA,B, :

Pr [x A (x) B] (A)(B), xUn |S| где (S) = обозначает плотность множества S.

2n Следствие 4.8. В терминах теоремы 4.10, для любых двух подмно жеств A, B {0, 1}n, Pr [x A (x) B] (A)(B) 2.

xUn,U(F ) PrxU,U(F )[x A (x) B] = Pr[x A Доказательство. n FA,B, ] Pr[ FA,B, ] + Pr[x A (x) B | (x) B | FA,B, ] Pr[ FA,B, ]. Из свойства перемешивания следует, что послед нее значение может быть ограничено сверху (A)(B) + 2, и снизу ((A)(B) )(1 ) (A)(B) 2, т.к. (A)(B) 1.

Теперь опишем (детерминированный) оценщик для детермини рованных алгоритмов. Пусть F будет семейством функций из теоре мы 4.10.

Алгоритм 4.6. Estimate-Deterministic(A, x, S, v,, T )  Положим n = |x| и = 8.

 Если 2n, то запустить AT (y) для всех y {0, 1}n и вычис лить частоту ответа v и выдать это число.

 Если 2n, то для всех F, запустить AT (S((x))) и и вычислить частоту ответа v и выдать это число.

– 66 – Предложение 4.8. Алгоритм Estimate-Deterministic является оцен щиком.

Доказательство. Если 2n, то алгоритм Estimate-Deterministic вычисляет точный ответ, и в этом случаем ему достаточно времени для этого, т.к. мала.

В противном случае, положим B = {y {0, 1}n | AT (S(y)) = v}.

PrU(F )[(x) B] (B) + Пусть C+ = {x {0, 1}n | }, и C = {x {0, 1}n | PrU(F ) [(x) B] (B) }.

PrxU,U(F )[x C+ (x) B] Пусть (C+ ) 2. Тогда n (C+ )((B) + ) (C+ )(B) +, что противоречит следствию 4.8.

Таким образом, (C+ ) 2. Аналогично, (C ) 2. И следовательно, (C C+ ).

Opt(A•, Estimate-Deterministic, x, d) являет Теорема 4.11. Алгоритм ся оптимальным в среднем, где A• перечисляет все детерминирован ные алгоритмы.

Доказательство. Пусть Ai будут (корректным) детерминированным эвристическим алгоритмом для (Im f, U). Чтобы показать асимптоти ческую оценку, достаточно рассмотреть |x| i. Тогда алгоритма Ai Opt.

запускается внутри Для того, чтобы оценить какая доля всех входов x отклоня Test(v, Estimate-Deterministic, Ai, T, x, d ), ет алгоритм заметим, что Estimate-Deterministic не использует случайность. Тогда лемма 4. влечет, что это для меньше чем 2 2d.

Opt полиноми Для всех остальных x время работы алгоритма ально от n, d и tAi (x, d ).

Замечание 4.9. Алгоритм, построенный в теореме 4.11 также являет ся оптимальным в среднем детерминированным аксептором для рас пределенной задачи (Im f, U) и для распределенной задачи (Im f, U).

– 67 – 5 Разработка новых конструкций криптографиче ских протоколов аутентификации и/или защиты информации 5.1 Краткая аннотация Данное направление работ представлено двумя результатами: кон струкциями непрерывных труднообратимых функций, основанных на тропических и полиномиальных конструкциях, а также новым клас сом схем аутентификации, обладающими свойством неразглашения.

Во-первых, мы предлагаем новые конструкции в области непре рывной криптографии. Многие важные криптографические приложе ния уже требуют от базовых примитивов некоторых свойств непре рывности. Это особенно важно в биометрических задачах: отпечатки пальцев, снимки сетчатки глаза, голоса людей меняются со временем и в зависимости от внешних условий. Однако система должна успеш но аутентифицировать слегка изменившегося человека и отказывать людям, которые изменились значительно больше, т.е. в биометри ческих задачах крайне важно было бы получить непрерывные крип тографические примитивы. В [45], была предложена так называемая схема нечёткого сейфа (fuzzy vault scheme);

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

Однако в этой схеме признаки остаются непрерывными и должны сов падать в точности. Схема нечёткого сейфа [45] была недавно подвер жена критике;

она оказалась уязвимой к некоторым правдоподобным атакам [64, 70]. Мы построили несколько кандидатов на непрерывные труднообратимые функции (труднообратимость понимается в смыс ле [34]). Непрерывность в наших конструкциях понимается в обыч – 68 – ном математическом смысле, как непрерывность функций, отобража ющих одно евклидово пространство в другое. Такая ситуация является вполне естественной для биометрических приложений.

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

прувер (сторона, проводящая доказательство) выдаёт верификатору ответ вида да или нет без какого бы то ни было доказательства этого результата, а верификатор, в свою очередь, знает верный ответ до того, как начинается обмен сообщениями, т.е. не может даже чисто теоретически получить какую-то новую информацию из ответа пруве ра. Мы называем такое свойство аутентификацией без утечки инфор мации, потому что термин неразглашение уже занят другим фор мальным определением [28]. Наше определение является более силь ным, чем классическое (вычислительное);

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

1. Честный верификатор не может получить от прувера никакой информации, которой он не знал заранее. Это верно и для пас сивного противника, в том числе противника неограниченной вы числительной мощности.

2. Нет никакой конкретной задачи, которую противник дол жен решить, чтобы получить долговременный секретный ключ прувера. Задача, с которой он имеет дело, – разработать тест на (не)принадлежность к множеству, которого он не знает.

Наша общая схема также может быть использована для кодирования.

– 69 – 5.2 Непрерывные труднообратимые функции: полиномиаль ные кандидаты Нащ первый кандидат – полиномиальное отображение f : Rn Rm for m n (к примеру, m = n + 1) для некоторого кольца R (обычно R = R или R = C, а f имеет целые коэффициенты). Обращение такой функции эквивалентно решению (слегка) переопределённой системы полиномиальных уравнений:

f1 (x1,..., xn ) = y1, f2 (x2,..., xn ) = y2,......

fm (x1,..., xn ) = ym.

До сих пор неизвестны эффективные алгоритмы для решения пере определённых систем как в худшем [6] (лучшее в этом смысле – эври стики линеаризации [13, 15]), так и в среднем случае. Для систем из n однородных полиномиальных уравнений с в точности n + 1 пере менными (f : Cn+1 Cn ) существует гомотопический метод Шуба и Смейла [73–77], однако он субэкспоненциален только от размерности N векторного пространства H(d) всех однородных полиномиальных отображений f : Cn+1 Cn, и N не полиномиально при росте d и n.

Более того, для переопределённых систем f : Cn Cm, m n, метод Шуба и Смейла не работает, и всё, что остаётся, – это метод Ньютона и его вариации [17].

Чтобы получить короткое представление многочлена с большим N, мы определяем полиномиальное отображение через арифметиче скую схему. Многие естественные вопросы о многочленах становятся в этом представлении вычислительно сложными. Например, в [50] по казано, что задача проверки тождественного равенства нулю много P#P.

члена в таком представлении сложна для класса Чтобы использовать непрерывную труднообратимую функцию, – 70 – нам также нужно указать оценку её модуля непрерывности sup |f(u) f(v)|, (f, ) = |uv| где – максимальное расстояние от точного хранимого кода (биомет рической информации), которое всё ещё позволяет аутентифициро вать пользователя. Нами было предложено несколько методов оценки модуля непрерывности.

1. На компактном множестве X модуль непрерывности мож но оценить индуктивно. Для входных переменных модуль непре рывности равен 1;

для констант он равен 0. Для гейта сложения wf+g wf + wg, и мы получаем новую верхнюю оценку модуля непрерывности как сумму верхних оценок родителей гейта. Для гейта умножения wfg wf sup g(x) + wg sup f(x).

x x Супремум также можно индуктивно оценить очевидным обра зом:

sup(f + g) sup f + sup g, sup(fg) sup f sup g.

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

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

(f + g) (x) = f (x) + g (x), (fg) (x) = f (x)g(x) + f(x)g (x).

3. Можно получить более точную оценку модуля непрерывности, если воспользоваться методами интервального анализа, изу ченного в работах Мура [59], Хансена [35] и Матиясевича [54];

– 71 – см. также свежие обзоры интервального анализа в [14,18]. Прора ботка деталей применения интервального анализа к этой задаче остаётся интересной открытой проблемой.

5.3 Непрерывные труднообратимые функции: случайное по рождение ключей Чтобы случайно порождать конкретных кандидатов в труднообра тимые функции, нужно уметь порождать случайный направленный ациклический граф с n вершинами входящей степени ноль (входы схемы и константы базового поля), m вершинами исходящей степени ноль (выходы) и внутренними вершинами входящей степени 2, снаб жённые одной из меток “+” или “”. Существуют алгоритмы порож дения случайных направленных ациклических графов, как равномер ные [57], так и основанные на модели упорядоченных графов [48]. Мы модифицируем модель порождения из [48], чтобы сохранить контроль над степенью многочлена.

Зафиксируем число n входов, число m выходов, верхнюю оцен ку на степень D, число константных входов c (все константные входы схемы равны 1 или 1, бльшие константы нужно будет случайно по о родить из них) и верхнюю оценку на исходящую степень вершин графа K 2. Входящая степень каждой внутренней вершины равна 2, исхо дящая выбирается случайно для каждой новой вершины. Мы строим случайную схему вершина за вершиной. Каждая вершина помечает ся парой (s, d), где s {xi, +, }, а d – натуральное число, равное формальной cтепени этой вершины. Процесс порождения идёт по следующему алгоритму.

1. Породить граф (G, E) с n + c вершинами – n с метками (xi, 1) и c с метками (±1, 0) (знак выбирается равновероятно) – и без рёбер.

Выбрать исходящие степени ki равномерно из {1,..., K} для каж – 72 – дой вершины и инициализировать ki обрубков для каждого потенциального исходящего ребра (см. [48]).

2. Пока не порождены m выходов:

(a) добавить новую вершину x, G := G {x}, выбрать её метку равномерно из {+, }, выбрать двух родителей y и z равно мерно из свободных обрубков предыдущих вершин, доба вить соответствующие рёбра E := E {(y, x), (z, x)} и удалить по одному обрубку у y и z;

(b) вычислить формальную степень fdeg(x):

max{fdeg(y), fdeg(z)}, if x is a +-vertex, fdeg(x) = fdeg(y) + fdeg(z), if x is a -vertex;

(c) вычислить модуль непрерывности wx (см. выше);

fdeg(x) D (d) если + 1, пометить x как выход и больше не генерировать для неё исходящих обрубков ;

в противном случае, выбрать k равномерно из {1,..., K} и сгенерировать k исходящих обрубков для вершины x.

3. Удалить оставшиеся обрубки и выдать (G, E).

Очевидно, эта модель порождения с подавляющей вероятностью по D родит m выходов формальной степени от до D за время, полиноми альное от n + m + c.

5.4 Непрерывные труднообратимые функции: протокол В этом разделе мы предлагаем простой протокол аутентификации с секретным ключом. Предположим, что агент A (Алиса) хочет аутен тифицировать себя на сервере S при помощи своей биометрической информации. В начале протокола S хранит биометрическую инфор мацию x, а Алиса знает свою собственную информацию x, предпо ложительно близкую к x. Параметры алгоритма – размерность n и – 73 – точность аутентификации.

1. A инициирует протокол и представляет свою биометрическую информацию как вектор x Cn.

2. S случайно выбирает арифметическую схему f с n входящими переменными, как показано выше, и посылает эту схему (в неко торой общеизвестной схеме кодирования) A.

3. A случайно выбирает вектор r Cn и скаляр C, вычисляет f(r + x ) и передаёт (r,, y) для y = f(r + x ).

4. S вычисляет, модуль непрерывности в точке r + x, любым из предложенных нами выше методов, и проверяет, что ||y f(r + x)||. Если так, S принимает аутентификацию A.

Пассивный противник в этом протоколе вынужден решить систе му полиномиальных уравнений f(r+x) = a относительно неизвестно го x для f, заданного в виде арифметической схемы. Если пассивный противник наблюдал k запусков этого протоколв с одним и тем же сервером и агентом, он должен решить систему уравнений f1 (r1 + 1 x) = a1, f2 (r2 + 2 x) = a2,..., fk (rk + k x) = ak.

Заметим, что противнику будет сложнжо применить методы [13, 15], т.к. мономы многочлена f неизвестны, и их экспоненциально много.

5.5 Непрерывные труднообратимые функции: супертропиче ские кандидаты Существуют точные алгебраические подходы к решению систем нели нейных уравнений, например, метод результантов и метод базисов Грёбнера. Вычисление результанта, несмотря на недавний прогресс в этой области [12], не представляется практически возможным для случаев больших систем многих переменных [46,47]. Базисы Грёбнера – более практически применимый подход [24, 47], но сложность точ – 74 – ных (символьных) методов решения больших систем полиномиальных уравнений всё равно слишком велика. Однако в нашем случае будет достаточно найти приближённое решение;

для поиска приближённых решений можно применить метод Ньютона (метод гомотопического продолжения тоже основан на методе Ньютона) и оптимизационные методы (см., например, [61]), которые сочетают сразу несколько мето дов.

Чтобы систему нелинейных уравнений трудно было решить ме тодом Ньютона и подобными, нужно, вообще говоря, чтобы функция системы имела много локальных минимумов и/или точек, где функ ция системы не дифференцируема. Такими свойствами обладают тро пические конструкции [10, 43, 58];

более того, для тропических кон струкций аналоги известных методов решения нелинейных систем пе рестают работать. Тропические алгебры основаны на тропическом полукольце (также известном как min-plus алгебра);

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

x y = min(x, y), x y = x + y.

Тропический моном m = a xi1... xin = a + xi1 +... + xin, 1 ij n, – это просто линейная функция;

тропический много min(m1,..., mk) член p = m1... mk = это минимум несколь ких линейных функций, т.е. вогнутая кусочно-линейная функция с несколькими областями, где нарушается непрерывность. Для целей непрерывных криптографических конструкций мы расширим тропи ческое полукольцо её одной операцией, а именно обычным арифмети ческим умножением. Полученное расширенное полукольцо (A, ·,, ), A R {} назовём супертропической алгеброй. В супертропиче – 75 – ской алгебре супертропический моном соответствует многочлену m(x1,..., xn ) = xi11 xi12... xi1n... xim1 xim2... ximn, n n 1 2 1 а супертропический многочлен p(x1,..., xn ) = m1 (x1,..., xn )... mk (x1,..., xn ) соответствует минимуму нескольких полиномиальных функций, т.е.

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

Мы представляем супертропическую систему полиномиальных уравнений с n переменными как направленный ациклический граф с по меньшей мере n вершинами входящей степени ноль (входы схемы и константы базового поля), m вершинами исходящей степени ноль (выходы) и внутренними вершинами входящей степени 2, снабжённые одной из меток “·”, “” или “”. Протокол случайного порождения остаётся прежним со следующими дополнениями: для -гейта x с ро дителями y и z, которые вычисляют функции f и g соответственно, fdeg(x) = max{fdeg(y), fdeg(z)}, wfg = max{wf, wg };

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

– 76 – 5.6 Непрерывные труднообратимые функции: пример интерак тивного протокола Нами также был разработан ещё один класс протоколов, которые мож но реализовать непрерывным образом при помощи полиномиальных и супертропических схем. Базовый протокол основан на сложности за дачи поиска сопряжённой матрицы. Протокол был представленв [33];

это интерактивная схема аутентификации, которая для некоторого ба зового матричного кольца G работает следующим образом.

1. Открытый ключ Алисы – пара матриц (A, X1 AX), where A G, X G;

секретный ключ Алисы – матрица X.

2. Боб выбирает случайную матрицу B G и случайный необрати мый эндоморфизм кольца G. Боб посылает B и Алисе.

3. Алиса отвечает случайными положительными числами p и q и просит Бобе рислать случайные ненулевые константы c1, c2 и c3 ;

новый (лучше рандомизированный) запрос вычисляется как B = c1 A + c2 B + c3 Ap Bq.

4. Алиса отвечает (X1 B X).

5. Боб выбирает случайное слово w(x, y) (без отрицательных экс понент), вычисляет M2 = w (X1 AX), (X1 B X) M1 = w ((A), (B )), и следы этих матриц. Если tr(M1 ) достаточно близок к tr(M2 ), Боб 1принимает аутентификацибю, otherwise he rejects.

5.7 Схемы аутентификации: метапротокол В этом разделе мы приводим описание общей схемы нашего метода аутентификации. Конкретные реализации будут приведены ниже. В этом разделе, следуя криптографической традиции, прувер называет ся Алисой, а верификатор – Бобом.

– 77 – Секретный ключ Алисы состоит из:

1. подмножества S0 некоторого “универсума” S;

2. эффективной процедуры, которая проверяет, что данный эле мент S не лежит в множестве S0 ;

3. способ маскировки (запутывания), отображающий S0 в некото рый S0, например, биекция универсума S на себя, для которой (S0 ) = S0, и Алиса может эффективно вычислить как, так и 1. В некоторых реализациях, этот пункт не является необхо димым, и роль S0 выполняет подмножество S0.

Открытый ключ Алисы – это пара множеств (S0, S1 ), которые либо не пересекаются, либо имеют пренебрежимо малое пересечение.

Заметим, что верификатор не знает, к какому множеству у Алисы есть тест на непринадлежность, для S0 или для S1 ;

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

Идея “теста на непринадлежность” множеству S0 может быть за писана и более формально. У Алисы должен быть секретный сепа ратор T, для которого S0 T, пересечение T S1 пусто или прене брежимо мало, и T является хорошим множеством в том смысле, что задача принадлежности T эффективно разрешима. Таким обра зом, Алиса может эффективно проверить принадлежность элемента x множеству T, и если x T, то наверняка x S0. Если же x T, Алиса / / предполагает, что x S0 ;

чем “теснее\ (т.е., чем ближе к S0 ) T, тем больше шансов на то, что это предположение окажется верным. Та ким образом, хотя у данной пары множеств может быть много разных сепараторов, противнику трудно найти хороший сепаратор, не зная множества S0.

Общая схема протокола приведена ниже.

– 78 – 1. Боб выбирает набор (x1,..., x2m ) случайных элементов S0 или S1 с ровно m элементами из S0 и ровно m элементами из S1 и посылает его Алисе.

2. Алиса для каждого i проверяет, используя свой секретный тест, верно ли, что для элемент xi, соответствующего xi, xi S0. Ес / ли тест не проходит, Алиса предполагает, что xi S0 (или, что то же самое, xi S0 ). Тогда она подсчитывает количество xi, не лежащих в S0. Если это число не равно m, Алиса прерывает сессию аутентификации. Если число ровно m, Алиса посылает Бобу набор нулей и единиц, в котором нули соответствуют слу чаям xi S0, а единицы – случаям xi S0.

/ 3. Боб, зная верный ответ, сравнивает его с ответом Алисы и при нимает или отклоняет попытку аутентификации.

Чтобы уменьшить шансы противника добиться успеха случайно (или грубой силой), можно провести несколько итераций этого прото кола, подобно схеме Фейге-Фиата-Шамира [21]. Заметим, что если, к примеру, m = 20, то вероятность угадать верный ответ в одной сессии аутентификации составляет менее 106.

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

Предложение 5.9. Описанный выше протокол является протоколом без утечки информации о секретном ключе прувера для любой сес сии аутентификации, проведённой с честным (следующим протоколу) верификатором.

Заметим также, что этот протокол можно использовать и для кодирования. Если Боб хочет передать закодированный бит Алисе, он посылает ей случайный элемент из S0, если он хочет передать 0, и случайный элемент из S1, если он хочет передать 1.

Если T S1 =, то протокол абсолютно корректен в том смыс – 79 – ле, что если у Алисы действительно есть её секретный ключ, и оба участника следуют протоколу, то Боб примет аутентификацию Али сы с вероятностью 1. Если вероятность того, что случайный элемент S1 попадёт в T S1, равна, то корректный участник Алиса может прервать корректную сессию аутентификации с вероятностью.

5.8 Схемы аутентификации: конкретная реализация на приме ре задачи Subset Sum В этом разделе мы предлагаем конкретную реализацию метапротоко ла из раздела 5.7, которая использует сложность задачи Subset Sum (сумма по подмножеству);

см, например, [26]. Заметим, что слож ность этой задачи уже использовалась ранее в криптографических контекстах [42] для конструкции псевдослучайного генератора и уни версальной односторонней хеш-функции.

В этом разделе в качестве универсума S будет выступать множе ство всех m-ок m-мерных векторов над Q.

Секретный ключ Алисы – это множество S0 = {a1,..., am }, со стоящее из m случайных линейно независимых (над Q) m-мерных векторов с целыми координатами, которое, таким образом, образу ет базис Qm. Однако вектор a1 в этом множестве – особенный: все его координаты чётные.

Открытый ключ Алисы – это вектор a1 и набор k m случайных векторов c1,..., ck из Z+ -оболочки S0.

Опишем теперь протокол аутентификации. Для упрощения обо значений, мы приводим версию, в которой Боб посылает Алисе только один элемент, а не набор элементов, как в метапротоколе из 5.7.

1. Боб выбирает, с равной вероятностью, либо случайный век тор c SpanZ+ (a1, c1,..., ck ), либо случайный вектор c SpanZ+ ( 1 a1, c1,..., ck ) и посылает вектор c Алисе;

в последнем – 80 – случае, Боб специально проверяет, что коэффициент при 2 a нечётный. Здесь SpanZ+ обозначает набор всех линейных ком бинаций данных векторов с неотрицательными целыми ко эффициентами.

2. При помощи обычной линейной алгебры Алиса находит (рацио нальные) координаты c в базисе S0. Если по крайней мере одна из этих координат не является неотрицательным целым числом, Алиса может быть уверена, что c SpanZ+ (a1, c1,..., ck );

в та / ком случае она отправляет Бобу 1. Если все координаты оказа лись неотрицательными целыми числами, Алиса предполагает, что c SpanZ+ (a1, c1,..., ck ), и отправляет Бобу 0.

3. Боб, зная правильный ответ, сверяет его с ответом Алисы и соот ветственно принимает или отвергает попытку аутентификации.

Заметим, что есть пренебрежимо малая вероятность того, что Боб отклонит честную Алису, потому что все координаты c в бази се S0 могут оказаться неотрицательными целыми числами, но всё таки c SpanZ+ (a1, c1,..., ck ). Может даже случиться (опять же, с / пренебрежимо малой вероятностью), что c SpanZ+ (a1, c1,..., ck ), но Боб ожидает, что Алиса вернёт ему 1, потому что он выбирал c SpanZ+ ( 2 a1, c1,..., ck ).

Мы используем публичный вектор a1 с чётными координатами для того, чтобы вектор Боба c лежал в SpanQ+ (a1, c1,..., ck ) в лю бом случае, потому что есть полиномиальный алгоритм, определя ющий, принадлежит ли данный вектор Q+ -оболочке других данных векторов (это частный случай задачи линейного программирования, см. [71, 101]).

Противник, желающий выдать себя за прувер, должен решить следующую задачу: выяснить, имеет ли матричное уравнение Bx = c решение, в котором x был бы вектором с неотрицательными целы – 81 – ми коэффициентами. Здесь B – матрица, составленная из координат векторов a1, c1,..., ck, c – выбранный Бобом вектор, x – неизвестный вектор. Частный случай этой задачи, в котором B – всего лишь вектор с целыми коэффициентами, x – вектор из нулей и единиц, а c – целое число, известен как задача Subset Sum. Она NP-полна [26]. Более того, как отмечено, например, на с. 41 [28], похоже, что задача Subsem Sum может быть сложной и на случайных входах, а не только в специально выбранных худших случаях.

Мы предлагаем использовать следующие значения параметров для вышеописанного протокола.

1. Размерность векторов m = 20.

2. Координаты векторов ai : случайные неотрицательные числа 10. Заметим, что m случайных таких m-мерных векторов будут линейно зависимы с исчезающе малой вероятностью.

3. Векторы ci конструируются Алисой как случайные линейные комбинации векторов ai с неотрицательными целыми коэффи циентами 10. Число векторов ci равно k = 2m.

4. На первом шаге протокола, Боб строит свой вектор c как слу чайную линейную комбинацию публичных векторов a1, c1,..., ck с неотрицательными целыми коэффициентами 10, с одним воз можным исключением: по определению протокола, он может вы брать коэффициент при a1 в виде n, где n нечётно, 1 n 19.

5.9 Схемы аутентификации: реализация через полиномиаль ные уравнения В этом разделе мы предлагаем другую конкретную реализацию мета протокола из раздела 5.7.

Секретный ключ Алисы состоит из: (i) многочлена h(x1,..., xk ) над Z;

(ii) большого целого числа p;

(iii) константы c Z.

– 82 – Открытый ключ Алисы состоит из: (i) многочлена f(x1,..., xk ) = (h(x1,..., xk )) c (mod p);

таким образом, для любых x1,..., xk Z существует такое u Z, что f(x1,..., xk ) + c = u2 (mod p);

(ii) случайный многочлен g(x1,..., xk ) над Z с тем же набором мономов как в f и с коэффици ентами того же порядка, что f.

Опишем теперь протокол аутентификации. Для упрощения обо значений, как и в предыдущем разделе, мы приводим версию, в кото рой Боб посылает Алисе только один элемент, а не набор элементов, как в метапротоколе из 5.7.

1. Боб выбирает случайные целые числа x1,..., xk и подставляет их, с равной вероятностью, либо в f, либо в g. Затем он посылает результат Bob(x1,..., xk ) Алисе.

2. Алиса вычисляет a = Bob(x1,..., xk ) + c (mod p) и проверяет, является ли a квадратом по модулю p. Если нет, Алиса делает вывод, что Bob(x1,..., xk ) = f(x1,..., xk ), и посылает Бобу 1. Ес ли да, Алиса предполагает, что Bob(x1,..., xk ) = f(x1,..., xk ) и посылает 0.

3. Боб, зная правильный ответ, сверяет его с ответом Алисы и соот ветственно принимает или отвергает попытку аутентификации.

Чтобы проверить, является ли a квадратом по модулю p, Алиса p возводит a в степень 2. Если результат сравним с 1 по модулю p, то a – квадрат по модулю p;

если нет – нет.

И снова заметим, что есть пренебрежимо малая вероятность то го, что Боб отклонит честную Алису, потому что может случить ся так, что Bob(x1,..., xk ) + c является квадратом по модулю p, но Bob(x1,..., xk ) = g(x).

Мы предлагаем использовать следующие значения параметров для вышеописанного протокола.

– 83 – 1. Число переменных k: от 3 до 5.

2. Значение p: порядка 2t, где t – параметр надёжности.

3. Степень секретного многочлена Алисы h: от 2 до 3. Порядок его коэффициентов: по крайней мере p.

4. Боб выбирает свои целые числа x1,..., xk равномерно из интер t вала [1, 2 k ].

Противник может попытаться ответить на вопрос Боба, решив одно из уравнений f(x1,..., xk ) = Bob(x1,..., xk ) или g(x1,..., xk ) = Bob(x1,..., xk ) в целых числах x1,..., xk, или просто попытаться вы яснить, имеет ли какое-либо из этих уравнений решения в целых чис лах. Соответствующая задача (разрешимость диофантовых уравне ний, или 10-я проблема Гильберта), как известно, неразрешима [55]. В нашем случае, однако, перед противником на самом деле стоит задача с обещанием (promise problem), поскольку он знает заранее, что по крайней мере одно из уравнений имеет целые решения. Более того, в нашем случае размер неизвестных тоже ограничен. Однако даже та кая ограниченная задача о разрешимости диофантовых уравнений NP-трудна [26], что заставляет сомневаться в её успехе.

– 84 – 6 Проведение научного семинара 12–13 июня 2011 года в нескольких залах ПОМИ РАН (Санкт Петербург, наб. р. Фонтанки, 27) был проведен научный семинар Workshop on post-quantum cryptography ( Семинар по посткванто вой криптографии ), являющийся семинаром–сателлитом междуна родной конференции Computer Science in Russia 2011. Руководитель и основной организатор семинара – руководитель работ, д.ф.-м.н. Д.Ю.

Григорьев.

Ниже приводится программа семинара. Рабочим языком семи нара был английский. В семинаре приняли участие исследователи из России, Франции (CNRS), США (City University of New York, Stevens Institute of Technology) и Канады (University of Montreal), студенты и аспиранты ПОМИ РАН, Санкт-Петербургского Государственного Уни верситета, Академического Университета. Официальный сайт семина ра – http://logic.pdmi.ras.ru/csr2011/quantumcryptography.

 Воскресенье, 12 июня.

10:00–10:15 Вступительное слово.

10:15–11:15 Владимир Шпильрайн (University of Montreal) Криптогра фия без односторонних функций.

11:15–11:30 Кофе-брейк.

11:30–12:30 Александр Ушаков (City University of New York), Аутенти фицированный протокол Аншель–Аншеля–Гольдфельда.

12:30–12:45 Кофе-брейк.

12:45–13:30 Деларам Каробей (City University of New York), Протокол публичного обмена ключами, основанный на матрицах над групповыми кольцами.

13:30–15:30 Обед.

15:30–16:30 Сергей Николенко (ПОМИ РАН), Нечёткая криптогра – 85 – фия 16:30–17:00 Общая дискуссия.

 Понедельник, 13 июня.

10:00–10:35 Дмитрий Ицыксон (ПОМИ РАН), Об оптимальном рандо мизированном аксепторе для задачи изоморфизма графов.

10:35–11:35 Александр Смаль (ПОМИ РАН), Оптимальные эвристиче ские алгоритмы для образа инъективной функции.

11:35–11:55 Кофе-брейк.

11:55–12:55 Дмитрий Григорьев (CNRS), Тропическая криптография.

12:55–13:10 Кофе-брейк.

13:10–13:40 Владимир Шпильрайн (University of Montreal), Аутенти фикация без разглашения при помощи метода Шерлока Холмса.

13:40–14:00 Заключительное слово.

– 86 – 7 Разработка программы внедрения результатов НИР в образовательный процесс и плана дальней шего взаимодействия с приглашённым исследова телем 7.1 Внедрение результатов НИР в образовательный процесс Результаты НИР внедряются участниками проекта в учебные про граммы курсов магистратуры кафедры математических и ин формационных технологий Учреждения Российской академии на ук Санкт-Петербургского Академического университета – научно образовательного центра нанотехнологий РАН (СПб АУ НОНЦТ РАН) и аспирантуры АУ РАН и ПОМИ РАН. Учебные программы некото рых из разработанных участниками проекта курсов приведены в при ложениях к настоящему отчёту.

7.2 План дальнейшего взаимодействия с приглашённым иссле дователем Взаимодействие исследователей ПОМИ РАН с Д.Ю. Григорьевым не закончится с окончанием проекта. В настоящее время можно выделить следующие основные направления дальнейшего сотрудничества.

1. Участник проекта, н.с. ПОМИ РАН С.И. Николенко планирует продолжать научное сотрудничество с Д.Ю. Григорьевым в об ласти теоретической криптографии и теории сложности вычис лений. В частности, планируется подать совместную немецко– российскую заявку в фонд DFG на осуществление большого проекта по математике с участием российских и немецких учё ных, в том числе других сотрудников ПОМИ РАН. В случае успеха заявки планируются научные визиты сотрудников ПО – 87 – МИ РАН в Институт Макса Планка в Бонне (Max Planck Instit t u f r Mathematik).

u 2. Д.Ю. Григорьев планирует продолжать сотрудничество с россий скими участниками проекта в области совместного руководства студентами и аспирантами ПОМИ РАН и СПб АУ НОНЦТ РАН.

3. Для осуществления этих и других научных планов Д.Ю. Григо рьев планирует продолжать визиты в Санкт-Петербург и после формального завершения проекта. Ближайший визит Д.Ю. Гри горьева планируется в октябре 2011 г.

– 88 – Список литературы [1] Ajtai M. 1 -formulae on nite structures // Annals of Pure and Applied Logic. 1983. Vol. 24. P. 1–48.

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

[3] Allender E. Circuit Complexity before the Dawn of the New Mil lennium // Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science. 1996. P. 1– 18.

[4] Alon N., Karchmer M., Wigderson A. Linear Circuits over GF(2) // SIAM Journal of Computing. 1990. Vol. 19, N. 6. P. 1064– 1067.

[5] Ben-Sasson E., Kopparty S. Ane dispersers from subspace poly nomials // Proceedings of the Annual Symposium on Theory of Computing (STOC). Vol. 679. ACM Press, 2009. P. 65–74.

http://portal.acm.org/citation.cfm?doid=1536414.1536426.

[6] Blum L., Shub M., Smale S. On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines // Bulletin of the American Math ematical Society. 1989. Vol. 21, N. 1. P. 1–46.

[7] Blum N. A Boolean Function Requiring 3n Network Size // Theo retical Computer Science. 1984. Vol. 28. P. 337–345.

[8] Bogdanov A., Trevisan L. Average-Case Complexity // Founda tions and Trends in Theoretical Computer Science. 2006. Vol. 2.

[9] Bublitz S. Decomposition of Graphs and Monotone Formula Size of Homogeneous Functions // Acta Informatica. 1986. Vol. 23. P. 410– 417.

– 89 – [10] Butkovic P. Max-linear systems: theory and algorithms. Springer Verlag London, 2010.

[11] Cai J. With probability 1, a random oracle separates PSPACE from the polynomial-time hierarchy // Journal of Computer and System Sciences. 1989. Vol. 38. P. 68–85.

[12] Chtcherba A. D. A new Sylvester-type resultant method based on the Dixon-Bezout formulation: Ph.D. thesis / The University of New Mexico. 2003.

[13] Cid C., Leurent G. An Analysis of the XSL Algorithm // Proceed ings of the 11th ASIACRYPT, International Conference on the Theo ry and Application of Cryptology and Information Security, Lecture Notes in Computer Science. Vol. 3788. 2005. P. 333–352.

[14] Cloud M. J., Moore R. E., Kearfott R. B. Introduction to Interval Analysis. Philadelphia: Society for Industrial and Applied Mathe matics, 2009.

[15] Courtois N., Pieprzyk J. Cryptanalysis of Block Ciphers with Overdened Systems of Equations // Proceedings of the 8th ASI ACRYPT, International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Science. Vol. 2501. 2002. P. 323–337.

[16] Davydow A., Nikolenko S. I. Gate elimination for linear functions and new feebly secure constructions // Proceedings of the 6th Com puter Science Symposium in Russia, Lecture Notes in Computer Sci ence. Vol. ??? 2011. P. ??–??

[17] Dedieu J. P., Shub M. Newton’s Method for Overdetermined Sys tems of Equations // Mathematics of Computation. 1999. Vol. 69, N. 231. P. 1099–1115.

[18] Didrit O., Jaulin L., Kieer M. Applied Interval Analysis. Berlin:

Springer-Verlag, 2001.

– 90 – [19] Die W., Hellman M. New directions in cryptography // IEEE Transactions on Information Theory. 1976. Vol. IT-22. P. 644–654.

[20] Dwork C. Positive Applications of Lattices to Cryptography // Proceedings of the 22nd International Symposium on Mathemati cal Foundations of Computer Science, Lecture Notes in Computer Science. Vol. 1295. 1997. P. 44–51.

[21] Feige U., Fiat A., Shamir A. Zero knowledge proofs of identity // Journal of Cryptology. 1987. Vol. 1. P. 77–94.

[22] Fortnow L., Santhanam R. Hierarchy Theorems for Probabilistic Polynomial Time // Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS 2004). 2004. P. 316–324.

[23] Fortnow L., Santhanam R. Time Hierarchies: A Survey: Tech. Rep.

07–004: Electronic Colloquium on Computational Complexity, 2007.

[24] Frberg R. An Introduction to Grbner Bases. Wiley & Sons, 1997.

o o [25] Furst M., Saxe J., Sipser M. Parity, circuits, and the polynomial time hierarchy // Mathematical Systems Theory. 1984. Vol. 17.

P. 13–27.

[26] Garey M. R., Johnson D. S. Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA, 1979.

[27] Goldreich O. Introduction to Complexity Theory. Lecture Notes.

Weizmann Institute of Science, 1998–99.

[28] Goldreich O. Foundations of Cryptography. Basic Tools. Cambridge University Press, 2001.

[29] Goldreich O., Wigderson A. Tiny Families of Functions with Ran dom Properties: A Quality-Size Trade-o for Hashing // Random Structures & Algorithms. 1997. Vol. 11, N. 4. P. 315–343.

[30] Grigoriev D., Hirsch E. A., Pervyshev K. A Complete Public-Key Cryptosystem // Groups, Complexity, and Cryptology. 2009. Vol. 1.

– 91 – P. 1–12.

[31] Grigoriev D., Hirsch E. A., Pervyshev K. A Complete Public-Key Cryptosystem // Groups, Complexity, and Cryptology. 2009. Vol. 1, N. 1. P. 1–12.

[32] Grigoriev D., Kojevnikov A. A., Nikolenko S. I. Invariant-Based Cryptosystems and Their Security Against Provable Break: Tech.

Rep. 158: Max-Planck-Instit t preprints, 2007.

u [33] Grigoriev D., Shpilrain V. Authentication from matrix conjuga tion // Groups, Complexity, and Cryptology. 2009. Vol. 1. P. 199– 205.

[34] Grigoriev D., Shpilrain V. Zero-knowledge authentication schemes from actions on graphs, groups, or rings // Annals of Pure and Ap plied Logic. 2010. Vol. 162. P. 194–200.

[35] Hansen E. R. A generalized interval arithmetic // Interval Mathe matics, Lecture Notes in Computer Science. Vol. 29. Springer-Verlag, Berlin, 1978. P. 7–18.

[36] Harnik D., Kilian J., Naor M., Reingold O., Rosen A. On robust combiners for oblivious transfers and other primitives // Proceedings of EuroCrypt ’05, Lecture Notes in Computer Science. Vol. 3494.

2005. P. 96–113.

[37] Hastad J. Computational Limitations for Small Depth Circuits.

MIT Press, Cambridge, MA, 1987.


[38] Hiltgen A. P. Constructions of Feebly-One-Way Families of Permu tations // Proc. of AsiaCrypt ’92. 1992. P. 422–434.

[39] Hirsch E. A., Itsykson D., Monakhov I., Smal A. On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography: Tech. Rep. 10–193: ECCC, 2010.

Extended

Abstract

appeared in the proceedings of STACS-2010.

[40] Hirsch E. A., Nikolenko S. I. A feebly secure trapdoor function // – 92 – Proceedings of the 4th Computer Science Symposium in Russia, Lec ture Notes in Computer Science. Vol. 5675. 2009. P. 129–142.

[41] Immerman M. Languages which capture complexity classes // SIAM Journal of Computing. 1987. Vol. 4. P. 760–778.

[42] Impagliazzo R., Naor M. Ecient cryptographic schemes provably as secure as subset sum // Journal of Cryptology. 1996. Vol. 9.

P. 199–216.

[43] Itenberg I., Mikhalkin G., Shustin E. Tropical algebraic geometry.

Birkhuser, Basel, 2007. Vol. 35 of Oberwolfach Seminars.

a [44] Itsykson D. Structural complexity of AvgBPP // Annals of Pure and Applied Logic. 2010. Vol. 162, N. 3. P. 204–215.

[45] Juels A., Sudan M. A Fuzzy Vault Scheme // Designs, Codes and Cryptography. 2006. Vol. 38, N. 2. P. 237–257.

[46] Kapur D., Lakshman Y. N. Elimination methods: an introduc tion // Symbolic and Numerical Computation for Articial Intelli gence / Ed. by B. Donald, D. Kapur, J. Mundy. Academic Press, 1992.

[47] Kapur D., Saxena T. Comparison of various multivariate resultant formulations // Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation. ACM Press, 1995. P. 187– 195.

[48] Karrer B., Newman M. E. J. Random Acyclic Networks // Phys ical Review Letters. 2009. Vol. 102, N. 12. P. 128701.

[49] Koblitz N., Menezes A. Another Look at “Provable Security” // Journal of Cryptology. 2007. Vol. 20, N. 1. P. 3–37.

[50] Koiran P., Perifel S. The Complexity of Two Problems on Arith metic Circuits // Theoretical Computer Science. 2007. Vol. 389, N. 1–2. P. 172–181.

[51] Lamagna E. A., Savage J. E. On the logical complexity of sym – 93 – metric switching functions in monotone and complete bases: Tech.

rep. Rhode Island: Brown University, July 1973.

[52] Levin L. A. Universal Search Problems // Problemy Peredachi In formacii. 1973. Vol. 9, N. 3. P. 265–266. English translation in: B.A.Trakhtenbrot. A Survey of Russian Approaches to Perebor (Brute- force Search) Algorithms. Annals of the History of Com puting 6(4):384-400, 1984.

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

[54] Matiyasevich Y. V. A Posteriori Interval Analysis // Proceedings of the EUROCAL’85, Lecture Notes in Computer Science. Vol. 204.

1985. P. 328–334.

[55] Matiyasevich Y. V. Hilbert’s Tenth Problem. MIT Press, 1993.

[56] McDiarmid C. Concentration // Probabilistic Methods for Algo rithmic Discrete Mathematics. Springer-Verlag, 1998. Vol. 16 of Algorithms and Combinatorics. P. 195–248.

[57] Melanon G., Dutour I., Bousquet-Mlou M. Random Generation c e of Directed Acyclic Graphs // Electronic Notes in Discrete Mathe matics. 2001. Vol. 10. P. 202–207.

[58] Mikhalkin G. Tropical geometry and its applications // Proceed ings of the International Congress of Mathematicians. Vol. 2. 2006.

P. 827–852.

[59] Moore R. E. Interval Analysis. Englewood Cli, New Jersey:

Prentice-Hall, 1966.

[60] Nikolenko S. I. Provably Secure Constructions in Cryptography.

LAP Lamberts Academic Publishing, 2011.

[61] Pan V. Y., Zheng A.-L. New progress in real and complex polyno mial root-nding // Computers & Mathematics with Applications.

2011. Vol. 61, N. 5. P. 1305–1334.

– 94 – [62] Paul W. J. A 2, 5n lower bound on the combinational complexity of Boolean functions // SIAM Journal of Computing. 1977. Vol. 6.

P. 427–443.

[63] Pervyshev K. On Heuristic Time Hierarchies // Proceedings of the IEEE Conference on Computational Complexity. 2007. P. 347–358.

[64] Poon H. T., Miri A. A Collusion Attack on the Fuzzy Vault Scheme // The ISC International Journal of Information Security.

2009. Vol. 1, N. 1. P. 27–34.

[65] Razborov A. A. Bounded arithmetic and lower bounds // Feasi ble Mathematics II / Ed. by P. Clote, J. Remmel. Birkhuser, a 1995. Vol. 13 of Progress in Computer Science and Applied Logic.

P. 344–386.

[66] Regev O. On lattices, learning with errors, random linear codes, and cryptography // Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 2005. P. 84–93.

[67] Regev O. Lattice-Based Cryptography // Proceedings of the 26th Annual International Cryptology Conference (CRYPTO’06), Lecture Notes in Computer Science. Vol. 4117. 2006. P. 131–141.

[68] Rivest R. L., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems // Communica tions of the ACM. 1978. Vol. 21, N. 2. P. 120–126.

[69] Savage J. E. The Complexity of Computing. New York: Wiley, 1976.

[70] Schreier W. J., Boult T. E. Cracking Fuzzy Vaults and Biometric Encryption // Proceedings of the Biometrics Symposium 2007 at The Biometric Consortium Conference (BCC), Baltimore, Maryland, USA. 2007.

[71] Schrijver A. Theory of Linear and Integer Programming. John Wi ley, 1998.

– 95 – [72] Shannon C. E. Communication Theory of Secrecy Systems // Bell System Technical Journal. 1949. Vol. 28, N. 4. P. 656–717.

[73] Shub M., Smale S. Complexity of Bezout’s Theorem I: Geometric aspects // Journal of the American Mathematical Society. 1993.

Vol. 6. P. 459–501.

[74] Shub M., Smale S. Complexity of Bezout’s Theorem II: Volumes and Probabilities // Computational Algebraic Geometry / Ed. by F. Eyssette, A. Galligo. Bikrhuser, 1993. Vol. 109 of Progress in a Mathematics. P. 267–285.

[75] Shub M., Smale S. Complexity of Bezout’s Theorem III: Condition Number and Packing // Journal of Complexity. 1993. Vol. 9. P. 4–14.

[76] Shub M., Smale S. Complexity of Bezout’s Theorem V: Polynomial Time // Theoretical Computer Science. 1994. Vol. 134. P. 141–164.

[77] Shub M., Smale S. Complexity of Bezout’s Theorem IV: Probability of Success;

Extensions // SIAM Journal of Numerical Analysis. 1996.

Vol. 33. P. 128–148.

[78] Smolensky R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity // Proceedings of the 19th Annual ACM Symposium on Theory of Computing. 1987. P. 77–82.

[79] Stockmeyer L. The complexity of decision problems in automata theory and logic: Ph.D. thesis / Massachusetts Institute of Technol ogy. 1974.

[80] Stockmeyer L. On the combinational complexity of certain sym metric Boolean functions // Mathematical Systems Theory. 1977.

Vol. 10. P. 323–326.

[81] Stockmeyer L. Classifying the computational complexity of prob lems // Journal of Symbolic Logic. 1987. Vol. 52. P. 1–43.

[82] van Melkebeek D., Pervyshev K. A Generic Time Hierarchy with One Bit of Advice // Computational Complexity. 2007. Vol. 16, – 96 – N. 2. P. 139–179.

[83] Vernam G. S. Cipher Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications // Journal of the IEEE.

1926. Vol. 55. P. 109–115.

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

[85] Yao A. C.-C. Separating the polynomial-time hierarchy by ora cles // Proceedings of the 26th Annual IEEE Symposium on the Foundations of Computer Science. 1985. P. 1–10.

[86] 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.

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

[88] Григорьев Д. Ю., Кожевников А. А., Николенко С. И. Алгеб раическая криптография: новые конструкции и их надёжность относительно доказуемого взлома // Алгебра и Анализ. 2008.

Т. 20, № 6. С. 119–147.

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

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

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

[92] Меланич О. Нелинейные надежные в слабом смысле криптогра фические примитивы // Препринты ПОМИ. 2009. № 12.

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

[94] Нигматуллин Р. Г. Сложность булевых функций. М., Наука, 1991.

[95] Николенко С. И. Новые конструкции криптографических при митивов, основанные на полугруппах, группах и линейной ал гебре: Ph.D. thesis / Санкт-Петербургское отделение Математи ческого института им. В. А. Стеклова РАН. 2009.

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

С. 887–900.

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

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

[99] Субботовская Б. А. О реализации линейных функций форму лами в базисе, &, ¬ // Доклады Академии Наук СССР. 1961.

Т. 136, № 3. С. 553–555.

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


[101] Хачиян Л. Я. Полиномиальный алгоритм в линейном програм мировании // Доклады Академии Наук СССР. 1979. Т. 244.

С. 1093–1096.

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

С. 36–40.

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

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

– 99 – УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru № 11102/33/ Министерство по образованию и науки РФ На от Заключение по открытому опубликованию Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН подтверждает, что все исследования, проводимые в рамках государственного контракта №02.740.11.5192 от 12 марта 2010 г., носят фундаментальный теоретический характер. Полученные результаты не содержат сведения, составляющие государственную тайну, а также информацию ограниченного распространения. В связи с этим результаты не требуют экспертного заключения и публикуются в открытой печати в установленном порядке.

Директор Учреждения Российской академии наук Санкт-Петербургского отделения Математического института им. В.А. Стеклова РАН, член-корр. РАН /С.В. Кисляков/ – 100 – Заключение Все задачи, которые предполагалось решить на втором этапе проекта, были решены.

Основные результаты исследования таковы.

1. Прототипы программного обеспечения, каталог эффективных схем, новые верхние оценки схемной сложности.

2. Новые конструкции линейных функций с секретом, доказуемо надёжных в слабом смысле.

3. Новые нижние оценки схемной сложности аффинных дисперсеров.

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

5. Новые непрерывные криптографические примитивы и протоколы аутентификации;

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

В рамках проекта в 2011 г. был проведён семинар “Workshop on Post-Quantum Cryptography” с участием руководителя проекта, учёных из США и Канады, сотрудников ПОМИ РАН, в т.ч. исполнителей проекта, студентов и аспирантов.

Ниже приведён список публикаций по результатам государственного контракта, вышедших и поданных к публикации во время исполнения второго этапа работ. Помимо научных статей, участник проекта С.И. Николенко опубликовал монографию “Provably Secure Constructions in Cryptography” («Доказуемо надёжные конструкции в криптографии»), которая содержит в том числе и результаты проекта. Публикации (в т.ч. оглавление и титульный лист монографии) прилагаются к отчёту в виде приложений.

1. S. I. Nikolenko. Provably Secure Constructions in Cryptography. LAP Lambert Academic Publishing, 2011.

2. E. Demenkov, A. Kulikov. An Elementary Proof of a 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers // Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), – 101 – LNCS 6907, 2011, pp. 256–265.

3. E. A. Hirsch. Optimal acceptors and optimal proof systems // Proceedings of Theory and Applications of Models of Computation (TAMC-2010), Springer, 2010, pp. 28-39.

4. A. Davydow, S. I. Nikolenko. Gate Elimination for Linear Functions and New Feebly Secure Constructions // Proceedings of the 6th Computer Science Symposium in Russia (CSR 2011), LNCS vol. 6651, pp. 148-161.

5. Edward A. Hirsch, Dmitry Itsykson, Valeria Nikolaenko and Alexander Smal.

Optimal heuristic algorithms for the image of an injective function. ECCC Report TR11-091.E.

6. D. Grigoriev, V. Shpilrain. No-Leak Authentication by the Sherlock Holmes Method // MPIM Preprint, Submitted to Groups, Complexity, Cryptology.

7. D. Grigoriev, S.I. Nikolenko. Continuous hard-to-invert functions with applications to biometric authentication // Submitted to Groups, Complexity, Cryptology.

– 102 – Приложение В настоящем Приложении приводятся программы учебных дисциплин аспирантуры ПОМИ РАН, подготовленные участниками проекта в течение второго этапа работ по проекту.

– 103 – Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru «УТВЕРЖДАЮ»:

Директор ПОМИ РАН Чл.-корр РАН _ С.В. Кисляков «»_ 2010 г.

ПРОГРАММА ДИСЦИПЛИНЫ ФД.А.00. «Теория сложности вычислений».

основной образовательной программы послевузовского профессионального образования по научной специальности 01.01. Рабочая программа составлена на основании Временных требований к основной образовательной программе послевузовского профессионального образования по отрасли 01.00.00 Физико математические науки Программа составлена м.н.с., к.ф.-м.н. Д.М. Ицыксон РАССМОТРЕНА И ОДОБРЕНА на заседании обеспечивающей лаборатории математической логики протокол № от _2010 г 1. ЦЕЛИ УЧЕБНОЙ ДИСЦИПЛИНЫ Дисциплина является факультативной в курсе обучения аспирантов, проходящих подготовку по специальности ВАК 01.01.06 - математическая логика, алгебра и теория чисел. Целью преподавания данной дисциплины является подготовка высококвалифицированных специалистов в области теории сложности вычислений. Курс посвящен основным сложностным классам вычислительных задач, методам доказательства соотношений между ними, методам доказательства нижних оценок вычислительной сложности и методам дерандомизации.

2. ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ – 104 – Задачей дисциплины является изучение основных сложностных классов, и методов, использующихся в теории сложности вычислений. После освоения курса аспиранты должны оперативно владеть основными понятиями теории сложности вычислений, доказывать соотношения между сложностными классами.

ОБЪЕМ ДИСЦИПЛИНЫ ПО ВИДАМ УЧЕБНОЙ ФОРМЫ И КОНТРОЛЯ Виды занятий и форма контроля часы Лекции, ч/нед Практические занятия, ч/нед Зачеты, кол./сем. Всего часов 3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Изучаемый вопрос К-во часов 1 Полиномиальная иерархия Недетерминированная машина Тьюринга — возможные определения и их эквивалентность.

Классы недетерминированных вычислений.

Вычисления с оракулом. Полиномиальная иерархия. Альтернативное определение классов полиномиальной иерархии и полные задачи для них. Вычисления с полиномиальной памятью, полнота задачи о справедливости булевой формулы с кванторами. Теорема Карпа-Липтона о коллапсе полиномиальной иерархии при наличии полиномиальных схем для языков из NP.

Существование оракулов A и B, для которых P^A=NP^B выполняется и не выполняется.

Сведение NP-задач поиска к NP-полным задачам распознавания. Оптимальный алгоритм для задач поиска из NP. Не NP-полные задачи в NP-P 2 Вероятностные алгоритмы Классы RP и BPP. Уменьшение вероятности ошибки. Включение BPP во второй уровень полиномиальной иерархии. Наличие полиномиальных схем для языков из BPP.

Эффективное уменьшение вероятности ошибки в BPP при помощи экспандеров. Лемма Вэлианта Вазирани.

3 Считающие классы Классы PP и #P. P^{PP}=P^{#P}. Полнота задачи о перманенте для класса #P 4 Интерактивные протоколы и вероятностно проверяемые доказательства Классы MA, AM, IP. Интерактивные протоколы для неизоморфизма графов и перманента матрицы. Теорема Шамира (IP=PSPACE).

Включение MA в ZPP^NP. PCP теорема:

определения, формулировки, эквивалентность – 105 – формулировок, следствие о неаппроксимируемости, доказательство 5 Схемная сложность Отсутствие схем размера n^k для P^{PP}.

Отсутствие схем размера n^k для PP. Отсутствие схем размера n^k для полиномиальной иерархии.

Отсутствие арифметических схем ограниченной глубины для функции чётности 6 Криптография Сильные и слабые односторонние функции.

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

Протоколы привязки к биту. Доказательство с нулевым разглашением.

7 Сложность в среднем Распределенные задачи. Полиномиальность в среднем по Левину и Импальяццо. Пример распределения, для которого сложность в среднем и наихудшем случае эквивалентны.

Доминирование распределений. Универсальное полиномиально моделируемые распределение.

Сведения. Полная задача в (NP, PSamp).

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

Полнота задачи об ограниченной остановке.

Сведение задач поиска к задачам распознавания.

Вероятностное сведение к (NP, PSamp) к (NP,U).

8 Методы доказательства нижних оценок Теорема Разборова о нижней оценки для монотонных схем. Нижние оценки для схем ограниченной глубины: лемма о переключениях.

Теорема Разборова-Смоленского. Нижние оценки в теории сложности доказательств: метод узкого места, интерполяция. Нижние оценки для деревьев принятия решения. Нижние оценки в коммуникационной сложности. Трудности доказательства нижних оценок: естественные доказательства.

9 Дерандомизация Генератор псевдослучайных чисел из функций большой схемной сложности. Яо XOR лемма, лемма Импальяццо о трудном ядре. Коды исправляющие ошибки. Декодирование списком.

Псевдослучайный генератор Нисана-Вигдерсона.

10 Псевдослучайные конструкции Алгебраические и комбинаторные экспандеры.

– 106 – Явная конструкция экспандеров.

Детерминированный логарифмический по памяти алгоритм достижимости в неориентированном графе. Экстракторы. Экстрактор Тревисана.

Генератор псевдослучайных чисел для вычислений с ограничениями по памяти.

ВСЕГО 4. МАТЕРИАЛЬНОТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Лаборатория математической логики ПОМИ РАН, оснащенная необходимой техникой, оборудованием и доступом к электронным ресурсам.

5. ФОРМА ИТОГОВОГО КОНТРОЛЯ Проверка усвоения материала курса проводится посредством проведения зачета.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Рекомендованная литература 1. А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления. М.: МЦНМО, 1999, 192 с.

2. S.Arora, B.Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

3. O.Goldreich. Foundations of cryptography. Vol. 1-2, Cambridge Unversity Press, 2001.

Дополнительная литература 1. C.Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

2. A. Bogdanov, L. Trevisan. Average-case complexity. Foundation and Trends in Theoretical Computer Science, 2(1):1_106, 3. S. Hoory, N. Linial, A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, vol.

43, Number 4, Oct. 2006, pp.439– – 107 – Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru «УТВЕРЖДАЮ»:

Директор ПОМИ РАН Чл.-корр РАН _ С.В. Кисляков «»_ 2010 г.

ПРОГРАММА ДИСЦИПЛИНЫ ФД.А.00. «Коммуникационная сложность».

основной образовательной программы послевузовского профессионального образования по научной специальности 05.13. Рабочая программа составлена на основании Временных требований к основной образовательной программе послевузовского профессионального образования по отрасли 01.00.00 Физико математические науки РАССМОТРЕНА И ОДОБРЕНА на заседании обеспечивающей лаборатории математической логики протокол № от _2009 г Программа составлена м.н.с., к.ф.-м.н. А.С. Куликов 1. ЦЕЛИ УЧЕБНОЙ ДИСЦИПЛИНЫ Дисциплина является факультативной в курсе обучения аспирантов, проходящих подготовку по специальности ВАК 05.13.17 – теоретические основы информатики. Целью преподавания данной дисциплины является подготовка высококвалифицированных специалистов в области теории сложности вычислений.

2. ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет – 108 – минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений.

ОБЪЕМ ДИСЦИПЛИНЫ ПО ВИДАМ УЧЕБНОЙ ФОРМЫ И КОНТРОЛЯ Виды занятий и форма контроля часы Лекции, ч/нед Практические занятия, ч/нед Зачеты, кол./сем. Всего часов 3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Изучаемый вопрос К-во часов 1 Определение детерминированного коммуникационного протокола.

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

2 методом трудных множеств Нижние оценки для функций. Нижняя оценка методом размера прямоугольников для функции (Inner Product). Нижние оценки для методом ранга для функций IP, EQ, GT.

Оценка. Покрытия нулей и единиц матрицы функции одноцветными прямоугольниками. Величины и интерпретация их логарифмов как недетерминированной коммуникационной сложности. Неравенство: меньше и. Верхняя и нижняя оценки и для функций.

3 Связь между детерминированной сложностью и разбиениями матрицы функции на одноцветные прямоугольники: не превосходит и, обратно,. Теорема о связи детерминированной и недетерминированной сложности: есть.

– 109 – Универсальность метода размера прямоугольников для оценки с точностью до : для всех найдется распределение вероятностей на нулях функции, для которого меньше для всех нуль-цветных прямоугольников.

4 Невозможность избавиться от в последнем утверждении (функция ). Для случайной функции метод размера прямоугольников значительно лучше метода трудного множества.

Функция для. Верхние оценки,. Нижняя оценка.

5 Вероятностные коммуникационные протоколы с частными датчиками. Три способа определения вычисления функции (с двусторонней ошибкой, с односторонней ошибкой и безошибочное). Два способа определения коммуникационной сложности вероятностного протокола (как максимума по всех входам среднего количества переданных битов и как максимума по всех входам максимума по всем случайным битам количества переданных битов). Обозначения и соотношения между этими величинами. Уменьшение вероятности ошибки за счет повторения протокола.

6 Вероятностный тест для равенства, оценка. Оценка и как следствие. Оценка. Теорема о связи детерминированной и вероятностной сложности:

. Вероятностные коммуникационные протоколы с общим источником случайности и обозначение.

Оценка.

7 Вероятностный тест для равенства, оценка. Оценка и как следствие. Оценка. Теорема о связи детерминированной и вероятностной сложности:

. Вероятностные коммуникационные протоколы с общим источником случайности и обозначение.

Оценка.

– 110 – 8 Теорема о переделывании общего источника в частный с увеличением сложности на не превосходит. Нижняя оценка методом трудных распределений вероятностей на входных парах. Неоднородность (discrepancy) функции для данного распределения и оценка трудности распределения через неоднородность.

Линейная нижняя оценка для. Нижняя оценка для неоднородности предиката DISJ: для любого распределения выполнено.

9 Вероятностная сложность предиката : верхние оценки и. Верхняя оценка безошибочной вероятностной сложности для функции :

.

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

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

ВСЕГО 4. МАТЕРИАЛЬНОТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Лаборатория Математической логики ПОМИ РАН, оснащенная необходимой техникой, оборудованием и доступом к электронным ресурсам.

5. ФОРМА ИТОГОВОГО КОНТРОЛЯ Проверка усвоения материала курса проводится посредством проведения зачета.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Рекомендованная литература E. Kushilevitz, N. Nisan. Communication Complexity. Cambridge University Press. 1996.

– 111 – Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН 191023 Санкт-Петербург, наб. р.Фонтанки, тел. (812) 312-40-58, факс (812) 310-53- e-mail: admin@pdmi.ras.ru «УТВЕРЖДАЮ»:

Директор ПОМИ РАН Чл.-корр РАН _ С.В. Кисляков «»_ 2010 г.

ПРОГРАММА ДИСЦИПЛИНЫ ФД.А.00. «Криптографические протоколы».

основной образовательной программы послевузовского профессионального образования по научной специальности 05.13. Рабочая программа составлена на основании Временных требований к основной образовательной программе послевузовского профессионального образования по отрасли 05.00.00 Технические науки Программа составлена м.н.с., к.ф.-м.н. С. И. Николенко РАССМОТРЕНА И ОДОБРЕНА на заседании обеспечивающей лаборатории математической логики протокол № от _2009 г 1. ЦЕЛИ УЧЕБНОЙ ДИСЦИПЛИНЫ Дисциплина является основной в курсе обучения аспирантов, проходящих подготовку по специальности ВАК 05.13.17 – Теоретические основы информатики. Целью изучения данной дисциплины является подготовка высококвалифицированных специалистов в области современной криптографии. Особое внимание в курсе уделяется базовым задачам популярных криптографических протоколов, изучению наиболее распространённых атак и методов решения базовых задач.

2. ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ Задачей дисциплины является изучение основных криптографических задач и протоколов, – 112 – использующихся в практической криптографии, а также наиболее популярных конструкций, которые используются для решения этих задач. После освоения курса аспиранты должны владеть основными понятиями и методами современной криптографии, уметь анализировать и конструировать встречающиеся на практике криптографические протоколы, применять основные методы атак на базовые задачи разложения на множители и дискретного логарифма.

ОБЪЕМ ДИСЦИПЛИНЫ ПО ВИДАМ УЧЕБНОЙ ФОРМЫ И КОНТРОЛЯ Виды занятий и форма контроля часы Лекции, ч/нед Практические занятия, ч/нед Зачеты, кол./сем. Всего часов 3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Изучаемый вопрос К-во часов 1 Цели и задачи криптографии. Методы криптографии с секретным ключом. Блочное кодирование.

Задачи криптографии: передача, хранение, аутентификация, проверка целостности.

Криптография с секретным ключом (симметрическое шифрование). Пример ненадёжной аутентификации. Криптографические атаки. Методы блочного кодирования: ECB, CBC, OFB, CTR..

2 Криптография с открытым ключом: система RSA и протокол Диффи-Хеллмана Криптография с открытым ключом. Разложение на множители. Криптосистема RSA. Электронная подпись RSA. Дискретный логарифм. Протокол согласования ключа Диффи-Хеллмана.

Криптосистема ElGamal. Цифровая подпись DSA..



Pages:     | 1 || 3 | 4 |   ...   | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.