размерность кодов Гоппы

Для криптосистем МакЭлиса/Нидеррайтера эффективным, казалось бы, безопасным выбором кода является неприводимый двоичный код Гоппы, определяемый неприводимым $g(x)\in GF(2^m)[x]$ степени $t$ и опорный вектор $L=(\alpha_0,\ldots,\alpha_{n-1})$ с отчетливым $\alpha_i\in GF(2^m)$.

Сам код является $GF(2)$-значные векторы в ядре проверочной матрицы $$ Н=\влево( \begin{массив}{cccc} g(\alpha_0)^{-1}&g(\alpha_1)^{-1}&\ldots&g(\alpha_{n-1})^{-1}\ g(\alpha_0)^{-1}\alpha_0&g(\alpha_1)^{-1}\alpha_1&\ldots&g(\alpha_{n-1})^{-1}\alpha_{n-1}\ \vdots&\vdots&\ldots&\vdots\ g(\alpha_0)^{-1}\alpha_0^{t-1}&g(\alpha_1)^{-1}\alpha_1^{t-1}&\ldots&g(\alpha_{n-1})^{ -1}\alpha_{n-1}^{t-1}\ \конец{массив}\справа). $$ Обратите внимание, что $Ч$ является полноценным. Чтобы создать матрицу проверки на четность $H'$ над $GF(2)$, можно заменить записи $Ч$ с векторами-столбцами в $GF(2)$ (используя некоторую основу для расширения $GF(2^m)/GF(2)$).

Почти все источники, с которыми я консультируюсь, перечисляют полученный код как $[n,k]=[n, n-mt]$, но общая конструкция (скажем, для альтернативных кодов) дает $k=n-mt$ как нижняя граница для размера $к$ полученного кода подпространства.

Мои вопросы:

1. Как часто полученный ранг $k=n-mt$? В установке AG, я думаю, это размерность Римана-Роха, поэтому, возможно, алгебраический геометр сможет ответить.
2. Имеет ли значение, если у нас есть избыточные строки в проверке четности? $H'$? Влияет ли это на реализацию криптосистемы?

Я предполагаю, что это адресовано в генераторе ключей от https://eprint.iacr.org/2017/595.pdf (раздел 5.2), хотя бы для возврата ошибки и перезапуска процесса генерации ключа, когда rref не достигнут; они дают 29% как вероятность успеха, основанную на плотности $GL_{мт}(GF(2))$ в $Mat_{mt\times mt}(GF(2))$, т. е. асимптотическая плотность $$ \prod_{i=1}^{\infty}\left(1-\frac{1}{2^i}\right)=0,288\ldots. $$

Если подумать о 1), я думаю, это больше вопрос о том, когда ядро ​​​​линейной карты определяется над подполем (например, ядро $х-\sqrt{2}у$ имеет размерность один больше $\mathbb{Q}(\sqrt{2})$ но размерность нулевая, когда она ограничена $\mathbb{Q}$).

1. С эвристической точки зрения (для параметров, представляющих криптографический интерес) это довольно маловероятно. Бинарный $n\times(n-r)$ матрицы со случайными элементами имеют менее $2^{-n+r}$ шанс получить недостаточный ранг. Может быть более точный геометрический ответ.

2. Код, вероятно, рассчитывается путем использования преобразований строк, чтобы поместить $H'$ в систематической форме $(Я|А)$ а затем принимая двоичный код Гоппы как $(I|A^t)$. Если $H'$ является недостаточным по рангу, тогда реализация должна иметь средства обнаружения того, что полная систематическая форма не была достигнута, и отбрасывания оставшихся строк $H'$. Если ранг $H'$ является $г$ тогда наша матрица генератора бинарного кода Гоппы будет $n\times(n-r)$ что, вероятно, больше, чем выделенная память (и добавляет к уже болезненным проблемам с пропускной способностью). Некоторые строки матрицы генератора теперь должны быть удалены. Мы хотим избежать избыточных столбцов, чтобы усложнить декодирование информационного набора, поэтому мы, вероятно, захотим случайным образом не систематизировать генераторную матрицу перед удалением строк, перестановкой столбцов и повторной систематизацией. Затем возникает интересная проблема, заключающаяся в том, что искажения удаленных строк могут быть представлены нашему декодеру и успешно восстановлены до чего-то, что не находится в диапазоне нашей порождающей матрицы, но наш декодер, вероятно, будет использовать нашу ресистематизированную матрицу, чтобы сопоставить ее с диапазоном нашей порождающей матрицы. генераторная матрица. Реализации вряд ли будут готовы к этому и могут демонстрировать непредсказуемое поведение. В общем, наверное, лучше взять новый. $г(Х)$ и начать сначала.