Алгоритмы и защищенные системы биометрической аутентификации личности тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Поляков, Андрей Владимирович

• Поляков, Андрей Владимирович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Поляков, Андрей Владимирович

Оглавление

Стр.

Введение

Глава 1. Алгоритмы верификации личности по отпечаткам

пальцев

1.1 Содержательная постановка задачи верификации личности по отпечаткам пальцев

1.1.1 Предварительные сведения о биометрических системах

1.1.2 Определение начальных условий

1.2 Существующие методы верификации личности по отпечаткам пальцев и мотивировка исследования

1.3 Алгоритм верификации личности по отпечаткам пальцев на

основе структуры созвездий

1.3.1 Математическая модель отпечатка пальца

1.3.2 Формальная постановка задачи верификации личности

1.3.3 Предварительные сведения и определения

1.3.4 Алгоритм верификации отпечатков пальцев на основе структуры созвездий («Аэ^-алгоритм»)

1.3.5 Экспериментальные результаты

1.4 Алгоритм верификации личности по отпечаткам пальцев на

основе поиска максимального пути в графе

1.4.1 Математическая модель отпечатка пальца

1.4.2 Формальная постановка задачи верификации личности

по отпечаткам пальцев

1.4.3 Алгоритм верификации отпечатков пальцев на основе поиска максимального пути в графе

(«Рт§егРа1;Ь»-алгоритм)

1.4.4 Экспериментальные результаты

1.5 Выводы

Глава 2. Алгоритм идентификации личности по отпечаткам

пальцев

2.1 Содержательная постановка задачи идентификации личности по

отпечаткам пальцев

2.2 Существующие методы идентификации личности по отпечаткам

пальцев

2.2.1 Оценка эффективности методов классификации

2.2.2 Методы непрерывной классификации (индексирование)

2.2.3 Оценка эффективности методов непрерывной классификации

2.2.4 Выводы по краткому обзору методов биометрической идентификации

2.3 Метод идентификации личности по отпечаткам пальцев на

основе сферического локально-чувствительного хэширования

2.3.1 Формальная постановка задачи поиска приближенного ближайшего соседа

2.3.2 Локально-чувствительное хэширование (ЬБЫ) и сферическое локально-чувствительное хэширование

2.3.3 Математическая модель отпечатка пальца, основанная на аппроксимации поля направлений обобщенными многочленами Чебышева

2.3.4 Алгоритм идентификации личности по отпечатку пальца на основе сферического локально-чувствительного хэширования

2.3.5 Экспериментальные результаты

2.4 Выводы

Глава 3. Защищенная система биометрической аутентификации

3.1 Синергия криптографии и биометрии

3.2 Системы шифрования с открытым ключом и их безопасность

3.2.1 Средства противника

3.2.2 Цели противника

3.2.3 Односторонность

3.2.4 Неразличимость

3.3 Предположения безопасности

3.3.1 Модель случайного оракула

3.3.2 Вычислительно сложные задачи

3.4 Предварительные сведения и определения

3.4.1 Схема разделения секрета Шамира

3.4.2 Нечеткие экстракторы

3.5 Обработка биометрических данных

3.6 Определение общей схемы биометрического личностного шифрования

3.7 Модель угрозы

3.8 Система биометрического личностного шифрования

3.8.1 Список обозначений

3.8.2 Подготовительный этап

3.8.3 Экстракция

3.8.4 Шифрование

3.8.5 Расшифровка

3.9 Анализ безопасности

3.10 Сравнение с существующими нечеткими системами личностного шифрования

3.11 Выводы

Заключение

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Алгоритмы и защищенные системы биометрической аутентификации личности»

Введение

Актуальность. Диссертация посвящена разработке новых технологий и защищенных систем биометрической верификации, идентификации и аутентификации личности, основанных на современных моделях описания и анализа отпечатков пальцев. Задача безопасной биометрической аутентификации является ключевой для многих важных приложений. К их числу относятся: контроль государственной границы, сопровождение электронных платежных систем, мониторинг контроля и управления доступом к ресурсам информационных систем и целый ряд других приложений.

Несмотря на то, что отпечатки пальцев являются наиболее изученной биометрической характеристикой, задача аутентификации личности по отпечаткам пальцев остается актуальной. В этой области по-прежнему ведутся активные исследования, направленные на разработку алгоритмов верификации и идентификации личности по отпечаткам пальцев, создаются их программные реализации, эффективность которых оценивается с позиций точности верификации и идентификации, скорости их выполнения, эргономичности и целому ряду иных показателей. Это связано со все большим распространением биометрических данных в информационных системах и процессах, развитием инфраструктуры интернета и облачных технологий, ориентацией на конечного пользователя интернет-сервисов и Web-приложений. Вместе с тем, возрастающий объем биометрических данных требует наличия все более эффективного математического и программного обеспечения.

За последние несколько десятилетий системы автоматической идентификации отпечатков пальцев (Automated Fingerprint Identification Systems, AFIS) сыграли важную роль в криминалистике. Тем не менее, до настоящего времени не отпала необходимость в ручном сравнении отпечатков пальцев экспертами, в частности, это справедливо для скрытых отпечатков, т.е. отпечатков, снятых криминалистами с различных поверхностей. Статус-кво сохраняется главным образом потому, что технологии AFIS с момента их рождения используют очень небольшое количество особенностей отпечатков пальцев из-за их нестабильности при экстракции (выделении признаков из отпечатка).

Как правило, особенности отпечатков пальцев делят на три уровня [1]. На первом уровне находятся потоки папиллярных линий и тип папиллярного узора. На втором уровне находятся характеристики Гальтона (минуции), включающие окончания линий и точки бифуркации. Третий уровень содержит размерные атрибуты линий (кривизна, ширина линий, форма, поры, край контура, изломы, складки, шрамы и другие постоянные детали). На сегодняшний день стандартом для AFIS, используемом в Федеральном Бюро Расследований США, является разрешение 500 точек на дюйм (шаг 50 мкм), которого недостаточно для извлечения особенностей третьего уровня (радиус пор - 60 мкм). Как следствие, в сегодняшних AFIS используются особенности только 1-го и 2-го уровней.

В настоящее время разработчиками биометрических систем, в основном, используются стандарты ANSI и ФБР США. В них определены следующие требования к образу отпечатка:

— каждый образ представляется в формате несжатого TIF;

— образ должен иметь разрешение не ниже 500 точек на дюйм;

— образ должен быть полутоновым с 256 уровнями яркости;

— максимальный угол поворота отпечатка от вертикали не более 15 градусов;

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

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

— ГОСТ Р ИСО/МЭК 19794-4-2006 Автоматическая идентификация. Идентификация биометрическая. Форматы обмена биометрическими данными. Часть 4. Данные изображения отпечатка пальца.

— ГОСТ Р ИСО/МЭК 19794-2-2005 Автоматическая идентификация. Идентификация биометрическая. Форматы обмена биометрическими данными. Часть 2. Данные изображения отпечатка пальца - контрольные точки.

- ГОСТ Р ИСО/МЭК 19794-3-2009 Автоматическая идентификация. Идентификация биометрическая. Форматы обмена биометрическими данными. Часть 3. Спектральные данные изображения отпечатка пальца.

- ГОСТ Р ИСО/МЭК 19794-8-2009 Автоматическая идентификация. Идентификация биометрическая. Форматы обмена биометрическими данными. Часть 8. Данные структуры остова отпечатка пальца.

В связи с постоянно расширяющимися областями применения биометрических технологий (контроль государственной границы, криминалистика, системы контроля удаленного доступа, электронные платежные системы, защита от мошенничества, аутентификация пользователей в информационных системах, медицина, мобильные устройства) в сочетании с увеличивающейся производительностью современных ЭВМ, постоянно растут требования к точности и скорости биометрического распознавания. C 2000 по 2006 год проводились очные соревнования Fingerprint Verification Competition, организаторами которого являлись университет Болонии (Италия), Мичиганский государственный университет (США), университет Сан-Хосе (США), Мадридский университет (Испания) [2], [3]. Лучший результат этих соревнований с позиций точности составил 2.07% EER [4]. C 2006 года по настоящее время проводятся заочные соревнования Fingerprint Verification Competition. Результаты соревнований по состоянию на февраль 2018 года, отсортированные по возрастанию EER, представлены на рисунке 1.13 главы 1 диссертации. По состоянию на март 2018 года более 25% лучших алгоритмов Т0П-40 рейтинга были написаны за период 2015-2018 годы, что подтверждает актуальность тематики биометрической верификации с точки зрения мирового сообщества биометрических компаний, академических исследовательских групп и независимых исследователей, причем интерес к этой сфере только растет. Так, по данным «Google Scholar» [5], c 2013 года по настоящее время в мире были опубликованы более 20000 статей, посвященных биометрической верификации личности по отпечаткам пальцев, при этом почти половина из них (9930 статей) были выпущены с 2016 года. Согласно тому же источнику, с 2013 года были опубликованы более 38000 статей по биометрической идентификации по отпечаткам пальцев. Из них 26000 были изданы не ранее 2016 года [6]. Заметим, что лучшие алгоритмы этих соревнований имеют уровень эквивалентной ошибки (EER) порядка десятых и

даже сотых долей процента. Поскольку они созданы коммерческими компаниями, то алгоритмы сравнения отпечатков и исходные коды закрыты. Предположительно, в их реализации используются продвинутые методы обработки изображений и методы глубинного обучения, такие как сверточные нейронные сети. Отметим, что один из лидеров российского рынка биометрии компания «Sonda Technologies ltd.» занимает 22-е место в рейтинге FVC On-going с результатом 0.7% EER (при собственном экстракторе). Забегая вперед, скажем, что это лишь на 1% лучше результата автора при том, что автор в ходе исследований занимался только алгоритмами сравнения биометрических шаблонов при фиксированном алгоритме извлечения признаков (экстракторе) из состава свободно распространяемого программном обеспечении SourceAFIS 1.7 [7], использующего для сравнения биометрических шаблонов алгоритм NIST BOZORTH 3 и занимающего 40-е место в рейтинге по состоянию на февраль 2018 года. При этом только лишь за счет создания новых алгоритмов сравнения автору удалось снизить уровень эквивалентной ошибки более чем в 2 раза (с 3.6% EER для ад-горитма NIST BOZORTH 3 до 1.7% EER алгоритма FingerPath), что позволяет оценивать пару «экстрактор SourceAFIS - авторский алгоритм FingerPath» как алгоритм верификации, входящий в ТОП-35 рейтинга с позиций точности.

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

Актуальность решаемых задач биометрической идентификации и аутентификации личности по отпечаткам пальцев с точки зрения развития страны подтверждается следующими нормативно-правовыми актами:

- указ Президента РФ от 29.12.2012 №1709 (ред. от 07.12.2016 г.) «О паспорте гражданина Российской Федерации, удостоверяющим личность гражданина Российской Федерации за пределами территории Российской Федерации, содержащем на электронном носителе информации дополнительные биометрические персональные данные его владельца»;

— проект Федерального закона № 157752-7 «О внесении изменений в Федеральный закон «О противодействии легализации (отмыванию) доходов, полученных преступным путем, и финансированию терроризма» (окончательная редакция, принятая Государственной Думой Федерального Собрания Российской Федерации 20.12.2017 г.), предусматривающий сбор, обработку, хранение и предоставление биометрических персональных данных клиентов - физических лиц кредитных организаций с последующем предоставлением биометрических данных в Федеральную Государственную Информационную Систему «Единая система идентификации и аутентификации» (ФГИС ЕСИА). Таким образом, тема диссертации «Алгоритмы и защищенные системы биометрической аутентификации личности» актуальна и отвечает критерию 2.1 Положения о присуждении ученых степеней в Московском государственном университете имени М.В.Ломоносова, согласно которому «Диссертация на соискание ученой степени кандидата наук должна быть научно-квалификационной работой, в которой содержится решение задачи, имеющей значение для развития соответствующей отрасли знаний, либо изложены новые научно обоснованные технические, технологические или иные решения и разработки, имеющие существенное значение для развития страны».

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

там паспорта специальности 05.13.19 — «Методы и системы защиты информации, информационная безопасность»: технологии идентификации и аутентификации пользователей и субъектов информационных процессов, системы разграничения доступа; методы и средства (комплексы средств) информационного противодействия угрозам нарушения информационной безопасности в открытых компьютерных сетях, включая Интернет; принципы и решения (технические, математические, организационные и др.) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности.

Для достижения поставленной цели в работе сформулированы и решаются следующие задачи.

— Разработка новых информационных структур представлений отпечатка пальца и основанных на них математических моделей отпечатков пальцев, создание методов верификации и идентификации личности по отпечаткам пальцев на основе новых информационных структур и математических моделей отпечатков пальцев.

— Теоретическая оценка сложности алгоритмов верификации и идентификации с целью оценки возможностей применения с позиции скорости новых алгоритмов верификации и идентификации личности по отпечаткам пальцев в качестве компонент реальных биометрических систем.

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

— Исследование возможности практического создания защищенной системы биометрической аутентификации.

— Анализ безопасности полученной защищенной системы биометрической аутентификации.

Новизна. Результаты диссертации являются новыми и получены автором самостоятельно. Основные результаты диссертации состоят в следующем.

1. Автором введена структура дактилоскопического созвездия, разработано представление отпечатка пальцев множеством созвездий, создан алгоритм верификации отпечатков пальцев на основе структуры дактилоскопического созвездия («Аэ^-алгоритм»), разработана его программная реализация, приведена теоретико-сложностная оценка време-

ни его работы и проведены экспериментальные исследования точности работы программной реализации алгоритма. Проведен сравнительный анализ работы программной реализации «Аэ^-алгоритма» с алгоритмом МЯТ MINDTCT/BOZORTH3, используемом в свободно распространяемом программном обеспечении ЗоигееАИЗ 1.7 [7], демонстрирующий превосходство программной реализации «Аэ^-алгоритма» с позиций точности (ЕЕЯ = 3% у Аэ^-алгоритма против ЕЕЯ = 3.6% у №БТ MINDTCT/BOZORTH3) на базе отпечатков РУС2002 DB1_b [2].

2. Автором введено представление пары отпечатков пальцев на основе структуры специального графа, создан алгоритм верификации отпечатков пальцев на основе поиска максимального пути в графе (алгоритм «Рт§егРа1;Ь»), разработана его программная реализа-ция,приведена теоретико-сложностная оценка его работы, проведены экспериментальные исследования точности работы программной реализации алгоритма. Проведено сравнение «Пп§егРа1Ь» с «Аэ^-алгоритмом» с позиций точности и вычислительной сложности, демонстрирующее превосходство алгоритма «Пп§егРа1Ь» над «Аэ^-алгоритмом» по точности (ЕЕЯ = 1.7% у алгоритма «Пп§егРа1Ь» против ЕЕЯ = 3% у «Аэ^-алгоритма») при более высокой вычислительной сложности (0(п4) операций у алгоритма «Пп§егРа1Ь» против 0(п3) операций у «Аэ^-алгоритма», где п - число особых точек в биометрическом шаблоне).

3. Автором разработаны: математическая модель отпечатка пальца на основе аппроксимации поля ориентаций в окрестности особых точек обобщенными полиномами Чебышева; алгоритм идентификации личности по отпечаткам пальцев на основе сферического локально-чувствительного хэширования. Автором получены: программная реализация этого алгоритма; теоретико-сложностная оценка времени его работы. Проведены экспериментальные исследования точности работы программной реализации алгоритма. Проведенный сравнительный анализ выявил преимущество разработанного алгоритма с позиций точности по сравнению с алгоритмом идентификации, разработанным Д. Мальтони, Р. Капелли и М. Феррара [8].

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

Метод исследования. В работе применялись методы теории графов, теории вероятностей и математической статистики, теории информации, теории алгоритмов и вычислительной сложности, комбинаторики и защиты информации.

Теоретическая и практическая значимость.

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

Апробация работы.

Основные результаты докладывались на семинарах механико-математического факультета МГУ имени М.В.Ломоносова, международных научных форумах и международных летних школах, включая:

— семинар «Биометрические системы» под руководством доцента А.А. Часовских и научного сотрудника В.С. Половникова, механико-математический факультет МГУ имени М.В.Ломоносова, 2014 г.;

— семинар «Современные проблемы криптографии» под руководством ведущего научного сотрудника В.А. Носова и доцента А.Е. Панкратьева, механико-математический факультет МГУ имени М.В.Ломоносова, 2015 г.;

— семинар «Компьютерная безопасность» под руководством старшего научного сотрудника А.В. Галатенко, механико-математический факультет МГУ имени М.В.Ломоносова, 2015 г.;

— XII международная летняя школа по биометрии, г. Альгеро (Италия), 2015 г.;

— XXIII международная конференция студентов, аспирантов и молодых ученых «Ломоносов», МГУ имени М.В. Ломоносова, 13-17 апреля

2016 г.;

— семинар «Проблемы современных информационно-вычислительных систем» под руководством профессора В.А. Васенина, механико-математический факультет МГУ имени М.В.Ломоносова, 2016 г.;

— XXIV международная конференция студентов, аспирантов и молодых ученых «Ломоносов», МГУ имени М.В. Ломоносова, 10-14 апреля

2017 г.;

— семинар «Теория автоматов» под руководством профессора В.Б. Кудрявцева, механико-математический факультет МГУ имени М.В.Ломоносова, 2017 г.

Публикации. Основные результаты по теме диссертации изложены в 4 печатных изданиях [9-12], 4 из которых изданы в журналах, рекомендованных ВАК.

Работа [10] выполнена автором совместно с выпускником кафедры вычислительной математики механико-математического факультета МГУ имени М.В. Ломоносова И.М. Ковалевым. В данной работе А.В.Полякову принадлежит алгоритм «Рт§егРа1;Ь» верификации на основе поиска максимального пути в графе, обоснование его работы и оценка вычислительной сложности этого алгоритма, И.М. Ковалеву принадлежит программная реализация алгоритма «Рт§егРа1;Ь» и экспериментальная часть работы.

Остальные работы выполнены автором самостоятельно.

Краткое содержание диссертации.

Во введении описаны структура диссертации и история рассматриваемых в ней вопросов. Обосновываются актуальность темы и научная новизна полученных результатов. Описываются основные результаты диссертации.

Глава 1 посвящена решению задачи верификации личности по отпечаткам пальцев.

Основными результатами главы являются два новых алгоритма верификации: «Аэ^-алгоритм» и алгоритм «Рт§егРа1;Ь».

На вход оба алгоритма получают два биометрических шаблона отпечатков I и Т, а на выходе возвращают меру похожести отпечатков в Е [0,1].

В разделе 1.1 на содержательном уровне ставится задача верификации личности по отпечаткам пальцев.

В разделе 1.2 изложен краткий обзор существующих методов и подходов к решению задачи верификации.

Раздел 1.3 содержит математическую модель отпечатка пальца, описание «Аэ^-алгоритма» , теоретико-сложностные характеристики алгоритма и экспериментальные результаты.

«Аэ^-алгоритм» основан на новой структуре дактилоскопических созвездий.

Определение. Пусть дано конечное множество точек плоскости М = {т\,..,т3}, а БТ(М) — триангуляция Делоне этого множества. Созвездием с центром в называется подграф ЛвЬт^^ графа БТ(М), АвЬт^^ = (У,Е), где V - объединение т^ и множества вершин, смежных с в БТ,

Е = (тг,тк), тк е V \ {тг}.

Идея «Аэ^-алгоритма» заключается в том, что по множеству особых точек отпечатка пальца (минуций) строится триангуляция Делоне этого множества, после чего для каждой особой точки строится соответствующее ей созвездие с центром в этой точке. Впоследствии каждое такое созвездие кодируется словом над 18-символьным алфавитом, а сам отпечаток - списком слов. Таким образом, задача сравнения двух отпечатков сводится к сравнению двух списков слов. При этом изменчивость биометрических данных (нелинейная деформация, поворот пальца на сканере, физическое состояние кожи, ошибки экстракции), возникающие при выделении признаков отпечатка, на уровне множества слов моделируются вставкой и удалением символов, заменой символов и транспозицией символов. В качестве меры близости слов используется метрика Левенштейна. Далее строится декартово произведение списков и вычисляется расстояние Левенштейна между всеми парами слов из декартова произведения списков и проводится процедура голосования, в рамках которой каждой паре слов выставляется количество баллов, равное количеству вершин в соответствующих созвездиях, согласующихся друг с другом при наложении этих созвездий. Затем декартово произведение списков слов представляется в виде взвешенного двудольного графа, веса ребер в котором определяются количеством голосов, отданных за каждую пару слов, и с помощью венгерского алгоритма производится поиск максимального паросочетания в двудольном графе.

Оценка вычислительной сложности «Astr-алгоритма» представлена в теореме 1 главы 1.

Теорема 1. Пусть отпечаток пальца I содержит т минуций, а отпечаток пальца Т - п минуций, без ограничения общности можно считать, что т < п. Тогда вычислительная сложность «Astr-алгоритма» составляет ö(n3) операций.

Результаты экспериментов показали, что «Astr-алгоритм» обладает точностью на уровне 3% EER (интегральная мера точности алгоритма,значение, при котором вероятность ошибки первого рода равна вероятности ошибки второго рода). Этот результат превосходит показатель алгоритма NIST STMINDTCT/BOZORTH3, основанный на сравнении минуций и используемый в свободно распространяемом программном обеспечении SourceAFIS 1.7 (EER = 3.6%) [7]. Вместе с тем, у «Astr-алгоритм» есть слабое место. А именно, «Astr-алгоритм» по построению хорошо работает с внутриклассовыми различиями и потому надежно опознает «свои» отпечатки, однако, не слишком хорошо различает межклассовые сходства. Это обстоятельство послужило мотивировкой для создания нового алгоритма верификации, который бы учитывал не только локальную конфигурацию особых точек отпечатков, но и глобальную за счет новой структуры данных.

В разделе 1.4 диссертации представлен новый алгоритм верификации личности по отпечаткам пальцев «FingerPath», созданный на основе представления отпечатков пальцев в виде специальным образом сконструированного графа, учитывающим не только локальные структуры особых точек отпечатка, но и их согласованность на глобальном уровне. Центральной идеей данного подхода является поиск максимального пути в специальным образом сконструированном ациклическом графе. А именно, рассматриваются пары (ориентированных в конечных точках) отрезков с концами в минуциях, один из которых принадлежит отпечатку I, а другой - отпечатку Т. Задаются угловые и метрические пороги eutresh, RCthresh, £thresh и £ chain, после чего строится ориентированный граф G, вершины которого - это пары отрезков вида (Table(I)(i),Table(T)(j)) такие, что выполнены следующие условия:

1 Vfal - Хг2)2 + (Уг\ - Уг2)2 - ^Цi - x'j2)2 + (у'3х - у'j2)2 1 < CUtresh, min (\9г1 - 9'3 ilfa - 1вц - 9'3 J) < Sthresh,

min (|0Й - Üj2^ - |0г2 - 2I) < ^thresh.

Две вершины (a,i,bj) и (ai,bm) графа G соединяются ребром (по направлению из (ai,bj) в (щ,bm)) тогда и только тогда, когда отрезки ai и ai имеют один общий конец, одновременно отрезки bj и Ьт имеют один общий конец, а угол поворота от ai к щ должен с точностью до £chain совпадать с углом поворота от bj к Ьт, причем ж-координаты пары отрезков с общей вершиной образуют строго возрастающую последовательность.

В утверждении 1 главы 1 показано, что сконструированный таким образом граф G является ациклическим. Как следствие, в этом графе можно провести топологическую сортировку и найти цепь максимальной длины.

Для оценки точности программной реализации алгоритма «FingerPath» было проведено экспериментальное исследование на базе данных отпечатков FVC2002 DB1, в рамках которого полученный уровень эквивалентной ошибки составил 1.7%. После этого была проведена теоретико-сложностная оценка работы алгоритма, результаты которой сформулированы в теореме 2 главы 1.

Теорема 2. Пусть отпечаток пальца I содержит т минуций, а отпечаток пальца Т - п минуций, без ограничения общности можно считать, что т < п. Тогда вычислительная сложность оптимизированного FingerPath-алгоритма составляет 0(п4) операций.

Таким образом, можно сделать вывод о том, что алгоритм «FingerPath» оказывается более точным на тестовой базе данных, чем «Astr-алгоритм», но при этом «Astr-алгоритм» работает асимптотически быстрее, чем «FingerPath».

Глава 2 посвящена решению задачи идентификации личности по отпечаткам пальцев.

В разделе 2.1 на содержательном уровне формулируется задача биометрической идентификации личности, т.е. удостоверение личности субъекта доступа через поиск по всей базе биометрических шаблонов. В этом случае проводятся сравнения один-ко-многим для выяснения, присутствует ли данная личность в базе данных, и если да, система возвращает идентификатор того пользователя, который соответствует поисковому запросу.

Список литературы диссертационного исследования кандидат наук Поляков, Андрей Владимирович, 2018 год

Список литературы

1. D. Maltoni, D. Maio, A. K. Jain. «Handbook of fingerprint recognition», Springer, 2003

2. Система тестирования алгоритмов верификации «FVC- onGoing» лаборатории биометрических систем Болонского университета (Италия), URL: https://biolab.csr.unibo.it/FVCOnGoing/UI/Form/Home.aspx (дата обращения 8.04.2015 г.)

3. B. Dorizzi, R. Cappelli, M. Ferrara. «Fingerprint and On-Line Signature Verification Competitions at ICB 2009» //proc. International Conference on Biometrics (ICB), Alghero, Italy, pp.725-732, June 2009

4. R. Cappelli, D. Maio, D. Maltoni, J. L. Wayman, and A. K. Jain. «Performance Evaluation Of Fingerprint Verification Systems», IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(1):3-18, 2006.

5. Список статей, посвященных верификации по отпечаткам пальцев, в системе «Google Scholar».

https://scholar.google.ru/scholar?as_ylo=2016&qfingerprintverification& hlru&as_sdt0,5

(Дата обращения 1.05.2017 г.)

6. Список статей, посвященных идентификации по отпечаткам пальцев, в системе «Google Scholar».

https://scholar.google.ru/scholar?as_ylo=2016&qfingerprint +identification&hl=ru&as_sdt=0,5

(Дата обращения 1.05.2017 г.)

7. Программное обеспечение для верификации отпечатков пальцев: http://sourceforge.net/projects/sourceafis/

(Дата обращения: 1.05.2017 г.)

8. R. Cappelli, M. Ferrara, and D. Maltoni„ «Fingerprint indexing based on minutia cylinder-code», Pattern Analysis and Machine intelligence, iEEE Transactions on, vol. 33, no. 5, pp. 1051-1 057, 2011

9. Поляков А.В. «Алгоритм сравнения отпечатков пальцев на основе структуры созвездий» //Программная инженерия, 2015, № 8, с.26-31

10. Поляков А.В., Ковалев И.М. «Алгоритм сравнения отпечатков пальцев на основе поиска максимального пути в графе» // Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460), издательство [б.и.] (М.), 2016,том 20, № 2, с. 103-117

11. Поляков А.В. «Метод идентификации личности по отпечаткам пальцев на основе сферического локально-чувствительного хэширования» //Программная инженерия, 2017, №5, с. 207 - 214

12. Поляков А.В. «Биометрическое личностное шифрование» // Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460), издательство [б.и.] (М.), 2017, том 21, № 1, с. 149-163

13. A. Townsend «Computing with functions in two dimensions», PhD Thesis, University of Oxford, 2014

14. K. Terasawa and Y. Tanaka, «Spherical lsh for approximate nearest neighbor search on unit hypersphere», in Algorithms and Data Structures. Springer Berlin Heidelberg, 2007, vol. 46 19, pp. 27-38

15. Shamir, A., 1984. «Identity-Based Cryptosystems and Signature Schemes», Proc. Crypto, p.47-53.

16. Boneh, D., Franklin, M.K., 2001. «Identity-Based Encryption from the Weil Pairing». Proc. CRYPTO, p.213-229.

17. Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith, «Fuzzy extractors: How to generate strong keys from biometrics and other noisy data», in Proc. Eurocrypt, 2004, pp. 523-540.

18. Sahai, A., Waters, B., 2005. «Fuzzy Identity-Based Encryption». Proc. EUROCRYPT, p.457-473

19. Burnett, A., Byrne, F., Dowling, T., Duffy, A., 2007. «A biometric identity based signature scheme». Int. J.Network Secur., 5(3):317-326

20. Sarier, N.D., 2008. «A New Biometric Identity Based Encryption Scheme». Proc. ICYCS, p.2061-2066

21. Sarier, N.D., 2010. «Generic Constructions of Biometric Identity Based Encryption Systems». Proc. WISTP, p.90-105.

22. Bazen et al. (2000). Bazen A.M., Verwaaijen G.T.B., Gerez S.H., Veelenturf L.P.J. and van der Zwaag B.J. A Correlation-Based Fingerprint Verification System // Proc. Workshop on Circuits Systems and Signal Processing (ProRISC 2000), 2000.

23. J. Starink, E. Backer. Finding point correspondences using simulated annealing"// Pattern Recognition, vol. 28, no. 2, pp. 231-240, 1995

24. George Bebis, Taisa Deaconu, Michael Georgiopoulos. «Fingerprint Identification Using Delaunay Triangulation», 1999

25. Ito et al. (2006). Ito K., Morita A., Aoki T., Nakajima H., Kobayashi K. and Higuchi T. «A Fingerprint Recognition Algorithm Combining Phase-Based Image Matching and Feature-Based Matching»,// Proc. Int. Conf. on Biometrics, LNCS 3832, pp. 316-325, 2006

26. Список статей, посвященных верификации по отпечаткам пальцев, в системе «Google Scholar». URL: https://scholar.google.ru/scholar?as_ylo2014&qfingerprintverification&hlru

(Дата обращения 8.04.2015 г.)

27. Делоне Б.Н. «О пустоте сферы» // Изв. АН СССР. ОМЕН. 1934. № 4. С. 793-800.

28. Скворцов А.В. «Триангуляция Делоне и её применение». - Томск: Изд-во Том. ун-та, 2002. - 128 с.

29. Кумсков М.И. «Методология прогнозирования свойств химических соединений и ее программная реализация»: диссертация на соискание ученой степени доктора физико-математических наук 05.13.17; [место защиты: Вычислительный Центр РАН] - Москва, 1997 - 196 с.

30. Кумсков М.И., Пономарева Л.А., Зефиров Н.С. Выбор алфавита структурных дескрипторов органических соединений при поиске зависимостей «структура-активность» / Материалы 4-ой Всесоюзной школы-семинара «Статистический и дискретный анализ данных и экспертные оценки», - Одесса, 1991, с.90-92.

31. Митюшев Д.Ф., Кумсков М.И., Зефиров Н.С. Программа нахождения по молекулярному графу дескрипторов «тип химической структуры» в задаче «структура-активность» / Материалы 4-ой Всесоюзной школы-семинара «Статистический и дискретный анализ данных и экспертные оценки», - Одесса, 1991, с.315-317.

32. Кумсков М.И., Пономарева В.А., Зефиров Н.С. «Окраска» структурных дескрипторов органических соединений при поиске зависимостей «структура-активность» / Тезисы докл. 1-ой Всесоюзной конф. по теоретич. органической химии - ВАТОХ, Волгоград, 1991, с.550.

33. Harold W. Kuhn, «The Hungarian Method for the assignment problem», Naval Research Logistics Quarterly, 2:83—97, 1955. Kuhn's original publication

34. Портал MAXimal: алгоритмы и олимпиадное программирование, статья «Венгерский алгоритм решения задачи о назначениях»: http://e-maxx.ru/algo/assignment_hungary (дата обращения 8.04.2015 г.)

35. R. A. Wagner, M. J. Fischer. «The string-to-string correction problem», J. ACM 21 1 (1974). P. 168—173

36. T. Cormen, C. Leiserson, R. Rivest. «Introduction to algorithms (second edition)», Williams, pp. 622-632, 2005

37. NIST Biometric Image Software: http://www.nist.gov/itl/iad/ig/nigos.cfm

38. Candela G.T., Grother P.J., Watson C.I., Wilkinson R.A. and Wilson C.L., «PCASYS - A Pattern-Level Classification Automation System for Fingerprints», Tech. Report: NIST TR 5647, Aug. 1995

39. Karu K. and Jain A.K., «Fingerprint classification», Pattern Recognition, vol. 29, no. 3, pp. 389-404, 1996

40. Cappelli R., Maio D. and Maltoni D., «Fingerprint Classification Based on Multi-space KL», in Proc. Workshop on Automatic Identification Advances Technologies, pp. 117-120, 1999

41. Hong L. and Jain A.K., «Integrating faces and fingerprints for personal identification», IEEE Transactions on Pattern Analysis Machine Intelligence, vol.

20, no. 12, pp. 1295-1307, 1998b.

42. Jain A.K., Prabhakar S. and Hong L., «A multichannel approach to fingerprint classification», IEEE Transactions on Pattern Analysis Machine Intelligence, vol.

21, no. 4, pp. 348-359, 1999

43. Marcialis G.L., Roli F. and Frasconi P., «Fingerprint Classificationby Combination of Flat and Structural Approaches», in Proc. Int. Conf. on Audio-and Video-Based Biometric Person Authentication (3rd), pp. 241-246, 2001

44. Senior A., «A combination fingerprint classifier», IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 23, no. 10, pp. 1165-1174, 2001.

45. Yao Y., Frasconi P. and Pontil M., «Fingerprint Classification with Combination of Support Vector Machines», in Proc. Int. Conf. on Audio- and Video-Based Biometric Person Authentication (3rd), pp. 253-258, 2001

46. Jain A.K. and Minut S., «Hierarchical Kernel Fitting for Fingerprint Classification and Alignment», in Proc. Int. Conf. on Pattern Recognition (16th), 2002

47. Cappelli R., Maio D., Maltoni D. and Nanni L., «A Two-Stage Fingerprint Classification System», in Proc. ACM SIGMM Multimedia Biometrics Methods and Applications Workshop, Berkley, pp. 95-99, Nov. 2003.

48. Yao Y., Marcialis G.L., Pontil M., Frasconi P. and Roli F., «Combining flat and structured representations for fingerprint classification with recursive neural networks and support vector machines», Pattern Recognition, vol. 36, no. 2, pp. 397-406, 2003.

49. Cappelli R., Maio D. and Maltoni D., «A multi-classifier approach to fingerprint classification», Pattern Analysis and Applications (special Issue on Fusion of Multiple Classifiers), vol. 5, no. 2, pp. 136-144, 2002

50. Wang X. and Xie M., «Fingerprint Classification: An Approach Based on Singularities and Analysis of Fingerprint Structure», in Proc. Int. Conf. on Biometric Authentication (1st), LNCS 3072, pp. 324-329, 2004.

51. Zhang Q. and Yan H., «Fingerprint classification based on extraction and analysis of singularities and pseudo ridges», Pattern Recognition, vol. 37, no. 11, pp. 2233-2243, 2004.

52. Neuhaus M. and Bunke H., «A Graph Matching Based Approach to Fingerprint Classification Using Directional Variance», in Proc. Int. Conf. on Audio- and Video- Based Biometric Person Authentication (5th), pp. 191-200, 2005.

53. Park C.H. and Park H., «Fingerprint classification using fast Fourier transform and nonlinear discriminant analysis», Pattern Recognition, vol. 38, no. 4, pp. 495-503, 2005

54. Tan X., Bhanu B. and Lin Y., «Fingerprint classification based on learned features», IEEE Transaction on Systems, Man, and Cybernetics, Part C, vol. 35, no. 3, pp. 287-300, 2005

55. Min J.K., Hong J.H. and Cho S.B., «Effective Fingerprint Classification by Localized Models of Support Vector Machines», in Proc. Int. Conf. on Biometrics, LNCS 3832, pp.287-293, 2006.

56. Wang L. and Dai M., «Application of a new type of singular points in fingerprint classification», Pattern Recognition Letters, vol. 28, no. 13, pp. 1640-1650, 2007.

57. Hong J.H., Min J.K., Cho U.K. and Cho S.B., «Fingerprint classification using one- vs-all support vector machines dynamically ordered with naive Bayes classifiers», Pattern Recognition, vol. 41, no. 2, pp. 662-671, 2008

58. Li J., Yau W.Y. and Wang H., «Combining singular points and orientation image information for fingerprint classification», Pattern Recognition, vol. 41, no. 1, pp. 353-366, 2008.

59. Lumini A., Maio D. and Maltoni D., «Continuous vs exclusive classification for fingerprint retrieval», Pattern Recognition Letters, vol. 18, no. 10, pp. 1027-1034, 1997.

60. R. Cappelli, D. Maio, and D. Maltoni, «A Multi-Classifier Approach to Fingerprint Classification», Pattern Analysis and Applications, vol. 5, pp. 136144, 2002.

61. R. Cappelli, A. Lumini, D. Maio, and D. Maltoni, «Fingerprint Classification by Directional Image Partitioning», IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 21, no. 5, pp. 402-421, May 1999.

62. S. Lee, Y. Kim, and G. Park, «A Feature Map Consisting of Orientation and Inter-Ridge Spacing for Fingerprint Retrieval», Proc. Audio and Video-Based Biometric Person Authentication, 2005.

63. R.S. Germain, A. Califano, and S. Colville, «Fingerprint Matching Using Transformation Parameter Clustering», IEEE Computational Science and Eng., vol. 4, no. 4, pp. 42-49, Oct.-Dec. 1997.

64. B. Bhanu and X. Tan, «Fingerprint Indexing Based on Novel Features of Minutiae Triplets», IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 5, pp. 616-622, May 2003.

65. X. Liang, T. Asano, and A. Bishnu, «Distorted Fingerprint Indexing Using Minutia Detail and Delaunay Triangle», Proc. Third Int'l Symp. Voronoi Diagrams in Science and Eng., 2006.

66. J. De Boer, A.M. Bazen, and S.H. Gerez, «Indexing Fingerprint Databases Based on Multiple Features», Proc. Ann. Workshop Circuits, Systems and Signal Processing, pp. 300-306, 2001.

67. Cappelli R., Maio D., Maltoni D., Wayman J.L. and Jain A.K., «Performance evaluation of fingerprint verification systems», IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 28, no. 1, pp. 3-18, 2006.

68. NIST Special Database 4,https://www.nist.gov/srd/nist-special-database-4

69. NIST Special Database 14, https://www.nist.gov/srd/nist-special-database-14

70. P. Indyk, R. Motwani, «Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality», Proc. 13th ACM Symp. Theory of Computing, pp. 604-613, 1998.

71. J. C. Mason and D. C. Handscomb, «Chebyshev Polynomials», CRC Press, Florida, 2003.

72. J. R. Rice, «Tchebycheff approximation in several variables», Trans. Amer. Math. Soc., 109 (1963), pp. 444-466

73. Y. Wang, J. Hu, and D. Phillips, «A fingerprint orientation model based on 2d fourier expansion (fomfe) and its application to singular point detection and fingerprint indexing», Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 29, no. 4, pp. 573-585, 2007.

74. Coxeter H. S. M., Regular Polytopes (3rd ed.). Dover. p. 123, 1973.

75. I. Razenshteyn, L. Smidt «Practical and Optimal LSH for Angular Distance», arXiv:1509.02897

76. http://www.chebfun.org/

77. FAst Lookups of Cosine and Other Nearest Neighbors, https://falconn-lib.org/

78. W. Diffie and M. E. Hellman. «New directions in cryptography». IEEE Transactions on Information Theory, 22:644-654, 1976

79. Введение в криптографию / Под общ. ред. В. В. Ященко. — 4-е изд., доп. М.: МЦНМО, 2012. — 348 с

80. J. Cheon, «Security Analysis of the Strong Diffie-Hellman Problem», Proc. of EUROCRYPT 2006, LNCS 4004, pp. 1-11, 2006

81. Jain A.K., Ross A. and Uludag U., «Biometric Template Security: Challenges and Solutions», in Proc. European Signal Processing Conference (EUSIPCO), 2005.

82. Шнайер, Б., «Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С», 2-е изд., М., Триумф, 2002 г., 816 с.

83. J. Bringer, H. Chabanne, M. Izabachène, D. Pointcheval, Q. Tang, and S. Zimmer. An application of the goldwasser-micali cryptosystem to biometric authentication. In ACISP'07, volume 4586 of LNCS, pages 96-106. Springer, 2007b.

84. Shamir A. «How to share a secret» // Commun. ACM — New York City: ACM, 1979. — Vol. 22, Iss. 11. — pp. 612-613.

Список рисунков

1.1 Вариативность изображений одного и того же отпечатка под действием различных факторов ......................................31

1.2 Межклассовое сходство отпечатков пальцев ........................32

1.3 Процессы регистрации и верификации личности....................34

1.4 Изображение отпечатка пальца........................................36

1.5 Построение сетки........................................................36

1.6 Маска контрастности ..................................................37

1.7 Карта углов ориентации ..............................................37

1.8 Фильтр Гаусса ..........................................................38

1.9 Фильтр Габора..........................................................38

1.10 Результат фильтрации изображения отпечатка пальца ............38

1.11 Бинаризированное изображение отпечатка пальца ..................39

1.12 Папиллярные линии и найденные особые точки изображения отпечатка пальца ......................................................39

1.13 Результаты международных соревнований FVC on-going по верификации отпечатков пальцев (на февраль 2018) ..............44

2.1 Процессы регистрации и идентификации личности..................70

2.2 Сравнение рабочих характеристик алгоритмов классификации . 78

2.3 Результат аппроксимации многочленами Чебышева поля направлений. Слева направо: оригинальное изображение; поле ориентаций, полученное методом градиентов; аппроксимация многочленами Чебышева (42 параметра)..............................89

Список таблиц

1.1 Значение ЕЕЯ на различных скорингах............... 67

1.2 Сравнение точности алгоритма «Ет§егРа1;Ь» с «Аэ^-алгоритмом». 68

2.1 Уровни ошибок методов классификации .............. 75

2.2 Сравнение результатов работы алгоритма Б-ЬЗЫ с МСС-ЬБЫ. . . 94

3.1 Сравнительный анализ ........................123