Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14.1.4 Гипотеза о существовании односторонних функций Вверх: 14.1 Односторонние функции Назад: 14.1.2 Односторонние функции в теории сложности   Содержание   Предметный указатель

14.1.3 Криптографические односторонние функции

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

Неформально, такая односторонняя функция может быть определена следующими условиями:

  • функция эффективно вычислима;

  • любой эффективный алгоритм инвертирует эту функцию лишь на пренебрежимо малой доле значений.

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

Перейдем к формальным определениям. Пусть $ \Sigma=\{0,1\}*$, $ \Sigma^n=\{0,1\}^n$. Всюду ниже будем предполагать, для простоты изложения, что множество $ \Sigma$ является областью определения всех рассматриваемых функций. Длину слова $ x$ будем обозначать через $ \vert x\vert$. Для некоторого события $ \alpha $ через $ \Pr(\alpha)$ будем обозначать вероятность этого события.

Прежде всего заметим, что функция может трудно инвертироваться просто потому, что она слишком сильно "сжимает" входные значения. Ясно, что никакой полиномиальный алгоритм не может ее инвертировать, поскольку за полиномиальное (от длины значения функции) время он не успеет выписать найденное значение из прообраза. Этот неинтересный случай исключается посредством требования так называемой честности.

Определение 1.  Функция $ f$ называется честной, если существует полином $ p$ такой, что $ \vert x\vert<p(\vert f(x)\vert)$ для любого $ x\in\Sigma$.

Определение 2.  Честная функция $ f$ называется односторонней в сильном смысле, если
  • существует полиномиальная машина Тьюринга $ T$, которая на любом входе $ x\in\Sigma$ вычисляет $ f(x)$;

  • для любого полиномиального алгоритма $ A$ справедливо следующее. Пусть $ x\in_{\mbox{\tiny\rm R}}\Sigma^n$ и слово $ y=f(x)$ подано на вход алгоритма $ A$. Тогда для любого полинома $ p$ и для всех достаточно больших $ n$

    $\displaystyle \Pr(f(A(y))=y)<1/p(n). $

Вероятность берется по выбору значения $ x$ из $ \Sigma^n$ и, если $ A$ -- это вероятностная машина Тьюринга, -- по вырабатываемым ею случайным величинам.

Если в определении 2 ограничение на вероятность заменить следующим более слабым условием:

$\displaystyle \ \Pr(f(A(y))=y)<1-1/p(n) $

для некоторого фиксированного полинома $ p$, то получим определение функции, односторонней в слабом смысле. Говоря неформально, такая функция трудно инвертируется по крайней мере на полиномиальной доле значений. Из результатов Яо [Yao] и Гольдрайха и др. [Getal] следует, что функции, односторонние в сильном смысле существуют тогда и только тогда, когда существуют функции, односторонние в слабом смысле. Такая "устойчивость" свидетельствует, что найдена адекватная формализация интуитивного понятия односторонней функции. В дальнейшем мы будем рассматривать только функции, односторонние в сильном смысле и для краткости называть их просто односторонними.

Необходимо отметить, что односторонняя функция -- гипотетический объект, поэтому называть конкретные функции (как, например, дискретный логарифм) односторонними математически некорректно. Очевидно, что из предположения о существовании односторонних функций следует, что P$ {}\ne{}$NP. Вопрос о том, является ли это условие одновременно и достаточным, остается открытым. Более того, никаких нетривиальных достаточных условий существования односторонних функций на данный момент не известно.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14.1.4 Гипотеза о существовании односторонних функций Вверх: 14.1 Односторонние функции Назад: 14.1.2 Односторонние функции в теории сложности   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100