Введение в криптографию
[an error occurred while processing this directive]

Односторонние функции - часть 2


Для других криптографических схем подобный результат доказывается не столь просто. В работе Импальяццо и Луби [] доказана необходимость односторонних функций для существования целого ряда стойких криптографических схем.

Из всего сказанного следует, что предположение о существовании односторонних функций является самым слабым криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем различных типов. На выяснение того, является ли это условие и в самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односторонних функций можно пояснить на следующем примере. Пусть  - односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ - секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования и дешифрования оба зависят от этого секретного ключа  и таковы, что для любого открытого текста . Ясно, что если криптограмму сообщения вычислять как , то противник, перехвативший , может вычислить лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет восстановить сообщение из криптограммы законный получатель? Во-вторых, из того, что функция

односторонняя следует лишь, что противник не может вычислить все сообщение целиком. А это - весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму , не мог вычислить ни одного бита открытого текста.

На настоящий момент доказано, что существование односторонних функций является необходимым и достаточным условием для существования стойких криптосистем с секретным ключом, а также стойких криптографических протоколов нескольких типов, включая протоколы электронной подписи. С другой стороны, имеется результат Импальяццо и Рудиха [], который является достаточно сильным аргументом в пользу того, что для некоторых типов криптографических схем (включая протоколы распределения ключей типа Диффи-Хеллмана) требуются более сильные предположения, чем предположение о существовании односторонних функций. К сожалению, этот результат слишком сложный, чтобы его можно было разъяснить в настоящей главе.

Next: 2.4. Псевдослучайные генераторы

Up: 2. Криптография и теория

Previous: 2.2. Криптография и гипотеза

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]