Solving undetermined systems of linear boolean equations with corrupted right-hand side and low-weight true solution.pdf Рассмотрим систему из фиксированного числа m < n линейных булевых уравнений (СЛУ) Ax = b = Axo 0 С, (1) где A - случайная двоичная матрица размера m х n; СT = (Со,..., Ст-1) - случайный двоичный вектор ошибок, координаты которого независимы и принимают значения с вероятностями Р{С = 1} = 1 - Р{С = 0} = p, i Е {0,... ,m - 1}, p Е [0,1/2); x0 - вектор истинного решения, ||x0|| = w, ||.|| -вес Хемминга. Для малых значений w известны алгоритмы решения таких систем, основанные на переборе возможных значений истинного решения [1, 2]. В алгоритме максимума правдоподобия [1] непосредственно вычисляются все возможные векторы y длины n веса w ив качестве решения выдаётся вектор с наименьшим значением || Ay ||. Алгоритм имеет асимптотическую сложность 0((1 - 2p)-2nw log n) при использовании 0(1) бит дополнительной (помимо хранения системы уравнений) памяти [2]. В работе [2] рассматривается вычислительно более эффективный алгоритм на основе метода «встречи посередине» с емкостной сложностью 0(nw/2) и вычислительной сложностью 0(nw/2l((m - t) log nw/2 + wm)), где t - пороговое значение || Ay||; l - число итераций. Вычислительная сложность алгоритмов данного класса более всего зависит от параметра w, что делает их малоприменимыми для слабоискажённых систем с достаточно большим весом истинного решения. С другой стороны, матрицу A можно рассматривать как проверочную матрицу некоторого случайного линейного блокового кода M(n, n - m), для которого вектор b является синдромом ошибки веса w, причём каждый бит синдрома дополнительно искажён с вероятностью p. Задача решения системы (1), таким образом, состоит в декодировании случайного кода по искажённому синдрому. Составим расширенную систему (2) Ch = b, где C = [I | A ] , I - единичная матрица размера m х m; hT = [ С | x0 ] и [ ■ | ■ ] обозначает конкатенацию. В системе (2) правая часть уже «неискажённая», при этом вектор решения имеет некоторый случайный вес w + t, где t зависит только от m и p. По условию p ^ 1 /2, поэтому с большой вероятностью вес решения по-прежнему останется малым. В рассмотренной постановке матрица C является проверочной матрицей для некоторого случайного кода M'(n + m,n). Известно [3], что почти все случайные коды лежат на границе Варшамова - Гилберта, т.е. код M'(n + m,n) почти наверное исправляет все ошибки кратности до d-2 |_(d - 1)/2_|, где d удовлетворяет неравенству 2m ^ Е (га+™- ). Таким образом, при i=0 г достаточно малых значениях вероятности искажения p для решения системы (2) могут быть использованы алгоритмы декодирования по информационным множествам, большое количество которых было разработано в рамках криптоанализа систем Мак-Элиса и Нидеррайтера [4]. Для оценки эффективности предлагаемого способа использован алгоритм Мэя - Мюэра - Томае [4] (ALG0RITHM 2), сравнение проводилось с алгоритмом из работы [2] (ALG0RITHM 1), результаты среднего времени выполнения приведены в табл. 1 и 2. Проведённые эксперименты показывают, что для достаточно малых вероятностей искажения предложенный способ позволяет находить истинное решение более эффективно, чем перебор возможных решений. Таблица 1 СЛУ с искажённой правой частью, n = 256, m = 128, w = 8 Вероятность искажения p Среднее время выполнения, c ALGORITHM 1 ALGORITHM 2 0,001 144,284 0,062 0,005 164,131 0,120 0,010 191,219 0,355 0,020 305,235 1,625 Та б л и ц а 2 СЛУ с искажённой правой частью, n = 512, m = 200, w = 10 Вероятность искажения p Среднее время выполнения, c ALGORITHM 1 ALGORITHM 2 0,001 > 7200 12,100 0,005 > 7200 49,021 0,010 > 7200 109,960 0,020 > 7200 576,460

Скачать электронную версию публикации