метод декодирования кодов Рида-Соломона на основе коррекции ошибок и стираний для биометрических систем
метод декодирования кодов Рида-Соломона на основе коррекции ошибок и стираний для биометрических систем
Аннотация
В работе рассматривается биометрическая система (БС) аутентификации, основанная на схеме нечеткого обязательства (fuzzy commitment), предназначенная для защиты секретных ключей с использованием помехоустойчивых кодов. Предлагается усовершенствованный метод декодирования с исправлением ошибок и стираний для недвоичных кодов Рида-Соломона (РС), использующий вспомогательные данные двух типов, связанных с предыдущими измерениями и их вариациями. Метод базируется на многоуровневой оценке надежности символов с возможностью персонализации на основе профилей пользователей, с использованием вспомогательных данных и хеша ключа, что позволяет снизить избыточность кодирования при сохранении высокой надежности восстановления.
Предложены две оригинальные стратегии: интеллектуальная, включающая трехкомпонентную оценку надежности символов на основе исторических данных биометрических измерений с гибридным алгоритмом управления стираниями с расширенным поиском (fall-back), а также каскадная, последовательно применяющая фиксированный, адаптивный и приоритетный методы отбора стираний. Оценка метода проводилась с использованием синтетических данных и реальной биометрии человеческих лиц из базы данных UvA-NEMO для кодов РС длины 63 с различной корректирующей способностью: РС(63,21), РС(63,15) и РС(63,11).
Результаты экспериментов демонстрируют прирост успешности декодирования относительно базового алгоритма (без обработки стираний) от 9,5% для РС(63,11) до 43,1% для кода РС(63,21). Интеллектуальная стратегия с fall-back механизмом достигает 96,3% успешности для РС(63,21) при нагрузке в 4 раза меньшей, чем каскадная, а для РС(63,11) обеспечивает 99,8% успешности. При решении задачи аутентификации достигнуты значения FRR менее 1% для РС(63,11) и менее 2% для РС(63,15), что соответствует требованиям большинства практических приложений.
1. Введение
Традиционные биометрические системы (БС) используют как отдельные, так и каскадные схемы кодирования с применением одного или нескольких помехоустойчивых кодов для обеспечения устойчивости к естественным вариациям биометрических характеристик
. Однако известные подходы приводят к недостаточной достоверности или значительной избыточности , . В данном исследовании демонстрируется, что использование расширенных возможностей кодов РС, в частности методов декодирования с исправлением ошибок и стираний, позволяет отказаться от второго каскада кодирования без потери достоверности.Предлагаемая БС реализует модифицированную схему JW (Juels-Wattenberg)
, которая выполняет авторизацию доступа для пользователя с использованием персонального ключа, связанного с его биометрией, имеющее название схемы нечеткого обязательства FC (Fuzzy Commitment). Это криптографический метод, который позволяет связать (зафиксировать) секретное значение с нечеткими, или «зашумленными», биометрическими данными. Применение кодов корректирующих ошибки ECC (Error Correcting Codes) позволяют восстановить исходный секретный ключ, даже если считываемые биометрические данные немного отличаются от тех, что были использованы при фиксации ключа. При регистрации биометрических данных генерируется секретное значение и создаются вспомогательные данные HD (Helper Data), состоящие из закодированного при помощи ЕСС ключа и «наложенного» на кодовое слово биометрического измерения. Вспомогательные данные, по сути, «подсказывают» системе, как восстановить секретное значение на основе последующих, возможно, «зашумленных» считываний биометрических данных. Схема FC при регистрации сохраняет не само секретное значение, а лишь хеш ключа и «зашумлённую» разницу между ключом и биометрией. При аутентификации в БС, реализующей FC, удается восстановить созданный ключ благодаря корректирующей способности кода . Таким образом, безопасная аутентификация обеспечивается проверкой хеша ключа, а конфиденциальность биометрии — отсутствием её хранения в открытом виде . Стремясь преодолеть неотъемлемую проблему шумов, присущих биометрическим данным, и отойдя от концепции безопасного хранения эталонного шаблона, Додис и соавторы в 2004 году модифицировали FC и предложили конструкцию так называемого нечеткого экстрактора FE (Fuzzy Extractor), который позволяет извлекать из биометрического образа стабильный и равномерно распределенный криптографический ключ . Несмотря на то, что фундамент нечётких экстракторов был построен достаточно давно, стремительная эволюция методов глубокого обучения (Deep Learning, DL) предъявляет новые требования к выбору признаков и модальностей.Одной из последних работ, учитывающих эти изменения, стало исследование Курбатова с соавторами
. В этой работе представлена конструкция X-Lock и её модификация Keyed X-Lock, отличающаяся простотой реализации и применимостью на устройствах с ограниченными ресурсами. Однако эти схемы фактически реализуют ЕСС с повторениями и в обоих случаях имеют достаточно высокую вероятность отказа FRR (False Rejection Rate) для ключей большой длины, что ограничивает их практическую применимость. Авторы также рассмотрели конструкцию с двоичными кодами Гоппы, где при длине кода 512 бит максимальная исправляющая способность составляет 56 ошибок (10.9%), что недостаточно для работы с реальным уровнем биометрического шума. Важным вкладом работы являются экспериментальные оценки средних внутриклассового d+ ≈ 0.20 — 0.25 и межклассового расстояния d- ≈ 0.48–0.50 в современных нейросетевых моделях распознавания лиц (InsightFace, AdaFace и других), что определяет требования по учету уровня искажений биометрических признаков более 20%.Для решения этой проблемы в современных БС широко применяются линейные коды блочного типа
, БЧХ-коды и коды РC , .Алгебраический алгоритм декодирования кодов Рида-Соломона
, известный как алгоритм Берлекэмпа-Мэсси (Berlekamp-Massey, BM), стал стандартом для декодирования кодов РС с жестким принятием решения. Алгоритм ВМ до сих пор широко применяется на практике и для его изучения и использования разработано множество программных комплексов, как например , что актуально для подготовки специалистов в области информационной безопасности.В последние годы отмечается активное внедрение методов DL в задачу декодирования помехоустойчивых кодов
, , . Так, в исследовании X. An и др. для оценки количества ошибок используется глубокая нейронная сеть (Deep Neural Network, DNN), которая динамически выбирает или оптимизирует алгоритм декодирования. Однако ограничением этого подхода является валидация на кодах малой длины, что ставит под вопрос его обобщающую способность для более длинных кодов. В работе W. Zhang и др. результатом является трансформация классического стохастического итеративного алгоритма в DNN, что позволяет ввести адаптивные веса и избегать локальных оптимумов, повышая корректирующую способность. Критическим недостатком данного исследования также является его ориентация исключительно на короткий код РС(15,11) без демонстрации масштабируемости, что оставляет открытым вопрос о его вычислительной эффективности и устойчивости при увеличении длины кода.Однако прямое применение передовых DL-методов с DNN к задачам биометрии сталкивается с вычислительными ограничениями при росте размерности полей Галуа и практическими ограничениями при развёртывании на мобильных и встроенных устройствах. В БС актуально применение «легковесных» алгебраических методов, которые эффективно используют информацию о надежности канала для маркировки стираний и коррекции ошибок, но при этом обладают предсказуемой вычислительной сложностью. Предлагаемый в данной работе подход фокусируется не на фундаментальном переосмыслении процесса декодирования с помощью DL, а на целевой оптимизации классической цепочки «оценка надежностей, маркировка стираний, алгебраическое декодирование» для специфических условий биометрических каналов.
В работе рассматривается биометрическая система, в которой секретный ключ K кодируется недвоичным кодом РС длины n символов, что позволяет улучшить эффективность декодирования без применения каскадных кодов
. Для этого вместо традиционного жёсткого декодирования (Hard Decision Decoding, HDD) предлагается метод мягкого декодирования (Soft Decision Decoding, SDD), базирующийся на оценке надёжности символов кода над целочисленным полем Галуа.Новизна исследования определяется двумя предложенными стратегиями обработки биометрических данных: интеллектуальной и каскадной.
Интеллектуальная стратегия — с трехкомпонентной оценкой надежности на основе исторических профилей пользователей и гибридным управлением стираниями с расширенным поиском. Каскадная стратегия — с последовательным применением фиксированного, адаптивного и приоритетного методов отбора стираний. Данные стратегии обеспечивают высокую успешность декодирования при оптимальном балансе вычислительной нагрузки для различных типов кодов.
2. Биометрическая система с двумя образцами вспомогательных данных
Для создания биометрического ключа и формирования устойчивого биометрического шаблона в БС создается супервектор Y = y1 ∪ y2 ⋯ ∪ yM из отдельных векторов yi, где M — количество обрабатываемых биометрических фреймов данных. Это может быть несколько отпечатков пальца либо видеокадров лица человека и т.п. Предлагаемая система реализует схему FC (ниже представлена ее формализация), используя один или два образца вспомогательных данных HD1 и HD2, которые выполняют принципиально различные функции. HD1 содержит данные, связанные с вариацией измерений, которые образуют персонализированную мета-информацию о стабильности биометрических признаков пользователя, применяемую адаптивным алгоритмом для оптимального выбора стираний. Информация HD2 представляет собой публичные криптографические данные, маскирующие секретный ключ. Инновация предлагаемого подхода заключается не в изменении схемы FC, а в использовании HD1 для аналитической оптимизации процесса коррекции ошибок, применяемого к HD2.
Важными характеристиками производительности БС являются вероятность ложного доступа FAR (False Acceptance Rate) и вероятность ложного отказа FRR (False Rejection Rate). Величина FRR зависит от вероятности ошибки на символ perr для биномиального распределения Xi ~Bin(ni, perr) и фактически ограничена сверху вероятностью того, что в i-том блоке данных число ошибок превысит порог коррекции ti FRRi ~ P(Xi>ti)
.При равномерном квантовании на L уровней вероятность «угадать» отдельный символ для злоумышленника равна (pg=1)/L. Тогда, в рамках биномиальной модели для Y~Bin(n, pg), где Y — количество угаданных злоумышленником символов, вероятность FAR вычисляется как FAR=P(Y≥k), где k – порог восстановления ключа. Оптимальным для решаемой задачи признано квантование на L=64 уровня. Данный шаг квантования более чем на порядок меньше среднего абсолютного отклонения биометрических данных и гарантирует надёжное разделение различных реализаций одного признака.
Классическая модель биномиального канала предполагает, что вероятность ошибки символа p_err фиксирована и одинакова для всех символов, а ошибки статистически независимы. Однако, как показано в работе
и подтверждено экспериментальными данными, реальное распределение вещественных биометрических признаков существенно отличается от равномерного. На основе анализа тестовой выборки базы данных UvA-NEMO с применением критерия согласия Колмогорова-Смирнова установлено, что распределение признаков наилучшим образом аппроксимируется бета-распределением с параметрами α=7,223 и β=3,754. Выбор обоснован минимальным значением статистики (D=0.024, с p-value>0.05) по сравнению с альтернативными распределениями (см. зависимость распределений от надежности на рис. 1).Переход от биномиальной модели к бета-распределению принципиально меняет оценку вероятности ошибки символа p_err при равномерном квантовании на L=64 уровня. Оценка ошибки квантования, отображающая вариативность биометрических данных, описывается на основе функции плотности вероятности f(x), которая аппроксимируется бета-распределением и может быть получена с учетом независимости двух измерений при попадании в интервал квантования
В биномиальной модели с равномерным распределением признаков perr составляла около 0.25, тогда как для бета-распределения численное интегрирование даёт perr=0.174.
Современные тенденции к криптографической стойкости биометрических систем определяют использование ключей длиной не менее 128 бит
. В данной работе были выбраны три основных кода для эффективной реализации БС в предположении, что используется квантование с уровнем L=6 бит:– код РС(63,21), для которого достаточно M=1 кодового слова (длина ключа: 21×6=126 бит, близко к 128 бит).
– код РС(63,15), в случае которого необходимо 2 кодовых слова для длины ключа 2×15×6=180 бит (более 128 бит).
– код РС(63,11), который требует M=2 кодовых слова (длина ключа: 2×11×6=132 бита).
Выбор между ними определяется компромиссом между вычислительной сложностью, особенностями применения в режиме исправления ошибок и стираний, в параметрах FAR и FRR. Для кода РС(63,21) без использования стираний переход от биномиальной модели (perr=0,22) к бета-распределению (perr=0,174) снижает FRR с 1,02% до 0.19%. А для кода РС(63,15) и РС(63,11) при perr=0,174 величина FRR составляет 3,4×10-6 и 1,2×10-7 соответственно.
При фиксированной общей вероятности искажения символа perr переход от ошибок к стираниям позволяет снизить «стоимость» искажений с 2perr до 2pe+ps, что эквивалентно увеличению запаса исправляющей способности на nps, где n — длина кода, а ps — вероятность стирания символа и pe — вероятность ошибки, которые в сумме дают perr.
Доля успешного декодирования кода с учетом стираний, например РС(63,21), вычисляется сумма трехчленного распределения по всем допустимым комбинациям числа ошибок Ne=e и числа стираний Ns=s:
где 1[2e+s≤42] — индикаторная функция, которая «включает» те слагаемые, которые допустимы с точки зрения корректирующей способности кода.
При введении декодирования со стираниями с параметрами pe=0,10, ps=0,074, сумма которых дает perr=0,174, FRR для кода РС(63,21) сокращается до 2,4×10-7, а для кодов РС(63,15) и РС(63,11) уменьшается до значений 2,3×10-10 и 10-12 соответственно. Параметр FAR также претерпевает изменения для бета-распределения с perr=0,174 и L=64 FAR и составляет менее 10-20 для всех кодов.
При бета-распределении код РС(63,21) остаётся вполне приемлемым для многих приложений с FRR=0,19%. Однако для критических применений, требующих FRR менее 10-6, безальтернативным становится использование двух кодовых слов РС(63,11) или РС(63,15). Декодирование со стираниями в сочетании с бета-распределением позволяет достичь FRR=2,4×10-7 даже для кода РС(63,21). Это демонстрирует, что правильный учёт статистических характеристик источника может компенсировать недостаточную исправляющую способность кода.
3. Декодирование кодов Рида-Соломона
Известно, что результатом HDD-декодирования кода с n символами является либо декодированное сообщение, либо индикация ошибки декодирования. Однако код РС позволяет исправлять не только ошибки, но и стирания. Если Ns символов кода помечены как стертые, а оставшиеся n-Ns символов содержат Ne ошибок, алгоритм BM находит правильное кодовое слово при выполнении условия, связанного с кодовым расстоянием d
:Если Ns=0, декодер используется как декодер только для коррекции ошибок, а если 0<Ns≤d-1, декодер называется декодером ошибок-и-стираний (Error-and-Erasure Decoding, EED). Однако для применения принципа EED необходимо определить, какие символы являются ошибочными или стертыми.
В распоряжении декодера имеются исторические данные HD1, формируемые на основе абсолютных отклонений предшествующих биометрических измерений от среднего значения (или от центра квантования):
где yij — i-ый элемент в j-том биометрическом образце, μi — его базовое значение.
Таким образом, отклонения Di могут служить дополнительной информацией для реализации EED на этапе верификации в биометрической системе. Для этого в обрабатываемом кодовом слове необходимо пометить Ns элементов из общего числа символов n как стирания и сформировать вектор стирания на основе интегральной метрики надежности, получаемой путем адаптивной агрегации трех компонент, описанной ниже.
В основу выбора стратегии стираний положим аналитический подход, основанный на работе Вебера и др.
, в которой параметры кода d и количество ошибок Ne заменяются относительными долями δ=d/n, ε=Ne/n. Дискретный вектор надёжности символов аппроксимируется непрерывной функцией распределения h(ϕ), ϕ∈(0,1]. Затем определяется оптимальная доля стираний τ*, максимизирующая корректирующую способность кода на основе интегральной «накопленной ненадежности» ∆h (τ). После этого значение τ* преобразуется в пороговый уровень надежности hthreshold и все символы с надежностью ниже этого порога объявляются стираниями.На основе сформированного вектора стирания выполняется процедура EED. Если декодирование оказывается неудачным, активируется механизм расширенного поиска (fall-back), в рамках которого количество стираний последовательно увеличивается. Процесс продолжается до тех пор, пока либо декодирование не завершится успешно с восстановлением ключа K, либо не будут исчерпаны все итерации.
4. Математическая модель БС и процедура верификации ключа
Пользовательский ключ K длины k кодируется кодом РС с параметрами (n, k) над полем GF(2m), в результате чего формируется кодовое слово:
На этапе регистрации биометрический образец пользователя подвергается квантованию
, в результате чего формируется вектор Z∈{0, 1, …, 2m-1}n. Побитовое сложение по модулю 2 кодового слова с квантованными данными дает публичные вспомогательные данные HD2:Параллельно формируется вектор исторических разностей D, статистические характеристики которого (квантили Q1, Q3, коэффициент вариации CVi) составляют вспомогательные данные HD1.
На этапе верификации пользователь предъявляет новое биометрическое измерение, которое квантуется в вектор Z'. Восстановление искаженного кодового слова выполняется как:
Разность Z⊕Z^' представляет собой зашумленный вектор, указывающий позиции, в которых произошли изменения квантованных значений.
Для организации эффективного декодирования вычисляется вектор надежности R=(R(1),R(2),…,R(n)) где R(i)∈[0,1] характеризует степень доверия к корректности i-того символа. Методика вычисления R(i) подробно рассматривается в следующем разделе.
На основе вектора R формируется множество стираний:
где h — пороговое значение, определяемое выбранной стратегией декодирования. Затем выполняется EED — декодирование искаженного кодового слова C' с учетом позиций стираний:
Успешным считается декодирование, при котором восстановленный ключ совпадает с исходным ключом.
5. Нахождение компонент надежности
Для реализации эффективного EED критически важной является точная оценка надежности символов. Предлагается трехкомпонентный метод оценки надежности на основе исторических разностей.
Компонента 1: Первая компонента отражает тот факт, что символы, демонстрирующие стабильность в предыдущих измерениях, должны получать более высокую оценку надёжности. Она вычисляется как:
где Di — историческая разность для i-того символа, определяемая как среднее отклонение его значений от среднего (или от центра квантования) на обучающей выборке, что на практике приводит фактически к тем же результатам.
Компонента 2: Вторая компонента учитывает относительную стабильность символа с учетом его среднеквадратичного отклонения σi, нормированного на значение центра квантования μi.
Эта компонента, обратная к коэффициенту вариации CVi=σi/μi, определяется как
Компонента 3: Третья компонента представляет собой дискретную оценку, основанную на положении исторической разности Di относительно квантилей её эмпирического распределения:
где Q1 и Q3 — первый и третий квантили распределения исторических разностей. Такой подход позволяет разделить символы на три категории: стабильные (высокая надёжность), промежуточные (средняя надёжность) и нестабильные (низкая надёжность).
В отличие от простого усреднения, предлагается изучить динамическое формирование весовых коэффициентов для каждой компоненты, учитывающее накопленный опыт взаимодействия с пользователем. Процесс адаптивной агрегации компонент надежности может быть реализован в четыре этапа:
Этапы адаптивной агрегации компонент надежности
здесь 0.9 и 0.1 – коэффициенты экспоненциального сглаживания веса
Этап | Измерения | Механизмы | Результат |
1 | a=1 | Разные веса w1=w2=w3=1⁄3 | Нейтральный статус |
2 | a=2 | Веса по согласованности wj=cj/(∑ck) | персонализация |
3 | a≥3 | Экспоненциальное сглаживание wj=0,9wj+0,1ej | Плавная оптимизация |
4 | a→∞ | Сходимость к оптимальным значениям | Стабилизация |
При первом измерении используется равное взвешивание. После второго измерения вычисляется согласованность каждого источника, отражающая стабильность его оценок между двумя последовательными измерениями, где верхние индексы 1 и 2 обозначают номер измерения (метку времени):
отражающая стабильность оценок между двумя последовательными измерениями. Веса для второго измерения формируются пропорционально согласованности:
Начиная с третьего измерения, включается механизм экспоненциального сглаживания с коэффициентом памяти p. После каждого успешного декодирования вычисляется эффективность источников:
где vi=1 если символ i декодирован правильно. Обновление весов производится по формуле wj(new)=0.9wj(old)+0.1ej с последующей нормировкой. Коэффициент p=0,9 обеспечивает время полужизни информации около 7 измерений, что гарантирует устойчивость к случайным выбросам.
Итоговая надежность символа вычисляется как взвешенная сумма:
6. Оптимизация стратегии стираний
Полученный вектор надежностей R используется для аналитической оптимизации доли стираний. Сначала строится эмпирическая функция распределения надежностей h(φ) путем сортировки R(i) по возрастанию. Полученное распределение аппроксимируется бета-распределением Beta(α,β). Для аппроксимирующего распределения Iφ(α,β) вычисляется оптимальная доля стираний τ*, максимизирующая корректирующую способность
:где τ — доля стираний, а λ — параметр декодирования кода РС, имеющий λ=2 (для BM случая) и определяющий нормированный радиус исправления ошибок ϵ(τ)=(δ-τ)/λ.
Далее методом прямого поиска по отсортированному массиву надежностей определяется пороговое значение hthreshold=R(⌈τ*n⌉), и все символы с R(i)≤hthreshold маркируются как стирания.
7. Две стратегии декодирования РС кодов с анализом надежностей символов
Искажённое кодовое слово, возникающее из-за различий биометрических образцов после вычитания HD2, в большинстве случаев успешно декодируется, позволяя восстановить ключ K, вычислить его хеш и сравнить с эталонным. Достоверность (успешность декодирования) определяется применяемым кодом и алгоритмом декодирования.
Для кода РС с кодовым расстоянием d условие успешного декодирования определяет нагрузку на декодер Load, при которой возможно выполнение декодирование EDD: Load≤2Ne+Ns и которая может иметь значение MaxLoad=d-1.
Предложим 2 стратегии маркировки стираний, представленные в виде алгоритма 1 и алгоритма 2.
1. Алгоритм 1. Адаптивное декодирование с интеллектуальным управлением
Вход: вектор надежностей R, полученное кодовое слово Cest, профиль пользователя profile
Выход: восстановленный ключ Kdecoded
1. Вычисление скорректированных метрик с учетом границ квантования.
Для каждого символа i:
Определить ближайший центр μtarget и соседний центр μneighbor
Вычислить базовое расстояние basedist=|yi-μtarget|
Вычислить расстояние до соседнего центра boundarydist=|yi-μneighbor|
Если нет превышения порога boundarydist<threshold,
то вводится штраф с коэффициентом kp:
Иначе penalty=0
Скорректированное расстояние: Di=basedist+penalty
Компоненты надежности:
R3(i) — квантильная классификация по Di и (Q1, Q3) из HD1
2. Адаптивная агрегация компонент
В зависимости от номера измерения a:
Если a=1: Rfinal(i)=(R1(i)+R2(i)+R3(i))/3
Если a=2:
Вычислить согласованности cj=1-1/n ∑|Rj1(i)-Rj2(i)|
Вычислить веса wj=cj/(c1+c2+c3)
Если a≥3:
Загрузить текущие веса wj из профиля
3. Оптимизация стратегии стираний
Отсортировать Rsorted=sort(Rfinal)
Аппроксимировать распределение R_sorted бета-распределением Beta(α,β) методом моментов
Найти оптимальную долю стираний τ*=arg maxr ∆h(τ)
Определить количество стираний k=⌈τ*∙n⌉
Вычислить порог hthreshold=Rsorted (k)
4. Основная попытка декодирования
Сформировать множество стираний erasures={i| Rfinal(i)≤hthreshold}
Если количество Ns: |erasures|≤2t:
Выполнить декодирование Kdecoded=EEDdecode(Cest, erasures)
При успехе: обновить профиль и вернуть Kdecoded
5. Расширенный поиск (резервный механизм)
6. Получить индексы в порядке возрастания надежности
Для ktest=k+1 до 2t:
При успехе: обновить профиль и вернуть Kdecoded
Обновление профиля при успехе
Вычислить эффективность ej каждого источника
Обновить веса: wj=0.9∙wj+0.1∙ej
Нормировать веса
Обновить квантили (Q1, Q3) с учетом новых Di
8. Возврат ошибки декодирования в случае неудачи всех попыток
2. Алгоритм 2: Каскадное декодирование с равными весами
Вход: вектор надежностей R, полученное кодовое слово Cest, профиль пользователя profile
Выход: восстановленный ключ Kdecoded
1. Вычисление базовых компонент надежности
Для каждого символа i:
Rbase(i)=1/(1+basedist(i)) — расстояние до центра интервала
R2(i)=1⁄((1+CV_i)) — коэффициент вариации
R3(i) — квантильная классификация по basedist(i) и (Q1, Q3) из HD1
Итоговая надежность с равными весами:
2. Каскадный перебор стратегий
Уровень 1: Фиксированная стратегия (Fixed)
Если для Ne, Ns: 2|errors|+|erasures|≤Max_Load:
При успехе: обновить профиль и вернуть Kdecoded
Уровень 2: Адаптивная стратегия с усечением нагрузки (Adaptive limited)
Вычислить квартили Q1(R) = quantile(Rfinal, 0.25); Q3(R) = quantile(Rfinal, 0.75)
Кандидаты на ошибки: allerrors = find(Q1(R)<Rfinal≤Q3(R))
Кандидаты на стирания: allerasures = find(Rfinal≤Q1(R))
Сортировать кандидаты по возрастанию надежности
Усечь нагрузку: удалять самые ненадежные символы, пока 2|errors|+|erasures|≤Max_Load
При успехе: обновить профиль и вернуть Kdecoded
Уровень 3: Стратегия приоритетного стирания (Erasure priority)
Определить максимально возможное число стираний
Отсортировать индексы по возрастанию надежности:
sortedindices=argsort(Rfinal)
Выбрать k' худших символов: erasures= sortedindices[1:k']
Kdecoded=EED_decode(Cest, erasures)
При успехе: обновить профиль и вернуть Kdecoded
3. Обновление профиля
Обновить квантили Q1, Q3 c учетом новых измерений
4. Возврат ошибки декодирования в случае неудачи всех трех попыток.
Представленные алгоритмы реализуют принципиально разные подходы к декодированию. Стратегия с интеллектуальным управлением делает акцент на максимально точную оценку надёжности каждого символа, используя штрафы за близость к границам квантования и динамическую адаптацию весов трёх компонент на основе истории пользователя. Дополнительно применяется аналитическая оптимизация доли стираний τ* через бета-аппроксимацию и резервный расширенный поиск fall-back.
Каскадная стратегия, напротив, использует упрощённые метрики без штрафов и с равными весами, но компенсирует это интеллектуальным перебором трёх базовых методов декодирования в оптимальном порядке. Сначала применяется быстрая фиксированная стратегия с эмпирически подобранными порогами 0,35/0,65. В случае неудачи задействуется адаптивная стратегия с усечением нагрузки, позволяющая уложиться в ограничения кода. Последним резервом служит стратегия приоритетного стирания, гарантирующая допустимую нагрузку ценой потери части информации.
8. Экспериментальные результаты
Перед непосредственным сравнением стратегий декодирования на основе статистического анализа был реализован этап предварительного обучения параметров штрафной функции penalty, учитывающей близость символа к границе интервала квантования. Из 15 возможных попарных комбинаций 6 биометрических измерений для каждого пользователя выделялось 7 обучающих пар и 8 тестовых. Для каждого символа фиксировались три величины: расстояние до соседнего центра boundarydist, расстояние до своего центра basedist и бинарный факт ошибки (перескока в другой интервал) erroroccurred.
Процесс обучения включал последовательную реализацию следующих шагов: дискретизацию пространства значений boundarydist на интервалы, оценку условной вероятности ошибки в каждом интервале, поиск порогового значения, при котором риск ошибки превышает 20%, и расчёт коэффициента штрафа kp, обеспечивающего желаемое снижение надёжности для символов в опасной зоне, определяемой пороговым значением threshold. Полученные таким образом параметры (threshold и kp) использовались в адаптивной стратегии с интеллектуальным управлением для коррекции метрики R1.
После завершения этапа обучения был проведён эксперимент по сравнению трёх стратегий декодирования: фиксированной (Fixed), адаптивной с интеллектуальным управлением (Adaptive+штраф+веса) и комбинированной каскадной. Оценка производилась для трёх кодов РС с различной избыточностью – РС(63,21), РС(63,15) и РС(63,11) — при пяти уровнях шума, соответствующих доле ошибочных символов от 16% до 46%. Данные, полученные при 95% уровне доверия, сведены в таблицу 2 и показаны на рисунке 1.
Сравнительный анализ трёх стратегий декодирования
Код РС | Шум | Фиксированная стратегия, % | Адаптивная стратегия с интеллектуальным управлением, % | Комбинированная каскадная стратегия, % |
РС(63,21) | 0,50 | 100,0 [99,3-100,0] | 99,5 [98,7-100,0] | 100,0 [99,3-100,0] |
0,75 | 86,0 [82,6-89,4] | 80,5 [76,7-84,3] | 89,0 [85,9-92,1] | |
1,00 | 50,0 [45,1-54,9] | 46,5 [41,6-51,4] | 52,0 [47,1-56,9] | |
1,25 | 25,5 [21,4-29,6] | 20,5 [16,8-24,2] | 30,0 [25,7-34,3] | |
1,50 | 12,0 [9,1-14,9] | 8,5 [6,1-10,9] | 12,5 [9,6-15,4] | |
РС(63,15) | 0,50 | 99,5 [98,7-100,0] | 99,0 [98,0-100,0] | 100,0 [99,3-100,0] |
0,75 | 89,0 [85,9-92,1] | 87,5 [84,2-90,8] | 90,0 [86,9-93,1] | |
1,00 | 70,0 [65,5-74,5] | 69,0 [64,4-73,6] | 75,0 [70,8-79,2] | |
1,25 | 48,5 [43,6-53,4] | 48,5 [43,6-53,4] | 52,5 [47,6-57,4] | |
1,50 | 20,0 [16,3-23,7] | 17,5 [14,0-21,0] | 22,5 [18,7-26,3] | |
РС(63,11) | 0,50 | 100,0 [99,3-100,0] | 99,5 [98,7-100,0] | 100,0 [99,3-100,0] |
0,75 | 96,5 [94,5-98,5] | 93,5 [90,9-96,1] | 98,5 [97,1-99,9] | |
1,00 | 81,0 [77,2-84,8] | 80,5 [76,7-84,3] | 85,0 [81,5-88,5] | |
1,25 | 54,0 [49,1-58,9] | 60,5 [55,7-65,3] | 57,5 [52,6-62,4] | |
1,50 | 36,0 [31,5-40,5] | 35,5 [31,0-40,0] | 39,5 [34,9-44,1] |
Усреднение результатов по всем трём кодам и пяти уровням шума (см. рисунок 1) показывает, что комбинированная каскадная стратегия обеспечивает наилучшие показатели с общей успешностью 65.2%, превосходя фиксированную стратегию (62.5%) на 2.7 процентных пункта и адаптивную с интеллектуальным управлением (60.4%) на 4.8 процентных пункта. При этом фиксированная стратегия, несмотря на свою простоту, демонстрирует более высокую эффективность, чем сложная адаптивная схема со штрафами и обучаемыми весами. Фиксированная стратегия применяет неизменные пороги для маркировки стираний и ошибок, что обеспечивает простоту и предсказуемость без этапа обучения.
Для кода с наименьшей избыточностью РС(63,21) комбинированная стратегия достигает средней успешности 56.7%, что на 1.9% выше фиксированной и на 5.6% выше адаптивной. Наибольший выигрыш наблюдается при средних уровнях шума: при σ=1.0 успешность комбинированной каскадной стратегии составляет 52.0% против 46.5% у адаптивной, при σ=1.0–30.0% против 20.5%. Это свидетельствует о способности каскадного подхода эффективно использовать резервные механизмы именно в тех условиях, где простые стратегии перестают справляться.
Для кода средней избыточности РС(63,15) средняя успешность комбинированной стратегии достигает 68.0%, что на 2.6% выше фиксированной и на 3.7% выше адаптивной. Максимальное преимущество зафиксировано при σ=1.0: 75.0% против 69.0% у адаптивной (+6.0%). При высоком уровне шума (σ=1.5) комбинированная стратегия сохраняет преимущество в 2.5% над фиксированной и 5.0% над адаптивной.
Наиболее мощный код РС(63,11) ожидаемо демонстрирует наилучшие абсолютные показатели: средняя успешность комбинированной стратегии составляет 76.1%, что на 2.6% выше фиксированной и на 2.2% выше адаптивной. При σ=1.25 наблюдается единственное исключение, где адаптивная стратегия незначительно превосходит комбинированную (60.5% против 57.5%), однако при максимальном шуме σ=1.5 комбинированная стратегия вновь выходит в лидеры с результатом 39.5% против 35.5% у адаптивной. Суммируя результаты по всем трём кодам, комбинированная каскадная стратегия обеспечивает устойчивое преимущество в 13 из 15 исследованных точек (87% случаев), а адаптивная стратегия с интеллектуальным управлением, несмотря на свою вычислительную сложность в среднем проигрывает всем стратегиям.
Для сравнения предлагаемых стратегий EDD декодирования кодов РС было также изучена обработка реальных измерений из биометрии человеческих лиц, взятых из базы данных UvA-NEMO [5] которые после квантования кодировались различными кодами РС длиной 63 символа. Выборка содержала 240 различных биометрических образцов, составленных из 6-ти измерений для 40 пользователей, что соответствовало объему сгенерированных синтетических данных.
Ключевым результатом стало то, что использование реальных данных показало существенно более высокую эффективность предложенных стратегий, чем предсказывали синтетические модели. Для кода РС(63,21) интеллектуальная стратегия достигла 84.2% успешности на реальных данных, что соответствует синтетическому шуму σ≈0.65, а каскадная стратегия (93.3%) – σ≈0.55. Еще более впечатляющие результаты получены для РС(63,11), где интеллектуальная стратегия обеспечила 99.8% успешности, что эквивалентно работе в условиях минимального шума.
На реальной биометрии отчетливо проявилось преимущество интеллектуальной стратегии, использующей индивидуальные профили пользователей (коэффициенты вариации CVi и квантили Q1, Q3). В то время как на синтетических данных преимущество интеллектуальной стратегии перед базовой было умеренным (46.5% против 50.0% для РС(63,21) при σ=1.0), а на реальных данных разрыв составил 43 процентных пункта (84.2% против 41.2%).
Сравнение эффективности 3-х методов декодирования
– адаптивная агрегация весов в зависимости от номера измерения не дает значимого преимущества (разница менее 1%), что позволяет использовать упрощенную версию с равными весами;
– использование центров квантования и средних значений дает сопоставимые результаты, оба подхода работоспособны;
– штраф за близость к границам квантования не влияет на итоговую успешность при качественном определении стираний.
Механизм резервирования fall-back с увеличением числа стираний при неудаче оказался критически важным, обеспечивая прирост успешности до 12% для слабых кодов.
9. Практические рекомендации и оценка сложности предложенных алгоритмов
На основе проведенного анализа может быть рекомендована следующая оптимальная стратегия для практического применения в биометрических системах:
– для высоконадежных систем целесообразно использовать код РС(63,11), обеспечивающий 99.8% успешности при минимальной нагрузке равной 13.
– для систем с ограниченными вычислительными ресурсами оптимален код РС(63,15) с 98.3% успешности и той же нагрузкой.
– интеллектуальная стратегия должна использовать равные веса компонент и обязательный fall-back механизм.
Важным аспектом практического применения разработанных алгоритмов является их вычислительная сложность, определяющая возможность реализации в системах реального времени с ограниченными ресурсами.
Базовая стратегия без использования стираний служит естественным ориентиром: она требует лишь однократного вызова декодера кода РС, что делает её минимальной по сложности. Фиксированная стратегия с порогами 0.35/0.65 добавляет к этому два линейных прохода по массиву надёжностей для идентификации стираний и ошибок (сложность O(n)), что увеличивает время выполнения примерно на 10-15% при незначительном росте потребления памяти.
Интеллектуальная адаптивная стратегия с персонализированными параметрами в своей теоретически полной реализации требует хранения профилей пользователей и нормализации массива надёжностей для аппроксимации бета-распределением. Однако, как показали эксперименты, вычисление оптимального τ является вычислительно затратным и не даёт значимого выигрыша по сравнению с использованием фиксированного значения τ. В упрощённой реализации, применённой в данном исследовании, интеллектуальная стратегия использует равные веса компонент и фиксированную долю стираний, что снижает её сложность.
Комбинированная каскадная стратегия, последовательно применяющая методы с фиксированными порогами, адаптивный с ограничением нагрузки и приоритетный по стираниям, демонстрирует оптимальный баланс между эффективностью и вычислительной сложностью. В лучшем случае (когда срабатывает fixed) она требует лишь линейного прохода по данным и одного декодирования; в худшем – выполняет до трёх попыток декодирования и две-три сортировки массива надёжностей. При этом каскадная стратегия не нуждается в предварительном обучении и может быть реализована с теми же требованиями к памяти, что и фиксированная.
Информация по оценке сложностей сведена в таблице 3.
Сводная таблица вычислительной сложности стратегий декодирования
*относительно базовой с кратным (×) увеличением времени обработки; ** – количество пользователей (хранение индивидуальных профилей)
Стратегия | Память | Попыток декодирования (ср./макс) | Доп. вычисления | Относительное время* |
Базовая | O(n) | 1,0/1 | нет | 1,0× |
Фиксированная | O(n) | 1,0/1 | линейный проход O(n) | 1,1-1,2× |
Интеллектуальная (упрощенная) | O(n) | 1,15/42 | 1 сортировка O(n logn)+fall-back | 2,0-2,5× |
Интеллектуальная (полная) | O(n∙m)** | 1,15/42 | 50×betainv+сорти-ровка | 50-100× |
Комбинированная | O(n) | 1,5/3 | 2-3 сортировки O(n logn) | 1,5-3,0× |
Интеллектуальная стратегия в полной версии требует хранения индивидуальных профилей для каждого пользователя (память O(n∙m), где m — число пользователей) и выполнения этапа обучения, в ходе которого методом полного перебора подбираются оптимальные весовые коэффициенты компонент надёжности. Интеллектуальная стратегия в упрощённой версии с фиксированным τ=0,2 и равными весами также требует формирования профиля пользователя (центры квантования, коэффициенты вариации CVi и квантили Q1, Q3), однако этот процесс не связан с пробными декодированиями и выполняется однократно по 5 эталонным измерениям с линейной вычислительной сложностью O(n).
На основе проведённого анализа вычислительной сложности и эффективности различных стратегий декодирования можно сформулировать следующие рекомендации для практической реализации.
Для большинства биометрических систем оптимальным выбором является комбинированная (каскадная) стратегия с кодом РС(63,15), которая обеспечивает 99.2% успешности декодирования при умеренной вычислительной нагрузке (в 1,5–3 раза выше базовой) и не требует предварительного обучения, что критически важно для сценариев с быстрой регистрацией новых пользователей.
В системах с жёсткими ограничениями по энергопотреблению или вычислительным ресурсам (мобильные устройства, встраиваемые системы) предпочтительна упрощённая интеллектуальная стратегия с фиксированным τ=0.2 в сочетании с кодом РС(63,11). Она демонстрирует 99,8% успешности при нагрузке всего 13, что в 2.5 раза меньше комбинированной стратегии, однако требует однократного формирования профиля пользователя по эталонным измерениям. Для слабых кодов, таких как РС(63,21), комбинированная стратегия остаётся безальтернативным лидером (93,3% против 84,3% у интеллектуальной), несмотря на более высокую нагрузку.
Полная версия интеллектуальной стратегии с оптимизацией доли стираний τ* через бета-аппроксимацию признана нецелесообразной для практического применения из-за многократного роста вычислительной сложности в (50–100×) при отсутствии значимого выигрыша в успешности. Однако при наличии 10 и более эталонных измерений интеллектуальная стратегия с fall-back становится предпочтительной, достигая сопоставимой успешности с нагрузкой 13,6 против 55 у комбинированной.
Комбинированная и фиксированная стратегии не нуждаются в предварительном обучении и могут применяться непосредственно после получения эталонных измерений.
10. Заключение
Оценка метода декодирования проводилась с применением синтетических данных для кодов РС(63,21), РС(63,15) и РС(63,11), а также с использованием биометрии человеческих лиц, взятых из базы данных UvA-NEMO
. Проведенное исследование продемонстрировало, что использование реальных биометрических данных позволило не только подтвердить эффективность разработанных алгоритмов, но и выявить их преимущества, которые оставались незамеченными при работе только с синтетической информацией. В частности, на реальных данных интеллектуальная стратегия показала результаты, соответствующие синтетическому шуму σ≈0.6-0.65, что подтверждает адекватность выбранных моделей и значимость персонализации.Разработанные методы обеспечивают прирост успешности декодирования относительно базового алгоритма без учета стираний от 9,5% для сильного кода РС(63,11) до 43,1% для слабого кода РС(63,21). Комбинированная (каскадная) стратегия достигла 93,3% успешности для РС(63,21), а интеллектуальная стратегия с fall-back механизмом — 96,3% при нагрузке в 4 раза меньшей.
Экспериментально установлено, что адаптивная агрегация весов компонент надежности не дает значимого выигрыша (разница менее 1%), что позволяет использовать упрощенную версию с равными весами. Фиксированная доля стираний τ=0.2 оказалась близкой к оптимальной для всех рассмотренных кодов, а применение fall-back механизма обеспечивает дополнительный прирост успешности до 12% для слабых кодов без существенного увеличения средней нагрузки. При решении задачи аутентификации предложенные методы позволяют достичь FRR менее 1% для кода РС(63,11) и FRR менее 2% для РС(63,15), что соответствует требованиям большинства практических приложений.
На основе анализа результатов экспериментов на реальных биометрических данных и синтетических данных можно сформулировать следующие рекомендации по выбору кода и стратегии декодирования.
– Для систем, требующих максимальной надежности (успешность >99%, FRR<1%), оптимальным выбором является код РС(63,11) в сочетании с интеллектуальной стратегией (равные веса, только стирания, fall-back механизм), которая обеспечивает 99,8% успешности при минимальной нагрузке 13 и сохраняет эффективность даже при высоком уровне шума (σ=1,0 в синтетических экспериментах).
– Для систем с ограниченными вычислительными ресурсами, где важен баланс между надежностью и сложностью, рекомендуется код РС(63,15) с той же интеллектуальной стратегией, демонстрирующий 98.3% успешности на реальных данных при нагрузке 13. Эта конфигурация обеспечивает оптимальное соотношение эффективности и вычислительных затрат.
– Код РС(63,21) с каскадной стратегией целесообразно применять в сценариях с очень высоким уровнем шума (эквивалентным σ≥1,25 в синтетике), когда критически важна максимальная успешность (93.3% на реальных данных), а вычислительные ресурсы не ограничены. При наличии 10 и более эталонных измерений интеллектуальная стратегия с fall-back становится предпочтительной, достигая 95–97% успешности при нагрузке 13.6.
– Во всех случаях ключевыми элементами успеха являются формирование индивидуальных профилей пользователей по эталонным измерениям и обязательное применение fall-back механизма.
– Кроме того, в отличие от ранее исследованного на базе UvA-NEMO подхода с каскадными кодами
, повышающего корректирующую способность ценой кратного роста сложности и длины ключа, предложенный метод интеллектуального управления стираниями решает ту же задачу за счет более точной оценки надежности символов на основе персонализированного профиля пользователя.– Достигнутые результаты открывают ряд перспективных направлений для развития предложенного метода декодирования кодов РС с интеллектуальным управлением стираниями:
– Расширение области применения. Валидация подхода на других биометрических модальностях (отпечатки пальцев, радужная оболочка, голос) для создания многомодальных систем.
– Совершенствование статистического профилирования. Разработка методов коррекции оценок распределения при малых выборках с использованием байесовских подходов и оптимизация бета-аппроксимации для снижения вычислительной сложности.
– Архитектурные преобразования. Переход к распределённым архитектурам на основе схем разделения секрета Шамира и интеграция с блокчейн-технологиями для децентрализованного хранения биометрических данных
, .