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

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


 

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

37922. ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЕЙ ПРЕЛОМЛЕНИЯ ЖИДКИХ И ТВЕРДЫХ ТЕЛ 235.5 KB
  Сагитова Определение показателей преломления жидких и твердых тел: Методические указания к лабораторной работе №62 по разделу Оптика Уфимск. Приведены краткая теория и методы измерения показателя преломления жидких и твердых тел.1 Определение показателя преломления стекла с помощью микроскопа [2.
37923. ИЗУЧЕНИЕ ОПТИЧЕСКИХ ХАРАКТЕРИСТИК ДИФРАКЦИОННОЙ РЕШЕТКИ 1.57 MB
  Изучение оптических характеристик дифракционной решетки. Студенты экспериментально определяют угловую дисперсию и разрешающую способность в различных порядках спектра фазовой дифракционной решетки.4 Оптические характеристики дифракционной решетки 10 3 Экспериментальная часть 13 3.
37924. ЭКСПЕРИМЕНТАЛЬНОЕ ИЗУЧЕНИЕ ЗАКОНОВ ТЕПЛОВОГО ИЗЛУЧЕНИЯ 2.24 MB
  Краузе Экспериментальное изучение законов теплового излучения: Методические указания к лабораторной работе № 64 по курсу общей физики Уфимск. Методические указания знакомят студентов с явлением теплового излучения. Описаны физические причины излучения электромагнитных волн нагретыми телами и приведены законы которым это излучение подчиняется.
37925. Изучение законов постоянного тока Исследование зависимости КПД источника тока от сопротивления нагрузки 383 KB
  Лабораторная работа № 33 Изучение законов постоянного тока Исследование зависимости КПД источника тока от сопротивления нагрузки 1. Определить КПД источника тока. Получить экспериментальную зависимость мощности источника тока от сопротивления нагрузки.
37926. Изучение явления термоэлектронной эмиссии и определение удельного заряда электрона 206.5 KB
  Благодаря пространственному заряду при малых анодных напряжениях анодный ток может быть значительно меньше возможного тока эмиссии катода и постепенно увеличивается при повышении анодного напряжения. Если поддерживать температуру накаленного катода постоянной и снять зависимость анодного тока Iа от анодного напряжения uа – вольт амперную характеристику рис.2 Вольт амперные характеристики диода при различных температурах T2  T1 Зависимость термоэлектронного тока Iа от анодного напряжения в области малых положительных значений uа...
37927. ИЗУЧЕНИЕ ТЕРМОЭЛЕКТРОННОЙ ЭМИССИИ МЕТАЛЛОВ. ОПРЕДЕЛЕНИЕ РАБОТЫ ВЫХОДА ЭЛЕКТРОНА 98 KB
  Сила термоэлектронного тока в диоде зависит от величины напряжения U рис. Отклонение зависимости анодного тока IА от анодного напряжения U от прямолинейной связано: а с наличием в промежутке между катодом и анодом неоднородной области пространственного заряда; б с отсутствием центров рассеяния в упомянутом промежутке. Зависимость тока диода IА от анодного напряжения U имеет вид: I=C U3 2 2.3 Is – величина тока насыщения три кривые относятся к трем разным...
37928. Изучение процессов заряда и разряда конденсатора 452 KB
  12 Лабораторная работа № 37 Изучение процессов заряда и разряда конденсатора 1. Цель работы Целью данной работы является изучение заряда и разряда конденсатора при различных параметрах электрической цепи и вычисление времени релаксации. В качестве примера квазистационарных токов рассмотрим процессы заряда и разряда конденсатора в электрической цепи содержащей последовательно соединенные конденсатор С сопротивление R включающие и внутреннее сопротивление источника и источник ЭДС ε рис. Пусть I q U – мгновенные значения тока заряда и...
37929. Изучение электрических свойств твердых диэлектриков 259.5 KB
  Типы диэлектриков Диэлектриками называются вещества которые при обычных условиях практически не проводят электрический ток. Согласно представлениям классической физики в диэлектриках в отличие от проводников нет свободных носителей заряда – заряженных частиц которые могли бы под действием электрического поля прийти в упорядоченное движение и образовать электрический ток проводимости. К диэлектрикам относятся все газы если они не подвергались ионизации некоторые жидкости дистиллированная вода бензол и др. Все молекулы диэлектрика...
37930. Определение электродвижущей силы 377 KB
  Эти частицы называют носителями тока. За положительное направление тока выбрано направление движения положительно заряженных частиц. Если бы в электрической цепи действовали только электростатические силы то положительные носители тока под действием этих сил перемещались бы от большего потенциала к меньшему и таким образом снижали больший и повышали меньший потенциал. Это привело бы к выравниванию потенциала во всех точках проводника и прекращению тока.