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

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

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

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

[math]\displaystyle{ \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 }[/math]

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

[math]\displaystyle{ \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\} }[/math]

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

[math]\displaystyle{ 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} }[/math]

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

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

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

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

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

[math]\displaystyle{ s(x) \equiv \sum_{i=0}^{n-1} \frac{c_i}{x - L_i} \mod g(x) }[/math]

Альтернативная форма матрицы контроля чётности основана на формуле для [math]\displaystyle{ s(x) }[/math] и может быть использована для создания такого синдрома с простым произведением матриц.

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

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

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

Если исходный ключ был декодирован и [math]\displaystyle{ e=(e_0,e_1,\dots,e_{n-1}) }[/math] — двоичный вектор ошибок, то:

[math]\displaystyle{ \sigma(x) = \prod_{i=0}^{n-1} e_i(x-L_i) }[/math].

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

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

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

Благодаря способности исправления ошибок, с учётом высокой скорости кодирования и сложной формы матрицы проверки на чётность (которую обычно трудно отличить от случайной двоичной матрицы того же ранга) двоичные коды Гоппы используются в нескольких постквантовых криптосистемах, в частности, в криптосистеме 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.