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) обратное преобразование эффективно вычисляемо.

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


 

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

78978. Особенности становления и основные принципы неклассической науки 43 KB
  Планк квантавая теория Резенфорд планетарная модель атома Ренген ренгеновские лучи Все эти открытия разрушили картину мира. Основные принципы: Установка на невозможность описать мир сам по себе Установлено различие в организации и развитии 3х уровней мира: макро микро мега. Нет качественной однородности в мега микро и макромирах Вероятностный детерменизм Признавалась роль случайностей. Случайность равноценный фактор необходимости Объект исследования не вещи а процессы Принципиально невозможно найти первокирпичик мира т.
78979. Понятие рациональности, научной рациональности. Виды и типы научной рациональности 48 KB
  Понятие рациональности научной рациональности. Виды и типы научной рациональности. В самой идее рациональности можно увидеть символ современной научно-технической цивилизации со всеми ее особенностями и противоречиями. Ее началом является некоторый тип активно-преобразовательного отношения человека к миру с которым и связывается как правило сама идея рациональности.
78980. Пространство и время в современной и классической картине мира 35 KB
  Пространство и время в современной и классической картине мира. Пространство есть форма координации сосуществующих объектов состояний материи. Пространство и время это всеобщие формы существования координации объектов. Пространство и время в классической картине мира.
78981. Философское значение синергетики 41 KB
  В своей классической работе Синергетика он отмечал что во многих дисциплинах от астрофизики до социологии мы часто наблюдаем как кооперация отдельных частей системы приводит к макроскопическим структурам или функциям. Синергетика в ее нынешнем состоянии фокусирует внимание на таких ситуациях в которых структуры или функции систем переживают драматические изменения на уровне макромасштабов. По мнению ученого существуют одни и те же принципы самоорганизации различных по своей природе систем от электронов до людей а значит речь должна...
78982. Этос науки и императивы, регулирующие поведение ученого 32.5 KB
  Понятие Императив и Этос науки Императив лат. Этос науки набор внутренних социальных норм которых придерживаются ученые в научной деятельности и которые обеспечивают функционирование социального института науки. Нормы этоса науки Попытка кодификации социальных норм науки была предпринята Р.
78983. Научная специальность и основные этапы ее становления 40.5 KB
  С этой характеристикой тесно связана потребность в такого рода вознаграждении которое служило бы достаточным стимулом для профессионалов будучи в то же время подконтрольно не столько посторонним сколько самой профессии. Внутренний мотив это познавательная потребность информация заключенная в объекте на который направлено внимание человека. Познавательная потребность характеризуется следующими основными критериями: интенсивное стремление субъекта к знанию и к познавательной деятельности на основании чего избирается его...
78985. Сциентизм и антисциентизм, их философские основания и историческая эволюция. Сциентизм и технократизм в их соотношении 16.8 KB
  В Новой Атлантиде Бэкон подробно рассказывает о том как наука практически может улучшать жизнь людей. Здесь наука расценивается как наивысшая культурная ценность наивысший вид духовной деятельности; техника играет главную и решающую роль в развитии общества. Три главных положения сциентизма: Наука может разрешить основные моральные и этические проблемы общества заменяя философию и метафизику.