Нечёткий экстрактор

Нечёткий экстрактор — способ, который позволяет однозначно восстанавливать секретный ключ из неточно воспроизводимых биометрических данных при участии вспомогательных данных, являющимися открытыми. «Нечёткий» в данном контексте относится к тому факту, что фиксированные значения, требуемые для криптографии, будут извлечены из значений, близких, но не идентичных исходному ключу. Одним из приложений является шифрование и аутентификация записей пользователей, используя биометрические данные пользователя в качестве ключа.

Нечёткий экстрактор — это способ, который позволяет аутентифицировать пользователя, используя в качестве ключа биометрический шаблон, созданный из биометрических данных пользователя. Они извлекают равномерную и случайную строку $R$ со входа $w$ с допуском на шум. Если вход изменяется на вес $w'$, но все ещё близкий к весу w, та же строка $R$ будет восстановлена. Для достижения этого, во время первоначального вычисления строки $R$ процесс также выводит вспомогательную строку $P$, которая будет храниться для восстановления $R$ позже и может быть обнародована без ущерба для безопасности R. Безопасность процесса обеспечивается также тогда, когда противник изменяет $P$. Однажды исправленная строка $R$, которая была рассчитана, её можно использовать, например, для согласования ключей между пользователем и сервером только на основе биометрического ввода.

Исторически, одна из первых биометрических систем такого типа была разработана О. Джуелсом и Б. Ваттенбергом и называлась «Нечёткое обязательство», где криптографический ключ извлекается с использованием биометрических данных. Позже О. Джуелс и М. Судан разработали схемы нечёткого контейнера, которые являются инвариантами порядка для схемы нечётких обязательств, но используют код Рида — Соломона. Кодовое слово оценивается полиномом, а секретное сообщение вставляется как коэффициенты полинома. Полином оценивается для разных значений набора признаков биометрических данных. Так что нечёткий контейнер были предшественниками нечётких экстракторов.

Основные определения

Предсказуемость

Предсказуемость указывает на вероятность того, что злоумышленник сможет угадать секретный ключ. По определению, предсказуемость случайной величины $A$ равно $\max _{\mathrm {a} }P[A=a]$.

Например, дана пара случайных величин $A$ и $B$, если противник знает $b$ из $B$, тогда предсказуемость $A$ будет равна $\max _{\mathrm {a} }P[A=a|B=b]$. Итак, противник может предсказать $A$ с $E_{b\leftarrow B}[\max _{\mathrm {a} }P[A=a|B=b]]$. Мы используем среднее по $B$, так как это не под контролем противника, но, так как зная $b$ делает предсказание $A$ противника, мы берём наихудший случай для $A$.

Минимальная энтропия

Минимальная энтропия указывает на энтропию в худшем случае. По определению, это определяется как $H_{\infty }(A)=-\log(\max _{\mathrm {a} }P[A=a])$.

Случайная величина с минимальной энтропией не менее $m$ называется $m$-источник.

Статистическая дистанция

Статистическое расстояние является мерой различимости. Математически это выражается для двух вероятностных распределений $A$ и $B$ и and $B$ как $SD[A,B]$ = ${\frac {1}{2}}\sum _{\mathrm {v} }|P[A=v]-P[B=v]|$. В любой системе, если $A$ заменяется на $B$, оно будет вести себя как исходная система с вероятностью не менее, чем $1-SD[A,B]$.

Определение 1 (случайный экстрактор)

Определим $M$ как экстрактор случайностей, где экстрактор случайностей — это функционал, которая принимает на вход строку с некоторым распределением и выдает на выход нормально распредленную строку из бит. Функция случайности $Ext:M\rightarrow \{0,1\}^{l}$ c случайной длиной $r$ это $(m,l,\epsilon )$ сильный экстрактор, если для всех $m$-sources $W$ на $M(Ext(W;I),I)\approx _{\epsilon }(U_{l},U_{r}),$ где $I=U_{r}$ независим от $W$.

Выход экстрактора является ключом, сгенерированным из $w\leftarrow W$ с ядрой $i\leftarrow I$. Он ведёт себя независимо от других частей системы с вероятностью $1-\epsilon$. Экстракторы могут извлечь максимум $l=m-2log{\frac {1}{\epsilon }}+O(1)$ бит из произвольного $m$-source.

Безопасный эскиз

Защищенный эскиз генерирует открытую информацию для своего входа $w$, не раскрывая его, но позволяет точно восстановить $w$, учитывая другое значение $w'$, но близкое к $w$. Защищённый эскиз позволяет реконструировать ввод с шумом, так что если вход $w$ и эскиз $s$, с учётом $s$ и значением $w'$ рядом с $w$, $w$ можно восстановить. Но эскиз $s$ не должен раскрывать информацию о $w$ , чтобы обеспечить его безопасность.

Если $\mathbb {M}$ метрическое пространство с функцией расстояния dis, безопасный эскиз восстанавливает строку $w\in \mathbb {M}$из любой близкой строки $w'\in \mathbb {M}$ без раскрытия $w$.

Основные конструкции

Благодаря устойчивым к ошибкам свойствам, безопасные эскизы можно обрабатывать, анализировать и конструировать как $(n,k,d)_{\mathcal {F}}$ для общего для исправления ошибок или как $[n,k,d]_{\mathcal {F}}$ для линейного кода, где $n$ — длина кодовых слов, $k$ — длина сообщения, которое должно быть закодировано, $d$ — расстояние между кодовыми словами и ${\mathcal {F}}$ это алфавит. Если ${\mathcal {F}}^{n}$ это вселенная возможных слов, тогда можно найти код $C\in {\mathcal {F}}^{n}$, исправляющий ошибки, который имеет уникальное кодовое слово $c\in C$ для каждого веса $w\in {\mathcal {F}}^{n}$ и имеет расстояние Хемминга $dis_{Ham}(c,w)\leq (d-1)/2$. Первым шагом для создания безопасного эскиза является определение типа возможных ошибок, а затем выбор расстояния для измерения.

Гарантии конфиденциальности

В целом, защищённая система пытается передать как можно меньше информации злоумышленнику. В случае биометрических данных, если информация о биометрических показаниях просочилась, злоумышленник может узнать личную информацию о пользователе. Например, злоумышленник замечает, что в вспомогательных строках есть определённый шаблон, который подразумевает этническую принадлежность пользователя. Мы можем считать эту дополнительную информацию функцией $f(W)$. Если противник мог узнать вспомогательную строку, необходимо убедиться, что из этих данных он не может вывести какие-либо данные о человеке, у которого было взяты биометрические данные.

Защита от активных атак

Активной атакой может быть атака, при которой злоумышленник может изменить вспомогательную строку $P$. Если злоумышленник может перейти на другую строку $P$, которая также приемлема для функции воспроизведения $Rep(W,P)$, он выдаёт $Rep(W,P)$ — неверную секретную строку ${\tilde {R}}$. Надёжные нечёткие экстракторы решают эту проблему, разрешая функции воспроизведения выдавать неверный результат, если в качестве входных данных предоставлена изменённая вспомогательная строка.

Литература

• Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data // Advances in Cryptology. — 2008. — P. 1—26. — doi:10.1007/978-3-540-24676-3_31.

• Ari Juels. A Fuzzy Vault Scheme. — 2008. — P. 1—10. — doi:10.1007/s10623-005-6343-z.

• А. Иванов, П. Чернов. Протоколы биометрико-криптографического рукопожатия. — 2019.

• Стойкий нечеткий экстрактор позволит оптимизировать применение биометрических технологий в криптографии. — 2008.

• Защита информации. Техника защиты информации. Требования к средствам высоконадежной биометрической аутентификации. — 2007.