Нечеткие экстракторы - это метод, который позволяет использовать биометрические данные в качестве входных данных для стандартных криптографических методов для обеспечения безопасности. «Нечеткий» в этом контексте относится к тому факту, что фиксированные значения, необходимые для криптографии, будут извлекаться из значений, близких к исходному ключу, но не идентичных ему, без ущерба для требуемой безопасности. Одно из приложений - шифрование и аутентификация записей пользователей с использованием биометрических данных пользователя в качестве ключа.
Нечеткие экстракторы - это биометрический инструмент, который позволяет аутентифицировать пользователя, используя в качестве ключа биометрический шаблон, созданный на основе биометрических данных пользователя. Они извлекают однородную и случайную строку с входа с толерантностью к шуму. Если вход изменится на но все еще близок к , та же строка будет реконструирован. Для этого при первоначальном вычислении процесс также выводит вспомогательную строку который будет сохранен для восстановления позже и могут быть обнародованы без ущерба для безопасности . Безопасность процесса обеспечивается также, когда злоумышленник изменяет. Как только фиксированная строка был рассчитан, его можно использовать, например, для ключевого соглашения между пользователем и сервером на основе только биометрических данных.
Исторически первая биометрическая система такого типа была разработана Джуэлсом и Ваттенбергом и называлась «Нечеткое обязательство», в которой криптографический ключ извлекается с использованием биометрических данных. Позже Джулс и Судан придумали схемы нечетких хранилищ , которые инвариантны по порядку для схемы нечетких обязательств, но используют код Рида – Соломона . Кодовое слово оценивается полиномом, и секретное сообщение вставляется как коэффициенты полинома. Полином оценивается для различных значений набора характеристик биометрических данных. Итак, Fuzzy Commitment и Fuzzy Vault были предшественниками нечетких экстракторов.
Это описание основано на статьях Евгения Додиса, Рафаила Островского, Леонида Рейзина « Нечеткие экстракторы: краткий обзор результатов с 2004 по 2006 год » и «Нечеткие экстракторы: как создать надежные ключи из биометрических и других зашумленных данных» [1] и Адам Смит
Мотивация
Чтобы нечеткие экстракторы могли генерировать надежные ключи из биометрических и других зашумленных данных, к этим биометрическим данным будут применяться парадигмы криптографии . Это означает, что им нужно разрешить
(1) Ограничьте количество предположений о содержании биометрических данных (эти данные поступают из различных источников, поэтому, чтобы избежать использования злоумышленником, лучше предполагать, что ввод непредсказуем)
(2) Примените к входу обычные криптографические методы. (Нечеткие экстракторы преобразуют биометрические данные в секретные, равномерно случайные и надежно воспроизводимые случайные строки).
Эти методы также могут иметь другие более широкие применения для других типов шумных входов, таких как приблизительные данные из человеческой памяти , изображения, используемые в качестве паролей, ключи из квантового канала. [1] Согласно статье Синтии Дворк (ICALP, 2006) « Дифференциальная конфиденциальность» , нечеткие экстракторы также используются для доказательства невозможности строгих представлений о конфиденциальности для статистических баз данных.
Основные определения
Предсказуемость
Предсказуемость указывает на вероятность того, что злоумышленник сможет угадать секретный ключ. С математической точки зрения предсказуемость случайной величины является .
Например, учитывая пару случайных величин а также , если противник знает из , то предсказуемость будет . Итак, противник может предсказать с участием . Мы используем среднее значение по поскольку он не находится под контролем противника, но поскольку зная делает предсказание состязательный, мы берем наихудший случай .
Мин-энтропия
Мин-энтропия указывает на наихудший случай энтропии. С математической точки зрения это определяется как .
Случайная величина с минимальной энтропией не менее называется -источник.
Статистическое расстояние
Статистическое расстояние - это мера различимости. С математической точки зрения, это выражается для двух распределений вероятностей а также в виде знак равно . В любой системе, если заменяется на , она будет вести себя как исходная система с вероятностью не менее .
Определение 1 (сильный экстрактор)
Параметр как сильный экстрактор случайности . Рандомизированная функция Ext: со случайностью длины это сильный экстрактор, если для всех -источники на где не зависит от .
Вывод экстрактора - это ключ, сгенерированный из с семенем . Он ведет себя независимо от других частей системы с вероятностью. Сильные экстракторы могут извлечь максимум биты из произвольного -источник.
Безопасный эскиз
Безопасный эскиз позволяет восстановить шумный вход, так что если вход и эскиз , дано и ценность рядом с , можно восстановить. Но эскиз не должен раскрывать информацию о , чтобы сохранить его в безопасности.
Если - метрическое пространство с функцией расстояния dis, Secure Sketch восстанавливает строку из любой близкой строки без раскрытия .
Определение 2 (безопасный эскиз)
An Secure Sketch - это пара эффективных рандомизированных процедур (в Sketch отмечен SS, в Recover отмечен Rec), таких что:
(1) Процедура создания эскиза SS, примененная к входу возвращает строку .
Процедура восстановления Rec использует в качестве входных данных два элемента а также .
(2) Правильность: если тогда .
(3) Безопасность: для любого -источник более , мин-энтропия дано в приоритете:
для любой , если , тогда .
Нечеткий экстрактор
Нечеткие экстракторы не восстанавливают исходный ввод, а генерируют строку (что близко к равномерному) от и разрешить его последующее воспроизведение (используя вспомогательную строку ) с учетом любых рядом с . Сильные экстракторы - это особый случай нечетких экстракторов, когда = 0 и .
Определение 3 (нечеткий экстрактор)
An нечеткий экстрактор - это пара эффективных рандомизированных процедур (Gen - Generate и Rep - Reproduce), таких что:
(1) Gen, учитывая , выводит извлеченную строку и вспомогательная строка .
(2) Правильность: если а также , тогда .
(3) Безопасность: для всех m-источников над , строка почти однороден даже с учетом , Так , тогда .
Таким образом, нечеткие экстракторы выводят почти однородные случайные последовательности битов, которые являются предпосылкой для использования криптографических приложений (в качестве секретных ключей). Поскольку выходные биты немного неоднородны, существует риск снижения безопасности, но расстояние от равномерного распределения не превышает и пока это расстояние достаточно мало, безопасность будет оставаться адекватной.
Надежные эскизы и нечеткие экстракторы
Надежные эскизы можно использовать для создания нечетких экстракторов. Как применение SS к чтобы получить и сильный экстрактор Ext со случайностью к получить . может храниться как вспомогательная строка . может быть воспроизведен а также . может восстановиться а также может воспроизвести . Следующая лемма формализует это.
Лемма 1 (нечеткие экстракторы из эскизов)
Предположим, что (SS, Rec) - безопасный эскиз и пусть Ext будет средним случаем сильный экстрактор. Тогда следующий (Gen, Rep) является нечеткий экстрактор: (1) Gen : набор и вывод . (2) Представитель: восстанавливаться и вывод .
Доказательство: из определения безопасного скетча (определение 2), . А поскольку Ext - это средний случай-сильный экстрактор.
Следствие 1.
Если (SS, Rec) является безопасный эскиз, а Ext - сильный экстрактор, то приведенная выше конструкция (Gen, Rep) является нечеткий экстрактор.
Справочный документ включает множество общих комбинаторных оценок безопасных эскизов и нечетких экстракторов. [1]
Основные конструкции
Благодаря своим свойствам устойчивости к ошибкам безопасные эскизы можно обрабатывать, анализировать и строить как общий код исправления ошибок илидля линейных кодов, где - длина кодовых слов, длина кодируемого сообщения, расстояние между кодовыми словами, а это алфавит. Если это вселенная возможных слов, тогда можно будет найти код исправления ошибок такое, что существует уникальное кодовое слово для каждого с расстоянием Хемминг из. Первым шагом для создания надежного эскиза является определение типа ошибок, которые могут произойти, а затем выбор расстояния для измерения.
Дистанционные конструкции Хэмминга
Когда нет риска удаления данных и только их повреждения, лучшим измерением для исправления ошибок является расстояние Хэмминга. Есть две общие конструкции для исправления ошибок Хэмминга в зависимости от того, является ли код линейным или нет. Обе конструкции начинаются с кода исправления ошибок, который имеет расстояние где количество допустимых ошибок.
Конструкция с кодовым смещением
При использовании общий код, назначьте равномерно случайное кодовое слово для каждого , тогда пусть какой сдвиг необходим, чтобы изменить в . Чтобы исправить ошибки в вычесть из затем исправьте ошибки в полученном некорректном кодовом слове, чтобы получить и, наконец, добавить к получить . Это означает. Эта конструкция может достичь наилучшего возможного компромисса между устойчивостью к ошибкам и потерей энтропии, когдаи используется код Рида – Соломона, приводящий к потере энтропии в размере. Единственный способ улучшить это - найти код лучше, чем код Рида – Соломона.
Синдром конструирования
При использовании линейный код позволяет быть синдром из. Исправлять найти вектор такой, что , тогда .
Установить разностные конструкции
При работе с очень большим алфавитом или очень длинными строками, в результате получается очень большая вселенная. , может быть более эффективным лечить а также как наборы и посмотрите на различия наборов, чтобы исправить ошибки. Для работы с большим набором полезно посмотреть на его характеристический вектор , который является двоичным вектором длины который имеет значение 1, когда элемент а также , или 0, когда . Лучший способ уменьшить размер защищенного эскиза, когда большой. большой, так как размер определяется . Хороший код, на котором основывается эта конструкция, - это Код BCH, где а также так , также полезно, чтобы коды BCH можно было декодировать за сублинейное время.
Построение эскиза булавкой
Позволять . Исправлять первая находка , затем найти множество v, где , наконец, вычислите симметричную разность, чтобы получить. Хотя это не единственная конструкция, с помощью которой можно установить разницу, она самая простая.
Редактировать дистанционные конструкции
Когда данные могут быть повреждены или удалены, лучшим способом измерения является расстояние редактирования . Чтобы создать конструкцию, основанную на расстоянии редактирования, проще всего начать с построения для заданной разницы или расстояния Хэмминга в качестве промежуточного шага коррекции, а затем построить вокруг него построение расстояния редактирования.
Прочие конструкции для измерения расстояния
Есть много других типов ошибок и расстояний, которые можно использовать для моделирования других ситуаций. Большинство этих других возможных конструкций построено на более простых конструкциях, таких как конструкции расстояния редактирования.
Повышение устойчивости к ошибкам за счет смягчения представлений о правильности
Можно показать, что устойчивость к ошибкам безопасного эскиза можно улучшить, применяя вероятностный метод к исправлению ошибок и запрашивая только ошибки, которые можно исправить с высокой вероятностью. Это позволяет выйти за пределы Плоткина, которые ограничивают исправлениеошибок и приблизиться к оценке Шеннона с учетом почтиисправления. Для достижения этой улучшенной коррекции ошибок необходимо использовать менее ограничительную модель распределения ошибок.
Случайные ошибки
Для этой наиболее жесткой модели используйте BSC. создать что вероятность на каждой позиции в что полученный бит неправильный. Эта модель может показать, что потеря энтропии ограничивается, где - бинарная функция энтропии , а если min-энтропия тогда ошибки можно терпеть, для некоторых постоянных .
Ошибки, зависящие от ввода
Для этой модели ошибки не имеют известного распределения и могут исходить от злоумышленника, единственными ограничениями являются и что искаженное слово зависит только от ввода а не на безопасном эскизе. Для этой модели ошибок можно показать, что никогда не будет больше, чем ошибок, поскольку эта модель может учитывать все сложные шумовые процессы, а это означает, что может быть достигнута граница Шеннона, для этого к защищенному эскизу добавляется случайная перестановка, которая уменьшит потерю энтропии.
Вычислительно ограниченные ошибки
Это отличается от модели, зависящей от входных данных, наличием ошибок, которые зависят как от входных данных. и безопасный эскиз, и злоумышленник ограничен алгоритмами с полиномиальным временем для внесения ошибок. Поскольку алгоритмы, которые могут работать за время, превышающее полиномиальное, в настоящее время невозможны в реальном мире, положительный результат с использованием этой модели ошибок будет гарантировать, что любые ошибки могут быть исправлены. Это наименее ограничительная модель, единственный известный способ приблизиться к границе Шеннона - использовать коды, декодируемые списком, хотя на практике это не всегда может быть полезно, поскольку возврат списка вместо одного кодового слова не всегда может быть приемлемым.
Гарантии конфиденциальности
В целом шифрованная попытка системы просачиваться как мало информация , как это возможно в качестве противника . В случае биометрии в случае утечки информации о считывании биометрических данных злоумышленник может получить личную информацию о пользователе. Например, злоумышленник замечает, что во вспомогательных строках есть определенный шаблон, который подразумевает этническую принадлежность пользователя. Мы можем рассматривать эту дополнительную информацию как функцию. Если злоумышленник узнает вспомогательную строку, необходимо убедиться, что из этих данных он не сможет вывести какие-либо данные о человеке, у которого были сняты биометрические данные.
Корреляция между вспомогательной строкой и биометрическим вводом
В идеале вспомогательная строка не будет раскрывать информацию о биометрическом вводе . Это возможно только тогда, когда каждое последующее биометрическое считывание идентичен оригиналу . В этом случае на самом деле нет необходимости во вспомогательной строке, поэтому легко сгенерировать строку, которая никоим образом не коррелирует с.
Поскольку желательно принимать биометрические данные похожий на вспомогательная строка должно быть как-то коррелировано. Более разные а также разрешены, тем больше будет корреляция между а также , чем больше они взаимосвязаны, тем больше информации показывает о . Мы можем рассматривать эту информацию как функцию. Лучшее возможное решение - убедиться, что злоумышленник не сможет узнать что-либо полезное из вспомогательной строки.
Gen ( W ) как вероятностная карта
Вероятностная карта скрывает результаты функций с небольшой утечкой . Утечка - это разница в вероятности угадывания двумя противниками некоторой функции, когда один знает вероятностную карту, а другой нет. Формально:
Если функция является вероятностной картой, то даже если противник знает как вспомогательную строку и секретная строка они лишь незначительно более вероятно поймут что-то о предмете, как если бы они ничего не знали. Строка предполагается, что он хранится в секрете, поэтому даже в случае утечки информации (что маловероятно) злоумышленник все равно не сможет выяснить ничего полезного о предмете, если маленький. Мы можем рассмотретьбыть какой-либо корреляцией между биометрическими данными и некоторыми физическими характеристиками человека. Параметр в приведенном выше уравнении меняет его на:
Это означает, что если один противник имеет и второй противник ничего не знает, их лучшие догадки на только отдельно.
Однородные нечеткие экстракторы
Унифицированные нечеткие экстракторы - это частный случай нечетких экстракторов, где выходные из незначительно отличаются от строк, выбранных из равномерного распределения, т. е.
Единые безопасные эскизы
Поскольку безопасные эскизы подразумевают нечеткие экстракторы, создание единого безопасного эскиза позволяет легко построить однородный нечеткий экстрактор. В едином безопасном эскизе процедура эскизаэто случайность экстрактор . Где биометрический ввод и - случайное семя . Поскольку экстракторы случайности выводят строку, которая выглядит как однородное распределение, они скрывают всю информацию о своем вводе.
Приложения
Эскизы экстрактора можно использовать для построения -нечеткие идеально односторонние хеш-функции. При использовании в качестве хеш-функции входэто объект, который вы хотите хешировать. В что output - это хеш-значение. Если бы кто-то хотел убедиться, что в из оригинала , они подтвердят, что . -нечеткие идеально односторонние хэш-функции - это специальные хеш-функции, в которых они принимают любой ввод не более чемошибок, по сравнению с традиционными хэш-функциями, которые принимают только тогда, когда ввод точно соответствует оригиналу. Традиционные криптографические хеш-функции пытаются гарантировать, что с вычислительной точки зрения невозможно найти два разных входа, которые хешируют одно и то же значение. Нечеткие идеально односторонние хеш-функции делают аналогичное утверждение. Они делают невозможным с точки зрения вычислений два нахождения двух входов, которые больше, чем Расстояние Хэмминга друг от друга и хеширование с одинаковым значением.
Защита от активных атак
Активная атака может быть такой, при которой злоумышленник может изменить вспомогательную строку. . Если противник может изменить в другую строку, которая также приемлема для функции воспроизведения , это приводит выводить неверную секретную строку . Надежные нечеткие экстракторы решают эту проблему, допуская сбой функции воспроизведения, если в качестве входных данных предоставляется измененная вспомогательная строка.
Надежные нечеткие экстракторы
Один из методов создания надежных нечетких экстракторов - использование хеш-функций . Эта конструкция требует двух хэш-функций а также . В functions производит вспомогательную строку путем добавления вывода безопасного эскиза к хешу обоих чтений и безопасный эскиз . Он генерирует секретную строку применяя вторую хеш-функцию к а также . Формально:
Функция воспроизведения также использует хэш-функции а также . В дополнение к проверке биометрических данных ввод достаточно похож на тот, который был восстановлен с помощью функция, он также проверяет этот хеш во второй части был фактически получен из а также . Если оба этих условия соблюдены, возвращается что само по себе является второй хеш-функцией, применяемой к а также . Формально:
Получать а также из Если а также тогда еще
Если было изменено, это будет очевидно, потому что, выдаст ошибку с очень высокой вероятностью. Чтобы алгоритм принял другой противнику придется найти такой, что . Поскольку хэш-функция считается односторонней , с вычислительной точки зрения найти такую. Видяне предоставит противнику никакой полезной информации. Поскольку, опять же, хеш-функция является односторонней, злоумышленник с вычислительной точки зрения не может отменить хеш-функцию и вычислить. Частьявляется безопасным скетчем, но по определению скетч раскрывает незначительную информацию о своем вводе. Аналогично видя (даже если он никогда не должен этого видеть) не предоставит противнику никакой полезной информации, поскольку злоумышленник не сможет отменить хэш-функцию и увидеть биометрические данные.
Рекомендации
- ^ a b c Евгений Додис, Рафаил Островский, Леонид Рейзин и Адам Смит. «Нечеткие экстракторы: как создать надежные ключи из биометрии и других зашумленных данных» . 2008 г.
- «Нечеткие экстракторы: краткий обзор результатов с 2004 по 2006 год» .
- «Схема биометрического нечеткого экстрактора для шаблонов радужки» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - «Нечеткая схема хранилища» (PDF) . Цитировать журнал требует
|journal=
( помощь )
Внешние ссылки
- «Minisketch: оптимизированная библиотека C ++ для согласования наборов на основе BCH (Pin Sketch)» . github.com . 31 мая 2021 г.