Двоичный код Goppa

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

Строительство и свойства [ править ]

Двоичный код Гоппы определяются многочленом степени над конечным полем без кратных нулей, и последовательность из различных элементов из , которые не являются корнями полинома:${\ 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} \ следует i = j) \ land g (L_ {i}) \ neq 0}$

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

${\ 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 (г, L)}$${\ displaystyle 2t + 1}$${\ displaystyle \ 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)\leq \lfloor t/2\rfloor }$${\displaystyle \deg(b)\leq \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}$

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

Ссылки [ править ]

• Элвин Р. Берлекамп, Коды Гоппы, Транзакции 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

См. Также [ править ]

• Коды BCH
• Кодовая скорость
• Исправление ошибок Рида – Соломона