Задачи по курсу Математическая криптография

Срок сдачи — 11 февраля (после этого срока задачи приниматься не будут):

1. Доказать, что существуют сильно необратимые семейства функций. Решение этой задачи.

2. Доказать, что семейство функций f_n(x)= x^2 mod 2^n,
определенных на n-битовых числах, не является слабо необратимым.

3. Доказать, что если мощность множества значений функции f_n
ограничена сверху некоторым полиномом от n, то семейство f_n не является
сильно необратимым.

Срок сдачи — 25 февраля (после этого срока задачи приниматься не будут):

4. Пусть даны две биективные полиномиально вычислимые
функции f_n,g_n:{0,1}^n —> {0,1}^n.
Докажите, что если хотя бы одна из них сильно [слабо] необратима,
то и их композиция сильно [слабо] необратима.
(Это верно как для равномерного, так и для
неравномерного противника.)

5. Предположив существованиие сильно односторонних функций h_n:{0,1}^n —> {0,1}^n,
докажите, что существуют сильно односторонние
функции f_n,g_n:{0,1}^n —> {0,1}^n, композиция которых
не является даже слабо необратимой. (Это верно как для равномерного, так и для
неравномерного противника.)

6. Пусть дана сильно [слабо] необратимая функция f_n:{0,1}^n —> {0,1}^n.
Докажите, что тогда функция xy —> f_n(x)y,
определенная на словах длины 2n, сильно
[слабо] необратима. (Это верно как для равномерного, так и для
неравномерного противника.)

Срок сдачи — 4 марта (после этого срока задачи приниматься не будут):

7. Пусть последовательности распределений вероятностей \mu_n и \nu_n вычислительно
неотличимы. Докажите, что для любой последовательности вероятностных схем из функциональных элементов C_n числа
P[C_n(x,r)=1] (где x выбирается случайно по распределению \mu_n, а r
выбирается случайно с равномерным распределением) и
P[C_n(x,r)=1] (где x выбирается случайно по распределению \nu_n, а r
выбирается случайно с равномерным распределением) приблизительно равны (то есть, их разность стремится к нулю быстрее любого обратного полинома).

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

9. Пусть f_n:{0,1}^n —> {0,1}^n сильно необратимая функция.
Докажите, что тогда и функция x —> f_n(x)1
(приписываем к значению функции единицу) также сильно необратима.

Срок сдачи — 11 марта (после этого срока задачи приниматься не будут):

10. Докажите, что композиция генераторов ПСЧ типа
k(n)—> l(n) и l(n)-> m(n) является генератором ПСЧ типа k(n)—> m(n).

11. Докажите, что если функция G_n является генератором типа k(n)—> l(n),
а x_n последовательность слов длины l(n),
вычислимая за время \poly(n), то
функция s |—> G_n(s)\oplus x_n является генератором.

Срок сдачи — 25 марта (после этого срока задачи приниматься не будут):

12. Докажите, что существуют сильно необратимые функции
$f_n,g_n$ такие, что функция
$x\mapsto f_n(x)g_n(x)$ не является
даже слабо необратимой.

13. Предположим, существует сильно односторонняя частичная функция. Докажите, что
тогда существует и сильно односторонняя всюду определенная функция.

14. Пусть дана некоторая схема шифрования с закрытым ключом.
Пусть противник интересуется некоторой информацией
$f(x)$ о передаваемом сообщении $x$, длина которого ему известна.
Путь для её извлечения он применяет к шифрограмме сообщения $x$
некоторую схему $D_n$ полиномиального от $n$ размера.
Докажите, что для любой последовательности слов $x_n$ полиномиальной от
$n$ длины та же самая информация $f(x_n)$ может быть вычислена
и без подслушивания с примерно той же вероятностью успеха
некоторой схемой $C_n$ полиномиального размера, зависящей только от длины слова $x_n$.

Срок сдачи — 1 апреля (после этого срока задачи приниматься не будут):

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

Срок сдачи — 8 апреля (после этого срока задачи приниматься не будут):

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

Срок сдачи — 15 апреля (после этого срока задачи приниматься не будут):

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

Срок сдачи — 29 апреля (после этого срока задачи приниматься не будут):

18. Постройте протоколы идентификации с открытым ключом
в предположении необратимости функции RSA и дискретной экспоненты.

Сданные задачи

Лысенко 2 (наполовину), 3, 4 (наполовину), 5, 7, 8, 9, 10 (наполовину), 11, 12, 14, 15, 16, 17

Янушевич 1, 2, 3, 4, 5, 6

Кулинич 4 (наполовину), 5, 6, 8, 9, 10, 14, 12

Абдуллаев 5, 7, 8, 9, 10, 12, 14

Архипова 4 (наполовину), 6, 9, 17 (наполовину)

Петров 4

Мартынов, Кречетов, Голубев 4, 5
(каждый получает по две трети балла, поскольку работы идентичные)

Аксёнов 4

Свешников 4, 5, 8, 9, 17 (наполовину)

Исмаилов 9

Аноним 8, 9