«Обратное» исправление ошибок Рида-Соломона с заданным префиксом ввода

у меня есть строка $S$ длины (скажем) 34, что я знаю первые (скажем) 24 байта, но не последние 10. У меня также есть 10-байтовый код исправления ошибок $RS_{44,34}(С)$ в полном объеме. Есть ли у меня надежда на выздоровление $S$?

Количество информации о $S$ что мне не хватает, намного превышает теоретическую гарантию Рида-Соломона (которая, я думаю, в данном случае составляет 3 байта), но в то же время есть $2^{80}$ возможные значения для неизвестной части $S$, а также $2^{80}$ возможные выходы для исправления ошибок. Если бы мы перебрали все возможные значения для неизвестной части $S$, я бы наивно ожидал, что примерно 1 из них будет соответствовать исправлению ошибок. Но $2^{80}$ слишком много для грубой силы.

Существуют ли какие-либо методы, которые могли бы восстановить (или, по крайней мере, уменьшить пространство состояний) вход, учитывая его EC Рида-Соломона? Есть ли основания так или иначе думать, что RS в этом смысле криптографически безопасен?

Для фона, приложение «реального мира» здесь заключается в том, что у меня есть QR-код (версия 2, L-уровень EC), где у меня нет основных битов данных, но у меня есть биты EC. Я знаю, что данные представляют собой URL-адрес определенного домена, поэтому префикс.

Существуют ли какие-либо методы, которые могли бы восстановить (или, по крайней мере, уменьшить пространство состояний) вход, учитывая его EC Рида-Соломона?

Вам повезло — код Рида-Соломона является линейным, то есть секция исправления ошибок является линейной функцией ввода, и фактически, фиксируя все, кроме 10 байтов ввода, это биекция.

Это означает, что вы можете эффективно восстановить недостающие 10 байтов ввода; Исключение Гаусса будет работать, и хотя, вероятно, будут доступны более эффективные алгоритмы, исключение Гаусса займет примерно $10^3$ операции, и поэтому это может быть достаточно эффективным.

Не все коды обладают хорошим свойством, которым обладают коды RS, а именно то, что каждый $к$ символы представляют собой информационный набор, который можно использовать для восстановления исходного кодового слова.

Есть эффективные декодеры стирания там. Стирание означает, что некоторые символы неизвестны, а не просто ошибочны.

Например, это недавняя статья представляет эффективный алгоритм декодирования кодов РС над конечным полем с $q$ элементы, $\mathbb{F}_q$ с $д=2^м,$ в $ О (д \ log_q д ^ 2) $ время. Он использует преобразования Уолша для интерполяции Лагранжа.