Односторонние функции

Что такое криптография? Традиционный подход: как обеспечить секретность сообщения Алиса и Боб разговаривают, Ева пытается подслушать Alice Bob Eve

Базовые определения Симметричные системы: Key 1 = Key 2 Открытые или ассимметричные системыetric: Key 1 Key 2 Key 1 или Key 2 являются публичными (открытыми) в зависимости от протокола Шифрование Расшифрование Key 1 Key 2 Криптограмма E key1 (M) = C D key2 (C) = M Исходное сообщение Сообщение

Что означает конфиденциальность ? Абсолютная стойкость: Зашифрованное сообщение невозможно расшифровать без знания ключа Шеннон (1943 г.) показал, что длина ключа должна быть не меньшей, чем длина сообщения для абсолютной стойкости системы (теория информации) Одноразовый блокнот (использовался во время Второй мировой войны) Вычислительная стойкость: Зашифрованное сообщение невозможно прочитать без знания ключа, используя современные вычислительные Не существует вероятностного полиномиального алгоритма, способного взломать зашифрованное сообщение.

ВВЕДЕНИЕ Односторонняя функция – это функция, которая легко вычисляется, но которую трудно инвертировать Два свойства односторонней функции f - Легко вычислимая - Трудно инвертируемая

ВВЕДЕНИЕ Односторонняя функция – это функция, которая легко вычисляется, но которую трудно инвертировать Два свойства односторонней функции f - Легко вычислимая Существует полиномиальный алгоритм, который по входу x дает на выходе y=f (x) - Трудно инвертируемая Всякий вероятностный полиномиальный алгоритм, пытающийся по входу y найти обратное значение f, будет иметь успех с ничтожно малой вероятностью.

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

Виды односторонней функции С фиксированной длиной С переменной длиной

Функции-кандилаты 1.Разложение целых: Время, необходимое для разложения целого числа N сильно зависит от второго наибольшего делителя P заданного числаr N. Функцию f = x. y - произведение целых x и y можно вычислить за полиномиальное время. Однако можно показать, что эта функция сильная односторонняя. 2.Декодирование случайного линейного кода

Литература 1. Lane A. Hemaspaandra and Joerg Rothe. Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory. Journal of Computer and System Sciences, 58(3): , Lane A. Hemaspaandra, Kari Pasanen, Joerg Rothe. If P NP Then Some Strongly Noninvertible Functions are Invertible. In Proceedings of the 13 th International Symposium on Foundations of Computation Theory, pages Springer-Verlag Lecture Notes in Computer Science #2138, August Christopher M. Homan and Mayur Thakur. One-Way Permutations and Self-Witnessing Languages. In Proceedings of the 2 nd IFIP International Conference on Theoretical Computer Science, pages Kluwer Academic Publishers, Christopher M. Homan. Low Ambiguity in Strong, Total, Associative, One-Way Functions. Technical Report TR734, Department of Computer Science, University of Rochester, August Joerg Rothe and Lane A. Hemaspaandra. Characterizing the Existence of Partial One-Way Permutations. Information Processing Letters, 82(3): , 2002.