28563

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

Доклад

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

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

Русский

2013-08-20

14.43 KB

7 чел.

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

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


 

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

25297. Основні положення християнського віровчення і культу. Нікейський символ віри, його аналітичний виклад 33.5 KB
  Він для нас людей і для нашого спасіння зійшов з небес і тіло прийняв від Духа Святого і Діви Марії і став людиною. І в Духа Святого Господа Животворящого що від Отця походить що Йому с Отцем і Сином однакове поклоніння і однакова слава належить що говорить через пророків. 8 член Символу віри про віру в Духа Святого. За традицією це ім'я пов'язано з ім'ям святого якому присвячено день коли хрестили немовля.
25298. Філософські дискусії 20-30-х років та їх переломлення в Україні 32 KB
  Філософські дискусії 2030х років та їх переломлення в Україні У 2030х роках починає формуватися марксистськоленінський світогляд. У звязку з цим починається боротьба за утвердження марксистськоленінського природознавства яке розпочавшись з дискусії 30х років завершилося не тільки встановленням повного контролю політичноідеологічної системи над природознавством але й розгромом цілого ряду наукових напрямів фізичним знищенням їх представників. З перших днів утвердження радянської влади на Україні культура освіта наука...
25299. Філософський доробок С.Семковського 93 KB
  Тут він заснував першу в Україні кафедру марксизму і марксознавства яка потім перетворилася на Український інститут марксизму в якому до 1931 р. інституті марксизмуленінізму був створений філсоціолог. марксизму У 1918 р. кафедру марксизму і марксознавства яка потім перетв.
25300. В.Юринець та його філософський спадок 28.5 KB
  Юринець та його філософський спадок Юринець Володимир Олександрович 18911937.
25301. Слуховой анализатор 48.5 KB
  Средняя сосудистая оболочка в передней части глаза образует ресничное тело и радужную оболочку обуславливающую цвет глаз. Внутренняя сетчатая оболочка сетчатка или ретина содержит фоторецепторы глаза палочки и колбочки и служит для преобразования световой энергии в нервное возбуждение. Светопреломляющие среды глаза преломляя световые лучи обеспечивают четкое изображение на сетчатке. Основными преломляющими средами глаза человека являются роговица и хрусталик.
25302. Вкусовой и обонятельный анализатор 23.5 KB
  Хеморецепторы вкуса представляют собой вкусовые луковицы расположенные в эпителии языка задней стенке глотки и мягкого неба. Микроворсинки рецепторных клеток выступают из луковицы на поверхность языка и реагируют на растворенные в воде вещества. Рецепторы разных частей языка воспринимают четыре основных вкуса: горького задняя часть языка кислого края языка сладкого передняя часть языка и соленого яердняя часть и края языка.
25303. РОЛЬ СЕНСОРНЫХ СИСТЕМ В УПРАВЛЕНИИ ДВИЖЕНИЯМИ. СОМАТОСЕНСОРНАЯ ЧУВСТВИТЕЛЬНОСТЬ И КОРРЕКЦИЯ ДВИЖЕНИЙ 35.5 KB
  СОМАТОСЕНСОРНАЯ ЧУВСТВИТЕЛЬНОСТЬ И КОРРЕКЦИЯ ДВИЖЕНИЙ Выполнение движений сопряжено с растягиванием кожи и давлением на отдельные ее участки поэтому кожные рецепторы оказываются включенными в анализ движений. Эта функциональная связь является физиологической основой комплексного кинестетического анализа движений при котором импульсы кожных рецепторов дополняют мышечную проприоцептивную чувствительность. Благодаря проприоцепции возможны коррекция уточнение движений в соответствии с текущими потребностями выполнения произвольного действия....
25304. Физиологические реакции живого организма 39 KB
  Раздражение Раздражителем живой клетки или организма как целого может оказаться любое изменение внешней среды или внутреннего состояния организма если оно достаточно велико возникло достаточно быстро и продолжается достаточно долго. Клетки значительно более чувствительны по отношению к своим адекватным раздражителям чем к неадекватным. Возбудимость Некоторые клетки и ткани нервная мышечная и железистая специально приспособлены к осуществлению быстрых реакций на раздражение.
25305. Стресс 33.5 KB
  0004 ГОМЕОСТАЗ Внутренняя среда организма в которой живут все его клетки это кровь лимфа межтканевая жидкость. Ее характеризует относительное постоянство гомеостаз различных показателей так как любые ее изменения приводят к нарушению функций клеток и тканей организма особенно высокоспециализированных клеток центральной нервной системы. Способность сохранять гомеостаз в условиях постоянного обмена веществ и значительных колебаний факторов внешней среды обеспечивается комплексом регуляторных функций организма. существовать и двигаться...