Использование радиуса устойчивости оптимизационных задач для скрытия и проверки …
3
Устойчивость и обратные оптимизационные задачи.
Предла-
гаемая здесь методика базируется на связи исследования устойчиво-
сти с обратными оптимизационными задачами. Эта тема исследова-
лась, например, в работах [3–5].
Показано, что знание радиуса устойчивости и его оценок при
определенных условиях позволяет решать такие задачи. В работе [5]
этому посвящен отдельный раздел, где в общем случае и на примере
задачи коммивояжера рассмотрена связь проблематики устойчивости
с подходами по решению обратных задач.
Рассмотрим возможность применения этих результатов для пере-
дачи информации по открытым каналам.
Пусть имеется канал связи, по которому работают пользователи
А
и
В
и злоумышленник
Z
имеет к нему доступ.
Для скрытия информации используется некоторая
NP
-полная за-
дача большой размерности, например, задача коммивояжера на графе
с
n
вершинами. На сегодня при достаточно больших
n
нет эффектив-
ных алгоритмов ее решения.
Типовым случаем (при вероятностном подходе «с вероятностью
единица») является ситуация |
(
A
)| = 1 (см., например, [8] и [4]). При
решении обратной задачи по заданной траектории нужно уметь стро-
ить вектор (матрицу)
A
, где заданная траектория является оптималь-
ной.
Пусть злоумышленнику известно
n
и тип используемой задачи.
Как показано, например, в работах [3–5] решение обратной задачи
базируется на задании некоторого множества параметров, связанных
с комбинаторикой задачи. При этом одним из главных (а в ряде слу-
чаев ключевым) является радиус устойчивости той прямой задачи (
E
,
D
n
,
A
), для которой найдено
(
A
). Обозначим этот набор параметров
через
P
(
).
Зная этот набор параметров
А
и
В
скрывают свою информацию с
помощью элементов оптимальной траектории, например, в случае
задачи коммивояжера передаваемая информация содержится только
в
n
элементах минимального гамильтонова цикла, а остальные эле-
менты вектора (матрица)
A
используются для ее сокрытия.
Не зная оптимальной траектории, злоумышленник информацию
из сообщения извлечь не может по той же причине, что и в алгорит-
мах
RSA
. Точное решение
NP
-трудных задач большой размерности
невозможно получить «за разумное время». В то же время
А
и
В
пе-
редают друг другу матрицу с известной оптимальной траекторией.
При этом за счет варьирования параметрами множества
P
(
) матри-
цы могут быть разными.
Если к этому добавить какой-нибудь алгоритм открытого распре-
деления ключей, то по нему можно передавать саму оптимальную
траекторию, тем самым постоянно ее меняя.
