Задачи по курсу «Теоретико-сложностные вопросы в криптографии»
Срок сдачи — 8 сентября
1. Постройте двухленточную машину Тьюринга, обращающую слово из нулей и единиц за $O(n)$ шагов, где n обозначает длину входа.
2. Постройте одноленточную машину Тьюринга, стирающую каждый второй символ слова из нулей и единиц (оставшиеся символы должны быть записаны подряд) за O(n^2) шагов, где n обозначает длину входа.
Срок сдачи — 15 сентября
3. Постройте РАМ, которая по двум n-битовым натуральным числам x,y находит x^y $ Какова длина машинного слова этой РАМ?
4. Постройте РАМ, которая по двум n-битовым натуральным числам x,y находит x^y за O(n) шагов и использует константу регистров.
Срок сдачи — 22 сентября
5. Постройте одноленточную машину Тьюринга, которая по двум n-битовым натуральным числам x,y за время O(n^2) выясняет, какое число больше.
6. Постройте одноленточную машину Тьюринга, которая по двум n-битовым натуральным числам x,y за время O(n^2) находит их произведение.
Срок сдачи — 6 октября
7. Сведите задачу выполнимости 4-КНФ к задаче выполнимости 3-КНФ
8. Сведите задачу СуммаПодмножества к задаче Разбиение (можно ли разбить данный набор слагаемых A на два набора с одинаковой суммой).
Срок сдачи — 13 октября
9. Постройте схему из функциональных элементов размера O(n) для сложения двух n-битовых чисел.
10. Постройте схему из функциональных элементов размера O(n^2) для умножения двух n-битовых чисел.
Срок сдачи — 20 октября
11. Докажите, что количество СФЭ размера s с n входами и одним выходом не превосходит (O((s+n)^2))^s. Выведите отсюда, что при всех достаточно больших n существует булева функция от n переменных, не вычисляемая никакой СФЭ размера 2^n/3n.
12. Докажите, что класс BPP замкнут относительно применения операций объединения, пересечения и дополнения языков.
Срок сдачи — 27 октября
13. Пусть f_n есть возведение в квадрат по модулю 2^n на n-битовых натуральных числах. Докажите, что f_n не является необратимым семейством функций даже для равномерного противника.
14. Пусть даны две биективные полиномиально вычислимые функции f_n,g_n : {0,1}^{n} —> {0,1^{n}. Докажите, что если хотя бы одна из них сильно необратима, то и их композиция сильно необратима. Это верно как для равномерного, так и для неравномерного противника.
Срок сдачи — 3 ноября
15. Предположим, что существует сильно одностороннее семейство функций f_n:{0,1}^n —> {0,1}^n. Докажите, что тогда существуют сильно односторонние семейства функций g_n,h_n:{0,1}^n —> {0,1}^n, композиция которых не является даже слабо необратимой.
16. Для неравномерного противника: пусть множество значений функции f_n:{0,1}^n —> {0,1}^n имеет не более poly(n) элементов. Докажите, что тогда f_n не является даже слабо необратимым семейством функций.
Срок сдачи — 10 ноября
17. Для равномерного противника: пусть функция f_n:{0,1}^n —> {0,1}^n равна константе, то есть, значение f_n(x) зависит только от n.
Докажите, что тогда f_n не является даже слабо необратимым семейством функций.
18. Пусть дано сильно одностороннее семейство функций f_n:{0,1}^n —> {0,1}^n. Докажите, что семейство функций x—> f_n(x)0 (к значению функции приписывается один нуль) также является сильно необратимым.
Срок сдачи — 17 ноября
19. Пусть дана сильно необратимая функция f_n:{0,1}^n —> {0,1}^n. Докажите, что тогда функция xy —> f_n(x)y (имеется в виду конкатенация), определенная на словах длины 2n, сильно необратима.
20. Пусть даны два семейства полиномиально вычислимых функций f_n, g_n с одинаковой областью определения. Рассмотрим новую функцию h_n(x)=f_n(x)g_n(x) (имеется в виду конкатенация значений двух функций). Приведите пример, когда обе функции f_n,g_n сильно односторонние, а h_n не является даже слабо односторонней (в решении можно пользоваться гипотезой о существовании одностороннего семейства функций).
Срок сдачи — 24 ноября
21. Докажите, что любое сильно одностороннее семейство частичных функций можно преобразовать в сильно одностороннее семейство всюду определенных частичных функций.
22. Докажите, что композиция двух перестановок с секретом f_n^e и g_n^{e’} множества {0,1}^n снова является перестановкой с секретом множества {0,1}^n.
Срок сдачи — 1 декабря
23. Пусть случайные величины \alpha_n и \beta_n вычислительно неотличимы, а p(n) — некоторый полином. Докажите, что случайная величина \alpha_n’, состоящая из первых p(n) битов слова \alpha_n, вычислительно неотличима от случайной величины \beta_n’, состоящей из первых p(n) битов слова \beta_n.
24. Пусть случайные величины \alpha_n и \beta_n вычислительно неотличимы, а \gamma_n произвольная случайная величина, независимая от
\alpha_n и \beta_n. Докажите, что \alpha_n\gamma_n и \beta_n\gamma_n вычислительно неотличимы.
Срок сдачи — 8 декабря
25. Пусть у полиномиально вычислимой частичной перестановки есть трудный бит. Докажите, что в этом случае перестановка является сильно необратимой.
26. Пусть оба семейства функций f_n:{0,1}^n->{0,1}^{2n} и g_n:{0,1}^{2n}->{0,1}^{3n} являются генераторами псевдослучайных чисел. Докажите, что и их композиция g_n(f_n(x)) является генератором псевдослучайных чисел.
Срок сдачи — 15 февраля
27. Объясните, как по таблице афинной функции a_0+a_1x_1+…+a_nx_n из (F_2)^n в F_2 (поле вычетов по модулю 2), испорченной в 10 процентах позиций, можно за полиномиальное время восстановить a_0 с вероятностью ошибки не более одного процента.
Срок сдачи — 20 февраля
28. Чему равны вероятности событий f(f(00…0))=00…0 и f(f(00…0))=11…1, где f выбирается с равномерным распределением среди всех функций из {0,1}^n в {0,1}^n ?
Срок сдачи — 29 февраля
29. Объясните, как из семейства ПСФ {f^n_s}, отображающих слова длины n в слова длины n, построить семейство ПСФ, отображающих слова длины n в слова длины 2n.
Срок сдачи — 14 марта
30. Пусть дано семейство ПСФ {f^n_s}, отображающих слова длины n в слова длины n, причем длина слова s равна n. Для каждого n и каждого слова s длины n+1 рассмотрим функцию g^n_{s}, отображающую слово x длины n в слово f^{n+1}_s(x0)f^{n+1}_s(x1) (длины 2(n+1), здесь x0 обозначает конкатенацию слова x и слова 0, аналогично x1). Докажите, что построенное так семейство функций g^n_{s} есть семейство ПСФ, отображающих слова длины n в слова длины 2(n+1).
Срок сдачи — 21 марта
31. Пусть имеются две схемы шифрования с закрытым ключом. Изготовим из них новую схему шифрования: ключ в новой схеме состоит из пары ключей для исходных схем, первая половина сообщения шифруется алгоритмом из первой схемы с помощью первого ключа, а вторая половина сообщения — алгоритмом из второй схемы в помощью второго ключа. Аналогичным образом шифрограмма расшифровывается. Докажите, что полученная таким образом схема также удовлетворяет определению схемы шифрования с закрытым ключом.
Срок сдачи — 28 марта
32. Пусть даны одноразовая схема шифрования (K,E,D) с закрытым ключом и семейство ПСФ f^n_s:{0,1}^n -> {0,1}^{p(n)}, где p(n) — количество случайных бит, нужное алгоритму K на входе 1^n. Постройте на этой основе многоразовую СШЗК.
33. Докажите, что построенная многоразовая СШЗК в самом деле выдерживает атаку с подслушиванием нескольких шифрограмм (а если сможете, то и атаку с подбрасыванием сообщений для шифрования).
Срок сдачи — 4 апреля
34. Докажите, что если схема шифрования с открытым ключом выдерживает подслушивание одного сообщения, то она выдерживает и подслушивание нескольких сообщений.
35. Докажите, что если схема шифрования с открытым ключом выдерживает подслушивание одного сообщения, то она выдерживает и атаку с подбрасыванием сообщений.
Срок сдачи — 11 апреля
36. Докажите, что алгоритм S в любом протоколе привязки к биту не может быть детерминированным.
37. Объясните, как любой неинтерактивный протокол привязки преобразовать в протокол привязки, который в качестве ключа выдаёт свои случайные биты и сообщение.
Срок сдачи — 25 апреля
38. Пусть в протоколе игры орлянки по телефону, изложенному на лекции, в качестве протокола привязки использован интерактивный протокол, основанный на генераторе псевдослучайных чисел. У кого из двух игроков есть выигрышная стратегия, если не требовать реализумости стратегии СФЭ полиномиального размера?
Срок сдачи — 16 мая
39. Построить протокол идентификации с открытым ключом, выдерживающий атаку с подслушиванием, на основе любой односторонней перестановки с секретом. Доказать, что он в самом деле надежен.
40. Построить протокол идентификации с открытым ключом, выдерживающий атаку с подслушиванием, на основе любого протокола шифрования с открытым ключом. Доказать, что он в самом деле надежен.
Срок сдачи — 23 мая
41. Докажите, что в любом протоколе идентификации, выдерживающем атаку с подслушиванием, алгоритм V должен быть вероятностным.