В математике и информатике , то двоичный код Гоппы является кодом коррекции ошибок , который принадлежит к классу общих кодов Гоппы первоначально описанному Валерий Денисович Гоппа , но бинарная структура дает ему несколько математических преимуществ перед небинарными вариантами, также обеспечивая лучше подходит для общего использования в компьютерах и телекоммуникациях. Двоичные коды Гоппа обладают интересными свойствами, подходящими для криптографии в криптосистемах типа Мак-Элиса и аналогичных установках.
Строительство и свойства [ править ]
Двоичный код Гоппы определяются многочленом степени над конечным полем без кратных нулей, и последовательность из различных элементов из , которые не являются корнями полинома:
Кодовые слова принадлежат ядру синдромной функции, образуя подпространство :
Код, определенный кортежем, имеет минимальное расстояние , поэтому он может исправлять ошибки в слове размера, используя кодовые слова размера . Он также имеет удобную матрицу проверки на четность в виде
Обратите внимание, что эта форма матрицы проверки на четность, состоящая из матрицы Вандермонда и диагональной матрицы , разделяет форму с проверочными матрицами альтернативных кодов , таким образом, альтернативные декодеры могут использоваться в этой форме. Такие декодеры обычно предоставляют лишь ограниченную возможность исправления ошибок (в большинстве случаев ).
Для практических целей, проверочная матрица двоичного кода Гоппы обычно преобразуется в более компьютерно-дружественном двоичную форму построения следа, который преобразует матрицу с размерностью матрица над к матрице с размерностью бинарной матрицы, записывая полиномиальные коэффициенты элементов в последовательных рядах.
Расшифровка [ править ]
Декодирование двоичных кодов Гоппы традиционно выполняется с помощью алгоритма Паттерсона, который дает хорошие возможности исправления ошибок (он исправляет все ошибки проектирования), а также довольно прост в реализации.
Алгоритм Паттерсона преобразует синдром в вектор ошибок. Предполагается, что синдром двоичного слова примет форму
Альтернативная форма матрицы проверки на четность, основанная на формуле для, может быть использована для создания такого синдрома с помощью простого умножения матриц.
Затем алгоритм вычисляет . Это не удается, когда , но это тот случай, когда входное слово является кодовым словом, поэтому исправление ошибок не требуется.
сводится к полиномам и с помощью расширенного алгоритма Евклида , так что , пока и .
Наконец, полином локатора ошибок вычисляется как . Обратите внимание, что в двоичном случае поиска ошибок достаточно для их исправления, поскольку возможно только одно другое значение. В недвоичных случаях также должен быть вычислен отдельный полином исправления ошибок.
Если исходное кодовое слово было декодируемым и это был двоичный вектор ошибок, то
Таким образом, факторинг или оценка всех корней дает достаточно информации для восстановления вектора ошибок и исправления ошибок.
Свойства и использование [ править ]
Двоичные коды Гоппы, рассматриваемые как частный случай кодов Гоппа, обладают тем интересным свойством, что они исправляют все ошибки, в то время как ошибки только в троичных и всех других случаях. Асимптотически эта возможность исправления ошибок соответствует известной границе Гилберта – Варшамова .
Из-за высокой способности исправлять ошибки по сравнению со скоростью кода и формой матрицы проверки на четность (которая обычно трудно отличить от случайной двоичной матрицы полного ранга), двоичные коды Гоппа используются в нескольких постквантовых криптосистемах , особенно в криптосистеме Мак-Элиса. и криптосистема Нидеррайтера .
Ссылки [ править ]
- Элвин Р. Берлекамп, Коды Гоппы, Транзакции 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