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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

112. Хопкрофт Д., Мотвани Р., Ульман Д.

Введение

в теорию автоматов, языков и вычислений. М., «Вильяме», 2002.

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

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

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