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

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

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


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

Российская академия наук

САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТИТУТА

ИМЕНИ В.А. СТЕКЛОВА РАН

УДК 510.6

ГРНТИ 27.03.19

Инв.

№ 11102/33/02-2151

УТВЕРЖДАЮ

Директор

д-р физ.-мат. наук, чл. корр. РАН

С. В. Кисляков «_»_ г.

ОТЧЕТ О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ В рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы по Государственному контракту №02.740.11.5192 от 12 марта 2010 г.

Шифр заявки «2010-1.5-503-007»

по теме:

СХЕМНАЯ СЛОЖНОСТЬ, ТЕОРИЯ СЛОЖНОСТИ В СРЕДНЕМ, НОВЫЕ КОНСТРУКЦИИ КРИПТОГРАФИЧЕСКИХ ПРИМИТИВОВ И ДОКАЗАТЕЛЬСТВА ИХ НАДЁЖНОСТИ В ОСЛАБЛЕННЫХ КОНТЕКСТАХ Наименование этапа: «Теоретические и практические исследования по алгебраической криптографии, схемной сложности и сложности в среднем»

(финальный, этап № 2) Руководитель НИР, д-р физ.-мат. наук _ Д. Ю. Григорьев «_»_ г.

Санкт-Петербург СПИСОК ОСНОВНЫХ ИСПОЛНИТЕЛЕЙ по Государственному контракту №02.740.11.5192 от 12 марта 2010 г.

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

доктор физико- Григорьев Д. Ю.

математических наук подпись, дата Исполнители темы:

научный сотрудник, Николенко С. И.

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

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

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

сотрудник, кандидат подпись, дата физико-математических наук, доцент аспирант Санкт- Деменков Е. А.

Петербургского подпись, дата государственного университета, без ученой степени, без ученого звания аспирант, без ученой Смаль А. В.

степени, без ученого подпись, дата звания –2– аспирант, без ученой Меланич О. Ю.

степени, без ученого подпись, дата звания студент УРАН Санкт- Соколов Д. О.

Петербургского подпись, дата Академического университета - научно образовательного центра нанотехнологий РАН, без ученой степени, без ученого звания ассистент кафедры Образцова С. А.

высшей математики подпись, дата Санкт-Петербургского государственного электротехнического университета «ЛЭТИ», без ученой степени, без ученого звания студент УРАН Санкт- Давыдов А. П.

Петербургского подпись, дата Академического университета - научно образовательного центра нанотехнологий РАН, без ученой степени, без ученого звания –3– Реферат Отчет: 199 с., 1 ч., 5 рис., 0 табл., 104 источн., 2 прил.

криптография, сложность вычислений, схемная сложность В отчете представлены результаты исследований, выполненных по 2 этапу Государственного контракта № 02.740.11.5192 " Схемная сложность, теория сложности в среднем, новые конструкции криптографических примитивов и доказательства их надёжности в ослабленных контекстах " от 12 марта 2010 по направлению "Математика" в рамках мероприятия 1.5 " Проведение научных исследований коллективами под руководством приглашенных исследователей" направления "Стимулирование закрепления молодежи в сфере науки, образования и высоких технологий." федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009-2013 годы.

Цели работы на втором этапе:

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

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

2.3. Доказательство новых оценок на схемную сложность булевских функций.

2.4. Исследование структурных свойств (наличия иерархии по времени, наличия полных задач) в семантических классах сложности в среднем случае.

2.5. Разработка новых конструкций криптографических протоколов аутентификации и/или защиты информации.

–4– 2.6. Проведение научного семинара по теме «Сложность в среднем, аутентификация и криптография с открытым ключом».

2.7 Разработка программы внедрения результатов НИР в образовательный процесс и плана дальнейшего взаимодействия с приглашённым исследователем.

Методы:

2.1. Методы теории схемной сложности, сведение к задаче выполнимости.

2.2. Методы теории криптографических примитивов, доказуемо надёжных в слабом смысле;

методы теории схемной сложности.

2.3. Методы теории схемной сложности.

2.4. Методы теории сложности в среднем.

2.5. Методы алгебраической криптографии.

Инструменты:

ГОСТ высшего профессионального образования, направление 511600 прикладные математика и физика.

ГОСТ 7.32- Материалы теоретических исследований, раскрывающие содержание работ по решению поставленных научно-исследовательских задач, достаточность теоретических и достоверность экспериментальных результатов. Основные теоретические результаты:

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

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

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

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

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

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

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

–6– Содержание 1 Разработка прототипов программного обеспечения для ав томатизированного доказательства новых оценок схемной сложности булевских функций 1.1 Краткая аннотация...................... 1.2 Использование SAT -солверов для нахождения эффек тивных булевых схем..................... 1.3 Кодировка остатков...................... 1.4 Верхние оценки для функции MOD3............ 2 Разработка новых конструкций криптографических при митивов, доказуемо надёжных в слабом смысле 2.1 Краткая аннотация...................... 2.2 Введение............................ 2.3 Определения и обозначения................. 2.4 Неконструктивные оценки схемной сложности линей ных функций.......................... 2.5 Метод исключения гейтов для линейных функций... 2.6 Функции с секретом, доказуемо надёжные в слабом смысле 2.7 Заключение и открытые проблемы............. 3 Доказательство новых оценок на схемную сложность бу левских функций 3.1 Краткая аннотация...................... 3.2 Нижняя оценка 3n o(n) для афинных дисперсеров.. 4 Исследование структурных свойств в семантических клас сах сложности в среднем случае 4.1 Краткая аннотация...................... 4.2 Оптимальный эвристический аксептор........... –7– 4.3 Оптимальный эвристический алгоритм для образа инъ ективной функции и его дерандомизация......... 4.4 Вероятностные эвристические алгоритмы......... 4.5 Задача распознавания образа инъективной функции.. 4.6 Основная конструкция оптимального алгоритма..... 4.7 Оптимальный вероятностный эвристический алгоритм. 4.8 Оптимальный детерминированный эвристический алго ритм............................... 5 Разработка новых конструкций криптографических про токолов аутентификации и/или защиты информации 5.1 Краткая аннотация...................... 5.2 Непрерывные труднообратимые функции: полиноми альные кандидаты....................... 5.3 Непрерывные труднообратимые функции: случайное по рождение ключей....................... 5.4 Непрерывные труднообратимые функции: протокол... 5.5 Непрерывные труднообратимые функции: супертропи ческие кандидаты....................... 5.6 Непрерывные труднообратимые функции: пример ин терактивного протокола................... 5.7 Схемы аутентификации: метапротокол........... 5.8 Схемы аутентификации: конкретная реализация на при мере задачи Subset Sum................... 5.9 Схемы аутентификации: реализация через полиноми альные уравнения....................... 6 Проведение научного семинара 7 Разработка программы внедрения результатов НИР в об –8– разовательный процесс и плана дальнейшего взаимодей ствия с приглашённым исследователем 7.1 Внедрение результатов НИР в образовательный процесс 7.2 План дальнейшего взаимодействия с приглашённым ис следователем.......................... Литература –9– 1 Разработка прототипов программного обеспечения для автоматизированного доказательства новых оценок схемной сложности булевских функций 1.1 Краткая аннотация Доказательство нижних и верхних оценок на схемную сложность бу левых функций является одним из самых старых и сложных направ лений теоретической информатики. Зазор между известными нижни ми и верхними оценками для многих функций по-прежнему остаётся очень велик. До сих пор не известно ни одной явно заданной функции, требующей схем суперполиномиального размера. И в то же время для многих функций минимальные известные схемы имеют экспоненци альный размер.

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

Были разработаны прототипы программного обеспечения, осуществ ляющие это сведение и реализующие переборные алгоритмы.

При помощи этих прототипов были улучшены верхние оценки на схемную сложность функции MODn в полном бинарном базисе B2, а также в базисе U2, содержащем только нелинейные бинарные функ ции. В базисе B2 получена верхняя оценка 3n + O(1), а в базисе U 5.5n + O(1). Известные нижние оценки в данных базисах для функ ции MODn равны 2.5n O(1) и 4n O(1) и доказаны в работах Cток – 10 – майера и Цвика. Предыдущие известные верхние оценки приводятся в книге Р. Г. Нигматуллина “Сложность булевых функций” и равны 5n + o(n) и 7n + o(n), соответственно. Улучшение верхних оценок бы ло достигнуто за счет нахождения оптимальных индуктивных блоков небольшого размера и построения из них схем для функций от произ вольного количества переменных по аналогии с тем, как это сделано в работе Стокмайера при доказательстве верхней оценки 2.5n + O(1) для функции MODn.

Также найдены оптимальные схемы для всех предикатов от че тырех переменных, всех биективных функций от трех переменных, а также доказаны верхние и нижние оценки для симметрических функ ций пяти переменных. Тем самым доказаны оценки на функцию Шен нона C(f) данных классов, где C(f) максимальная схемная слож ность функции, принадлежащей классу. В классе предикатов от четы рех переменных и биективных функций от трех переменных C(f) = 7.

Для класса симметрических функций от пяти переменных доказана нижняя оценка C(f) 9.

1.2 Использование SAT -солверов для нахождения эффектив ных булевых схем В этой части описаны детали сведения, которое используется при ко дировке факта существования схемы для конкретной функции в виде КНФ. Сначала приводится описание общей конструкции сведения, а затем обсуждаем некоторые дополнительные особенности сведения, которые использовались для поиска схем для рассматриваемых нами функций.

Пусть дана таблица истинности булевой функции f : {0, 1}n {0, 1}m и нужно найти булеву схему в базисе A B2, которая вычисля ет f и состоит из минимально возможного количества гейтов. Можно – 11 – закодировать факт существования схемы из N гейтов, вычисляющей функцию f в виде КНФ, используя следующие пропозициональные переменные (входные аргументы пронумерованы индексами от 0 до n 1), а гейты индексами от n до n + N 1 соответственно:

1. tib1 b2 (n i n + N 1, 0 b1 1, 0 b2 1) соответ ствует значению на выходе i-го гейта, если на первый вход ему подано значение b1, а на второй b2. Таким образом, четыре переменные ti00, ti01, ti10, ti11 полностью определяют бинарную булеву функцию, вычисляемую i-ым гейтом. Всего переменных данного типа O(N).

2. cikj (n i n+N1, 0 k 1, 0 j n+N1) принимает зна чение истина, если значение в k-ый вход i-го гейта поступает из j-го гейта, в противном случае принимает значение ложь. Данные переменные полностью описывают структуры ориентированного графа, соответствующего схеме. Всего переменных данного типа O(N2 ).

3. oij (n i n + N 1, 0 j m 1) принимает значение ис тина тогда и только тогда, когда j-ый выход схемы находится в i-ом гейте. Данные переменные полностью определяют положе ние выходов схемы. Всего переменных данного типа O(Nm).

4. vit (0 i n + N 1, 0 t 2n 1) соответствует значению на выходе i-го гейта, если входные аргументы имеют значения, задаваемые битовой маской t. Данные переменные используются для того, чтобы описать тот факт, что значения, вычисляемые в выходах схемы совпадают со значениями из таблицы истинности при всех 2n возможных значениях входных аргументов. Всего переменных данного типа O(2n N).

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

1. Бинарные функции, которые вычисляются в гейтах, принадле жат базису A.

2. Для всех (i, k) в точности одна из переменных cikj является ис тиной (k-ый вход i-го гейта подключен только к одному гейту).

Это дает O(N3 ) 2-дизъюнктов и O(N) O(N)-дизъюнктов.

3. Для всех j в точности одна из переменных oij является истиной (j-ый выход вычисляется в точности одним гейтом). Это дает O(N2 m) 2-дизъюнктов и O(m) O(N)-дизъюнктов.

4. Для всех 0 i n 1 и 0 t 2n 1, vit совпадает с соответ ствующим битом в t. Это дает O(n · 2n ) 1-дизъюнктов.

5. Для всех n i n + N 1 и 0 t 2n 1, vit равно зна чению, которое вычисляется i-ым гейтом в схеме, описываемой остальными переменными. Это дает O(N3 · 2n ) 6-дизъюнктов и является частью сведения, которая приводит к появлению боль шинства дизъюнктов. Дизъюнкты данного типа записывают для всех n i n + N, n j0 i, j0 j1 i, 0 i0 2, 0 i1 2, 0 r 2n и описывают следующее условие:

¬ci0 j0 ¬ci1 j1 ¬(vj0 r = i0 ) ¬(vj1 r = i1 ) (vir = tii0 i1 ).

Здесь первые два литерала позволяют найти те два гейта, кото рые являются входами i-го гейта, следующие два литерала нуж ны для нахождения значений этих гейтов на входном наборе r, а последнее условие необходимо для проверки того, что значе ние в i-ом гейте вычисляется правильно (на самом деле, так как описанное выше условие не является дизъюнктом, поскольку со держит равенство, то для его записи необходимо два похожих дизъюнкта для разбора случаев: обе переменные истинны или – 13 – обе ложны):

¬ci0 j0 ¬ci1 j1 ¬(vj0 r = i0 ) ¬(vj1 r = i1 ) ¬vir tii0 i1.

¬ci0 j0 ¬ci1 j1 ¬(vj0 r = i0 ) ¬(vj1 r = i1 ) vir ¬tii0 i1.

6. Для всех входных значений аргументов значения выходов совпа дают со значениями, заданными в таблице истинности. Это дает O(N2n m) 2-дизъюнктами. Дизъюнкты этого типа записываются для всех 0 k m 1, 0 r 2n 1, n i n + N 1 и выглядят следующим образом:

¬oik (vir = valuekr ), где valuekr это значение k-го выхода на наборе входных зна чений r в соответствии с таблицей истинности.

Для сокращения перебора также можно считать без потери общ ности, что верны следующие утверждения, которые кодируются до полнительными дизъюнктами при сведении.

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

2. Для каждого гейта номер его первого входа меньше номера вто рого.

3. Гейты не вычисляют вырожденные функции.

4. Хотя бы один из выходов находится в последнем гейте.

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

– 14 – Это связано с тем, что количество схем экспоненциально растет с ростом числа гейтов. Грубая оценка сверху на число схем, вычис ляющих предикаты от n аргументов и состоящих из N гейтов, дает их количество (10(n + N + 2)2 )N. Столько итераций потребуется на ивному перебору для доказательство того, что не существует схемы данного размера для конкретной функции. В случае же, если схема существует, перебор может работать быстрее, особенно если схем дан ного размера много. При использовании солверов такой эффект тоже наблюдается оптимальные схемы часто находятся гораздо быстрее, чем доказывается отсутствие схем меньшего размера.

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

Наиболее удачные ограничения приведены ниже.

1. Ограничение на исходящую степень гейтов.

2. Ограничение, описывающее существование ориентированного пути, проходящего через все гейты (для этого одним из входов i-го гейта должен быть (i 1)-ый гейт).

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

Предположим, что нужно найти блок для функции MODK. Та кой блок складывает несколько новых переменных с остатком по мо дулю K, который как-то закодирован. Остаток по модулю K может log2 K быть закодирован в битах. Поскольку кодировку неизвестна, то введем новые переменные eij, где eij истинно тогда и только то гда, когда битовое представление 0 j 2 log2 K кодирует остаток 0 i K 1. Таким образом, каждый остаток может кодироваться несколькими значениями j (такая возможность оказалось ключевой при поиске оптимального блока для функции MOD3 ).

Кроме очевидных дизъюнктов, описывающих то, что каждый остаток i кодируется хотя бы одной кодировкой j и что каждая коди ровка j используется ровно для одного остатка i, добавляется также следующее условие. Для всех возможных входных наборов перемен ных, всех возможных сумм битов s, которые данный блок добавля ет к закодированному остатку, и всех возможных значений закодиро ванных остатков i (то есть соответствующая переменная eij истинна), остаток на выходе должен быть равен i+s (фактически же в виде КНФ на самом деле записывается тот факт, что значения выходов схемы не равны j для всех j таких, что ei j истинно для некоторого i i + s (mod K)) В качестве примера предположим, что нужно найти блок, ко торый получает на вход остаток t по модулю 3, который некоторым образом закодирован в виде двух битов (z0, z1 ), и новую переменную – 16 – xn и выдает два бита (z0, z1 ), которые кодируют в той же самой ко дировке t + xn (mod 3). Тогда переменная e23 истинна тогда и только тогда, когда из того, что (z0, z1 ) = (1, 1) следует, что t = 2, а перемен ная e11 истинна тогда и только тогда, когда из того, что (z0, z1 ) = (0, 1) следует, что t = 1. Описанное условие тогда записывается в виде сле дующего выражения:

(e23 z0 z1 xn e11 ) (z0 ¬z1 ).

Такой автоматический поиск кодировки остатка оказался весь ма полезным, поскольку только с его использованием удалось найти эффективный блок, из которого следует верхняя оценка 5.5n + c для CU2 (MODn ). Однако понятно, что поиск блока с произвольной коди ровкой представляет из себя более трудную задачу в общем случае.

1.4 Верхние оценки для функции MOD В данном разделе описываются верхние оценки для функции MODn в базисах B2 и U2, полученные при помощи описанного выше све дения к задаче SAT с использованием SAT -солверов. Верхние оцен ки получаются путем построения схемы из блоков, изображенных на n рис. 1 и рис. 2. Каждый из блоков получает на вход значение i=1 xi (mod 3), закодированное парой битов (z1, z2 ) и несколько новых пере менных (три и две соответственно). Выходом блока является пара би n+3 n+ тов (z1, z2 ), кодирующая значения (mod 3) и i=1 xi i=1 xi (mod 3) соответственно. В блоках используются следующие кодировки остат ков:

0, (z0, z1 ) = (0, 0), n xi (mod 3) = 1, (z0, z1 ) = (0, 1, i= 2, z0 = 1, – 17 – n=3 n=4 n= k=0 3 k=1 4 k=2 4 Таблица 1: Размеры оптимальных схем в базисе B2 для MODn 3,k и 0, z0 = 0, k xi (mod 3) = 1, (z0, z1 ) = (1, 0), i= 2, (z0, z1 ) = (1, 1).

Верхние оценки CB2 (MODn ) 3n + O(1) и CU2 (MODn ) 5.5n + 3 O(1) следуют из существования блоков непосредственно.

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

В таблице 1 также приводятся размеры оптимальных схем в ба зисе B2 для MODn для различных значений n и k. CB2 (MOD5 ) 3,k 3, означает, что была найдена схема размера 10, но доказать невыпол нимость формулы, описывающей существование схемы (без ограниче ний) размера 9, не удалось. Сами оптимальные схемы приведены на рис. – 18 – xn+1 z1 z0 xn+2 xn+ g g g g g ¬ g g ¬ g g z0 z xn+1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 xn+2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 xn+3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 z z g g g g g g g g g z z Рис. 1: Индуктивный блок для функции MOD3 в базисе B2 и его таб лица истинности.

– 19 – xn+1 xn+2 z0 z ¬ g1 g2 g ¬ g ¬ ¬¬ g4 g ¬ ¬ g ¬ g8 ¬ g ¬ ¬ g9 g z1 z xn+1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 xn+2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 z z g g g g g g g g g g g z z Рис. 2: Индуктивный блок для функции MOD3 в базисе U2 и его таб лица истинности.

– 20 – x1 x2 x3 x1 x2 x3 x1 x3 x ¬ ¬ MOD3 MOD3 MOD 3,0 3,1 3, x1 x2 x3 x4 x1 x4 x2 x3 x1 x4 x2 x ¬ ¬ ¬ ¬ MOD4 MOD4 MOD 3,0 3,1 3, Рис. 3: Оптимальные схемы для функции MODn для n = 3, 3,k – 21 – 2 Разработка новых конструкций криптографиче ских примитивов, доказуемо надёжных в слабом смысле 2.1 Краткая аннотация В этой части проекта мы продолжали исследование вопроса о том, как построить конструкции, в которых можно доказать хоть какую-нибудь разницу между честным декодированием и взломом в модели схемной сложности. В 1992 году Ален Хильтген [38] сконструировал функцию, для которой сумел доказать некоторую разницу между сложностью её вычисления и обращения: функцию Хильтгена почти вдвое (в 2 o(1) раз) труднее обратить, чем вычислить. Его пример является линейной функцией над GF(2) с матрицей, у которой мало ненулевых элементов, в то время как в обратной к ней матрице ненулевых элементов много.

Сложность обращения при этом следует из простого наблюдения Ла маньи и Сэвиджа [51, 69]: каждый бит выхода нетривиально зависит от многих переменных, и эти биты все разные, следовательно, можно доказать нижнюю оценку на сложность вычисления их всех вместе взятых.

Эта работа была продолжена участниками проекта С. И. Нико ленко, Э. А. Гиршем и О. Меланич [40, 60, 87, 92, 95]. В [40, 87] была построена первая (линейная) конструкция функций с секретом, дока зуемо надёжных в слабом смысле, а в [92] было построено семейство нелинейных функций с секретом, чей порядок надёжности превышает порядок надёжности первой конструкции.

Настоящая работа посвящена схемной сложности линейных функций и новым конструкциям линейных функций с секретом, до казуемо надёжных в слабом смысле. В разделе 2.3 мы вводим основ ные определения. В разделе 2.4 приводится (неконструктивное) до – 22 – казательство того, что среди линейных функций существуют функ ции нелинейной схемной сложности, т.е. того, что линейные функции действительно представляют интерес с точки зрения нижних оценок схемной сложности. В разделе 2.5 подробно анализируется метод ис ключения гейтов (gate elimination) для случая схем, реализующих ли нейные функции, а в разделе 2.6 результаты раздела 2.5 применяются для получения новых конструкций линейных функций с секретом, доказуемо надёжных в слабом смысле, и уточнения их оценок надёж ности.

2.2 Введение В современной криптографии практически нет доказуемо надёжных конструкций с открытым ключом. Начиная с первого протокола со гласования ключа Диффи-Хеллмана [19] и первой криптосистемы с открытым ключом RSA [68], не была доказана надёжность ни од ного криптографического протокола с открытым ключом (разумеет ся, существуют надёжные протоколы с секретным ключом;

в част ности, современная криптография фактически началась с одного из таких протоколов – одноразовых блокнотов [72, 83]). Конечно, без условное доказательство надёжности было бы трудно получить, ведь P = NP. Но дела обстоят ещё из него неизбежно следовало бы, что хуже: нет и условных доказательств, которые могли бы установить связь между какими-либо естественными структурными предположе ниями (такими, как P=NP или BPP=NP) и криптографической на дёжностью. Недавно появившиеся разработки основанных на решёт ках криптосистем, связывающих криптографическую надёжность со сложностью в худшем случае, в действительности имеют дело с зада чами, NP-трудность которых не доказана и, более того, маловероят на [2, 20, 66, 67].

– 23 – Известны полные конструкции криптографических примитивов:

как односторонних функций [27, 32, 53, 60, 88, 89, 95], так и криптоси стем с открытым ключом [30, 36]. Однако они тоже не позволяют свя зать криптографическую надёжность с ключевыми предположениями традиционной структурной теории сложности. Кажется, что класси ческой современной криптографии ещё очень далеко до каких-либо доказуемо надёжных конструкций.

Более того, асимптотическая природа имеющихся утверждений о полноте не позволяет утверждать, что ту или иную криптографи ческую конструкцию трудно взломать для ключей какой-либо фик сированной длины. Однако именно ключи фиксированной длины ин тересуют конечных пользователей криптографических конструкций, ведь их протокол защищён ключом одной конкретной длины. Асимп тотические оценки сложности алгоритмов, как правило, действитель но имеют прямое отношение к их практической сложности, но доказа тельства асимптотической надёжности может оказаться недостаточно для практической надёжности: почему трудно взломать RSA для 2048 битных чисел? Может быть, кто-то сможет построить устройство не слишком большого размера, которое взламывает тот или иной прото кол для всех ключей одной и той же реально использующейся длины?

Никаких теоретических препятствий к этому формальные крипто графические определения не представляют: конкретные длины клю чей вообще не рассматриваются в принципиально асимптотической теории. Сложность задач, которые уже долгое время исследовались в криптографическом контексте (разложение на множители и дис кретный логарифм), действительно представляется равномерной по длинам ключей, но для этих задач никаких суперполиномиальных нижних оценок сложности не известно, и получение их в ближайшем будущем крайне маловероятно. Другие опасности асимптотического – 24 – подхода заключаются в неаккуратном использовании сведний в до е казательствах надёжности (см. [49] и комментарии к этой вызвавшей противоречивые отклики публикации).

В связи с этим представляется, что идеальной моделью вычисле ний для криптографических нужд является схемная сложность одна из немногих моделей вычислений, в которых возможны доказа тельства конкретных, а не асимптотических оценок сложности. На пример, Л. Стокмайер в своей диссертации привёл функцию, любая реализация которой при помощи бинарной булевской схемы на входах размера 616 должна иметь не менее 10123 гейтов [3, 79, 81].

Основные результаты в классической схемной сложности отно сятся к 1980-м гг. и раньше;

в них значительна заслуга отечественных учёных [7,62,80,81,90,91,93,94,96,98–100,102–104]. Однако очевидным недостатком такого подхода является то, что, несмотря на многолет ние исследования, в настоящее время мы очень плохо понимаем, как доказывать нижние оценки в этой модели вычислений. Наилучшие известные нижние оценки схемной сложности без дополнительных ограничений линейны от количества входов, да и константы там со всем небольшие: так, лучшая нижняя оценка для булевской функции Bn B составляет всего лишь 3no(n) [7,62,80,84]. В последние годы центр усилий в теории схемной сложности переместился на результа ты, связанные со схемами ограниченной глубины и/или ограниченным набором вычисляемых в них функций [1, 11, 25, 37, 41, 65, 78, 85, 86, 97], однако в криптографическом контексте мы вряд ли сможем убедить противника использовать, скажем, схемы только глубины 64 и не боль ше.

– 25 – 2.3 Определения и обозначения Прежде всего дадим точное определение схемы. Обозначим через Bn,m n множество всех 2m2 функций f : Bn Bm, где B = {0, 1} поле из двух элементов.

Определение 2.1. Пусть некоторое множество булевских функ ций f : Bm B (m может быть разным для разных f). Тогда схема это ациклический направленный граф с метками, состоящий из вершин двух типов:

 вершин входящей степени 0 (вершин, в которые не входят рёбра), маркированных одной из переменных x1,..., xn,  и вершин, маркированных одной из функций f, в которые входит столько рёбер, какова арность этой функции.

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

Каждый гейт -схемы вычисляет некоторую булевскую функ цию. Соответственно, схемная сложность функции f : Bn Bm в бази се определяется как размер минимальной -схемы, которая вычис ляет функцию f (в которой есть m гейтов, вычисляющих результат применения функции f ко входным битам). Чтобы можно было без оговорок устранить унарные гейты, будем считать, что в гейте вычис ляется как сам результат его функции, так и его отрицание. Наша мо дель вычислений это булевские схемы с произвольными бинарными гейтами;

иными словами, каждый гейт схемы маркируется одной из 16 булевских функций из B2,1. В дальнейшем через C(f) будет обозна чаться схемная сложность f в базисе B2,1, состоящем из всех бинарных булевских функций. Мы будем предполагать, что каждый гейт в этой схеме зависит от обоих входов, т.е. нет гейтов, маркированных кон 1В русскоязычной литературе встречается термин вентиль, и лет сорок назад он был обще употребителен, но мы, пожалуй, не рискнём его использовать.

– 26 – Id и ¬. Это не умаляет общности, стантами и унарными функциями потому что такие гейты легко исключить из нетривиальной схемы, не увеличивая её размер.

А. Хильтген ввёл для каждой обратимой функции n перемен ных f Bn,m понятие меры сложности в слабом смысле (measure of feeble one-wayness) C(f1 ) MF (f) = C(f) (напомним, что C(f) размер минимальной схемы с бинарными гей тами, реализующей f). Результаты Хильтгена заключались в том, что он нашёл последовательности функций {fn } с нетривиальными (т.е.

n= большими единицы) константами lim n MF(fn), inf которые Хильтген называет порядком необратимости (order of one wayness).

pi, ti, m, c : N N. Семей Определение 2.2. Зафиксируем функции ство кандидатов в функции с секретом представляет собой после довательность троек C = {(Seedn, Evaln, Invn )}, где:

n=  {Seedn } это семейство схем порождения ключей n= Seedn : Bn Bpi(n) Bti(n),  {Evaln } это семейство вычисляющих функцию схем n= Evaln : Bpi(n) Bm(n) Bc(n), а  {Invn } это семейство обращающих функцию схем n= Invn : Bti(n) Bc(n) Bm(n), причём для каждого n, каждого s Bn (начального числа генератора) и каждого m Bm(n) (сообщения) Invn(Seedn,2(s), Evaln(Seedn,1(s), m)) = m, – 27 – Seedn,1(s) Seedn,2(s) pi(n) бит ( публичная инфор где и первые мация, public information) и последние ti(n) бит ( секрет, trapdoor information) выхода схемы Seedn (s), соответственно.

Неформально говоря, здесь число n это параметр надёжности функции с секретом, длина начального числа генератора случайных чисел. Длину входа функции с секретом мы обозначили через m(n), длину её выхода, а через pi(n) и ti(n) через c(n) длину публичной информации и секрета соответственно. Мы называем такое семейство функций кандидатом, потому что в определении 2.2 ничего не гово рится о надёжности, а только вводятся обозначения для размерностей и устанавливается корректность обращения.

Чтобы понять, насколько функция надёжна, нужно ввести по нятие взлома функции. Неформально говоря, противник должен об ратить функцию, не зная секрета. Мы вводим успешный взлом как обращение с вероятностью более некоторой константы ( обычно равно 1, или 7 ). Через C (f) будем обозначать минимальный размер 2 4 схемы, которая вычисляет функцию f Bn,m на более чем доле её входов (длины n). Очевидно, C (f) C (f) для всех функций f и всех, и C(f) = C1 (f).

Определение 2.3. Схема N успешно обращает семейство кандида тов в функции с секретом {Seedn, Evaln, Invn } на входах длины n, если для равномерного распределения U, взятого по s Bn и m Bm(n) (по начальным числам генератора и входам), Pr [N(Seedn,1(s), Evaln(Seedn,1(s), m)) = m] 1.

(s,m)U Определение 2.4. Будем говорить, что семейство кандидатов в функ ции с секретом C = {(Seedn, Evaln, Invn )} имеет порядок надёжно n= сти k R, если для каждой такой последовательности схем {Nn }, n= – 28 – в которой Nn успешно обращает C на входах длины n, lim n min inf C(Nn ) C(Nn ) C(Nn ) k.

,, C(Seedn ) C(Evaln ) C(Invn ) Иначе говоря, C1/2 (fpi(n)+c(n) ) C1/2 (fpi(n)+c(n) ) C1/2 (fpi(n)+c(n) ) lim n min inf k,,, C(Seedn ) C(Evaln ) C(Invn ) где функция fpi(n)+c(n) Bpi(n)+c(n),m(n) отображает (Seedn,1 (s), Evaln (Seedn,1 (s), m)) m.

Приведём несколько простых примеров. Если секретного клю ча нет вовсе (pi(n) = 0), то каждое семейство кандидатов в функ ции с секретом {(Seedn, Evaln, Invn )} имеет порядок надёжности 1, n= т.к. последовательность схем {Invn } успешно его обращает. Если n= {(Seedn, Evaln, Invn )} реализуют функцию с секретом в обычном n= криптографическом, не в слабом смысле, то k =. Более того, k = даже если оценки на размер схем противника просто более чем линей но превышают оценки на размер схем честных участников протоко ла, например, если противнику требуется O(n log n) гейтов, а честное участие линейно. К сожалению, даже таких оценок на размер схем из произвольных бинарных гейтов, реализующих конкретные булевские функции, пока не известно.

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

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

– 29 – 2.4 Неконструктивные оценки схемной сложности линейных функций Классический результат показывает подсчётом, что среди булевских 1n функций n переменных почти все имеют схемную сложность n2.

Но, возможно, для линейных функций не бывает нелинейных оценок?

Мы доказали, что бывает. Ссылки на этот результат можно найти [4,9], но нам не удалось найти доказательство в доступной литературе, поэтому оно было включено в работу [16].

Теорема 2.1. 1. Для каждого n существует такая константа n, что схемная сложность всех линейных функций : {0, 1}n {0, 1}n не превышает n log n, и limn n = 1.

n 2. Для каждого n 3 существует линейная булевская функция : {0, 1}n {0, 1}n со схемной сложностью более 2 log n.

n 2.5 Метод исключения гейтов для линейных функций Для доказательства нижних оценок мы используем метод исключе ния гейтов, который до сих пор был использован во всех доказатель ствах нижних оценок в классической теории схемной сложности [84].

Основная идея этого метода индуктивное рассуждение следу ющего вида. Рассмотрим функцию f и подставим некоторое значение c в некоторую переменную x, получив таким образом схему, вычисля ющую функцию f|x=c. Эту схему можно упростить, потому что гейты, в которые входила эта переменная, теперь либо стали унарными (а отрицание можно удалить из схемы, перенеся его роль на следующие гейты), либо и вовсе превратились в константы (и тогда можно будет удалять и их потомков). Важный случай здесь тот, когда гейт нелине ен, например гейт, вычисляющий конъюнкцию AND или дизъюнкцию OR. В этом случае всегда возможно выбрать такое значение для вхо – 30 – да, что гейт станет константным. Этот процесс можно продолжать ин дуктивно, пока можно выбирать подходящую переменную, входящую в достаточное количество гейтов. Очевидно, количество исключённых в течение этого процесса гейтов представляет собой нижнюю оценку на схемную сложность f.

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

Идея 1. Предположим, что в течение n шагов элиминации остаётся по крайней мере один гейт. Тогда C(f) n.

Теорема 2.2. Зафиксируем число [0, 1]. Пусть P = {Pn } – по n= следовательность предикатов, определённых на матрицах над F2 со следующими свойствами:

 если P1 (A) выполняется, то C (A) 1;

 если Pn (A) выполняется, то Pm (A) выполняется для каждого m n;

 если Pn (A) выполняется, то для каждого i Pn1 (Ai ) выполняет ся.

Тогда для каждой матрицы A с n + 1 столбцами, если Pn (A) выпол няется, то C (A) n.

Следствие 2.1. Если A – матрица ранга n, и в каждом столбце A есть 2 единиц, то C(A) n 2.

Эта тривиальная теорема до недавнего времени была единствен ным инструментов для исключения гейтов в линейных функциях;

на самом деле использовалось даже более простое утверждение, впервые появившееся в середине 1970-х.

Предложение 2.1 ( [51, 69];

[38, Theorems 3 and 4];

[40, Proposition 1] ).

– 31 – 1. Предположим, что функция f : Bn B нетривиально зависит от каждой из n своих переменных, то есть для любого i, 1 i n, найдутся такие значения a1,..., ai1, ai+1,..., an B, что f(a1,..., ai1, 0, ai+1,..., an ) = f(a1,..., ai1, 1, ai+1,..., an ).

Тогда C(f) n 1.

2. Пусть f = (f(1),..., f(m) ) : Bn Bm, где f(k) это k-я компонента функции f. Если все m функций–компонент f(i) попарно различ ны, и для каждой из них C(f(i) ) c 1, то C(f) c + m 1.

Идея 2. Предположим, что в течение n шагов в схеме су ществует вход с двумя исходящими рёбрами и, более того в m из этих случаев оба ребра ведут в гейт (а не в гейт и выход).

Тогда C(f) n + m.

Теорема 2.3. Назовём ненулевой элемент матрицы уникальным, ес ли это единственный ненулевой элемент в своей строке. Зафиксируем число [0, 1]. Пусть P = {Pn } – последовательность предикатов, n= определённых на матрицах над F2 со следующими свойствами:

 если P1 (A) выполняется, то C(A) 1;

 если Pn (A) выполняется, то Pm (A) выполняется для каждого m n;

 если Pn (A) выполняется, то для каждого i, если в i-м столбце нет уникальных элементов, то выполняется Pn2 (Ai ), иначе вы полняется Pn1 (Ai ).

Тогда для каждой матрицы A с n + 1 различными столбцами, ес ли Pn (A) выполняется для некоторого n, то C(A) n и, более того, C3 (A) n.

Следствие 2.2. Зафиксируем число [0, 1]. Предположим, что R = {Rn } и Q = {Qm } – две последовательности предикатов, n=1 m= определённых на матрицах над F2, со следующими свойствами:

 если R1 (A) выполняется, то C(A) 1;

– 32 –  если Rn (A) выполняется, то Rk (A) holds for every 1 k n;

 если Rn (A) выполняется, то для каждого i выполняется Rn1 (Ai );

 если Q1 (A) выполняется, то C(A) 1;

 если Qm (A) выполняется, то Qk (A) holds for every 1 k n;

 если Qm (A) выполняется, то для каждого i выполняется Qm1 (Ai );

 если Qm (A) выполняется и Ai содержит больше нулевых строк, чем A (т.е. удаление i-го столбца удаляет последний ненулевой элемент в какой-то строке), то выполняется Qm (Ai ).

Тогда для каждой матрицы A с n+1 столбцами, все столбцы которой различны, если Rn (A) и Qm (A) выполняются для некоторого n m, то C(A) n + m и, более того, C3 (A) n + m.

Следствие 2.3 ( [40, Lemma 5] ). Пусть t, u 1. Предположим, что – линейная функция с матрицей A над F2, причём:

1. все столбцы A различны;

2. в каждой строке A по крайней мере u ненулевых элементов;

3. после удаления любых t столбцов A в матрице всё ещё останется по крайней мере одна строка с по крайней мере двумя ненулевы ми элементами.

Тогда C() u + t и, более того, C3/4 () u + t.

Следствие 2.4. Пусть t u 2. Предположим, что A – матрица размера ut с различными столбцами, и каждый столбец A содержит по крайней мере два ненулевых элемента (две единицы). Тогда C(A) 2t u и, более того, C3 (A) 2t u.

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

см. [84]. Од нако для линейных функций и для исключения гейтов при помощи – 33 – Теорем 2.2 и 2.3 это становится верным. Следующая теорема обобщает Лемму 6 работы [40].

Теорема 2.4. Предположим, что линейная функция задаётся блочно-диагональной матрицей A1 0 ··· 0 A2 ···,...

...

...

0 ··· Ak каждый блок Aj удовлетворяет условиям Теоремы 2.3 с предикатом k Pj = {Pn }, и Pnj (Aj ) выполняются для каждого j. Тогда C() j j nj.

n= j= 2.6 Функции с секретом, доказуемо надёжные в слабом смысле В наших конструкциях мы следуем общей идее [40]: сначала мы стро им кандидата в функции с секретом, доказуемо надёжные в слабом смысле, в котором противник должен затратить больше гейтов чем нужно для обращения функции, но вычисление функции оказывает ся ещё сложнее. Затем мы добавляем отдельным блоком доказуемо надёжную в слабом смысле одностороннюю функцию и тем самым восстанавливаем баланс, сокращая работу, требующуюся для вычис ления функции, относительно её обращения (с секретом или без). Эта идея была подробно исследована в [40].

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

1 1 ··· 1 1 1 0 ··· 0 1 ··· 1 0 1 1 ··· U Un =, = ;

.......

.......

n.......

0 0 ··· 1 0 0 0 ··· заметим, что U2 – верхнетреугольная матрица, в которой нули и еди n ницы заполняют верхний треугольник в шахматном порядке. В даль нейшем мы часто используем матрицы, состоящие из других матриц – это матрица порядка n 2n, состоя как блоков;

например, ( Un Un ) щая из двух верхнетреугольных блоков.

– 34 – Лемма 2.1. 1. C3 (Un ) = n 1.

C3 (U2 ) = n 2.

2. n C3 (U1 ) = n 1.

3. n 4. C3 (( Un Un )) = 2n 1.

5. 3n 6 C3 (( U2 C(( U2 3n 3.

Un )) Un )) n n 6. 3n 4 C3 (( Un C(( Un 3n 2.

U1 )) U1 )) n n Для первой конструкции мы предполагаем, что длины публич ного ключа pi, секретного ключа ti, сообщения m и кода c одинаковы m и равны n. Положим ti = Un · pi, c = ( U1 · ( pi ). В этом случае Un ) n c c Un ) · ( ti ) U2 ) · ( pi ).

противнику придётся вычислить матрицу ( Un = ( Un n Теперь обращение без секрета сложнее, чем обращение с секретом, но вычисление прямой функции имеет примерно ту же сложность, что и обращение без секрета, поэтому это пока нельзя назвать функцией с секретом.

Чтобы решить эту проблему, рассмотрим линейную функцию с матрицей A, представляющую собой одностороннюю функцию, дока зуемо надёжную в слабом смысле, и построим протокол следующим образом (здесь In – единичная матрица):

Seedn Un 0 ti 0 In · ( = s s) =, pi Evaln m U1 Un 0 = ( c1 ), · = pi n c 0 0A m Invn c Un Un = ( m1 ).

· = ti m 0 0 A1 c Задача противника теперь состоит в том, чтобы вычислить Advn = c Un U2 = ( m1 ).

· n pi m 0 0 A1 c Чтобы получить функцию A, мы фиксируем маленькое число 0 и рассматриваем линейную функцию Хильтгена с порядком надёжности 2 [38];

положим её размер равным n, где выбирается ниже. В конструкциях Хильтгена это означает, что C3 (A) = n + o(n), и C3 (A ) = (2 )n + o(n). Лемма 2.1 и Теорема 2.4 дают нам – 35 – следующие оценки сложности:

C3 (Seedn ) = n 1, C3 (Evaln ) = 3n + n + o(n) = (3 + )n + o(n), C3 (Invn ) = 2n + (2 )n + o(n) = (2 + (2 ))n + o(n), C3 (Advn ) = 3n + (2 )n + o(n) = (3 + (2 ))n + o(n).

Порядок надёжности этой конструкции равен C3/4 (Advn ) C3/4 (Advn ) C3/4 (Advn ) lim min,, = C(Evaln ) C(Invn ) C(Seedn ) n = min 3 + (2 ) 3 + (2 ),.

3+ 2 + (2 ) Это выражение достигает максимума для =, и максимум ра 0. Таким образом, мы доказали 54 вен, что стремится к при 4 следующую теорему.

Теорема 2.5. Для каждого 0 существует линейная функция с секретом, доказуемо надёжная в слабом смысле, с длиной ключа pi(n) = ti(n) = n, длиной входа и выхода c(n) = m(n) = 2n и поряд ком надёжности.

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

порядок на дёжности построенного семейства превосходит известный ранее [40].

Конечно, в настоящее время криптографические конструкции, дока зуемо надёжные в слабом смысле, вряд ли могут найти какое-либо – 36 – практическое применение, однако они представляются важными с тео ретической точки зрения. К сожалению, результаты этой статьи и ра бот [40, 92] – это передний край математически доказуемых резуль татов о криптографической надёжности;

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

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

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

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

легко доказать неконструктивные нижние оценки, сравнив число схем и функций, но конструктивные оценки получить не удаётся: лучшая известная нижняя оценка – это оценка 3no(n), доказанная в 1984 г. [7]. Ни один из известных методов не позволяет надеяться на нелинейные нижние оценки схемной слож ности, и для таких оценок потребуется серьёзный прорыв, разработ ка принципиально новых методов. Важность такого прорыва трудно переоценить;

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

– 38 – 3 Доказательство новых оценок на схемную слож ность булевских функций 3.1 Краткая аннотация Почти все известные нижние оценки на размер схем доказаны мето дом элиминации гейтов. Основная идея данного метода заключается в следующем. Рассматривается функция от n переменных из некоторого класса функций и показывается, что для любой схемы, вычисляющи ей данную функцию, присваивание значений некоторым переменным приводит к подфункции из того же подкласса и удаляет несколько гейтов из схемы. По индукции заключается, что исходная схема имеет большой размера. Несмотря на то, что это практический единствен ный метод для доказательства нижних оценко, как отмечают мно гие авторы, очень вряд ли этот метод позволит получить нелинейные нижние оценки.


Мы доказываем нижнюю оценку 3n O(d) на схемную слож ность функции f : Fn F2, которая не обращается в константу ни на каком аффинном подпространстве Fn размерности хотя бы d. Такие функции называются аффинными дисперсерами размерности d. Дока зательство нижней оценки гораздо проще доказательства наилучшей известной оценки 3n o(n), представленной Блюмом в 1984 году [7].

Однако не так просто построить афинный дисперсер для малых d.

Только недавно Бен-Сассон и Коппарти [5] привели явную конструк цию для сублинейного d = o(n) (а именно для d = (n4/5 )).

3.2 Нижняя оценка 3n o(n) для афинных дисперсеров Пусть µ(C) = s(C) + N(C), где s(C) размер (количество гейтов) схе мы C, а N(C) количество входных переменных схемы C, исходящая – 39 – степень которых превосходит 1.

Лемма 3.2. Пусть P есть гейт схемы C, имеющий тип и зависящий только от гейтов типа исходящей степени 1 и переменных. Тогда найдётся переменная xj и (возможно, пустое) подмножество перемен ных I {1,..., n} \ {j}, такое что для любой константы c F2, подста iI xi c новка xj = делает гейт P константой и уменьшает N(C) хотя бы на 1.

Доказательство. Легко видеть, что P вычисляет функцию типа xj c0 для некоторых 1 j n, I {1,... n} \ {j}, c0 F2.

iI xi Рассмотрим, как меняется C после подстановки xj = c, где iI xi c F2. Пусть S есть множество гейтов, от которых зависит P. Ясно, что S содержит хотя бы |I|1 гейтов. Чтобы упростить C после подста iI xi c, новки xj = мы удаляем гейт P (так как он теперь вычисляет константу c c0 ) и всех его потомков (так как они теперь вычисляют вырожденные функции).

iI xi c.

Чтобы уменьшить N(C) на 1, нам нужно заменить xj на Для этого мы удаляем все гейты из S (они были нужны лишь для вычисления P) и добавляем |I| 1 гейтов, вчисляющих iI xi. Теперь мы можем использовать их вместо xj. Ясно, что полученная схема выдает то же самое, что исходная, для всех входов x Fn таких что c.

xj = iI xi Пример такого упрощения приведён на рис. 4 (I = {2, 3, 4, 5}, j = 1).

Теорема 3.6. Пусть f : Fn F2 афинный дисперсер размерности афинное подпространство Fn рзамерности D, C схема с n d, A входами, такая что x A, C(x) = f(x). Тогда µ(C) 4(D d).

– 40 – x1 x2 x1 x2 x x4 x Q R x3 x 5 x x1 = i=2 xi P Q R Рис. 4: Пример линейной подстановки.

Доказательство. Доказательство проводится индукцией по D. Ба зовый случай D d очеивден. Пусть теперь D d + 1. Рассмотрим схему C, вычисляющую f на A с минимальным возможным µ(C). До пустим НУО, что C не содержит вырожденных гейтов (все такие гейты можно удалить их схемы без увелчиения µ(C)). Отметим также, что C не может выислять линейную функцию. Действительно, если бы C вы iI xi c, числяла функцию типа то f была бы константой на подпро странстве A = {x A : = c} размерности хотя бы D 1 d. та iI xi ким образом, C содержит хотя бы один гейт типа. Ниже мы находим iI xi c, для которой C упрощается к C, такой что подстановку типа µ(C) µ(C ) + 4 и C(x) = C (x) для всех x A = {x A : iI xi = c}.

Так как A имеет размерность хотя бы D 1, wмы заключаем по ин дукции, что µ(C) 4(D 1 d) + 4 = 4(D d). Отметим, что любой гейт, который становится константой при такой подстановке, не может быть выходным гейтом, поскольку иначе C вычисляла бы линейную функцию.

Рассмотрим топологическую сортировку гейтов C и пусть P есть первый гейт относительно этой сортировки, не явлюящийся гейтом типа исходящей степени 1. Поскольку он зависит лишь от гейтов типа и входных переменных, функции на входах P имеют форму xi c1 и xi c2. Ниже мы рассматриваем пять случаев.

iI1 iI – 41 – xj xj xj xi xi xi Q P P P P P Q Case 1 Case 2.1Case 2.2.1 ase 2.2.2Case 2. C Рис. 5: Все случаи доказательства Рис. 5 показывает все эти случаи.

 Случай 1. P есть гейт типа исходящей степени хотя бы 2. Тогда iI xi c.

P вычисляет функцию типа По лемме выше, найдётся линейная подстановка, при которой P становится константой и µ уменьшится хотя бы на 4.

 Случай 2. P есть гейт типа.

– Случай 2.1. Один из входов P есть гейт Q. Тогда Q есть гейт типа. Делая Q константой (как в лемме), которая тривиализирует P, мы удаляем P, Q и всех потомков P. Так же, N(C) уменьшается хотя бы на 1, поэтому µ уменьшается хотя бы на 4.

– Случай 2.2. Входами гейта P являются переменные xi и xj, и хотя бы одна из них (скажем, xi ) имеет исходяющую степень хотя бы 2. Присвоив xi значение, тривиализирующее P, мы убиваем всех потомков xi и всех потомков P. Ясно, что N(C) уменьшается хотя бы 1. Рассмотрев два подслучая, мы покажем, что s(C) уменьшается хотя бы на 3.

Случай 2.2.1. xi имеет потомка, который не является потомком P. Тогда удаляется этот потомок и все потом ки P.

– 42 – Случай 2.2.2. Единственный потомок P есть гейт Q и он также является потомком xi. Тогда он становится кон стантной (поскольку оба его входа константы) и все его потомки также удаляются.

– Случай 2.3. Оба входа P являются переменными исходящей степени 1. Присвиваивая xi константу, тривиализирующую P, мы удаляем P и всех его потомков и тем самым N(C) уменьшается хотя бы на 2. Тогда µ уменьшается хотя бы на 4.

Следствие 3.5. Любая схема над базисом B2, вычисляющая афинный дисперсер размерности d, имеет хотя бы 3n 4d гейтов.

Доказательство. Действительно, по теореме 3.6, для любой схемы C, вычисляющей афинный дисперсер размерности d, s(C) = µ(C) N(C) 4(n d) N(C) 3n 4d.

Таким образом, афинный дисперсер сублинейной размерности имеет схемную сложность хотя бы 3n o(n). Легко видеть также, что точно тем же методом можно доказать нижнюю оценку n o(n) на мультипликативную сложность таких функций. Для этого можно сделать n o(n) линейных подстановок, каждый раз убивая первый гейт типа.

– 43 – 4 Исследование структурных свойств в семантиче ских классах сложности в среднем случае 4.1 Краткая аннотация Основной задачей теории сложности вычислений является определе ние ресурсов (времени и памяти), которые необходимы и достаточны для решения той или иной вычислительной задачи. При структурном подходе к теории сложности вычислений задачи объединяются в клас сы задач, решаемых теми или иными моделями вычислений с учетом определенного числа ресурсов. Важнейшими вопросами в структур ной теории сложности являются вопросы о совпадении или различии тех или иных классов сложности. На сегодняшний день большинство интересных вопросов остаются открытыми.

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

P NP.

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

Каждый класс сложности задается моделью вычислений и огра P задается полиномиальными ничением ресурсов. К примеру, класс алгоритмами, класс NP задается по времени детерминированными полиномиальными по времени недетерминированными алгоритмами, – 44 – BPP задается полиномиальными вероятностными алгоритмам класс с ограниченной вероятностью ошибки на каждом входе и т.д. Внутри каждого класса сложности можно выстроить иерархию классов, если ограничивать ресурсы более тонким образом. Например, вместо того, чтобы ограничивать время работы алгоритмов произвольным полино мом, можно было бы ограничивать временем работы nc, где n это длина входа. Вопрос в том, будет ли такая иерархия строгой? Сов падают ли такие классы для разных c? Говорят, что для модели вы числений выполняется теорема об иерархии по времени, если можно доказать, что за большее время вычислительная модель может решить большее число задач.

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

Существование полных задач в классах сложности, справедли вость теоремы об иерархии по времени для моделей вычислений и су ществование оптимальных алгоритмов для тех или иных задач это тесно связанные проблемы, поскольку они основываются на возмож ности перечисления алгоритмов, которые удовлетворяют определен ным свойствам. Если свойство алгоритма является синтаксическим, т.е. его можно эффективно проверить по записи алгоритма, то про блем с построением полной задачи, доказательством иерархии по вре мени и построению оптимальных алгоритмов нет. К примеру, свойство алгоритма быть недетерминированным является синтаксическим, это – 45 – NP и теоремы об иерар и объясняет наличие полной задачи в классе хии по времени для недетерминированных вычислений. Свойство ал горитм либо не останавливается, либо находит выполняющий набор для формулы тоже является синтаксическим, поскольку алгоритм можно дополнить процедурой проверки выполняющего набора, кото рая не закончит работу, если набор не подходит.


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

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

Есть два основных подхода к преодолению таких препятствий.

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

BPP/1 [22], ZPP/1, MA/1 и др. [82]. Однако, понятие подсказки, ис пользуемое в этих результатах, нестандартное, поскольку машины мо гут нарушать условие ограниченности ошибки, если подсказка непра вильная. В случае классического определения подсказки существова ние иерархии по времени остается открытым вопросом, так как оно эквивалентно иерархии по времени без подсказки [23].

Другой подход состоит в переходе к анализу поведения алгорит мов в среднем случае вместо наихудшего случая. Основными моделя ми вычислений являются полиномиальные по времени эвристические – 46 – алгоритмы, которые выдают правильный ответ на почти всех входах и работают за полиномиальное в среднем случае время. Иерархия по Heur BPP (с равномерным распределением) была времени в классе nc доказана в [22], доказательство было существенно упрощено в [63]. Од нако, в этих результатах алгоритмы не только могут давать неверный ответ, но и нарушают условие ограниченности ошибки на малой доле входов. Возможность выдавать неверный ответ помогает и в постро ении полных объектов, например, существует полная криптосистема с открытым ключом, если декодирующий алгоритм может ошибать ся с маленькой вероятностью [36] (см. также [30]). В работе [44] была AvgBPP с полиномиально модели построена полная задача в классе руемыми распределениями на входах. В той же работе была доказана теорема об иерархии по среднему времени работы для вероятностных вычислений с ограниченной ошибкой.

В этой части проекта мы применили последний подход к задаче построения оптимальных алгоритмов. Мы вводим понятие распреде ленной задачи доказательств это пара (L, D), состоящая из перечис лимого языка L и полиномиально моделируемого распределения D, сосредоточенного на дополнении языка. Мы вводим определение по нятия вероятностного эвристического аксептора такого алгоритма, который останавливается на входах из языка L и лишь на маленькой D-доли дополнения языка. Для каждой распределенной задачи до казательств мы строим оптимальный вероятностный эвристический аксептор.

Этот общий результат мы усиливаем в важном частном случае:

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

– 47 – В отличии от предыдущего случая тут оптимальность достигается в том числе и на дополнении языка. Вторым результатом в этом част ном случае стала дерандомизация оптимального алгоритма: существу ет оптимальный эвристический алгоритм среди детерминированных эвристических алгоритмов. Правда оптимальность в этом случае яв ляется не поточечной, а в среднем случае.

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

Определение 4.5. Будем называть пару (D, L) распределенной зада чей доказательства, если L это некоторый язык (подмножество {0, 1} ), а D это последовательность распределений Dn сконцентриро ванных на L {0, 1}n. Будем предполагать также, что D можно генери ровать за полиномиальное время, т.е. существует такая вероятностная машина Тьюринга (генератор), которая на вход получает 1n и за по линомиальное от n количество шагов выдает x с вероятностью Dn (x) для каждого x {0, 1}n.

В дальнейшем будем обозначать PrxDn вероятность относитель но такого распределения, в то время как PrA будет обозначать вероят ность относительно внутренних случайных битов алгоритма A (иногда A будет опускаться).

Определение 4.6. Эвристический аксептор для распределенной задачи доказательства (D, L) это вероятностный алгоритма A с дву мя входными параметрами x {0, 1} и d N, которые удовлетворяет следующим свойствам.

– 48 – 1. Алгоритм A либо принимает вход, т.е. выдает 1 (обозначается A(...) = 1), либо не останавливается.

2. Для всех x L и d N, A(x, d) = 1.

3. Для всех n, d N, Pr Pr{A(r, d) = 1} 1.

8 d rD An Понятие нормализованного эвристического аксептора определено аналогично, за исключением того, что условие (3) заменено 3. Для всех n, d N, Pr {A(r, d) = 1} d.

rDn A Замечание 4.1. Нормализованный эвристический аксептор не обяза тельно является эвристическим аксептором для того же входа. Од нако, как мы покажем далее, он является эвристическим аксептором для другого значения d.

Замечание 4.2. Полуразрешающая процедура для любого рекурсивно-перечислимого языка L это эвристический аксеп тор для любого D.

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

Определение 4.7. Медианное время алгоритма A на входе z это tA (z) = min{t | Pr{A(z) останавливается за не более чем t шагов} }.

A Будем также использовать обозначение “время вероятности p”:

tA (z) = min{t | Pr{A(z) останавливается за не более чем t шагов} p}.

(p) A Определение 4.8. Функция f : {0, 1} N N полиномально огра ничена на L, если существует полином p, такой что для всех x L и d N, f(x, d) p(|x|d).

– 49 – Определение 4.9. Функция f : {0, 1} N N доминирует функцию g : {0, 1} N N на языка L (обозначается f g), если существуют полиномы p и q, такие что для всех x L и d N, max {p(f(x, d )d|x|)}.

g(x, d) d q(|x|d) Замечание 4.3.

1. Если f g на L и f полиномально ограничена на L, то g тоже полиномально ограничена на L.

2. Отношение транзитивно.

Определение 4.10. Эвристический аксептор A для распределенной задачи доказательства (D, L) полиномиально ограничен, если tA (x, d) полиномиально ограничено на L.

Определение 4.11. Для эвристических аксепторов A и A для одного языка L будем говорить, что эвристический аксептор A моделирует A, если tA tA на L. Эвристический аксептор A сильно моделирует (3/4) A, если tA на L.

tA Определение 4.12. Эвристический аксептор для (L, D) называется оптимальным, если он моделирует все эвристические аксепторы для (L, D).

Предложение 4.2 (Оценки Чернова [56]). Для независимых случай ных величин Xi {0, 1}, для которых EXi = µ, где 1 i N, для всех 0 выполняется:

N Pr i=1 Xi 2e2 N µ.

N Предложение 4.3. Для каждого эвристического аксептора A для за дачи (D, L), существует нормализованный эвристический аксептор B, который строго моделирует A.

Доказательство. Новый алгоритм B(x, d) запускает параллельно копий A(x, 2d) (где будет определено позже) и принимает вход как – 50 – только копий алгоритма A остановятся. Такое количество копий должно остановиться за время не более tA (x, 2d) с вероятностью не менее 1 2e 128 (по оценкам Чернова). Таким образом, для всех x L (x, d) poly(, tA (x, 2d)).

(3/4) и достаточно больших время tB supp Dn. Разделим supp Dn на два подмножества Пусть x S1 = {x supp Dn | PrA {A(x, 2d) = 1} 8 } и S2 = supp Dn \S1. Так как A Для x S1 оцен является эвристическим аксептором, то Dn (S2 ) 2d.

ки Чернова дают экспоненциально малую вероятность 2e 128 того, что Тогда PrxDn ;

B {B(x, d) = 9 B примет x. Выберем таким, что 2e 128 4d.

PrxD ;

B{B(x, d) = 1 | x S1}Dn(S1) + PrxD {B(x, d) = 1 | x 1} = n n S2 }Dn (S2 ) PrxD ;

B {B(x, d) = 1 | x S1 } + Dn (S2 ) 4d + 2d d.

1 1 n PrxD ;

A{A(x, d) = 1} d выполняется для Предложение 4.4. Если n всех d, тогда для всех 0, PrxD {PrA {A(x, d) = 1} } d.

1 n PrxD ;

A{A(x, d) = 1} PrxD ;

A{A(x, d) = Доказательство. d n n PrA{A(x, d) } · PrxD {PrA {A(x, d) = 1} } 1| 1 = 1} n PrxD {PrA {A(x, d) = 1} }.

1 n Следствие 4.6. Если A является нормализованным эвристическим аксептором, тогда B(x, d) = A(x, 8d) эвристический аксептор, моде лирующий A.

Из предложений 4.3 и 4.4 следует, что каждый эвристический аксептор моделируется нормализованным эвристическим аксептором и наоборот.

Теперь построим оптимальный эвристический аксептор, т.е. та кой, который моделирует каждый эвристический аксептор. По пред ложениям 4.3 и 4.4 достаточно построить оптимальный нормализован ный эвристический аксептор. В пределах этой главы L будет обозна чать рекурсивно-перечислимый язык.

– 51 – Алгоритм, который мы построим, запускает параллельно все эв ристические аксепторы и останавливается, когда первый из аксепто ров остановится (аналогично алгоритму Левина для SAT [52]). Основ ным препятствием для реализации этого простого плана является тот факт, что совершенно непонятно, как эффективно перебрать все эври стические аксепторы. Другими словами, непонятно как по данному ал горитму определить является ли он эвристическим аксептором. Наш план преодоления этого препятствия аналогичен конструкции полной криптосистемы с открытым ключом [36] (см. также [31]). План заклю чается в следующем:

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

 предложить процедуру “сертификации” которая отличает очень хороший эвристический аксептор от некорректного с подавляю щей вероятностью;

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

Сертификационная процедура устроена следующим образом.

Алгоритм 4.1 (Алгоритм Certify(A, d, n, T,, )).

 Повторить раз:

– Выбрать x Dn.

– Запустить A(x, d ) на не более чем T шагов.

 Вернуть 1, если не более вычислений из оказались принима ющими.

Предложение 4.5. Пусть AT будет обозначать алгоритм, который ведет себя как алгоритм A, если A останавливается за первые T шагов;

– 52 – в противном случае, если A не останавливается, AT выдает. Тогда PrxD ;

A{AT (x, d )  если 2, то = 1} n Pr{Certify(A, d, n, T,, ) = 1} 1 2e /2;

PrxD ;

A{AT (x, d )  если то = 1} 2, n Pr{Certify{A, d, n, T,, ) = 1} 2e2. Доказательство. Следует из оценок Чернова.

Теперь построим оптимальный нормализованный эвристический аксептор U.

Алгоритм 4.2 (Алгоритм U(x, d)).

1. Запустить параллельно A1 (x, 4dn), A2 (x, 4dn),..., A (x, 4dn), и n полуразрешающую процедуру для L на входе x, где n = |x| и Ai алгоритм с Геделевым номером i.

2. Если принимает вход за шагов, то запустить Ai Ti Certify(Ai, 4dn, Ti, 2n3 d3, 2dn ). Принять, если Certify при няла A, в противном случае завершить этот параллельный процесс не затрагивая другие процессы.

3. Принять, если полуразрешающая процедура приняла вход x.

Если один из параллельных процессов принял вход, завершить все остальные процессы.

Лемма 4.3. U(x, d) является нормализованным эвристическим аксеп тором.

Доказательство. По построению U либо принимает вход, либо не останавливается. Для каждого x L алгоритм гарантированно оста навливается благодаря полуразрешающей процедуре для L.

max{T | PrxD ;

A {AT (x, 4dn) dn }.

= 1} Пусть i обозначает i n i Пусть Xi (x) будет случайной переменной равной количеству шагов, которые Ai (x, 4dn) сделает перед тем, как принять вход x. Если – 53 – Ai (x, 4dn) не принимает вход x, то Xi (x) =. Пусть Ci (T ) обозначает событие Certify(Ai, 4dn, T, 2n3 d3, 2dn ) = 1.

Для каждого i мы оцениваем вероятность того, что U принимает supp D благодаря алгоритму Ai:

входы из Pr Pr {T N : Xi (x) = T Ci (T )} = {Xi (x) = T Ci (T )} xDn xDn Ai Ai T = Certify Certify i Pr {Xi(x) = T } Certify{Ci(T )} + Pr Pr {Xi(x) = T } Certify{Ci(T )}.

Pr = xDn xDn Ai Ti Ai T = (4.1) Мы можем оценить первую сумму в (4.1) по определению i :

i i Pr {Xi(x) = T } Certify{Ci(T )} Pr Pr {Xi(x) = T } xDn xDn Ai Ai T =1 T = Pr {1 Xi(x) i} nd.

= xDn Ai Мы можем оценить вторую сумму в (4.1) используя предложе ние 4.5:

Pr {Xi(x) = T } Certify{Ci(T )} Pr {Xi(x) i} Certify{Ci(i + 1)} Pr Pr xDn xDn Ti Ai Ai Pr {Ci(i + 1)} Prop. 4. 2edn.

dn Certify Таким образом, (4.1) меньше, чем dn. D-мера множества входов, на которых U ошибочно выдает n/ Pr {U(x, d) = 1} Pr n2 {T N : Xi (x) = T Ci (T )} · =.

2 dn d xDn xDn Ai U i= Certify Лемма 4.4. Нормализованный эвристический аксептор U моделирует каждый другой нормализованный эвристический аксептор.

– 54 – Доказательство. Пусть A эвристический аксептор. Тогда из пред ложения 4.3 следует существование нормализованного эвристического аксептора B, который строго моделирует A. Предположим, что этот n алгоритм B имеет Геделев номер b. Тогда для b, алгоритм U запускает B. По предложению 4.5, Certify принимает с вероятностью n не менее 1 2edn/2. Таким образом, для b с вероятностью не (3/4) время работы U(x, d) не более p1 (dn · tB менее (x, 4dn)) для неко (3/4) торого полинома p1, а значит tU tB. Так как B строго моделирует (3/4) A, мы имеем tB tA. Следовательно, tU tA.

Теорема 4.7. U (x, d) = U(x, 8d) является эвристическим аксептором, который моделирует каждый другой эвристический аксептор.

Доказательство. U является эвристическим аксептором по лем ме 4.3 и следствию 4.6. Он моделирует каждый другой эвристический аксептор по лемме 4.4, предложению 4.3 и исходя из того факта, что U(x, 8d) моделирует U(x, d).

4.3 Оптимальный эвристический алгоритм для образа инъек тивной функции и его дерандомизация Обозначим за U последовательность распределений {Un }nN, где Un равномерное распределение на {0, 1}n. Для каждого языка L {0, 1}, Un (L) будет обозначать равномерное распределение на L{0, 1}n ;

тогда U(L) = {Un (L)}nN.

Распределенной задача это пара (L, D) состоящая из языка L {0, 1} и распределения D.

Мы будем использовать нижние индексы для обозначения веро ятностного пространства;

к примеру, PrxDn означает, что вероятность PrA означает, что ве берется по x относительно распределения Dn, а роятность берется по всем внутренним случайным битам алгоритма – 55 – A.

Алгоритмы, которые мы рассматриваем, могут выдавать 1 (вход принят), 0 (вход не принят), и (сдаюсь). Алгоритмы также могут зацикливаться, т.е. работать бесконечно (обозначается ). Для ал горитма A и целого числа T, обозначим за AT алгоритма, который ведет себя как алгоритм A в течении первых T шагов, а после сдается (возвращает ).

Время, потраченное вероятностным алгоритмом A на входе x, определяется как медианное время (определение 4.7).

4.4 Вероятностные эвристические алгоритмы Определение 4.13. Алгоритм A(x, d) является вероятностным эври стическим алгоритмом для распределенной задачи (L, D), если для каждого n, Pr ;

A[A(x, d) = L(x)] d.

xD n Замечание 4.4. В работах [8] и [39] вероятностные эвристические ал горитмы и аксепторы определяются иным образом: разделяется веро ятность по x и вероятность по случайным битам A. Отметим также, что в [39, Sect. 2] доказывается, что алгоритмы определенные двумя различными образами моделируют друг друга (доказательство для аксепторов применимо в случае алгоритмов без изменений).

Определение 4.14. Функция f : {0, 1} N N полиномиально огра ничена на множестве X, если существует полином p, такой что для всех x X и d N f(x, d) p(|x|d).

Эвристический алгоритм A полиномиально ограничен на мно жестве X, если его медианное время tA полиномиально ограничено на X. Мы опускаем X, если оно совпадает с {0, 1}.

Определение 4.15 ( [8]). Класс HeurBPP это класс распределен ных задач, которые могут быть решены полиномиально ограниченным – 56 – вероятностным алгоритмом.

Определение 4.16. Функция f : {0, 1} N N доминирует функ цию g : {0, 1} N N на множестве X (обозначается f g), если существуют полиномы p и q, такие что для всех x X и d N, max {p(f(x, d )d|x|)}.

g(x, d) d q(|x|d) Замечание 4.5.

1. Если f g на X и f полиномиально ограниченна на X, то g также полиномиально ограниченна.

2. транзитивно.

Определение 4.17. Для эвристических алгоритмов A и A для зада чи (L, D) говорят, что алгоритм A моделирует A, если tA tA на supp D.

Оптимальный вероятностный эвристический алгоритм для распределенной задачи (L, D) моделирует каждый эвристический ал горитм для (L, D).

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

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

Определение 4.19. Функция f : {0, 1} N N полиномиально огра ниченна в среднем относительно распределения D, если существует полином p, такой что для всех n, d N, Pr [f(x, d) p(n · d)] 1 2d.

xD n – 57 – Детерминированный эвристический алгоритм является полино миально ограниченным в среднем, если его время работы полиноми ально ограниченно в среднем.

Определение 4.20. Функция f : {0, 1} N N, моделирует g : {0, 1} N N в среднем относительно распределения D (обозначается f g), если существуют полиномы p и q такие что q(n, d) 2d и для всех n, d N, Pr [g(x, d) p(n · d · f(x, q(n, d)))] 1 d.

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

Предложение 4.6. Пусть f g и f полиномиально ограниченна в среднем относительно D. Тогда g также полиномиально ограниченна в среднем относительно D.

Доказательство. Пусть p и q будут полиномами из определения,и p будет полиномом из определения полиномиальной ограниченности g;

не умаляя общности мы предполагаем, что p является неубываю щей. Из полиномиальной ограниченности и ограничений на q следует PrxD 1 [f(x, q(n, d)) p (n · q(n, d))] 1 q(n,d) 1 2d. Подставляя в n условие доминирования имеем PrxDn [g(x, d) p(n·d·p (n·q(n, d)))] 1 1 1 = 1 d.

2d 2d Определение 4.21. Для эвристических алгоритмов A и A для рас пределенной задачи (L, D), будем говорить, что A моделирует A, если tA tA относительно D.

Детерминированный эвристический алгоритм для распределен ной задачи (L, D) оптимален в среднем, если он моделирует все дру гие детерминированные эвристические алгоритмы для (L, D).

Определение 4.22 ( [8]). HeurP это класс всех распределенных – 58 – задач, которые могут быть решены детерминированными эвристиче скими алгоритмами, полиномиально ограниченными в среднем.

4.5 Задача распознавания образа инъективной функции Определение 4.23. Пусть функция f : {0, 1} {0, 1} вычислима за полиномиальное время и |f(x)| = |x| + 1. Задача распознавания обра за это распределенная задача (Im f, U), где U является равномер Im f ным распределением. Мы так же будем обозначать через соот ветствующую характеристическую функцию, т.е. (Im f)(x) = 1, если x Im f, и (Im f)(x) = 0, если x Im f.



Pages:   || 2 | 3 | 4 | 5 |
 





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

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