Локально декодируемый код

( Локально декодируемый код LDC ) — это код с исправлением ошибок , который позволяет декодировать один бит исходного сообщения с высокой вероятностью, только исследуя (или запрашивая) небольшое количество битов возможно поврежденного кодового слова . Это свойство может быть полезно, скажем, в контексте, когда информация передается по зашумленному каналу, и в определенный момент времени требуется только небольшой подмножество данных и нет необходимости декодировать все сообщение сразу. Обратите внимание, что локально декодируемые коды не являются подмножеством локально проверяемых кодов , хотя между ними есть некоторое перекрытие.

Кодовые слова генерируются из исходного сообщения с использованием алгоритма, который вносит в кодовое слово определенную избыточность; таким образом, кодовое слово всегда длиннее исходного сообщения. Эта избыточность распределяется по кодовому слову и позволяет с высокой вероятностью восстановить исходное сообщение даже при наличии ошибок. Чем более избыточно кодовое слово, тем более устойчиво оно к ошибкам и тем меньше запросов требуется для восстановления части исходного сообщения.

Обзор

Более формально, А. $(q,\delta ,\epsilon )$-локально декодируемый код кодирует $n$-битное сообщение $x$ к $N$-битное кодовое слово $C(x)$ такой, что хоть немного $x_{i}$ сообщения может быть восстановлено с вероятностью $1-\epsilon$ используя алгоритм рандомизированного декодирования, который запрашивает только $q$ биты кодового слова $C(x)$, даже если до $\delta N$ местоположения кодового слова были повреждены.

Более того, идеально гладкий локальный декодер — это такой декодер, который не только всегда генерирует правильный вывод, но и имеет доступ к неповреждённому кодовому слову, для каждого $j\in [q]$ и $i\in [n]$ тот $j^{th}$ запрос на восстановление $i^{th}$ бит однороден $[N]$. (Обозначение $[y]$ обозначает множество $\{1,\ldots ,y\}$). Неформально это означает, что набор запросов, необходимых для декодирования любого заданного бита, равномерно распределен по кодовому слову.

Декодеры локальных списков — еще одно интересное подмножество локальных декодеров. Декодирование списка полезно, когда кодовое слово повреждено более чем в $\delta /2$ места, где $\delta$ — минимальное расстояние Хэмминга между двумя кодовыми словами. В этом случае уже невозможно точно определить, какое исходное сообщение было закодировано, поскольку внутри может быть несколько кодовых слов. $\delta$ расстояние до поврежденного кодового слова. Однако, учитывая радиус $\epsilon$, можно идентифицировать набор сообщений, которые кодируются в кодовые слова, находящиеся внутри $\epsilon$ поврежденного кодового слова. Верхнюю границу размера набора сообщений можно определить по формуле $\delta$ и $\epsilon$.

Локально декодируемые коды также могут быть объединены, при этом сообщение сначала кодируется с использованием одной схемы, а полученное кодовое слово снова кодируется с использованием другой схемы. (Обратите внимание, что в этом контексте конкатенация — это термин, используемый учеными для обозначения того, что обычно называют композицией ; см. ). Это может быть полезно, если, например, первый код имеет некоторые желательные свойства в отношении скорости, но у него есть некоторые нежелательные свойства, такие как создание кодового слова в недвоичном алфавите. Затем второй код может преобразовать результат первого кодирования из недвоичного алфавита в двоичный алфавит. Окончательное кодирование по-прежнему декодируется локально и требует дополнительных шагов для декодирования обоих уровней кодирования.

Длина кодового слова и сложность запроса

Скорость кода относится к соотношению длины его сообщения и длины кодового слова: ${\frac {|x|}{|C(x)|}}$, а количество запросов, необходимых для восстановления 1 бита сообщения, называется сложностью запроса кода.

Скорость кода обратно пропорциональна сложности запроса, но точная форма этого компромисса является серьезной открытой проблемой. Известно, что не существует LDC, которые запрашивают кодовое слово только в одной позиции, и что оптимальный размер кодового слова для сложности запроса 2 экспоненциально зависит от размера исходного сообщения. Однако не существует известных точных нижних границ для кодов со сложностью запроса больше 2. Если подойти к компромиссу со стороны длины кодового слова, то единственные известные коды с длиной кодового слова, пропорциональной длине сообщения, имеют сложность запроса. $k^{\epsilon }$ для $\epsilon >0$ Существуют также промежуточные коды, кодовые слова которых полиномиальны по размеру исходного сообщения и полилогарифмической сложности запроса.

Приложения

Локально декодируемые коды имеют приложения к передаче и хранению данных, теории сложности, структурам данных, дерандомизации, теории отказоустойчивых вычислений и схемам поиска частной информации.

Передача и хранение данных

Локально декодируемые коды особенно полезны для передачи данных по зашумленным каналам. Код Адамара (особый случай кодов Рида-Мюллера) использовался в 1971 году кораблем «Маринер-9» для передачи изображений Марса обратно на Землю. Он был выбран вместо кода с 5 повторениями (где каждый бит повторяется 5 раз), поскольку при примерно одинаковом количестве битов, передаваемых на пиксель, он имел более высокую способность к исправлению ошибок. (Код Адамара подпадает под общую концепцию прямого исправления ошибок и просто оказывается локально декодируемым; фактический алгоритм, используемый для декодирования передачи с Марса, представлял собой общую схему исправления ошибок.)

НРС также полезны для хранения данных, где носитель со временем может быть частично поврежден или устройство чтения подвержено ошибкам. В обоих случаях НРС позволит восстановить информацию, несмотря на ошибки, при условии, что их относительно немного. Кроме того, НРС не требуют декодирования всего исходного сообщения; пользователь может декодировать определенную часть исходного сообщения без необходимости декодировать все сообщение целиком.

Теория сложности

Одним из применений локально декодируемых кодов в теории сложности является усиление жесткости. Используя НРС с полиномиальной длиной кодового слова и полилогарифмической сложностью запроса, можно взять функцию $L:\{0,1\}^{n}\rightarrow \{0,1\}$ это трудно решить для входных данных в худшем случае и разработать функцию $L':\{0,1\}^{N}\rightarrow \{0,1\}$ это трудно вычислить на входных данных в среднем случае.

Учитывать $L$ ограничено только длиной $t$ входы. Тогда мы сможем увидеть $L$ как двоичную строку длины $2^{t}$, где каждый бит $L(x)$ для каждого $x\in \{0,1\}^{t}$. Мы можем использовать локально декодируемый код полиномиальной длины. $C$ с полилогарифмической сложностью запроса, которая допускает некоторую постоянную долю ошибок для кодирования строки, представляющей $L$ чтобы создать новую строку длины $2^{O(t)}=2^{t'}$. Мы думаем об этой новой строке как об определении новой проблемы. $L'$ по длине $t'$ входы. Если $L'$ в среднем легко решить, то есть мы можем решить $L'$ правильно в большой дроби $1-\epsilon$ входных данных, то, используя свойства LDC, используемые для его кодирования, мы можем использовать $L'$ вероятностно вычислить $L$ на всех входах. Таким образом, решение $L'$ для большинства входных данных позволит нам решить $L$ на всех входах, что противоречит нашему предположению, что $L$ сложно работать с входными данными в худшем случае.

Схемы поиска частной информации

Схема поиска частной информации позволяет пользователю получить элемент с сервера, владеющего базой данных, не раскрывая, какой именно элемент был получен. Одним из распространенных способов обеспечения конфиденциальности является наличие $k$ отдельные необщающиеся серверы, на каждом из которых есть копия базы данных. При наличии соответствующей схемы пользователь может делать запросы к каждому серверу, которые по отдельности не раскрывают, какой бит ищет пользователь, но которые вместе предоставляют достаточно информации, чтобы пользователь мог определить конкретный интересующий его бит в базе данных.

Легко видеть, что локально декодируемые коды имеют применение в этой ситуации. Общая процедура изготовления $k$-Схема приватной информации сервера с идеально гладкой $k$-query локально декодируемый код выглядит следующим образом:

Позволять $C$ быть идеально гладким НРС, который кодирует $n$-битные сообщения для $N$-битовые кодовые слова. На этапе предварительной обработки каждый из $k$ серверы $S_{1},\ldots ,S_{k}$ кодирует $n$-битная база данных $x$ с кодом $C$, поэтому каждый сервер теперь хранит $N$-битное кодовое слово $C(x)$. Пользователь, заинтересованный в получении $i^{th}$ немного $x$ случайным образом генерирует набор $k$ запросы $q_{1},\ldots q_{k}$ такой, что $x_{i}$ можно вычислить из $C(x)_{q_{1}},\ldots C(x)_{q_{k}}$ используя локальный алгоритм декодирования $A$ для $C$. Пользователь отправляет каждый запрос на другой сервер, и каждый сервер отвечает запрошенным битом. Затем пользователь использует $A$ вычислить $x_{i}$ из ответов. Поскольку алгоритм декодирования совершенно гладкий, каждый запрос $q_{j}$ равномерно распределен по кодовому слову; таким образом, ни один отдельный сервер не может получить никакой информации о намерениях пользователя, поэтому протокол является конфиденциальным, пока серверы не обмениваются данными.

Примеры

Код Адамара

Код Адамара (или Уолша-Адамара) является примером простого локально декодируемого кода, который отображает строку длины $k$ к кодовому слову длины $2^{k}$. Кодовое слово для строки $x\in \{0,1\}^{k}$ строится следующим образом: для каждого $a_{j}\in \{0,1\}^{k}$, $j^{th}$ бит кодового слова равен $x\odot a_{j}$, где $x\odot y=\sum \limits _{i=1}^{k}x_{i}y_{i}$ (мод 2). Легко видеть, что каждое кодовое слово имеет Хэмминга расстояние ${\frac {n}{2}}$ от любого другого кодового слова.

Алгоритм локального декодирования имеет сложность запроса 2, и все исходное сообщение может быть декодировано с хорошей вероятностью, если кодовое слово будет повреждено менее чем за ${\frac {1}{4}}$ из его битов. Для $\rho <{\frac {1}{4}}$, если кодовое слово повреждено в $\rho$ доли мест, локальный алгоритм декодирования может восстановить $i^{th}$ бит исходного сообщения с вероятностью $1-2\rho$.

Доказательство: задано кодовое слово. $H$ и индекс $i$, алгоритм восстановления $i^{th}$ часть исходного сообщения $x$ работает следующим образом:

Позволять $e^{j}$ обратитесь к вектору в $\{0,1\}^{k}$ у которого есть 1 в $j^{th}$ позиция и 0 в другом месте. Для $y\in \{0,1\}^{k}$, $f(y)$ обозначает один бит в $H$ что соответствует $x\odot y$. Алгоритм выбирает случайный вектор $y\in \{0,1\}^{k}$ и вектор $y'=y\oplus e^{i}$ (где $\oplus$ обозначает побитовое исключающее ИЛИ ). Алгоритм выводит $f(y)\oplus f(y')$ (против 2).

Корректность: По линейности,

$(x\odot y)\oplus (x\odot y')=(x\odot y)\oplus (x\odot (y\oplus e^{i}))=(x\odot y)\oplus (x\odot y)\oplus (x\odot e^{i})=x\odot e^{i}$

Но $(x\odot e^{i})=x_{i}$, поэтому нам просто нужно это показать $f(y)=x\odot y$ и $f(y')=x\odot y'$ с хорошей вероятностью.

С $y$ и $y'$ равномерно распределены (даже несмотря на то, что они зависимы), граница объединения подразумевает, что $f(y)=x\odot y$ и $f(y')=x\odot y'$ с вероятностью по крайней мере $1-2\rho$. Примечание. Чтобы повысить вероятность успеха, можно повторить процедуру с разными случайными векторами и получить ответ большинства.

Код Рида-Мюллера

Основная идея локального декодирования кодов Рида-Мюллера — полиномиальная интерполяция . Ключевой концепцией кода Рида-Мюллера является многомерный полином степени $d$ на $l$ переменные. Сообщение рассматривается как оценка полинома в наборе предопределенных точек. Чтобы закодировать эти значения, из них экстраполируется полином, а кодовое слово представляет собой оценку этого полинома во всех возможных точках. На высоком уровне для декодирования точки этого полинома алгоритм декодирования выбирает набор $S$ точек на линии, проходящей через точку интереса $x$. Затем он запрашивает кодовое слово для оценки полинома в точках $S$ и интерполирует этот полином. Тогда легко вычислить полином в той точке, которая даст $x$. Этот окольный способ оценки $x$ полезен, потому что (а) алгоритм можно повторять, используя разные линии через одну и ту же точку, чтобы повысить вероятность правильности, и (б) запросы равномерно распределяются по кодовому слову.

Более формально, пусть $\mathbb {F}$ — конечное поле, и пусть $l,d$ быть числами с $d<|\mathbb {F} |$. Код Рида-Мюллера с параметрами $\mathbb {F} ,l,d$ это функция RM: $\mathbb {F} ^{\binom {l+d}{d}}\rightarrow \mathbb {F} ^{|\mathbb {F} |^{l}}$ который отображает каждый $l$-переменный полином $P$ над $\mathbb {F}$ общей степени $d$ ценностям $P$ на всех входах в $\mathbb {F} ^{l}$. То есть входные данные представляют собой полином вида $P(x_{1},\ldots ,x_{l})=\sum \limits _{i_{1}+\ldots +i_{l}\leq d}c_{i_{1},\ldots ,i_{l}}x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots x_{l}^{i_{l}}$ определяется интерполяцией ${\binom {l+d}{d}}$ значения предопределенных точек, а вывод представляет собой последовательность $\{P(x_{1},\ldots ,x_{l})\}$ для каждого $x_{1},\ldots ,x_{l}\in \mathbb {F}$.

Чтобы восстановить стоимость диплома $d$ полином в точке $w\in \mathbb {F} ^{n}$, локальный декодер пропускает случайную аффинную строку через $w$. Затем он выбирает $d+1$ точки на этой линии, которые он использует для интерполяции полинома, а затем оценивает его в той точке, где результат равен $w$. Для этого алгоритм выбирает вектор $v\in \mathbb {F} ^{n}$ равномерно случайным образом и рассматривает линию $L=\{w+\lambda v\mid \lambda \in \mathbb {F} \}$ через $w$. Алгоритм выбирает произвольное подмножество $S$ из $\mathbb {F}$, где $|S|=d+1$и запрашивает координаты кодового слова, соответствующие точкам $w+\lambda v$ для всех $\lambda \in S$ и получает значения $\{e_{\lambda }\}$. Затем он использует полиномиальную интерполяцию для восстановления уникального одномерного полинома. $h$ со степенью меньше или равной $d$ такой, что $h(\lambda )=e_{\lambda }$ для всех $\lambda \in S$. Затем, чтобы получить значение $w$, он просто оценивает $h(0)$. Чтобы восстановить одно значение исходного сообщения, нужно выбрать $w$ быть одной из точек, определяющих полином.

Каждый отдельный запрос равномерно случайным образом распределяется по кодовому слову. Таким образом, если кодовое слово повреждено не более чем за $\delta$ доля местоположений, согласно границе объединения, вероятность того, что алгоритм выберет только неповрежденные координаты (и, следовательно, правильно восстановит бит), равна как минимум $1-(d+1)\delta$. Другие алгоритмы декодирования см.

См. также

• Получение частной информации
• Линейный криптоанализ