Криптосистема с коротким ключом, стойкая к анализу на основе большого количества шифртекста

Семенов А.А.
Институт динамики систем и теории управления СО РАН, Иркутск.

Аннотация:

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

Введение

В 1949 г., в работе [3] К.Э. Шеннон построил общую теорию шифров с секретным ключом, (симметричных криптосистем). Следует отметить, что по сути никаких принципиально новых методов шифрования Шеннон не предложил, а лишь проанализировал известные шифры на стойкость, используя для этого фундаментальные понятия теории информации, введенные им же годом ранее в работе [4]. С позиции анализа Шеннона "наилучшими" из известных шифров являются совершенно секретные шифры, то есть криптосистемы, для любой криптограммы которых справедливо т.н. условие совершенной секретности:
\begin{displaymath} P\{ x = x_{0} \vert y\} = P\{ x = x_{0} \} , \end{displaymath} (1)

где $x$-оценка открытого текста, выбираемая из множества открытых текстов $X$, $x_{0} \in X$- истинный открытый текст, $y$- криптограмма, являющаяся элементом множества криптограмм $Y$. Важнейшим результатом работы [3] стало доказательство совершенной секретности некоторых известных типов шифров, простейшим из которых является шифр Вернама. Однако там же было показано, что в рамках общепринятых (на момент 1949 г.) концепций шифрования совершенно секретные системы непрактичны, поскольку условие (1) влечет за собой необходимость передавать по секретному каналу не меньший объем информации, чем по открытому. Таким образом, неявно была поставлена задача построения практичных криптосистем, в которых возможна передача большого объема шифртекста (по отношению к объему информации, переданной по секретному каналу) с сохранением совершенной секретности.

В представляемой работе предлагается подход к решению данной проблемы. В разделе II описывается общая конструкция криптосистемы, базовыми объектами которой являются линейные векторные пространства над произвольным полем. Показывается, что в случае конечных полей $\Im = GF(q)$ ($q$- простое число, либо натуральная степень простого числа) в рамках криптосистемы возможно породить $q^{\left[ {c \cdot {\textstyle{{n} \over {2}}}} \right]}$ ($c \in ]0,1[$) криптограмм, обладающих совершенной секретностью с вероятностью, отличной от единицы на произвольную (наперед заданную) малую константу (относительно дискретной вероятностной меры). При этом по секретному каналу передается не более ${\textstyle{{n + n^{2}} \over {2}}} \cdot ]\log q[$ бит секретной информации (где $n$- размерность векторного пространства над $\Im $, $n$- четное число).

Конструкция криптосистемы допускает абстрактное обобщение на бесконечные поля и, в частности, на $R$.

Описание криптосистемы и основные результаты.

Рассматривается поле $\Im $ (конечное или бесконечное) с аддитивной ($\oplus $ ) и мультипликативной ($ \otimes $) операциями на нем. $V_{n} $ - векторное пространство над $\Im $, $dimV_{n} = n$.

Пусть $n \in N$- четное. Отправитель строит две прямоугольные матрицы $A,B$ размерности $n \times {\textstyle{{n} \over {2}}}$ с компонентами из $\Im $. Матрицы выбираются таким образом, что каждая из них имеет ранг, равный ${\textstyle{{n} \over {2}}}$, и матрица $C = A\vert B$ (построенная в результате конкатенации $A$ и $B$) является невырожденной: $\det C \ne 0$ (несложно заметить, что такие матрицы всегда существуют).

Выбирается вектор ${\bf v} \in V_{n} $ , такой, что система

\begin{displaymath} {\bf z} \cdot B = {\bf v} \end{displaymath} (2)

совместна (несколько "экзотическая" запись умножения в (2) применяется лишь из соображений экономии).

Матрицу $A$ отправитель публикует, матрица $B$ и вектор ${\bf v}$ отправляются по секретному каналу получателю.

Теперь описываем процедуру порождения криптограмм. Отправитель формирует вектор ${\bf z} \in V_{n} $, являющийся некоторым произвольным образом выбранным решением системы линейных уравнений (2). Происходит это следующим образом. Фиксируется некоторая нумерация $m = {\textstyle{{n} \over {2}}}$, ( $k = rankA = rankB = {\textstyle{{n} \over {2}}}$) свободных переменных (система линейных уравнений, полученная после подстановки произвольного набора значений свободных переменных, должна иметь единственное решение). Значения свободных переменных при решении системы (2) выбираются случайно и независимо друг от друга из поля $\Im $.

Считаем, что номера свободных переменных известны отправителю и получателю. Обозначим свободные переменные в векторе ${\bf z}$ следующим образом:

\begin{displaymath} z_{f_{1}} ,...,z_{f_{m}} ,\{ f_{1} ,...,f_{m} \} \subset \{ 1,...,n\} . \end{displaymath}


Вектор открытого текста -- ${\bf x} = ({x_{1} ,...,x_{m}})\in V_{m}$. Шифрующее преобразование -- покомпонентное применение аддитивной операции поля $\Im $ к векторам ${\bf x'} = ({x'_{1},...,x'_{n}})$ и ${\bf z}$, где компоненты вектора ${\bf x'}$ с номерами $f_{1} ,...,f_{m} $ (назовем их информационными) есть скаляры $x_{1} ,...,x_{m} $, а остальные компоненты (избыточные) выбираются из $\Im $ случайно и независимо друг от друга.

В открытый канал отправляется вектор ${\bf u} = {\bf z} \cdot A$ и собственно криптограмма - вектор ${\bf y} ={\bf x'} + {\bf z}$, составленный из покомпонентных сумм $x'_{i} \oplus z_{i} ,i \in \{ 1,...,n\} $. Последовательность компонент $y_{f_{1}} ^{i} ,....,y_{f_{m}} ^{i} $ криптограммы ${\bf y}_{i}$ назовем информационным блоком криптограммы, оставшиеся компоненты образуют избыточный блок.

На приемном конце получатель строит вектор ${\bf d} = \left( {\bf u}\vert{\bf v} \right)$ (конкатенация), матрица $C$ ему известна. Таким образом, получатель имеет в своем распоряжении систему

\begin{displaymath} {\bf d} ={\bf z} \cdot C, \end{displaymath}

которая однозначно разрешима относительно вектора ${\bf z}$. Выбирая из полученного таким образом вектора ${\bf z}$ и вектора ${\bf y}$ компоненты с номерами $f_{1} ,...,f_{m} $ и осуществляя обратное преобразование, получатель находит вектор открытого текста ${\bf x}$.

Криптоаналитик, перехватывающий векторы ${\bf u},{\bf y}$ и знающий матрицу $A$, оказывается перед необходимостью выбора фиксированного отправителем решения системы ${\bf z} \cdot A = {\bf u}$. Однако множество решений последней образует плоскость размерности $m = {\textstyle{{n} \over {2}}}$ ($m$-плоскость) в евклидовой геометрии $EG\left( {n,q} \right)$ (определение и основные свойства конечных геометрий можно найти, например, в [2]). Таким образом, криптоаналитик оказывается перед задачей выбора фиксированной отправителем точки из наблюдаемой им некоторой $m$- плоскости в $EG\left( {n,q} \right)$.

Ниже будет определен класс матриц, удовлетворяющих всем оговоренным условиям, таких, что свободные переменные в системе ${\bf z} \cdot A = {\bf u}$ имеют ту же нумерацию, что и в системе ${\bf z} \cdot B = {\bf v}$ и при этом

\begin{displaymath} f_{i} = i,i \in \{ 1,...,m = {\textstyle{{n} \over {2}}}\} . \end{displaymath}

Теперь предположим, что построенная криптосистема используется для многократной передачи секретных данных при фиксированных $A,B,{\bf v}$. В результате криптоаналитик располагает последовательностями векторов: ${\bf u}_{1} ,...,{\bf u}_{t} $ и ${\bf y}_{1} ,...,{\bf y}_{t} $.

Заметим, что в силу конструкции системы при попарно различных векторах ${\bf z}_{1} ,...,{\bf z}_{t} $ векторы ${\bf u}_{1} ,...,{\bf u}_{t} $ также попарно различны (предположив, что ${\bf u}_{i} ={\bf u}_{j} $ и при этом ${\bf z}_{i} \ne {\bf z}_{j} $, получим, что система линейных уравнений ${\bf z} \cdot С = {\bf d}$ имеет два различных решения, притом, что $\det C \ne 0$). Откуда сразу следует, что наблюдая различные векторы ${\bf u}_{1} ,...,{\bf u}_{t} $, криптоаналитик наблюдает непересекающиеся $m$- плоскости в $EG\left( {n,q} \right)$. Действительно, предположив, что пара плоскостей (с номерами $i$ и $j$) пересекается, получим, что существует хотя бы одно общее решение

\begin{displaymath} {\bf z}_{*} :{\bf z}_{*} \cdot A ={\bf u}_{i} , {\bf z}_{*} \cdot A = {\bf u}_{j} , {\bf u}_{i}\ne {\bf u}_{j}. \end{displaymath}

Если же секретные ключи ( ${\bf z}_{i} ,{\bf z}_{j} $) повторяются, то повторяются и соответствующие им векторы ( ${\bf u}_{i}, {\bf u}_{i} $) и этот факт становится доступным криптоаналитику (таким образом, он знает, какие участки открытого текста зашифрованы одним и тем же секретным ключом).

Результатом, резюмирующим свойства построенной криптосистемы, является следующая теорема.

Теорема 1.
Предположим, что для любого четного $n \in N$ существуют матрицы $A,B$ размерности $n \times {\textstyle{{n} \over {2}}}$, такие, что выполнены следующие условия:

1. $rankA = rankB = {\textstyle{{n} \over {2}}} = m$, $rank(C = A\vert B) = n$ ($n$ назовем размерностью криптосистемы),

2. нумерации свободных переменных в произвольных совместных системах ${\bf z} \cdot A = {\bf u},{\bf z} \cdot B = {\bf v}$ совпадают.

Тогда можно указать такой способ генерации последовательности секретных ключей $\{{\bf z}_{i} \} _{i = 1}^{t}$ и такой способ порождения избыточных компонент в последовательности $\{ {\bf x}_{i} \} _{i = 1}^{t} $ (для произвольного $t \in N$), что для любой наперед заданной константы $\varepsilon \in ]0,1[$ найдется константа $c_{\varepsilon} \in ]0,1[$, такая, что для всех $m \ge m_{0}$ (начиная с некоторого $m_{0} \in N$) в криптосистеме описанного типа (с фиксированными $A,B,{\bf v}$) размерности $n = 2 \cdot m$ каждая из криптограмм ${\bf y}_{i} ,i \in \{ 1,...,q^{\left[ {c_{\varepsilon} \cdot m} \right]}\}$ с вероятностью $P: P \ge 1 - \varepsilon $ обладает совершенной секретностью.

Доказательство.
Опишем общую схему порождения последовательности секретных ключей и последовательности избыточных блоков исходных сообщений. Обозначим

\begin{displaymath} I = \{ f_{1} ,...,f_{m} \} , J = \{ g_{1} ,...,g_{m} \} = \{ 1,...,n\} \backslash I. \end{displaymath}

Предположим, что в векторах

\begin{displaymath} {\bf z}_{1} = \left( {z_{1}^{1} ,...,z_{n}^{1}} \right),..., {\bf z}_{t} = \left( {z_{1}^{t} ,...,z_{n}^{t}} \right) \end{displaymath}

и

\begin{displaymath} {\bf x}_{1} = \left( {x_{1}^{1} ,...,x_{n}^{1}} \right),...,{\bf x}_{t} = \left( {x_{1}^{t} ,...,x_{n}^{t}} \right) \end{displaymath}

последовательность:

\begin{displaymath} z_{f_{1}} ^{1} ,...,z_{f_{m}} ^{1} ,x_{g_{1}} ^{1} ,...,x... ... ^{t} ,...,z_{f_{m}} ^{t} ,x_{g_{1}} ^{t} ,...,x_{g_{m}} ^{t} \end{displaymath} (3)

есть последовательность элементов поля $\Im $, выбранных случайно и независимо друг от друга.

Стандартное допущение состоит в том, что сообщение ${\bf x}_{i} $ выбирается из $V_{m} $ случайно и, таким образом, для криптоаналитика

\begin{displaymath} P\{{\bf x}_{i} = {\bf x}_{i}^{0} \} = {\textstyle{{1} \over {q^{m}}}}. \end{displaymath} (4)

Если предположить, что при конструировании последовательности (3) с соблюдением всех перечисленных требований для некоторого $t \in N$ среди векторов ${\bf z}_{1} ,...,{\bf z}_{t} $ нет повторяющихся, то все $m$-плоскости в $EG\left( {n,q} \right)$, доступные криптоаналитику в результате наблюдения векторов ${\bf u}_{1} ,...,{\bf u}_{t} $, оказываются непересекающимися. Последнее означает, что для любого $i \in \{ 1,...,t\} $ (зная матрицу $A$) криптоаналитик должен верно выбрать ${\bf z}_{i} $ из $q^{m}$ равновозможных альтернатив (иными словами, случай непересекающихся $m$-плоскостей не дает криптоаналитику никакой дополнительной информации о секретных ключах за исключением того, что все они различны).

В силу конструкции последовательности (3) информационный и избыточный блоки произвольной криптограммы ${\bf y}_{i}$ статистически независимы. Откуда получаем, что если среди ${\bf z}_{1} ,...,{\bf z}_{t} $ нет одинаковых, то для $\forall i \in \{ 1,...,t\} $

\begin{displaymath} P\{{\bf x}_{i} = {\bf x}_{i}^{0} \vert{\bf y}_{i} ;{\bf u}_... ...{0} \vert\left( {y_{f_{1}} ^{i} ,...,y_{f_{m}} ^{i}} \right)\} \end{displaymath}

Последнее соотношение, в силу того, что $V_{m} $ образует группу относительно покомпонентного сложения векторов, дает: для любого $i \in \{ 1,...,t\} $ справедливо (с учетом (4)):

\begin{displaymath} P\{{\bf x}_{i} = {\bf x}_{i}^{0} \vert{\bf y}_{i} \} = P\{{... ...}_{i} = {\bf x}_{i}^{0} \} = {\textstyle{{1} \over {q^{m}}}}. \end{displaymath}

Проанализируем ситуацию с возникновением в последовательности ${\bf z}_{1} ,...,{\bf z}_{t} $ (которая строится согласно описанной выше схеме) повторяющихся элементов. Обозначим последовательность информационных компонент векторов ${\bf z}_{1} ,...,{\bf z}_{t} $ следующим образом

\begin{displaymath} \{ z\} _{f} = z_{f_{1}} ^{1} ,...,z_{f_{m}} ^{1} ,...,z_{f_{1}} ^{t} ,...,z_{f_{m}} ^{t} . \end{displaymath} (5)

Зафиксируем первые $m$ компонент последовательности $\{ z\} _{f} $, то есть вектор ${\bf s}_{1} = z_{f_{1}} ^{1} ,...,z_{f_{m}} ^{1} $. Всего существует $q^{m}$ различных векторов над $GF\left( {q} \right)$ длины $m$. Задачу о повторном появлении вектора ${\bf s}_{1} $ в последовательности (5) можно поставить в контексте следующей классической вероятностной задачи. Рассматривается процесс, на каждом шаге которого осуществляется случайная выборка с возвращением из генеральной совокупности объема $q^{m}$, каждый элемент выбирается с равной вероятностью (равной ${\textstyle{{1} \over {q^{m}}}}$), $s_{r} $- элемент, выбранный на $r$-том шаге. Процесс прекращается, как только в последовательности из $r$ выбранных элементов $s_{r} = s_{1} ,r > 1$. Какова вероятность $P_{r} $ того, что процесс продолжится после $r$-того шага? Хорошо известно (см. [5]), что

\begin{displaymath} P_{r} = \left( {1 - {\textstyle{{1} \over {q^{m}}}}} \right)^{r}. \end{displaymath}

Для некоторого фиксированного $\varepsilon > 0$ запишем следующее условие:

\begin{displaymath} 1 - \varepsilon < \left( {1 - {\textstyle{{1} \over {q^{m}}}}} \right)^{c_{\varepsilon} \cdot q^{m}} < 1, \end{displaymath}

где $c_{\varepsilon} \in ]0,1[$, смысл которого очевиден (если предположить, что $r = q^{m} \cdot \alpha (m)$, где $\alpha (m) \to 0$ с ростом $m$, то $P_{r} \to 1$).

При достаточно больших $m$ получаем приблизительную оценку для $c_{\varepsilon} $:

\begin{displaymath} 0 < c_{\varepsilon} < \ln{\textstyle{{1} \over {1 - \varepsilon}}}. \end{displaymath}

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

Замечание. Если в описанной схеме по открытому каналу передаются только векторы ${\bf u}_{1} ,...,{\bf u}_{t} $, то схема представляется собой протокол обмена между двумя пользователями "почти" случайной (в оговоренном выше смысле) последовательностью элементов поля $GF\left( {q} \right)$.

Дополнительные конструкции, уточнения и эффективность.

Определим класс матриц, являющихся базовыми объектами для построения описанной криптосистемы. Легко видеть, что для этой цели "подходят" матрицы

\begin{displaymath} A = \left\Vert {{\begin{array}{*{20}c} {} \hfill & {} \hf... ... \hfill \\ \end{array}} } \right\Vert, \quad C = A\vert B \end{displaymath}

где $G,F$- невырожденные над $\Im $ квадратные матрицы размерности ${\textstyle{{n} \over {2}}} \times {\textstyle{{n} \over {2}}}$). Дополнительно необходимо потребовать, чтобы матрицы $G$ и $F$ имели "случайную структуру".

Например в качестве $G$ и $F$ можно рассматривать верхнетреугольные матрицы с элементами из $\Im $ (на главной диагонали стоят ненулевые элементы поля) или произведения таких матриц.

Совершенно очевидно, что описанную выше конструкцию можно перенести и на бесконечные тела и, в частности, на $R$. В данном случае множества решений вырожденных систем линейных уравнений типа ${\bf z} \cdot A = {\bf u}$ представляют собой "плоскости" в $R^{n}$ размерности ${\textstyle{{n} \over {2}}}$ (такие "плоскости" являются смежными классами векторов ${\bf u} \in R^{n}$, таких, что $rank\left( {A\vert{\bf u}^{t}} \right) = rankA$ по подпространству решений системы $z \cdot A = 0$, которое, в свою очередь, изоморфно $R^{{\textstyle{{n} \over {2}}}}$).

На каждой плоскости вводится полная лебегова мера, имеющая смысл площади любой измеримой по Лебегу области рассматриваемой плоскости. Такая мера в общем случае $\sigma $-конечна (и $\sigma $-аддитивна) и от нее можно при помощи стандартных конструкций перейти к вероятностной мере.

Каждый фиксированный открытый текст (вектор из $R^{n}$) представлен на соответствующей плоскости некоторой точкой и имеет нулевую меру, таким образом,

\begin{displaymath} P\{{\bf x}_{i} = {\bf x}_{i}^{0} \} = 0, \end{displaymath}

более того, нетрудно видеть, что событие "в последовательности ${\bf z}_{1} ,...,{\bf z}_{t} ,...$ есть совпадающие элементы" имеет нулевую вероятность (каждый вектор ${\bf z}_{i} $ данной последовательности получается в результате ${\textstyle{{n} \over {2}}}$ кратного "случайного бросания" точки на числовую прямую $R^{1}$). Таким образом, все плоскости почти наверное различны и в силу тех же причин, что и для дискретного случая не пересекаются. Применяя схему порождения секретных ключей и избыточных символов в векторах открытого текста, аналогичную описанной выше, получим самый сильный вариант совершенной секретности:

\begin{displaymath} P\{ {\bf x}_{i} = {\bf x}_{i}^{0} \vert{\bf y}_{i} \} = P\{... ...i} = {\bf x}_{i}^{0} \} = 0, \quad \forall i \in \{ 1,...,t\} \end{displaymath}

(в тех же терминах). В данном контексте можно говорить о том, что криптоаналитик, располагая даже счетным множеством шифртекста, оказывается в положении, в котором он вынужден решать некоторую "вырожденную задачу".

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

Последний тезис можно несколько развить. Снова рассматриваем случай поля $\Im = GF\left( {q} \right)$. Отношение $\Theta = {\textstyle{{K} \over {k}}}$, где $K$- общее число символов в передаваемом по открытому каналу сообщении, а $k$- число информационных символов, назовем избыточностью криптосистемы. Обозначим через $\Sigma $-общий объем символов (например, бит), передаваемый для организации криптосистемы по секретному каналу, $\Lambda $- общий объем символов (бит), составляющих пространство ключей, которое можно сформировать, используя один раз секретный канал для передачи $\Sigma $ символов так, чтобы каждая криптограмма оставалась совершенно секретной (с вероятностью, отличающейся от 1 на заданную малую (быть может нулевую) константу $\varepsilon $), тогда можно определить величину $\Omega = \Theta \cdot {\textstyle{{\Sigma} \over {\Lambda} }}$- коэффициент практичности криптосистемы. Очевидно, что для криптосистемы Вернама (непрактичной) $\Omega _{Vern} = 1$ (в криптосистеме Вернама $\varepsilon = 0$).

Следующее утверждение (с учетом сделанных замечаний) фактически является следствием теоремы 1.

Теорема 2.
Для любого натурального $k \in N$ можно построить криптосистему описанного типа над полем $GF\left( {q} \right)$, такую, что:

1. криптосистема избыточна с $\Theta = 3$,

2. существует такая константа $c \in ]0,1[$, что передав однократно по секретному каналу

\begin{displaymath} \left( {{\textstyle{{n + n^{2}} \over {2}}}} \right) \cdot ]\log q[ \end{displaymath}

бит секретной информации, можно передать по открытому каналу

\begin{displaymath} {\textstyle{{n} \over {2}}} \cdot q^{\left[ {{\textstyle{{c \cdot n} \over {2}}}} \right]} \cdot [\log q] \end{displaymath}

бит шифртекста, при этом каждая из $q^{\left[ {{\textstyle{{c \cdot n} \over {2}}}} \right]}$ криптограмм с вероятностью отличной от 1 на заранее заданную малую константу является совершенно секретной ($n = 2 \cdot k$).

Первый пункт очевиден. Относительно справедливости второго достаточно заметить, что при произвольной разумной схеме кодирования каждый элемент поля $GF(q)$ кодируется не более, чем $ ]\log q[$ битами двоичного кода.

Различные криптосистемы можно сравнивать по параметру $\Omega $. Например, если для двух криптосистем (1 и 2) имеет место

\begin{displaymath} \mathop {lim}\limits_{k \to \infty} {\textstyle{{\Omega _{2}} \over {\Omega _{1}} }} = 0, \end{displaymath}

то про криптосистему 2 можно сказать, что она асимптотически более практичная, чем 1. Каждой константе $c \in ]0,1[$ поставим в соответствие величину ${\textstyle{{1} \over {q^{c \cdot k}}}}$ как показатель практичности некоторой "идеальной" криптосистемы $\Gamma _{c}^{\ast}$ над полем $GF(q)$, у такой криптосистемы открытый текст состоит из $k$ символов поля (количество информационных символов).

Для произвольной криптосистемы $\Gamma $ над $GF(q)$, у которой количество информационных символов есть $k$ введем функцию сравнения

\begin{displaymath} F_{c} \left( {\Gamma} \right) = {\textstyle{{\Omega _{\Gamm... ...mma _{c}^{\ast} } } }} = q^{c \cdot k} \cdot \Omega _{\Gamma} \end{displaymath}

для $\forall c \in ]0,1[$.

Следующее определение согласуется с принятыми парадигмами теории вычислительной сложности (см. [1]).

Определение.
По определению криптосистема $\Gamma $ считается эффективной, если $\exists c \in ]0,1[$, такая, что

\begin{displaymath} F_{c}(\Gamma) = O(poly(k)), \end{displaymath} (6)

где $poly(\cdot)$ - некоторый полином и неэффективной, в противном случае (то есть когда $\forall c \in ]0,1[$ $F(\Gamma) = O(q^{c \cdot k}),c > 0$)

Для эффективных криптосистем эффективность тем выше, чем ниже степень соответствующего полинома $poly(k)$.

Для криптосистемы, предложенной в данной работе, $\exists c \in ]0,1[$, такая, что имеет место (6) и при этом $\deg (poly(k)) = 1$, поэтому ее можно считать очень эффективной.

Литература

  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. ``Мир'' 1982. 416с.
  2. МакВильямс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М., ``Связь'', 1979. 744с.
  3. Шеннон К. Э. Теория связи в секретных системах. В кн.: Шеннон К.Э. Работы по теории информации и кибернетике. М.: ИЛ, 1963, с. 333-402.
  4. Шеннон К. Э. Математическая теория связи В кн.: Шеннон К.Э. Работы по теории информации и кибернетике. М.: ИЛ, 1963, с. 243-332.
  5. Феллер В. Введение в теорию вероятностей и ее приложения. т.1 М.: Мир, 1984. 527с.
Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Tuesday, 14-Aug-2001 21:21:28 NOVST