Известия РАН. Теория и системы управления, 2020, № 5, стр. 60-72

Введение. В настоящее время повсеместно применяется защита информации, основанная на криптографических алгоритмах. Таких алгоритмов, равно как и способов их применения, изобретено большое количество [1]. Здесь мы ограничимся случаем симметричного шифрования, при котором на этапе кодирования из сообщения $M$ и секретного ключа $K$ функцией-кодером $\Phi $ вычисляется код $C = \Phi (M,K)$, а на этапе декодирования функция-декодер $\Psi $ восстанавливает сообщение: $M = \Psi (C,K)$. Из кода $C$ без ключа $K$ невозможно получить M, поэтому $C$ будет открытым, не секретным. Cвойством симметричного шифрования является то, что используемый ключ $K$ должен быть повторен совершенно точно, например, в случае двоичной последовательности должны совпадать все ее биты. Острая проблема при этом состоит в том, что такие ключи легко отчуждаются (передаются, похищаются, теряются). Столь же насущная проблема – слабая способность человека запоминать парольные последовательности. Если придуманный лично им пароль человек в состоянии запомнить и воспроизвести (хотя уже здесь появляются трудности), то для автоматически сгенерированной последовательности из нескольких десятков псевдослучайных символов это практически невозможно [2].

В то же время человек располагает легко извлекаемыми, сложно отчуждаемыми и имеющими значительный информационный объем биометрическими признаками. Речь идет прежде всего о радужной оболочке глаза (РОГ) [3] и, в меньшей степени, об изображениях лица [4], отпечатках пальцев [5], подписи [6]. Биометрия редко утрачивается, сложно подделывается, легко предъявляется при наличии специального оборудования. Недостатком биометрических признаков в данном приложении является их изменчивость: невозможно в точности повторить результаты измерения, можно лишь утверждать, что два набора признаков, полученные от одного человека, в некотором смысле различаются слабее,чем наборы, взятые от разных людей.

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

1. Выбор метода встраивания ключа в биометрию. Автоматическая биометрия уже достаточно долго используется для идентификации (поиска) и аутентификации (подтверждения) личности человека. Центральную задачу, решаемую такими системами, можно сформулировать как задачу создания оптимального классификатора: необходимо построить функцию расстояния между двумя наборами биометрических данных $\rho ({{D}_{1}},{{D}_{2}})$ и задать порог $\theta $ так, что как можно большее число пар ${{D}_{1}}$ и ${{D}_{2}}$, принадлежащих одному человеку, дает расстояние $\rho ({{D}_{1}},{{D}_{2}}) < \theta $, а как можно большее число от разных людей дает $\rho ({{D}_{1}},{{D}_{2}}) > \theta $. Функцию $\rho $ можно представить как суперпозицию двух этапов: вычисление биометрического эталона T по данным $T = T(D)$, т.е. выделение признаков, устойчиво близких для одного человека и различающихся для разных людей, и расчет собственно расстояния $\rho ({{T}_{1}},{{T}_{2}})$. Эталон T представляет собой набор данных размером от нескольких сотен байт до нескольких килобайт, хотя элементы этих данных (в отличие от криптографических ключей) сильно коррелированы. Тем не менее, информационная емкость (энтропия) биометрического эталона сравнима или превосходит таковую для используемых в настоящее время криптографических ключей [7]. Например, для РОГ существует оценка в 249 степеней свободы [8], для отпечатка пальца разработана система, выделяющая 80 некоррелированных параметров [9]. Это дает основания считать, что возможно внедрить криптографический ключ в биометрию, не снизив его стойкости.

Следует отметить, что основное количество работ, посвященных применению криптографических методов в биометрии, развивают схему отменяемой биометрии (cancelable biometrics) [10]. Суть ее состоит в преобразовании биометрических данных в формат, из которого их нельзя извлечь в исходном виде, но в котором их можно сравнивать в системе распознавания. Отменяемая биометрия – ни что иное как разновидность нечеткого хеширования [11], что можно формально представить как введение дополнительного шага в расчет функции расстояния $\rho $. В этой схеме вычисляется $\rho ({{H}_{1}},{{H}_{2}})$ (в некоторых вариантах $\rho ({{H}_{1}},{{T}_{2}})$), где $H$ – хэш-функция биометрического эталона $H = H(T)$. Очевидно, что по-прежнему решается задача распознавания.

Существует два подхода к тому, каким образом обрабатывать изменчивую биометрию, приводя ее к неизменному криптографическому ключу. В первом используются уже вычисленные биометрические признаки, которые исправляются различными вариантами избыточного кодирования с коррекцией ошибок. В русле данного подхода сделана и эта работа. Во втором подходе, развиваемом отечественными исследователями [12], биометрические признаки явно не вычисляются, вместо этого на “сырых” биометрических данных тренируется нейросеть, обучаемая выдавать тот или иной код [13]. Преимуществом этого подхода называется меньшая избыточность кодирования за счет использования на всех этапах непрерывных данных и квантования только в конце. Недостатки – непредсказуемость обучения нейросети, отсутствие гарантированного качества работы, в том числе отсутствие гарантии того, что результаты сохранят качество при работе с большим разнообразнем данных, чем использовалось при обучении.

Задача воспроизведения криптографического ключа решается биометрическими криптосистемами (biometric crypto system) [10], которые делятся на два класса, реализующих разные схемы работы: генерации ключа (key generation) и встраивания ключа (key binding).

В [14, 15] исследовались методы прямой генерации ключа из биометрических данных без использования какой-либо дополнительной информации. В этом случае при регистрации и распознавании вычисляется одна и та же функция, отображающая многообразие биометрических данных в пространство криптографических ключей (как правило, битовых строк): K(D): $D \to \mathop {\{ 0,1\} }\nolimits^n $, где n – битовая длина ключа. При этом должны выполняться условия

где ${{K}_{1}} = K({{D}_{1}})$, ${{K}_{2}} = K({{D}_{2}})$. Невыполнение первого условия является ошибкой первого рода (ложный недопуск), ее вероятность обозначается FRR (false reject rate), невыполнение второго – ошибка второго рода (ложный допуск), ее вероятность обозначается FAR (false accept rate). Из-за изменчивости биометрических данных такой подход дает большое количество ошибок: FRR = 24% при FAR = 0.07% [15] даже на базе однородных качественных изображений CASIA-3-Lamp [16], что делает его малопригодным на практике.

Лучшие показатели имеет схема с использованием вспомогательного кода (helper code). В этом случае при регистрации кроме криптографического ключа ${{K}_{1}} = K({{D}_{1}})$, который применяется для шифрования сообщения M и немедленно после этого уничтожается, при помощи кодера вычисляется вспомогательный код $h = \Phi ({{D}_{1}})$. Он обладает следующими свойствами: (1) исходные данные D₁ из него восстановить невозможно; (2) при предъявлении биометрии D₂ с помощью декодера можно вычислить ключ ${{K}_{2}} = \Psi ({{D}_{2}},h)$, который удовлетворяет условиям (1.1). Таким образом, предъявив вспомогательный код h и биометрию, пользователь может получить ключ K₁, а значит, и сообщение M, зашифрованное этим ключом при регистрации. Нарушитель, даже зная $h$, не сможет получить ${{K}_{1}}$ [17].

Если в качестве ключа использовать сами данные ${{K}_{1}} = {{D}_{1}}$, то восстанавливается исходная биометрия. Такая схема называется защищенным оттиском (secure sketch) [18]. С помощью вспомогательного кода можно работать даже с весьма изменчивыми биометрическими данными. Однако имеющиеся в печати работы показывают довольно скромные результаты. Например, в [19] делается предположение о внутриклассовой изменчивости в 10% признаков, хотя на практике она составляет больше 20%, что приводит к неработоспособности предлагаемого метода.

Схема встраивания ключа в заданных выше терминах выглядит как совокупность функций кодера $C = \Phi ({{K}_{1}},{{D}_{1}})$, декодера ${{K}_{2}} = \Psi (C,{{D}_{2}})$, удовлетворяющих условию (1.1). Ключ K₁ задается извне, что является преимуществом, поскольку не нужно учитывать природу алгоритма шифрования. С этой точки зрения ключ K₁ можно воспринимать как внешнее по отношению к системе кодирования сообщение M, что немедленно приводит к сценарию, сходному с симметричным шифрованием. Отличие состоит в том, что в симметричном шифровании секретный ключ $K$ не должен изменяться, а биометрические признаки (тоже секретные) отличаются при кодировании и декодировании: ${{D}_{1}} \ne {{D}_{2}}$. Такая схема называется нечетким экстрактором (fuzzy extractor) [18]. Схемы биометрической идентификации и нечеткого экстрактора приведены на рис. 1.

Если биометрические данные представляют собой набор действительных чисел $D \in {{\mathbb{R}}^{d}}$, а функции $\Phi $ и $\Psi $ обратны друг другу: $K = \Psi \left( {\Phi (K,D),D} \right)$, то полученная схема называется экранирующими функциями (shielding functions) [20]. В современных системах регистрации и распознавания РОГ признаками являются целые числа или даже биты, поэтому использование экранирующих функций затруднено.

Очень популярное направление развития схемы встраивания ключа – нечеткое хранилище (fuzzy vault) [7]. Данный подход по сути есть приложение схемы разделения секрета Шамира [21]. При этом получены достаточно низкие, имеющие практический смысл значения ошибок: в [22] при нулевом FAR достигнуто значение ${\text{FRR}} = 0.78\% $, в [23] ${\text{FRR}} = 4.8\% $. Однако каждый из этих результатов показан на одной небольшой (меньше 1000 изображений) базе.

Наиболее перспективной для использования в системах биометрии РОГ является схема нечеткого связывания (fuzzy commitment) [24]. Для радужки можно построить простой метод, описанный в [25]. Эталон радужки в большинстве систем распознавания представляет собой битовое изображение (растр) определенных размеров, как правило, это $N = 256 * 8 = 2048$ бит, каждый бит – локальный признак, обычно знак свертки с фильтром в данной точке. Основой сравнения таких эталонов является нормированное расстояние Хэмминга – доля несовпадающих бит:

Если расстояние меньше некоторого порога p, который устанавливается разработчиками системы, то эталоны ${{T}_{1}}$ и ${{T}_{2}}$ признаются принадлежащими одному человеку.

Основная идея [25] состоит в использовании кодирования, исправляющего ошибки (error correcting code, ECC) [26]. Схема кодирования состоит из пары функций: кодера $R = {{\Phi }_{p}}(M)$, отображающего сообщение в больший по размеру код с избыточностью $R$, и декодера $M = {{\Psi }_{p}}(R)$, где p – доля ошибок в коде $R$, которая может быть исправлена декодером. Секретное сообщение M кодируется, причем вероятность “ошибки передачи данных” устанавливается равной порогу классификации. Код ${{R}_{1}} = {{\Phi }_{p}}(M)$ (в общем случае представляющий собой псевдослучайные числа) побитово складывается по модулю $2$ (исключающее или) с эталоном радужки $C = {{R}_{1}} \oplus {{T}_{1}}$. После вычисления C эталон и секретное сообщение уничтожаются. Полученные данные C также имеют вид случайных, из них нельзя извлечь ни эталон радужки ${{T}_{1}}$, ни сообщение M, их допустимо передавать по незащищенным каналам. Для декодирования регистрируется радужка и формируется новый эталон ${{T}_{2}}$, который, конечно, не совпадает с исходным. Однако если эталоны ${{T}_{1}}$ и ${{T}_{2}}$ принадлежат одному человеку, то они близки в смысле расстояния (1.2): $\rho ({{T}_{1}},{{T}_{2}}) \leqslant p$. Можно записать ${{R}_{2}} = C \oplus {{T}_{2}}$ $ = ({{R}_{1}} \oplus {{T}_{1}}) \oplus {{T}_{2}}$, откуда ${{R}_{1}} \oplus {{R}_{2}} = {{T}_{1}} \oplus {{T}_{2}}$, значит, справедливо $\rho ({{R}_{1}},{{R}_{2}}) \leqslant p$ и можно восстановить секретное сообщение $M = {{\Psi }_{p}}({{R}_{2}})$. Схема работы показана на рис. 2. Интересным развитием этого метода представляется обобщение операции сложения по модулю 2 до более широкого класса операторов поиска различия [27, 28].

В [25] используется каскад двух алгоритмов помехоустойчивого кодирования: Рида–Соломона [29] и Адамара [26]. Кодирование Рида–Соломона обрабатывает весь блок данных длины L, трактуя его как последовательность из L/s s-битовых символов, при этом любые как угодно расположенные символы (не биты!) могут отличаться, если их количество не больше pL. Это кодирование предназначено для того, чтобы компенсировать групповые ошибки, возникающие из-за наличия различных затенений (ресниц, бликов), закрывающих значительные области радужки. Кодирование Адамара исполняется для малых групп данных (несколько бит), и исправляет не более 25% ошибок в каждой группе. Другими словами, ошибки (различия эталонов ${{T}_{1}}$ и ${{T}_{2}}$) должны быть распределены равномерно по эталону с плотностью не выше 25%. Это кодирование предназначено для борьбы с точечными различиями, вызываемыми шумом камеры. Сообщение $M$ кодируется последовательно сначала кодом Рида–Соломона, потом результат – кодом Адамара.

Однако данный каскад алгоритмов может использоваться лишь, если доля различающихся бит в эталонах одного человека не превышает 25%. На реальных базах данных и в приложениях это не так, и такое ограничение приводит к неприемлемо высокой (более 50%) ошибке первого рода. Для преодоления этого затруднения в [30] дополнительно вводится маскирование эталона: каждый четвертый бит эталонов РОГ устанавливается в 0. За счет этого доля различающихся бит в эталонах одного человека снижается до 20%. Критика этого метода, с точки зрения неустойчивости ко взлому, приведена в [31]. Атака осуществляется путем постепенного восстановления исходного эталона (приближения к нему).

В данной работе предпринята попытка доработать схему [25] более разумным образом и построить практически пригодный метод встраивания ключа. На основе системы выделения признаков РОГ проведены численные эксперименты на нескольких открытых базах изображений, определено пороговое расстояние Хэмминга. Вводятся дополнительные два шага: простое мажоритарное кодирование и псевдослучайное перемешивание. Параметры полученных четырех последовательных шагов кодера (и соответствующих им шагов декодера) подбираются решением дискретной оптимизационной задачи.

2. Определение пороговой вероятности. Алгоритм биометрического распознавания можно разбить на функцию выделения признаков (построения эталона) $T = T(D)$ и функцию сравнения эталонов $\rho ({{T}_{1}},{{T}_{2}})$. Биометрические системы распознавания прошли большой путь и достигли очень хороших показателей точности классификации (малых значений ошибок), в том числе за счет оптимизации методов выделения признаков. Поэтому обосновано использование признаков, получаемых имеющимися методами. В работе применялось выделение области радужки на изображении [32] и вычисление признаков РОГ [33], которые в совокупности реализуют функцию $T = T(D)$.

Согласно развиваемой в работе разновидности нечеткого экстрактора, предложенной в [25], для сравнения используется расстояние Хэмминга (1.2). В этой схеме если биометрический эталон ${{T}_{1}}$, использованный при регистрации, и предъявляемый эталон ${{T}_{2}}$ находятся на расстоянии меньше порога $p$, то зашифрованное сообщение $M$ восстанавливается, иначе – нет. Другими словами, порог $p$ разделяет “своих” и “нарушителей”. На рис. 3 показана типичная картина распределения сравнений по расстоянию $\rho ({{T}_{1}},{{T}_{2}})$. Левая группа соответствует случаю, когда ${{T}_{1}}$ и ${{T}_{2}}$ получены регистрацией одной радужки (“свои”). При этом исключены сравнения эталона с собой (дающие нулевое расстояние), как не встречающиеся на практике. Правая группа соответсвует случаю, когда ${{T}_{1}}$ и ${{T}_{2}}$ получены с разных радужек (“нарушители”). Необходимо определить величину порога.

Для экспериментов использованы базы данных (БД), находящиеся в открытом доступе: CASIA-4-Thousand [16], BATH [34], подмножество ICE базы NDIRIS [35], UBIRIS-1 [36]. Кроме того также участвовали базы изображений, собранных авторами [32, 33] на устройствах регистрации РОГ Panasonic BM-ET300 [37], LG IrisAccess-3000 [38] и Iritech Irishield MK2120U [39].

В табл. 1 приведен список семи использованных БД. Для каждой даны их собственные параметры (количество индивидуальных радужек и количество изображений) и значение порога, при котором ошибка второго рода равна 10^–4, что соответствует вероятности угадать четырехзначный пин-код банкомата. Из таблицы видно, что, взяв порог $\theta = 0.35$, можно добиться того, чтобы, предъявив чужую биометрию, получить доступ к секрету лишь с вероятностью, меньшей 10^–4.

Таким образом, значение $\theta = 0.35$ далее используется как базовое, т.е. трактуется как вероятность ошибки, которую должен исправлять код. В табл. 1 также приведены значения вероятностей ошибок первого и второго рода для этого порога. Очевидно, вероятность ошибки второго рода лишь убывает на каждой из баз и тем сильнее, чем собственное значение порога при FAR = 10^–4 отличается от 0.35. При этом максимальное значение ошибки первого рода не превышает 8%.

3. Описание методов. Описывать применяемые методы будем в последовательности их исполнения декодером, что также соответствует переходу “от простого к сложному”, так как вначале единицей данных является один бит, а в конце – все сообщение.

Итак, необходимо сконструировать код, восстанавливающий исходное сообщение из блока данных, каждый бит которых может быть изменен со средней вероятностью не более $p = 0.35$. Во-первых, это значение существенно больше $p = 0.25$, являющегося пороговым для возможности применения популярных методов Уолша–Адамара или Рида–Мюллера [40]. Во-вторых, возникновение этих ошибок нельзя считать независимым. Напротив, ошибки в близких элементах сильно коррелированы (возникают блоками).

3.1. Декоррелирование псевдослучайным перемешиванием. Проектировать методы, исправляющие коррелированные ошибки, значительно труднее, и их показатели хуже, чем для случая некоррелированных ошибок. Значительная часть усилий в этом случае направлена именно на декорреляцию. В рассматриваемой системе весь блок данных доступен целиком (а не последовательно, как во многих системах, работающих с каналами передачи) и можно применить простой метод декорреляции – псевдослучайное перемешивание битов эталона радужки. Если ко всем эталонам применяется одинаковое перемешивание, то расстояние Хэмминга не изменяется и сохраняются все конструкции, основанные на нем. Но при этом соседние биты последовательностей, используемых в кодах на следующих этапах, берутся уже из разнесенных пикселей эталона и ошибки в них независимы.

3.2. Битовое мажоритарное кодирование. Уровень ошибок $p = 0.35$ слишком высок для большинства корректирующих кодов. Практически единственной возможностью здесь остается мажоритарное кодирование отдельных битов, исправляющее до 50% ошибок. При кодировании значение бита повторяется $n$ раз, при декодировании подсчитывается сумма принятых $n$ бит, и если она меньше n/2, то принимается значение 0, иначе 1. Если $p$ – вероятность ошибки в единичном бите и искажения битов независимы, то вероятность ошибки при приеме составляет

где $C_{n}^{l}$ – число сочетаний из $n$ по l.

На рис. 4 приведены графики функции (3.1) при некоторых n.

Видно, что если вероятность ошибки одного бита кода равна $p = 0.35$, то, семикратно продублировав бит сообщения, можно передать его с вероятностью ошибки ${{p}_{D}} = 0.2$, что позволяет использовать коды Адамара. Большая кратность дублирования также допустима, но приводит к большему размеру кода.

Параметром этого метода является кратность повтора бита $n$.

3.3. Блоковое кодирование Адамара. Обозначим через $\mathbb{B} = \{ 0,1\} $, ${{\mathbb{B}}^{l}}$ = {(b₁, ..., ${{b}_{l}}){\kern 1pt} :\;{{b}_{i}} \in \mathbb{B}$ ${{b}_{l}}){\kern 1pt} :\;{{b}_{i}} \in \mathbb{B}$, $i = \overline {1,l} \} $ множество всех двоичных последовательностей длины l (l-мерный двоичный куб). Для любых двух элементов $u,v \in {{\mathbb{B}}^{l}}$ задано нормированное расстояние Хэмминга (1.2), равное отношению количества различающихся бит в последовательностях к их длине. Также обозначим через $b(u)$ число единичных бит в последовательности u.

Пусть $M$ – исходное сообщение (message) длиной k бит, $M \in {{\mathbb{B}}^{k}}$, т.е. единицей кодирования является блок из нескольких бит. Алгоритм кодирования Адамара отображает сообщение в избыточный код длиной $n$ бит из некоторого известного алфавита $\mathbb{H}$: $C{\kern 1pt} *(M) \in \mathbb{H} \subset {{\mathbb{B}}^{n}}$, $n > k$. Пусть $C \in {{\mathbb{B}}^{n}}$ – искаженный код, возникший при замене (инвертировании) некоторых бит исходного кода C*. Вероятность искажения одного бита равна p_D (взята из предыдущего этапа (3.1)), искажения независимы. Далее в этом разделе для простоты переобозначим ${{p}_{D}} \to p$. Будем декодировать сообщение, предполагая, что исходный код искажен минимально, т.е. для $C$ будем искать ближайший в смысле расстояния Хэмминга код из алфавита $\mathbb{H}$. Назовем его аттрактором. Аттракторов может быть несколько (несколько кодов могут иметь одинаковое минимальное расстояние до C). Если аттракторов несколько, то выбирается случайный. Обозначим множество аттракторов $C$ как $A(C)$.

Известна простая оценка вероятности ошибки блокового кодирования Адамара, с длиной кодового слова $n$ используемая в так называемой границе Хэмминга:

что совпадает с (3.1) за исключением верхнего предела суммирования.

Но это довольно грубая оценка, ухудшающаяся с ростом $n$. Найдем точную формулу. Вероятность правильного декодирования

где $P(M)$ – доля сообщений M во входном потоке (вероятность встретить сообщение M), $p(C\,{\text{|}}\,C{\kern 1pt} *)$ – вероятность получить искаженный код $C$ при передаче сообщения M (которое кодируется кодом C*), $p(C{\kern 1pt} *\,{\text{|}}\,C)$ – вероятность восстановить сообщение M из искаженного кода C. Считая все сообщения равновероятными, можно рассчитывать вероятность по одному из них, например нулевому (M = 0):

Без ограничения общности в силу симметричности кода Адамара [26] можно считать, что $C{\kern 1pt} *$ – нулевой код, т.е. последовательность нулевых бит соответствующей длины (так оно и есть при стандартном кодировании). Тогда вероятность получить определенный код $C$ из нулевого равна ${{p}^{{b(C)}}}{{(1 - p)}^{{n - b(C)}}}$ и

где $p(0|C)$ – вероятность получить нулевой код из $C$:

Для небольших значений длины кода $n$ можно построить гистограмму распределения точек пространства кодов ${{\mathbb{B}}^{n}}$ в зависимости от расстояния до нулевого кода $b = b(C)$ и количества аттракторов $a = {\text{|}}A(C){\text{|}}$. Положим a = 0 в случае выполнения первого условия из (3.3). Тогда можно записать двумерное распределение

получить вероятность правильного декодирования и ошибку кодирования

Запись совпадает с (3.2) за исключением используемых коэффициентов и пределов суммирования (в (3.4) суммирование производится по всем b). Таблица значений $H(b,a)$ и h(b) для пополненного кода Адамара порядка 5 ($n = {{2}^{5}} - 1 = 31$, $k = 5 + 1 = 6$) дана ниже (табл. 2). Для сравнения приведены значения $C_{n}^{b}$. Также представлены средние значения вероятности выбора правильного аттрактора:

Для этого кода значения b изменяются от 0 до 31, приведены первые 12. Остальные значения нулевые, все последовательности, отличающиеся от нулевой более чем на 11 бит, “притягиваются” к другим кодовым векторам. Из таблицы видно, что вплоть до значений $b = 7$ происходит выбор лишь одного аттрактора, т.е. при таком или меньшем расхождении сообщение восстанавливается всегда. Это соответствует границе Хэмминга. Однако и при больших расхождениях существует значительная вероятность правильного восстановления. Это существенно, поскольку кодов за границей Хэмминга существует гораздо больше, чем внутри. Таким образом, оценка по Хэммингу вероятности ошибки декодирования сильно завышена. Например, для пополненного кода Адамара k = 6, n = 31 и ошибке $p = 0.250$ оценка по (3.2) дает ${{p}_{H}} = 0.527$, что, казалось бы, исключает использование такого кода. Однако расчет по формуле (3.4) дает ${{p}_{H}} = 0.261$, что вполне пригодно для использования на следующем шаге – коировании Рида–Соломона. На рис. 5 приведены графики функции (3.2) и (3.4) для k = 6, n = 31.

Параметр кодирования Адамара – длина слова k.

3.4. Кодирование Рида–Соломона. Единицей кодирования для алгоритма Рида–Соломона является все сообщение, которое разбивается на слова фиксированного размера, s бит каждое. Одно такое слово – запись целого числа в диапазоне $[0;{{2}^{s}} - 1]$. Последовательность из $L$ бит разбивается на $k = \left\lceil {L{\text{/}}s} \right\rceil $ слов, т.е. чисел. Эти числа трактуются как коэффициенты полинома над полем Галуа $GF({{2}^{k}})$. Оказывается, что если определенным образом расширить полином с $k$ коэффициентами до полинома с $n > k$ коэффициентами, то можно среди полученных $n$ коэффициентов произвольно исказить любые $t \leqslant (n - k){\text{/}}2$ из них и из полученной записи восстановить исходные коэффициенты.

Обозначим: $L$ – длина сообщения (число кодируемых бит); $s$ – размер слова кода Рида–Соломона (РС); $k$ – число слов РС в сообщении, $k = \left\lceil {L{\text{/}}s} \right\rceil $; $n$ – число слов РС в коде; $N$ – длина кода (число бит в коде, полученном методом РС), $N = ns$; p – доля допустимых ошибочных слов в коде, при которой еще возможно восстановление сообщения. Код РС исправляет не более $t$ ошибок, где $t$ равно половине избыточных слов в коде, добавленных к исходному сообщению, т.е. $n = k + 2t$, обозначив $p = t{\text{/}}n$, получим

Вычисленная таким образом доля может служить оценкой допустимой вероятности ошибки слова кода. Также есть ограничение на максимальное число слов кода:

Зафиксировав длину сообщения $L$, выбрав длину слова $s$ и зная вероятность ошибки декодирования предыдущего шага $p = {{p}_{H}}$, можно построить код РС. Вероятность ${{p}_{H}}$ определяется извне, поэтому код РС параметризуется двумя величинами: размером слова $s$ и длиной сообщения $L$.

3.5. Добавочная ошибка восстановления кода. Расстояние Хэмминга задает функцию зависимости ошибки первого рода от ошибки второго рода. Для некоторой базы данных и фиксированного порога $\theta $ рассмотрим количества различных исходов. Существует всего четыре исхода: истинный допуск (обозначим число таких событий “true positive” ${{N}_{{TP}}}$), ложный отказ (“false positive” ${{N}_{{FR}}}$), истинный отказ (“true negative” ${{N}_{{TN}}}$) и ложный отказ (“false negative” ${{N}_{{FN}}}$). Вероятности ошибки первого (false reject) и второго (false accept) рода определяются как

Следует отметить, что при работе с БД сумма ${{N}_{{FN}}} + {{N}_{{TP}}}$ постоянна и равна числу сравнений эталонов одного человека, а сумма ${{N}_{{FP}}} + {{N}_{{TN}}}$ постоянна и равна числу сравнений эталонов разных людей.

Восстановление сообщения из кода вносит дополнительную ошибку, оценим ее. Обозначим вероятность ошибки восстановления ${{p}_{R}}$. Соответственно вероятность правильного восстановления равна $1 - {{p}_{R}}$. Ожидаемое число событий истинного допуска в схеме с восстановлением уменьшается пропорционально этой вероятности: $N_{{TP}}^{'} = {{N}_{{TP}}}(1 - {{p}_{R}})$. Значит, увеличивается число ложных отказов: $N_{{FN}}^{'} = {{N}_{{FN}}} + {{N}_{{TP}}}{{p}_{R}}$. Аналогично число ложных допусков уменьшается: $N_{{FP}}^{'} = {{N}_{{FP}}}(1 - {{p}_{R}})$, число истинных отказов увеличивается: $N_{{TN}}^{'} = {{N}_{{TN}}} + {{N}_{{FP}}}{{p}_{R}}$. Рассчитывая новые вероятности ошибок первого и второго рода, получаем:

Если ${{p}_{R}} \ll 1$, ${{p}_{{FR}}} \ll 1$, то можно приблизить: $p_{{FR}}^{'} \approx {{p}_{{FR}}} + {{p}_{R}}$, $p_{{FA}}^{'} \approx {{p}_{{FA}}}$. Таким образом, вероятность ошибки первого рода увеличивается на величину вероятности ошибки восстановления, вероятность ошибки второго рода можно считать неизменной.

4. Подбор параметров схемы кодирования. Описанные четыре последовательно исполняемых алгоритма имеют следующие параметры, влияющие на их характеристики: (1) псевдослучайное перемешивание не имеет таких параметров; (2) мажоритарное кодирование параметризуется кратностью повтора бита $n$; (3) кодирование Адамара – размером слова k, кодирование РС – размером слова $s$ и длиной сообщения $L$. Различные комбинации значений $(n,k,s,L)$ приводят к построению различных кодеков, имеющих разные отношения длины кода к длине сообщения. Можно формально записать зависимости ошибок первого и второго рода от этих параметров: $FRR(n,k,s,l)$ и $FFR(n,k,s,l)$. Фактически, эти значения находились экспериментально. Используемая биометрия [33] имеет размер $Z = 6656$ бит. Размер кода $C$ не может быть больше, дублирование и маскирование недопустимы, так как делают тривиальным взлом такого кода. Также следует учесть, что практически осмысленным является кодирование сообщения некоторой минимальной длины $Y$. Тогда можно записать задачу поиска оптимального кода:

Для $Y = 64$ решение найдено: $n = 13$, $k = 5$, $s = 5$, $L = 65$, $FRR$ = 10.4%. Такой размер считается достаточным для “обычных” пользовательских ключей. Для Y = 128 и выше решение данной задачи не получено. Следует отметить, что без псевдослучайного перемешивания (явным образом не участвующего в (4.1)) задача не решается и при $Y = 64$.

Заключение. В парадигме нечеткого экстрактора построен метод внедрения криптографического ключа в биометрию радужной оболочки глаза. Успешно внедряется ключ размером до $65$ бит, для больших размеров решение не получено. Использование дополнительных шагов псевдослучайного перемешивания и мажоритарного битового кодирования позволило решить проблемы изменчивости и локальной коррелированности биометрических признаков. Метод протестирован на нескольких базах изображений радужной оболочки глаза. Требуется изучение криптостойкости представленного метода.