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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двоичные коды Гоппы обладают специфическим свойством — они исправляют все ${\displaystyle \deg(g)}$ ошибок, в то время как троичные и прочие коды исправляют только ${\displaystyle \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 :
• Daniel J. Bernstein. (англ.) // Department of Computer Science University of Illinois at Chicago. — 2008.