Задачи по курсу «Теоретико-сложностные вопросы в криптографии»
Срок сдачи — 1 апреля
1. Постройте протокол идентификации с открытым ключом в предположении необратимости функции RSA
2. Докажите, что существует СТОЗ, если функция RSA необратима.
Срок сдачи — 8 апреля
3. Постройте протокол идентификации с открытым ключом в предположении необратимости дискретной экспоненты.
4. Докажите, что существует СТОЗ, если дискретная экспонента необратима.
Срок сдачи — 14 апреля
5. Докажите, что любой интерактивный протокол привязки к биту можно перестроить так, чтобы алгоритм Посылающего в качестве ключа выдавал свои случайные биты и секретный бит.
6. Приведите пример алгоритма и общеизвестной информации, такие, что алгоритм имеет нулевое разглашение, однако при увеличении общеизвестной информации нулевое разглашение пропадает. Приведите обратный пример (когда алгоритм не имеет нулевого разглашения, но после увеличения общеизвестной информации он становится алгоритмом с нулевым разглашением).
Срок сдачи — 21 апреля
7. Пусть даны две биективные полиномиально вычислимые функции f,g:{0,1}^n —> {0,1}^n. Докажите, что если хотя бы одна из них сильно [слабо] необратима, то и их композиция сильно [слабо] необратима.
8. Докажите, что существуют сильно односторонние функции f,g:{0,1}^n —> {0,1}^n, композиция которых не является даже слабо необратимой (в предположении существования сильно односторонних функций).
Срок сдачи — 28 апреля
9. Докажите, что если функция RSA сильно односторонняя, то она является улучшенной перестановкой с секретом.
10. Приведите пример сильно односторонних функций f_n,g_n, определенных на одном и том же множестве, для которых функция f_n(x)g_n(x) (конкатенация значений) не является даже слабо односторонней (в предположении существования сильно односторонних функций).
Срок сдачи — 5 мая
11. Докажите, что для любой сильно односторонней функции f существует неразглашающий протокол доказательства знания обратного элемента к данному $y$ (алгоритм доказывающего может разглашать только $y$ и то, принадлежит ли $y$ множеству значений функции). Докажите, что построенный протокол имеет нужные свойства. В этой задаче можно использовать нераглашающий протокол доказательства знания раскраски графа в три цвета.
12. Постройте протокол идентификации с открытым ключом на основе любой сильно односторонней функции. Докажите, что построенный протокол имеет нужные свойства. В этой задаче можно использовать протокол из предыдущей задачи.
Срок сдачи — 12 мая
13. Постройте протокол конфиденциального вычисления x+y mod 2 на числах от 1 до 3: у Алисы имеется целое число x от 1 до 3, у Боба — целое число y в тех же пределах. Боб должен узнать x+y mod 2, а Алиса не должна узнать ничего.
14. Докажите, что если функция f_n односторонняя, а функция g_n полиномиально вычислима и длина g_n(x) есть O(log n), то и функция f_n(x)g_n(x) (конкатенация) односторонняя.
Срок сдачи — 19 мая
15. Постройте универсальное семейство хэш-функций из {0,1}^n в {0,1}^m,
в котором каждая функция задаётся O(n) битами (предполагается, что m меньше n).
16. Постройте генератор ПСЧ, исходя из односторонней функции f_n, у которой каждое слово из множества значений имеет одинаковое количество k_n про-образов, где k_n некоторая полиномиально вычислимая функция.