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

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

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

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

$\mathrm{\forall }i,j\in \{0,\dots ,n-1\}:L_i\in GF(2^m)\wedge (L_i=L_j⟹i=j)\wedge g(L_i)\ne 0$

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

$\mathrm{\Gamma }(g,L)=\{c\in \{0,1{\}}^n|\sum _{i=0}^{n-1}\frac{c_i}{x-L_i}\equiv 0modg(x)\}$

Код определён, как пара $(g,L)$ с минимальной длиной $2t+1$, таким образом, он может исправить $t=\lfloor \frac{(2t+1)-1}{2}\rfloor$ ошибок в слове длиной $n-mt$, используя ключи размером $n$. Он также обладает удобной Шаблон:Iw $H$ в виде:

$H=VD=\left(\begin{array}{ccccc}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\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ L_0^{t-1}& L_1^{t-1}& L_2^{t-1}& \cdots & L_{n-1}^{t-1}\end{array}\right)\left(\begin{array}{ccccc}\frac{1}{g(L_0)}& & & & \\ & \frac{1}{g(L_1)}& & & \\ & & \frac{1}{g(L_2)}& & \\ & & & \ddots & \\ & & & & \frac{1}{g(L_{n-1})}\end{array}\right)$

Эта форма матрицы контроля чётности состоит из определителя Вандермонда $V$ и диагональной матрицы $D$, имеет форму, схожую с проверочными матрицами Шаблон:Iw. Таким образом, в этой форме могут использоваться альтернативные декодеры. Они обычно обеспечивают только ограниченную возможность исправления ошибок (чаще всего $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}modg(x)$

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

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

Использованием расширенного алгоритма Евклида $v(x)$ сводится к многочленам $a(x)$ и $b(x)$, так, что $a(x)\equiv b(x)\cdot v(x)modg(x)$, при этом $\mathrm{deg}(a)⩽\lfloor t/2\rfloor$ и $\mathrm{deg}(b)⩽\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)$ дает достаточно информации, чтобы восстановить вектор ошибок и исправить их.

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Статья Шаблон:MR Предыдущая версия
• Шаблон:Статья