Неподатливый код

Понятие неподатливых кодов было введено в 2009 году Дзембовским, Петржаком и Вихсом. за смягчение понятий исправления и обнаружения ошибок . Неформально код является неподатливым, если сообщение, содержащееся в измененном кодовом слове, является либо исходным сообщением, либо совершенно несвязанным значением. Негибкие коды обеспечивают полезную и значимую гарантию безопасности в ситуациях, когда традиционное исправление и обнаружение ошибок невозможно; например, когда злоумышленник может полностью перезаписать закодированное сообщение. Хотя такие коды не существуют, если семейство « функций вмешательства » F совершенно неограничено, известно, что они существуют для многих широких семейств F вмешательства.

Фон

Эксперимент по фальсификации

Чтобы знать схему работы неподатливого кода, нам необходимо знать базовый эксперимент, на котором он основан. Ниже приводится трехэтапный метод эксперимента по фальсификации .

1. Исходное сообщение $s$ кодируется с помощью (возможно , рандомизированной) процедуры $Enc$, давая кодовое слово $c$ = $Enc(s)$.
2. Кодовое слово модифицируется под действием какой-либо функции вмешательства. $f\in F$ к ошибочному кодовому слову $c^{*}$= $f(c)$.
3. Ошибочное кодовое слово $c^{*}$ декодируется с помощью процедуры $Dec$, в результате чего получается декодированное сообщение $s^{*}$= $Dec(c^{*})$.

Эксперимент по фальсификации можно использовать для моделирования нескольких интересных реальных условий, таких как передача данных по зашумленному каналу или состязательное вмешательство в данные, хранящиеся в памяти физического устройства. Имея эту экспериментальную базу, мы хотели бы построить специальные процедуры кодирования/декодирования. $(Enc,Dec)$, которые дают нам некоторые значимые гарантии относительно результатов вышеупомянутого эксперимента по вмешательству для больших и интересных семей. $F$ функций вмешательства. Ниже приведены несколько возможных типов гарантий, на которые мы можем надеяться.

Исправление ошибок

Одна очень естественная гарантия, называемая коррекцией ошибок , заключается в том, чтобы потребовать, чтобы для любой функции вмешательства и любого исходного сообщения эксперимент по изменению всегда производил правильное декодированное сообщение. $s^{*}=s$.

Обнаружение ошибок

Более слабая гарантия, называемая обнаружением ошибок , требует, чтобы эксперимент по изменению всегда приводил либо к правильному значению, либо к правильному значению. $s^{*}=s$ или специальный символ $s^{*}=\perp$ указывает на то, что было обнаружено вмешательство. Это понятие обнаружения ошибок является более слабой гарантией, чем исправление ошибок, и достижимо для большего F функций вмешательства.

Описание алгоритма

Неподатливый код гарантирует, что любой эксперимент по вмешательству приведет к правильному декодированию сообщения. $s^{*}=s$, или декодированное сообщение $s^{*}$ полностью независим и не связан с исходным сообщением $s$. Другими словами, понятие неподатливости кодов по духу схоже с понятиями неподатливости криптографических примитивов (таких как шифрование2, обязательства и доказательства с нулевым разглашением), введенных в плодотворной работе Долева, Дворка и Наор.

По сравнению с исправлением или обнаружением ошибок «правильную» формализацию неподатливых кодов определить несколько сложнее. Позволять $Tamper_{s}^{f}$ быть случайной величиной для значения декодированного сообщения, которое получается, когда мы запускаем эксперимент по вмешательству в исходное сообщение. $s$ и функция взлома $f$, над случайностью процедуры кодирования. Интуитивно мы хотим сказать, что распределение $Tamper_{s}^{f}$ не зависит от закодированного сообщения $s$. Конечно, мы также хотим учесть случай, когда эксперимент по вмешательству приводит к $s^{*}=s$ (например, если функцией взлома является идентичность), что, очевидно, зависит от $s$.

Таким образом, мы требуем, чтобы для каждой тамперной функции $f\in F$, существует распределение $D_{f}$ который выводит либо конкретные значения $s^{*}$ или особенный же $*$ символ и точно моделирует распределение $Tamper_{s}^{f}$ для всех $s$ в следующем смысле: для каждого исходного сообщения $s$, распределения $Tamper_{s}^{f}$ и $D_{f}$ статистически близки, когда $*$ символ интерпретируется как $s$. То есть, $D_{f}$ правильно моделирует «результат» эксперимента по изменению функции $f\in F$ не зная исходных сообщений $s$, но допускается некоторая двусмысленность, выводя одно и то же $*$ символ, указывающий, что декодированное сообщение должно быть таким же, как исходное сообщение, без указания точного значения. Тот факт, что $D_{f}$ зависит только от $f$ и не на $s$, показывает, что результат $Tamper_{s}^{f}$ не зависит от $s$, исключая равенство.

Отношение к исправлению/обнаружению ошибок

Обратите внимание, что неподатливость является более слабой гарантией, чем исправление/обнаружение ошибок; последние гарантируют, что любое изменение кодового слова может быть исправлено или, по крайней мере, обнаружено процедурой декодирования, тогда как первый позволяет изменять сообщение, но только до несвязанного значения. Однако при изучении исправления/обнаружения ошибок мы обычно ограничиваемся ограниченными формами вмешательства, которые сохраняют некоторое представление о расстоянии (например, обычно расстоянии Хэмминга ) между исходным и подделанным кодовым словом. Например, для простого семейства функций уже невозможно добиться исправления/обнаружения ошибок. $F_{const}$ что для каждой константы $c^{*}$, включает в себя « константную » функцию $f_{c^{*}}$ который отображает все входы в $c^{*}$. Всегда есть какая-то функция $F_{const}$ который сопоставляет все с действительным кодовым словом $c^{*}$. Напротив, легко построить коды, которые не податливы относительно $F_{const}$, поскольку выход постоянной функции явно не зависит от ее входа. Предыдущие работы над неподатливыми кодами показывают, что можно создавать неподатливые коды для очень сложных семейств функций вмешательства. $F$ для которых исправление/обнаружение ошибок невозможно.

Применение функций несанкционированного вмешательства

Побитовое независимое вмешательство

В качестве одного очень конкретного примера мы изучаем неподатливость по отношению к семейству функций $f$ которые определяют для каждого бита кодового слова $c$, следует ли оставить его как есть, перевернуть его, установить на 0, установить на 1. То есть каждый бит кодового слова изменяется произвольно, но независимо от значения других битов кодового слова. Мы называем это семейством «побитового независимого вмешательства». $F_{BIT}$. Обратите внимание, что это семейство содержит постоянные функции $F_{const}$ и функции постоянной ошибки $F_{err}$ как подмножества. Поэтому, как мы уже упоминали, исправление и обнаружение ошибок не могут быть достигнуты в отношении этого семейства. Тем не менее, нижеследующее может показать эффективный негибкий код для этого мощного семейства.

С $F_{BIT}$ мы обозначаем семейство, которое содержит все функции вмешательства, которые изменяют каждый бит независимо. Формально это семейство содержит все функции $f_{i}:\left\{{0},{1}\right\}^{n}\to \left\{{0},{1}\right\}^{n}$ которые определяются n функциями $f_{i}:\left\{{0},{1}\right\}\to \left\{{0},{1}\right\}$ (для i=1...n) как $f(c_{1}..c_{n})=f_{1}(c_{1})..f_{n}(c_{n})$. Обратите внимание, что для каждого варианта существует только 4 возможных варианта. $f_{i}$ (т.е. как изменить конкретный бит), и мы называем их «установить в 0», «установить в 1», «перевернуть», «сохранить», где значения должны быть интуитивно понятны. Мы называем указанное выше семейство побитовым независимым семейством несанкционированного вмешательства.

Все семьи ограниченного размера

• Вероятностный метод

Для любого «достаточно маленького» семейства функций $F$, существует (возможно, неэффективная) схема кодирования, которая не податлива относительно F. Более того, для фиксированного «достаточно малого» семейства функций $F$, схема случайного кодирования, вероятно, будет негибкой относительно F с подавляющей вероятностью. К сожалению, схемы случайного кодирования не могут быть эффективно представлены, а функция кодирования/декодирования вряд ли будет эффективной. Следовательно, этот результат следует рассматривать просто как демонстрацию «возможности» и поставленную цель, которой мы затем должны конструктивно стремиться соответствовать. Более того, этот результат также подчеркивает разницу между «исправлением/обнаружением ошибок» и «неподатливостью», поскольку результат этой формы не может быть верным для первых понятий.

• Случайный подход к модели Oracle

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

Модель защиты от несанкционированного доступа

В этой модели мы рассматриваем два способа взаимодействия с системой:

Выполнять( $x$): Пользователь может предоставить системе запросы Execute(x), например $x\in \left\{{0},{1}\right\}^{u}$, и в этом случае система вычисляет $(y,s^{'})\gets G(x,s)$, обновляет состояние системы до $s:=s^{'}$ и результаты $y$.

Тампер( $f$) : Мы также рассматриваем несанкционированные атаки на систему, смоделированные Tamper( $f$) команды для функций $f:\left\{{0},{1}\right\}^{n}\to \left\{{0},{1}\right\}^{n}$. При получении такой команды состояние системы устанавливается на $s:=f(s)$.

Злоумышленник, который также может взаимодействовать с системой через запросы Tamper, потенциально может узнать значительно больше о секретном состоянии и даже полностью его восстановить. Поэтому нам хотелось бы иметь общий метод защиты систем от несанкционированных атак, чтобы иметь возможность выдавать запросы на несанкционированный доступ (по крайней мере, для функций f в каком-то большом семействе). $F$) не может предоставить злоумышленнику дополнительную информацию. Используя для этой цели неподатливый код, мы приходим к выводу: пусть $(Enc,Dec)$ быть любой схемой кодирования, которая не является гибкой по отношению к $F$, затем $(Enc,Dec)$ также может быть имитирован несанкционированный доступ к $F$.

Емкость неподатливых кодов

1. Для каждой семьи $F$ с $|F|\leq 2^{2^{\alpha n}}$, существуют неподатливые коды против $F$ со ставкой, сколь угодно близкой к 1 − $\alpha$ (это достигается за счет рандомизированной конструкции).
2. Для большой семьи $exp(n^{O(1)}2^{\alpha n})$ против которого нет неподатливого кода скорости 1 — $\alpha$ (на самом деле это тот случай, когда случайная семья такого размера).
3. 1 − $\alpha$ — это наилучшая достижимая скорость для семейства функций, которым разрешено изменять только первые $\alpha n$ бит кодового слова, что представляет особый интерес.