Двоичный код Гоппы

Двоичный код Гоппы — код коррекции ошибок из класса общих кодов Гоппы^[en], описан Валерием Денисовичем Гоппой. В сравнении с другими вариантами, бинарная структура даёт несколько математических преимуществ, а также подходит для общего использования в вычислительной технике и телекоммуникациях. Двоичные коды Гоппы обладают интересными свойствами, полезными в криптосистемах, подобных McEliece.

Строение и свойстваПравить

Двоичный код Гоппы определяется как многочлен $g(x)$$g(x)$  степени $t$$t$  над конечным полем $GF(2^m)$$GF(2^{m})$  без конечного числа нулей, и последовательность $L$$L$  из $n$$n$  различных элементов $GF(2^m)$$GF(2^{m})$ , которые не являются корнями или полиномами.

$\mathrm{\forall <!--\; \forall \; -->}i,j\in <!--\; \in \; -->\{0,\dots <!--\; \dots \; -->,n-<!--\; -\; -->1\}:L_i\in <!--\; \in \; -->GF(2^m)\wedge <!--\; \wedge \; -->(L_i=L_j⟹<!--\; ⟹\; -->i=j)\wedge <!--\; \wedge \; -->g(L_i)\ne <!--\; \ne \; -->0$$\forall i,j\in \{0,\ldots ,n-1\}:L_{i}\in GF(2^{m})\land (L_{i}=L_{j}\implies i=j)\land g(L_{i})\neq 0$ 

Ключи принадлежат ядру функции, формируя подпространство $\{0,1{\}}^n$$\{0,1\}^n$ :

$\mathrm{\Gamma <!--\; \Gamma \; -->}(g,L)=\left\{c\in <!--\; \in \; -->\{0,1{\}}^n|\underset{i=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\frac{c_i}{x-<!--\; -\; -->L_i}\equiv <!--\; \equiv \; -->0\mathrm{mod}g(x)\right\}$$\Gamma (g,L)=\left\{c\in \{0,1\}^{n}\left|\sum _{i=0}^{n-1}{\frac {c_{i}}{x-L_{i}}}\equiv 0\mod g(x)\right.\right\}$ 

Код определён, как пара $(g,L)$$(g,L)$  с минимальной длиной $2t+1$$2t+1$ , таким образом, он может исправить $t=\lfloor \frac{(2t+1)-<!--\; -\; -->1}{2}\rfloor$$t=\left\lfloor {\frac {(2t+1)-1}{2}}\right\rfloor$  ошибок в слове длиной $n-<!--\; -\; -->mt$$n-mt$ , используя ключи размером $n$$n$ . Он также обладает удобной матрицей контроля чётности^[en] $H$$H$  в виде:

$H=VD={\begin{pmatrix}1&1&1&\cdots &1\\L_{0}^{1}&L_{1}^{1}&L_{2}^{1}&\cdots &L_{n-1}^{1}\\L_{0}^{2}&L_{1}^{2}&L_{2}^{2}&\cdots &L_{n-1}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\L_{0}^{t-1}&L_{1}^{t-1}&L_{2}^{t-1}&\cdots &L_{n-1}^{t-1}\end{pmatrix}}{\begin{pmatrix}{\frac {1}{g(L_{0})}}&&&&\\&{\frac {1}{g(L_{1})}}&&&\\&&{\frac {1}{g(L_{2})}}&&\\&&&\ddots &\\&&&&{\frac {1}{g(L_{n-1})}}\end{pmatrix}}$ 

Эта форма матрицы контроля чётности состоит из определителя Вандермонда $V$$V$  и диагональной матрицы $D$$D$ , имеет форму, схожую с проверочными матрицами альтернативных кодов^[en]. Таким образом, в этой форме могут использоваться альтернативные декодеры. Они обычно обеспечивают только ограниченную возможность исправления ошибок (чаще всего $t/2$$t/2$ ).

Для практических целей матрица проверки на чётность кода Гоппы обычно преобразуется в более удобную для использования компьютером двоичную форму с помощью конструкции трассировки, которая преобразует $t$$t$ -на-$n$$n$  матрицу над $GF(2^m)$$GF(2^{m})$  в двоичную матрицу $mt$$mt$ -на-$n$$n$ , разделив полиномиальные коэффициенты $GF(2^m)$$GF(2^{m})$  на $m$$m$  последовательных рядов.

ДекодированиеПравить

Обычно декодирование двоичного кода Гоппы производится алгоритмом Паттерсона, который способен эффективно исправлять ошибки (он исправляет все $t$$t$  обнаруженные ошибки^{[уточнить]}), и который также достаточно прост в реализации.

Алгоритм Паттерсона преобразует синдром в вектор ошибок. Предполагается, что синдром двоичного слова $c=(c_0,\dots <!--\; \dots \; -->,c_{n-<!--\; -\; -->1})$$c=(c_{0},\dots ,c_{n-1})$  примет вид:

$s(x)\equiv <!--\; \equiv \; -->\underset{i=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\frac{c_i}{x-<!--\; -\; -->L_i}\mathrm{mod}g(x)$$s(x)\equiv \sum _{i=0}^{n-1}{\frac {c_{i}}{x-L_{i}}}\mod g(x)$ 

Альтернативная форма матрицы контроля чётности основана на формуле для $s(x)$$s(x)$  и может быть использована для создания такого синдрома с простым произведением матриц.

Далее алгоритм производит расчёт $v(x)\equiv <!--\; \equiv \; -->\sqrt{s(x{)}^{-<!--\; -\; -->1}-<!--\; -\; -->x}\mathrm{mod}g(x)$$v(x)\equiv {\sqrt {s(x)^{-1}-x}}\mod g(x)$ . Это не удается, когда $s(x)\equiv <!--\; \equiv \; -->0$$s(x)\equiv 0$ , но это тот случай, когда входное слово является ключом, поэтому исправление ошибок не требуется.

Использованием расширенного алгоритма Евклида $v(x)$$v(x)$  сводится к многочленам $a(x)$$a(x)$  и $b(x)$$b(x)$ , так, что $a(x)\equiv <!--\; \equiv \; -->b(x)\cdot <!--\; \cdot \; -->v(x)\mathrm{mod}g(x)$$a(x)\equiv b(x)\cdot v(x)\mod g(x)$ , при этом $\mathrm{deg}<!--\; \; -->(a)⩽<!--\; ⩽\; -->\lfloor <!--\; \lfloor \; -->t/2\rfloor <!--\; \rfloor \; -->$$\deg(a)\leqslant \lfloor t/2\rfloor$  и $\mathrm{deg}<!--\; \; -->(b)⩽<!--\; ⩽\; -->\lfloor <!--\; \lfloor \; -->(t-<!--\; -\; -->1)/2\rfloor <!--\; \rfloor \; -->$$\deg(b)\leqslant \lfloor (t-1)/2\rfloor$ .

Наконец, многочлен, определяющий расположение ошибок, вычисляется как $\mathrm{\sigma <!--\; \sigma \; -->}(x)=a(x{)}^2+x\cdot <!--\; \cdot \; -->b(x{)}^2$$\sigma (x)=a(x)^{2}+x\cdot b(x)^{2}$ . При этом в двоичном случае для исправления ошибок достаточно их найти, так как существует только одно отличное значение.

Если исходный ключ был декодирован и $e=(e_0,e_1,\dots <!--\; \dots \; -->,e_{n-<!--\; -\; -->1})$$e=(e_{0},e_{1},\dots ,e_{n-1})$  — двоичный вектор ошибок, то:

$\mathrm{\sigma <!--\; \sigma \; -->}(x)=\underset{i=0}{\overset{n-<!--\; -\; -->1}{\prod <!--\; \prod \; -->}}{e}_i(x-<!--\; -\; -->L_i)$$\sigma (x)=\prod _{i=0}^{n-1}e_{i}(x-L_{i})$ .

Разложение на множители или оценка всех корней $\mathrm{\sigma <!--\; \sigma \; -->}(x)$$\sigma (x)$  дает достаточно информации, чтобы восстановить вектор ошибок и исправить их.

Свойства и использованиеПравить

Двоичные коды Гоппы обладают специфическим свойством — они исправляют все $\mathrm{deg}<!--\; \; -->(g)$$\deg(g)$  ошибок, в то время как троичные и прочие коды исправляют только $\mathrm{deg}<!--\; \; -->(g)/2$$\deg(g)/2$ . Асимптотически такая способность к исправлению ошибок соответствует известной границе Гилберта — Варшамова.

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

ЛитератураПравить

• В. Д. Гоппa. Введение в алгебраическую теорию информации. — Физматлит, 1995.
• Daniela Engelbert, Raphael Overbeck, Arthur Schmidt. A summary of McEliece-type cryptosystems and their securi (англ.) // Journal of Mathematical Cryptology. — 2007. — No. 2. — P. 151—199. MR: 2345114 Предыдущая версия
• Daniel J. Bernstein. ist decoding for binary Goppa codes. Technical report (англ.) // Department of Computer Science University of Illinois at Chicago. — 2008.