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

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


 

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

30915. Энергообмен 36.5 KB
  Энергообмен Обмен веществ и энергии связаны между собой. Обмен веществ сопровождается преобразованием энергии химической механической электрической в тепловую. Количество тепла выделяемое живым организмом пропорционально интенсивности обмена веществ. По количеству выделяемого организмом тепла можно оценить интенсивность обменных процессов.
30916. Тепловой обмен 42.5 KB
  Баланс теплопродукции и теплоотдачи является главным условием поддержания постоянной температуры тела. Механизмы теплоотдачи: Излучение способ отдачи тепла в окружающую среду поверхностью тела человек в виде электромагнитных волн инфракрасного диапазона. Теплопроведение способ отдачи тепла при соприкосновении тела человека с другими физическими телами. Количество отдаваемого при этом тепла прямопропорционально: а разнице средних температур контактирующих тел б площади контактирующих поверхностей в времени теплового контакта г...
30917. Гомеостатические функции почек 26.5 KB
  поддержание осмотического давления крови за счет уровня глюкозы аминокислот липидов гормонов в ней 4. поддержание ионного состава крови 5.регуляция кислотнощелочного баланса рН мочи от 45 до 84 тогда как рН крови постоянная 6. удаление из крови чужеродных соединений и нейтрализация токсических веществ 9.
30918. Выделительная функция почек. Механизмы образования первичной мочи 25 KB
  Ряд веществ находящихся в плазме крови в норме отсутствуют во вторичной моче. Другие вещества находятся во вторичной моче в концентрациях значительно превышающие таковые в плазме крови. Некоторые соли выводятся в концентрациях близких или равных таковым в крови. Клубочковая фильтрация процесс фильтрации из плазмы крови протекающей через капилляры клубочка в полость капсулы почечного клубочка воды и растворенных в плазме веществ за исключением крупномолекулярных соединений.
30919. Выделительная функция почек. Образование конечной (вторичной) мочи 44.5 KB
  Канальцевая реабсорбция. Канальцевая реабсорбция процесс обратного всасывания воды и ряда растворенных в ней веществ. Реабсорбция подразделяется на облигатную обязательную и факультативную не обязательную зависящую от функционального состояния проницаемости стенки канальцев скорости движения жидкости по канальцам величине осмотического градиента. Канальцевая реабсорбция обеспечивается: 1.
30920. Регуляция функции почек 25.5 KB
  Нервная же система может вызвать болевую анурию при болевых раздражениях выброс АДГ усиливается. В нормальных условиях на клубочковую фильтрацию не влияет но усиливает обратное всасывание воды тем самым уменьшает диурез. Альдостерон гормон коркового вещества надпочечников N сберегающий гормон усиливает реабсорцию натрия в проксимальных канальцах усиливает секрецию К в дистальных канальцах. Паратгормон влияет на проксимальные и дистальные канальцы усиливает реабсорбцию Са2 снижает канальцевую реабсорбцию...
30921. Водный баланс 33.5 KB
  Водный баланс односолевой баланс обеспечивается совокупностью процессов поступления воды и электролитов в организм распределения их во внутренней среде и выделения из организма. Водный баланс равенство объемов выделяющейся из организма и поступающей за сутки воды. Общее количество воды в организме 4470 массы тела примерно 3842 литра. Уменьшение воды: а с возрастом б у женщин в при ожирении Н2О в организме образует водные пространства: 1.
30922. Особенности организации и функционирования спинного мозга 37 KB
  Особенности организации и функционирования спинного мозга Спинной мозг Самое древнее образование ЦНС подчиняется всем вышележащим отделам ЦНС. Центры спинного мозга не обладают автоматией дыхание. Для спинного мозга характерно сегментарное строение. Дорсальные корешки спинного мозга образованы чувствительными отростками афферентных нейронов вентральные корешки образованы двигательными отростками мотонейронов и преганглионарными волокнами вегетативной нервной системы.
30923. Ретикулярная формация 35.5 KB
  Нисходящее тормозящее влияние на спинной мозг 2. Восходящее активирующее влияние на кору больших полушарий. Нисходящее ретикулоспинальное влияние РФ: Слабое одностороннее раздражение торможение на той же стороне. Восходящее ретикулокортикальное влияние РФ: Особенности восходящего влияния РФ: 1.