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

Односторонняя функция с потайным входом (, ) — это односторонняя функция  из множества  в множество , обладающая свойством (потайным входом, лазейкой), благодаря которому становится возможным найти для любого  такое, что , то есть обратить функцию.

Односторонние функции с потайным входом широко используются в асимметричных методах шифрования (шифрование с открытым ключом) таких как: RSA, функция Рабина, схемы Эль-Гамаля, криптосистема McEliece, криптографическая система NTRUEncrypt, Polly Cracker, а также в менее популярной, из-за своей криптографической нестойкости, ранцевой криптосистеме Меркла — Хеллмана.

В настоящее время доподлинно не установлено, что односторонние функции с потайным входом действительно являются односторонними, то есть нет доказательства того, что, не зная потайной вход, криптоаналитик не сможет обратить функцию.

Определение 
Функция , где

 — множество открытых ключей,

 — отображаемый элемент, состоящий из n битов,

называется односторонней с потайным входом, если

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

История

Развитие односторонних функций с потайным входом 
Понятие односторонней функции с потайным входом было введено в середине 1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мёрклом статьи об асимметричных методах шифрования (шифрование с открытым ключом). Именно Диффи и Хеллман ввели данный термин. Но первой системой, в которой были использованы такие идеи, считается система, изобретённая в 1973 году , работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года.

Статья описывала новый способ для минимизации необходимости передачи ключей по защищённым каналам, а также в ней была разобрана криптографическая система, которая может использоваться в создании цифровой подписи.

Авторы показали, что односторонняя функция с потайным входом может быть использована в криптосистемах с открытым ключом и в устройстве цифровой подписи. Криптосистема с открытым ключом — система, в которой открытый ключ передается по незащищённому каналу. Смысл цифровой подписи заключается в том, что при пересылке подписанного сообщения от Алисы к Бобу, Боб может убедиться в том, что сообщение действительно было послано Алисой.

Благодаря односторонним функциям с потайным входом могут быть реализованы различные шифры с потайным входом, которые являются криптозащищёнными.

Было предложено несколько классов функций, но скоро стало понятно, что подходящие функции труднее найти, чем считалось изначально.
Например, сначала предполагалось использовать функции, основанные на задаче о сумме подмножеств. Вскоре выяснилось, что этот способ неприемлем. Примером подобной реализации может служить ранцевая криптосистема Меркла — Хеллмана.

В 2005 году самыми подходящими кандидатами в односторонние функции с потайным входом являлись функции из классов RSA и Рабина
. Эти функции используют возведение в степень по модулю составного числа, и обе они основаны на задаче факторизации целых чисел.

В 2008 году были представлены односторонние функции с потайным входом, допускающие потерю информации о изначальном сообщении.

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

Множество данных функций состоит из семейства двух функций:
 Повторяют работу односторонней функции с потайным входом без потери части информации, то есть при наличии «лазейки» можно эффективно вычислить  по значению .
 Теряют часть информации о входе, тогда у выхода  существует много прообразов (то есть невозможно однозначно обратить функцию).
Ключевым моментом является то, что выбранные семейства функций — . Следовательно, ключи могут быть заменены ключами с потерями без уведомления кого-либо. Но как только все ключи потеряны, шифрованный текст больше не содержит (значительную) информацию об зашифрованном сообщении. В то же время, если просто заменить функцию с лазейкой функцией с потерями, то нет возможности ответить даже на правильно сформированный запрос на дешифрование, потому что информация открытого текста будет утеряна. Поэтому используются более полные абстракции

Односторонние функции с потайным входом «All-but-one» 
Функция «All-but-one» (ABO) может быть построена из набора односторонних функций с потайным входом и с достаточной потерей информации.

Набор функций ABO связан с множеством , элементы которого называются ветвями. Генератор функции ABO принимает дополнительный параметр , называемый ветвью с потерями, и выводит функцию  и потайной ход t. Функция  обладает тем свойством, что для любой ветви  функция  обладает потайным входом (и может быть инвертирована с ), но функция  — функция с потерями. Более того, ветвь с потерями скрыта (вычислительно) по описанию ..

Односторонние функции с потайным входом «All-but-N» 
«All-but-N»(ABN) функции имеют ровно  веток с потерями; все другие ветки обладают потайным входом. Это можно использовать для точного определения зашифрованных текстов с помощью веток с потерями — все другие зашифрованные тексты соответствуют функциям с лазейкой и могут быть дешифрованы. Обратите внимание, что ABN кодируют набор веток с потерями по их ключу. То есть вычислительно неограниченный противник всегда может использовать грубую силу, для поиска ветвей, приводящих к функции с потерями.

Следовательно, ABN функции имеют серьезный недостаток: а именно, пространственная сложность ключей линейна в

Односторонние функции с потайным входом «All-but-many» 
«All-but-many»(ABM) функция имеет суперполиномиальное множество ветвей с потерями, которые требуют наличия специального потайного хода.

Самое важное отличие от ABN-функции: с ABN набор ветвей с потерями указывается первоначально, во время построения, а ABM функции имеют лазейку, позволяющую пробовать дешифровку «на лету» из большого пула ветвей с потерями. Без этого потайного хода и даже при произвольном известном множестве ветвей с потерями нет возможности найти другую ветвь, не принадлежащую известному множеству. Это, в частности, позволяет создавать экземпляры ABM с компактными ключами и изображениями, размер которых не зависит от количества ветвей с потерями.

Данные конструкции можно рассматривать как «замаскированные» варианты сигнальных схем Boneh-Boyen (BB). В частности, ветви с потерями соответствуют действительным сигнатурам. Тем не менее, чтобы метки потерь и метки потайных ходов казались неотличимыми, необходимо делать слепые подписи, путем их шифрования или путем умножения на случайный элемент подгруппы.

Построение односторонних функций с потайным входом с потерями 
Чтобы отметить основные принципы, предположим, что общая криптосистема с поддержкой CPA имеет несколько специальных (но неформально описанных) свойств.

Первое свойство предполагает, что лежащая в основе криптосистема аддитивно-гомоморфна. Функция  (односторонняя функция с лазейкой или функция с потерями) на  определяется путем шифрования поэлементно квадратной матрицы .

Для оценки , подаем вход  — n-мерный бинарный вектор и вычислим (поэтапно) шифрование линейного произведения , применяя гомоморфные операции к зашифрованным записям .

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

Для функции с потерями зашифрованная матрица  является матрицей, состоящей из нулей: . Тогда, для каждого входного сообщения , значение  является поэлементным шифрованием нулевого-вектора, поэтому  "теряет" информацию о  . Однако этого недостаточно для обеспечения полной потери, поскольку выходные зашифрованные сообщения по-прежнему несут некоторую внутреннюю случайную информацию, которая может служить источником данных о входном сообщении. Поэтому необходим дополнительный контроль за их поведением. Для этого существуют специальные свойства криптосистемы:
 случайности можно использовать повторно в комбинациях с различными ключами без ухудшения стойкости.
 гомоморфная операция изолирует случайность, то есть случайность выходного шифротекста зависит только от случайностей во входном сообщении (а не от открытого ключа или зашифрованных сообщений). Многие известные криптосистемы гомоморфны по отношению к случайности.
С этими двумя свойствами зашифровываем матрицу  особым образом. Каждый столбец  матрицы связан с другим ключом , а лазейка — это набор соответствующих ключей расшифровки. Через каждую строку  шифруем запись  под ключ  и ту же случайность  (используя новую случайность для каждой строки). По условию, повторно использовать случайность в паре с ключом  безопасно, поэтому матрица  является вычислительно скрытой. Кроме того, поскольку гомоморфизм изолирует случайность, все зашифрованные тексты в конечном векторе  также зашифровываются под такую же случайность  (которая зависит только от .

Когда , мы все ещё можем инвертировать функцию (с помощью лазейки), расшифровывая каждую зашифрованную запись . С другой стороны, когда матрица нулевая , выход функции всегда является вектором зашифрованных нулевых сообщений, где каждая запись зашифровывается по одной и той же случайности (но под разными фиксированными ключами). Поэтому число возможных выходов  ограничено числом возможных случайных строк, которые могут возникнуть. Выбирая размерность  так, что количество входов  является значительно больше, чем число случайных строк, мы можем гарантировать, что функция содержит потею информации.

Построение функций с потайным ходом «All-but-one» 
Построение функций «All-but-one» с потайным входом несколько более общее. Каждая ветвь  функции просто соответствует другой матрице , шифрование которой может быть получено из публичного описания функции. Функция генерируется так, что  является обратимой матрицей (и вычисляется с помощью потайного входа) для всех ветвей , тогда как  для ветвей с потерями

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

RSA 
Возьмём число , где  и  принадлежат множеству простых чисел. Считается, что для данного числа  вычисление  и  является математически трудной задачей. Функция шифрования RSA — , где  — взаимнопростое с . Числа  и  являются потайным входом, зная которые вычислить обратную функцию  легко. На сегодняшний день лучшей атакой на RSA является факторизация числа .

Функция Рабина 
Рассмотрим функцию , где , а p и q принадлежат множеству простых чисел. Рабин показал, что вычислить функцию  легко тогда и только тогда, когда разложение на множители составного числа из двух простых является простой задачей.

Схема Эль-Гамаля 
Данная схема была предложена Тахером Эль-Гамалем в 1984 году. Она основывается на задаче дискретного логарифмирования.

Алгоритм
 Алиса выбирает простое число p и произвольное число a.
 Алиса вычисляет свой открытый ключ (а, b), где , 
 Боб выбирает  и шифрует сообщение m: 
 Алиса расшифровывает сообщение

Криптосистема Polly Cracker 
Алгоритм
 Алиса случайным образом выбирает вектор в конечном поле.
 Алиса строит полиномы, которые в точке, задаваемой этим вектором, обращаются в ноль.
 Боб генерирует сумму 
 Боб посылает

Другие примеры 
Известно, что функции, связанные с задачей дискретного логарифмирования, не являются односторонними функциями с потайным входом, потому что нет никакой информации о «лазейке», которая позволила бы эффективно вычислять дискретный логарифм. Однако, задача дискретного логарифмирования может использоваться в качестве основы для «лазейки», например,  и его разновидности. Алгоритм цифровой подписи основан на данной вычислительной задаче.

Замечания 
Односторонние функции с потайным входом имеют очень специфическое применение в криптографии и их не нужно путать с бэкдором (часто одно понятие подменяется другим, но это неправильно). Бэкдор — механизм, который намеренно добавляется к шифровальному алгоритму (например, алгоритм генерации ключевых пар, алгоритм цифровой подписи, и т. д.) или к операционным системам, позволяя одному или нескольким посторонним лицам обходить или подрывать безопасность системы.

См. также 
 Односторонняя функция

Примечания

Литература 
 
 
 
 
 
 
  

Криптография
Аутентификация
Криптография с открытым ключом
Теоретико-числовые алгоритмы