28563

Однонаправленные функции, построение однонаправленных функций с секретами

Доклад

Информатика, кибернетика и программирование

Обозначим через QF сложность вычисления значения Fx для произвольного xX через QF1 сложность вычисления по произвольному yY значения x такого что Fx=y сложность вычисления понимается в стандартном смысле теории сложности. Сложность вычисления F такова что алгоритм ее вычисления реализуем на современной технике и выдает ответ за приемлемое время 2. Сложность вычисления F1 такова что алгоритм ее вычисления либо не реализуем на современной технике либо не дает ответ за приемлемое время. Что считать приемлемым...

Русский

2013-08-20

14.43 KB

5 чел.

41. Однонаправленные функции, построение однонаправленных функций с секретами.

В основе идей, изложенных в статье Уитфилда Диффи и Мартина Хеллмана  лежало понятие однонаправленной функции.

   Пусть X, Y - произвольные равномощные множества, F -  биективная  функция, отображающая X в Y. Обозначим через Q(F) - сложность вычисления значения F(x) для произвольного xX, через Q(F-1) - сложность вычисления по произвольному yY значения x, такого, что F(x)=y (сложность вычисления понимается в стандартном смысле теории сложности).

    В данных терминах будем говорить, что функция F является однонаправленной, если Q(F-1) много больше Q(F). Как видно, данное определение не является достаточно строгим. Под термином «много больше» можно подразумевать весьма разные понятия, например то, что вычисление F имеет полиномиальную сложность, а F-1- экспоненциальную.

Для того, чтобы под понятием однонаправленная функция понимался вполне конкретный класс объектов считают, что под термином «много больше», понимается следующее:

1.   Сложность вычисления F такова, что алгоритм ее вычисления реализуем на современной технике и выдает ответ  за приемлемое время

2.   Сложность вычисления F-1 такова, что алгоритм ее вычисления либо не реализуем на современной технике, либо не дает ответ за приемлемое время.

   Что считать приемлемым временем следует из практических соображений - вычисление F не должно замедлять скорости обработки информации, а сложность вычисления F-1 должна быть столь велика, чтобы не допускать обращения функции F злоумышленником.

На момент опубликования статьи авторы не имели конкретной системы ЭЦП и по этой причине их система ОРК повисла в воздухе, так как в ней не решался вопрос аутентификации отправителя сообщения. Такое решение появилось значительно позднее  - в 1984 году. Пока же авторы предложили еще одну абстрактную схему с использованием так называемых однонаправленных функций с секретом (trapdoor one-way function). Строгое определения однонаправленной функции с секретом дать весьма затруднительно.

Попробуем сформулировать его следующим образом.

    Однонаправленной функцией с секретом S называется  биективная функция F отображающая произвольное множество X в множество Y, зависящая от параметров T1,...,TL  и обладающая следующим свойствами: 

1.     Существует некоторая функция S, зависящая от параметров T1,...,TL 

2.   По виду функции F значение функции S для конкретных параметров T1,...,TL  не восстанавливается 

3.   Сложность вычисления значения F-1(y)  yY при знании значения S(T1,...,TL) не превосходит сложности вычисления прямого преобразования  F 

4.   Сложность вычисления преобразования F-1 без знания значения S(T1,...,TL) много больше сложности вычисления прямого преобразования F. 

     Иными словами, без знания дополнительной информации о функции F она является однонаправленной, при наличии некоторой дополнительной информации (которую нельзя получить по функции F) обратное преобразование эффективно вычисляемо.

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


 

А также другие работы, которые могут Вас заинтересовать

81904. Проблемы оптимизации соотношения централизации и децентрализации в структуре органов управления фирмы 39.29 KB
  Быстрая разработка и принятие решений адекватно отражающих реальную ситуацию максимальное использование опыта и знаний персонала более простое управление менее бюрократизированное. децентрализации: узость и тактический характер решений слабый учет или даже игнорирование в принимаемых решениях интересов других участников управления и организации в целом вследствие обособленности процесса их выработки. Таким образом появляется проблема оптимизации соотношения централизации и децентрализации проблема поиска золотой...
81905. Мотивация в менеджменте 41.86 KB
  Материальная мотивация стремление к достатку более высокому уровню жизни зависит от уровня личного дохода его структуры дифференциации доходов в организации и обществе действенности системы материальных стимулов применяемых в организации. Трудовая мотивация порождается непосредственно работой ее содержанием условиями организацией трудового процесса режимом труда. Это внутренняя мотивация человека совокупность его внутренних движущих сил поведения связанных с работой как таковой. Статусная мотивация является внутренней движущей...
81906. Эволюция подходов к мотивации в рамках научных школ управления 40.55 KB
  На основании анализа и сопоставления существующих подходов можно выделить следующие концепции мотивации в рамках которых происходила исторически оправданная эволюция понятий мотивации: традиционный подход основывающийся на использовании метода кнута и пряника и рассматривающий модели поведения человека работника: верующий человек экономический человек и механистический человек ; подход с позиций человеческих отношений основывающийся на использовании в управлении методов психологии и рассматривающий модели поведения человека ...
81907. Основные подходы к мотивации труда, используемые в менеджменте 41.1 KB
  Концепция верующего человека относится к периоду капитализма первоначального накопления состоит в том что в соответствии с духом протестантской этики при помощи веры обосновывалось поддерживалось и оправдывалось приумножение капитала честным путем как самоцель. Концепцию верующего человека в XIX в. сменила концепция экономического человека которая в упрощенном виде сводилась к тому что если работнику платить больше за сделанную работу он...
81908. Содержательные теории мотивации 41.35 KB
  К ним относятся теория иерархии потребностей А. Маслоу теория приобретенных потребностей МакКлелланда двухфакторная теория Герцберга и некоторые другие. Что касается вторичных потребностей высших уровней мотивации то несмотря на различия в формулировках все три автора содержательных теорий сходились во мнении что они активно воздействуют на поведение человека. Основными недостатками данной группы теорий является то что в реальной жизни проявление потребностей не осуществляется в строгой иерархической последовательности а является...
81910. Мотивационная теория подкрепления 40.74 KB
  Теория подкрепления исходит из того что у любого действия или поведения есть последствия: негативные и позитивные. При этом люди повторяют поведение которое приносило удовольствие было позитивно подкреплено и избегают поведения которое доставило им неприятности. Подкрепление определяется как любые действия которые вызывают повторение или напротив подавление определенных образцов поведения. Позитивное подкрепление представляет собой вознаграждение желательного для руководства организации поведения с целью формирования или закрепление у...
81911. Контроль как функция менеджмента 41.93 KB
  Существует три аспекта управленческого контроля: установление стандартов точное определение целей которые должны быть достигнуты в определенный отрезок времени. Необходимость контроля обусловлена следующими обстоятельствами: потребностью организации процесса производства в соответствии с имеющимися резервами и ресурсами; требованиями потребителей к качеству стандарту и сертификации выпускаемой продукции; изменяющимися внутренними и внешними условиями производства необходимостью выявления тенденций меняющегося спроса и предложения...