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

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


 

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

47452. Клетка – элементарная биологическая система 117 KB
  Вне клетки не существует настоящей жизнедеятельности. Исходя из предположения о схожести гомологичности растительных и животных клеток доказываемой одинаковым механизмом их возникновения Шванн обобщил многочисленные данные в виде теории согласно которой клетки являются структурной и функциональной основой живых существ. Ему принадлежит вывод о том что клетка может возникнуть лишь из предсуществующей клетки. Выдающаяся роль клетки как первоисточника жизни обусловливается тем что именно она является биологической единицей с помощью...
47453. Изменчивость и ее формы 41.5 KB
  Изменчивость и ее формы. Изменчивость как свойство живых систем Модификационная изменчивость. Наследственная генотипическая изменчивость
47454. Генетика человека. Нормальная наследственность человека 31.5 KB
  Генеалогический метод Популяционностатистический метод Близнецовый метод Метод дерматоглифики Цитогенетический метод Биохимические методы Методы рекомбинантной ДНК Методы генетики соматических клеток Карты хромосом 1. Генеалогический метод Генеалогический метод является наиболее старым методом генетики человека. Метод относительно прост и доступен. В методе составляются и ё анализируются семейные родословные что позволяет определить наследственный или ненаследственный характер заболевания отдельного симптома;...
47455. Медицинская генетика. Медико-генетическое консультирование 33.5 KB
  Наследственные болезни человека Генные болезни Хромосомные болезни Болезни с наследственным предрасположением
47456. Воспроизведение на организменном уровне (размножение организмов). Онтогенез, общие закономерности. Прогенез 42.5 KB
  Тема: Воспроизведение на организменном уровне размножение организмов. Размножение организмов Бесполое размножение. Половое размножение
47457. ЭЛЕКТРОНИКА. Учебное пособие 21.81 MB
  Для полупроводников наиболее важной является валентная зона, образованная уровнями энергии валентных электронов невозбужденных атомов (т.е. при отсутствии внешней энергии) и ближайшая к ней разрешенная зона (см. рис.9-1). Разрешенная зона, в которой при возбуждении могут находиться электроны, называется зоной проводимости, или свободной зоной.
47458. Бухгалтерский учет, анализ и аудит, Методические указания по дипломному проектированию 665.5 KB
  В методических указаниях определены цель и задачи дипломного проектирования требования к содержанию структуре и оформлению дипломной работы порядок проведения защиты работы. Назначение руководителя и выбор темы дипломной работы Содержание основной части дипломной работы Порядок проведения защиты дипломной работы
47460. Строительство многопрофильного культурно-спортивного комплекса Минск-Арена расположена в северо-восточной части г. Минска 531.5 KB
  Технические решения, принятые на стройгенплане, соответствуют требованиям экологических, санитарно-гигиенических и противопожарных норм и правил и обеспечивают безопасное для жизни и здоровья людей производство строительно-монтажных работ при соблюдении предусмотренных проектом мероприятий.