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

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

Строительство и недвижимость

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

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

\Gamma (g,L)=\left\{c\in \{0,1\}^{n}\left|\sum _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\equiv 0\mod g(x)\right.\right\}

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

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

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

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

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

Декодирование двоичных кодов Гоппы традиционно выполняется алгоритмом Паттерсона, который дает хорошие возможности исправления ошибок (он исправляет все $t$ ошибки проектирования), а также довольно прост в реализации.

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

s(x)\equiv \sum _{i=1}^{n}{\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)\leq \lfloor t/2\rfloor$ и $\deg(b)\leq \lfloor (t-1)/2\rfloor$ .

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

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

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

Факторизация или оценка всех корней $\sigma (x)$ поэтому дает достаточно информации для восстановления вектора ошибок и исправления ошибок.

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

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

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

Ссылки

Элвин Р. Берлекамп, Коды Гоппы, Транзакции IEEE по теории информации, Vol. IT-19, № 5, сентябрь 1973 г., https://web.archive.org/web/20170829142555/http://infosec.seu.edu.cn/space/kangwei/senior_thesis/Goppa.pdf
Даниэла Энгельберт, Рафаэль Овербек, Артур Шмидт. «Краткий обзор криптосистем типа МакЭлиса и их безопасности». Журнал математической криптологии 1, 151–199. МИСТЕР 2345114 . Предыдущая версия: http://eprint.iacr.org/2006/162/
Дэниел Дж. Бернштейн. «Декодирование списка двоичных кодов Гоппы». http://cr.yp.to/codes/goppalist-20110303.pdf

См. также