Отметим, что если
ν
0
, ν
1
, ν
2
, . . . ν
n
из формулы (7) равняются
e
, то
равенство (7) будет сводиться к системе равенств следующего вида:
⎧⎪⎪⎪⎨
⎪⎪⎪⎩
π
0
=
ν
0
=
e
;
π
1
=
π
1
∗
ν
1
;
π
2
=
π
2
∗
ν
2
;
. . . . . . . . . . .
π
n
=
π
n
∗
ν
n
.
(8)
Действительно, компоненты формулы (7) в данном случае могут
анализироваться алгоритмом оптимизации независимо друг от друга.
Таким образом, существенно упрощается процедура анализа, а следо-
вательно, повышается вероятность существования алгоритма оптими-
зации, лежащего в классе сложности
P
.
На самом деле, несводимость равенства (7) к системе (8) можно
обеспечить. Для этого, прежде всего, необходимо, чтобы подпрограм-
мы с функциональными свойствами
π
i
и
ν
i
определяли разные эле-
менты выходных векторов, а подпрограмма с функциональным свой-
ством
ν
k
−
1
восстанавливала необходимые элементы входных векторов
перед тем, как будет запущена подпрограмма с функциональным свой-
ством
π
k
, которая будет работать непосредственно с этими элемента-
ми (
k > n
). Однако такой подход не обладает высокой стойкостью по
интуитивно понятным причинам. Есть еще одна возможность обес-
печить несводимость равенства (7) к системе (8). Далее приведено
применение алгоритмов гомоморфного шифрования или вычисления
над зашифрованными данными:
m
1
opm
2
⇔
E
(
m
1
)
op E
(
m
2
)
,
(9)
т.е. определенной операции над двумя исходными текстами
m
1
opm
2
взаимно однозначно соответствует другая операция над зашифрован-
ными данными
E
(
m
1
)
op E
(
m
2
)
. Однако известно, что формула (9)
выполнима не для всех операций
op
.
Рассмотрим еще раз последовательность в правой части равенства
(7). Предположим, что все еe элементы обратимы. Тогда справедливо
следующее:
ν
0
=
π
∗
ν
n
∗
π
n
∗
...
∗
ν
1
∗
π
1
,
(10)
т.е.
π
=
π
∗
γ,
(11)
где
γ
=
ν
n
∗
π
n
∗
. . .
∗
ν
1
∗
π
1
∗
π
1
∗
ν
1
∗
. . .
∗
π
n
∗
ν
n
.
(12)
Из равенства (9) следует, что
γ
=
e
, т.е. злоумышленнику доста-
точно будет выделить свойства
π
и
γ
.
98 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
