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

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

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

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

$\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}$:

$\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)$ с минимальной длиной $2t+1$, таким образом, он может исправить $t=\left\lfloor {\frac {(2t+1)-1}{2}}\right\rfloor$ ошибок в слове длиной $n-mt$, используя ключи размером $n$. Он также обладает удобной матрицей контроля чётности $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$ и диагональной матрицы $D$, имеет форму, схожую с проверочными матрицами альтернативных кодов. Таким образом, в этой форме могут использоваться альтернативные декодеры. Они обычно обеспечивают только ограниченную возможность исправления ошибок (чаще всего $t/2$).

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

Декодирование

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

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

$s(x)\equiv \sum _{i=0}^{n-1}{\frac {c_{i}}{x-L_{i}}}\mod g(x)$

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

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

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

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

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

$\sigma (x)=\prod _{i=0}^{n-1}e_{i}(x-L_{i})$.

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

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

Двоичные коды Гоппы обладают специфическим свойством — они исправляют все $\deg(g)$ ошибок, в то время как троичные и прочие коды исправляют только $\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.