Симметричное шифрование с возможностью поиска

Симметричное шифрование с возможностью поиска ( SSE ) — это форма шифрования , которая позволяет эффективно выполнять поиск по коллекции зашифрованных документов или файлов без возможности их расшифровки. ^[1]^[2]^[3] SSE можно использовать для передачи файлов на ненадежный сервер облачного хранилища, не раскрывая файлы в открытом виде, но сохраняя при этом способность сервера выполнять поиск по ним.

Описание

Схема симметричного шифрования с возможностью поиска — это схема шифрования с симметричным ключом , которая шифрует набор документов. $\mathbf {D} =(\mathrm {D_{1}} ,\dots ,\mathrm {D_{n}} )$ , где каждый документ $\mathrm {D_{i}} \subseteq \mathbb {W}$ рассматривается как набор ключевых слов из пространства ключевых слов. $\mathbb {W}$ . Учитывая ключ шифрования $K$ и ключевое слово $w\in \mathbb {W}$ , можно сгенерировать токен поиска $tk$ с помощью которого можно искать зашифрованный набор данных $w$ . Результатом поиска является подмножество зашифрованных документов, содержащих ключевое слово $w$ .

Статический SSE

Статическая схема SSE состоит из трех алгоритмов. ${\mathsf {SSE=(Setup,Token,Search)}}$ которые работают следующим образом:

${\mathsf {Setup}}$ принимает в качестве входных данных параметр безопасности $k$ и сборник документов $\mathbf {D}$ и выводит симметричный ключ $K$ , зашифрованный индекс $\mathbf {I}$ и коллекция зашифрованных документов $\mathbf {ED}$
${\mathsf {Token}}$ принимает в качестве входных данных секретный ключ $K$ и ключевое слово $w$ и выводит токен поиска $tk$
${\mathsf {Search}}$ принимает на вход зашифрованный индекс $\mathbf {I}$ , коллекция зашифрованных документов $\mathbf {ED}$ и токен поиска $tk$ и выводит набор зашифрованных документов $\mathbf {R} \subseteq \mathbf {ED}$

Статическая схема SSE используется клиентом и недоверенным сервером следующим образом. Клиент шифрует собранные данные с помощью ${\mathsf {Setup}}$ алгоритм, который возвращает секретный ключ $K$ и коллекция зашифрованных документов $\mathbf {ED}$ . Клиент сохраняет $K$ секрет и отправляет $\mathbf {ED}$ и $\mathbf {I}$ на ненадежный сервер. Для поиска по ключевому слову $w$ , клиент запускает ${\mathsf {Token}}$ алгоритм на $K$ и $w$ для создания токена поиска $tk$ который он отправляет на сервер. Сервер запускает поиск с помощью $\mathbf {ED}$ , $\mathbf {I}$ , и $tk$ и возвращает полученные зашифрованные документы обратно клиенту.

Динамический SSE

Динамическая схема SSE поддерживает, помимо поиска, вставку и удаление документов. Динамическая схема SSE состоит из семи алгоритмов. ${\mathsf {SSE=(Setup,Token,Search,InsertToken,Insert,DeleteToken,Delete)}}$ где ${\mathsf {Setup}}$ , ${\mathsf {Token}}$ и ${\mathsf {Search}}$ такие же, как и в статическом случае, а остальные алгоритмы работают следующим образом:

${\mathsf {InsertToken}}$ принимает в качестве входных данных секретный ключ $K$ и новый документ $\mathrm {D_{n+1}}$ и выводит токен вставки $itk$
${\mathsf {Insert}}$ принимает в качестве входных данных коллекцию зашифрованных документов EDC и токен вставки $itk$ и выводит обновленную коллекцию зашифрованных документов $\mathbf {ED'}$
${\mathsf {DeleteToken}}$ принимает в качестве входных данных секретный ключ $K$ и идентификатор документа $id$ и выводит токен удаления $dtk$
${\mathsf {Delete}}$ принимает в качестве входных данных сбор зашифрованных данных $\mathrm {EDC}$ и токен удаления $dtk$ и выводит обновленную коллекцию зашифрованных данных $\mathbf {ED'}$

Чтобы добавить новый документ $\mathrm {D_{n+1}}$ клиент работает ${\mathsf {InsertToken}}$ на $K$ и $\mathrm {D_{n+1}}$ для создания токена вставки $itk$ который он отправляет на сервер. Сервер работает ${\mathsf {Insert}}$ с $\mathbf {ED}$ и $itk$ и сохраняет обновленную коллекцию зашифрованных документов. Чтобы удалить документ с идентификатором $id$ , клиент запускает ${\mathsf {DeleteToken}}$ алгоритм с $K$ и $id$ для создания токена удаления $dtk$ который он отправляет на сервер. Сервер работает ${\mathsf {Delete}}$ с $\mathbf {ED}$ и $dtk$ и сохраняет обновленную коллекцию зашифрованных документов.

Схема SSE, которая не поддерживает ${\mathsf {DeleteToken}}$ и ${\mathsf {Delete}}$ называется полудинамическим.

История симметричного шифрования с возможностью поиска

Проблему поиска по зашифрованным данным рассматривали Сонг , Вагнер и Перриг. ^[1] Oblivious RAM и хотя предыдущая работа Гольдрейха Островского над ^[4] Теоретически можно использовать для решения этой проблемы. Эта работа ^[1] предложил схему SSE с алгоритмом поиска, работающим во времени $O(s)$ , где $s=|\mathbf {D} |$ . Гох ^[5] и Чанг и Митценмахер ^[6] дал новые конструкции SSE с алгоритмами поиска, работающими во времени $O(n)$ , где $n$ это количество документов. Куртмола, Гарай, Камара и Островский ^[2] позже предложил две статические конструкции с $O(\mathrm {opt} )$ время поиска, где $\mathrm {opt}$ количество документов, содержащих $w$ , что является оптимальным. В этой работе также была предложена полудинамическая конструкция с $O(\mathrm {opt} \cdot \log(u))$ время поиска, где $u$ это количество обновлений. Оптимальная динамическая конструкция SSE была позже предложена Камарой , Папаманту и Рёдером. ^[7]

Гох ^[5] и Чанг и Митценмахер ^[6] предложенные определения безопасности для SSE. Их усилили и расширили Куртмола, Гарай, Камара и Островский. ^[2] который предложил понятие адаптивной безопасности для SSE. Эта работа также была первой, в которой была обнаружена утечка в SSE и формально зафиксирована как часть определения безопасности. В дальнейшем утечка была формализована и обобщена Чейзом и Камарой . ^[8] Ислам, Кузу и Кантарджиоглу описали первую атаку утечки. ^[9]

Все ранее упомянутые конструкции поддерживают поиск по одному ключевому слову. Кэш, Яреки, Ютла, Кравчик , Розу и Штайнер ^[10] предложил схему SSE, которая поддерживает конъюнктивный поиск в сублинейном времени в $n$ . Конструкция также может быть расширена для поддержки дизъюнктивного и логического поиска, который может быть выражен в нормальной форме с возможностью поиска (SNF) за сублинейное время. В то же время Паппас, Крелл, Во, Колесников, Малкин , Цой, Георгий, Керомитис и Белловин ^[11] описал конструкцию, которая поддерживает конъюнктивный, а также все дизъюнктивные и логические поиски в сублинейном времени.

Безопасность

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

Безопасность SSE можно анализировать с помощью нескольких состязательных моделей, но наиболее распространенными являются:

постоянная модель, ^[2] когда злоумышленнику предоставляется зашифрованная коллекция данных и расшифровка всех операций, выполненных с этой коллекцией;
модель моментального снимка, ^[12] где злоумышленнику предоставляется только зашифрованный набор данных (но, возможно, после каждой операции).

Безопасность в постоянной модели

В постоянной модели существуют схемы SSE, которые обеспечивают широкий спектр профилей утечек. Наиболее распространенный профиль утечки для статических схем, которые обеспечивают поиск по одному ключевому слову в оптимальное время: $\Lambda _{\mathrm {opt} }$ который показывает количество документов в коллекции, размер каждого документа в коллекции, повторялся ли запрос и когда и какие зашифрованные документы соответствуют поисковому запросу. ^[2]^[13] Однако известно, как построить схемы со значительно меньшими утечками при дополнительных затратах времени поиска и хранения. ^[14]^[15]

При рассмотрении динамических схем SSE современные конструкции с поиском оптимального времени имеют профили утечки, гарантирующие прямую конфиденциальность. ^[16] это означает, что вставки не могут быть сопоставлены с прошлыми поисковыми запросами.

Безопасность в модели моментальных снимков

В модели моментального снимка можно построить эффективные динамические схемы SSE без утечек, выходящих за рамки количества документов и размера коллекции. ^[12] При использовании конструкции SSE, которая безопасна в модели моментального снимка, необходимо тщательно продумать, как будет развернута схема, поскольку некоторые системы могут кэшировать предыдущие поисковые запросы. ^[17]

Криптоанализ

Профиль утечки описывает только утечку схемы SSE, но ничего не говорит о том, можно ли использовать эту утечку или нет. Поэтому криптоанализ используется для лучшего понимания реальной безопасности профиля утечки. Существует множество атак, работающих в различных состязательных моделях, основанных на различных предположениях и атакующих различные профили утечек. ^[18]^[19]

См. также

Ссылки

^ Jump up to: ^а ^б ^с Рассвет Сяодин Сун; Вагнер, Д.; Перриг, А. (2000). «Практические приемы поиска зашифрованных данных» . Продолжается симпозиум IEEE 2000 г. по безопасности и конфиденциальности. S&P 2000 . IEEE-компьютер. Соц. стр. 44–55. дои : 10.1109/secpri.2000.848445 . ISBN 0-7695-0665-8 . S2CID 2829840 .
^ Jump up to: ^а ^б ^с ^д ^и Куртмола, Реза; Гарай, Хуан; Камара, Сени; Островский, Рафаил (30 октября 2006 г.). «Симметричное шифрование с возможностью поиска» . Материалы 13-й конференции ACM «Компьютерная и коммуникационная безопасность» . ККС '06. Александрия, Вирджиния, США: Ассоциация вычислительной техники. стр. 79–88. дои : 10.1145/1180405.1180417 . ISBN 978-1-59593-518-2 . S2CID 961719 .
^ Аморим, Ивоне; Коста, Иван (01 июля 2023 г.). «Использование шифрования с возможностью поиска посредством гомоморфного шифрования: комплексный анализ» . Математика . 11 (13): 2948. arXiv : 2306.14407 . дои : 10.3390/math11132948 . ISSN 2227-7390 .
^ Гольдрейх, Одед; Островский, Рафаил (май 1996 г.). «Программная защита и моделирование на забывчивой оперативной памяти» . Журнал АКМ . 43 (3): 431–473. дои : 10.1145/233551.233553 . hdl : 1721.1/103684 . ISSN 0004-5411 . S2CID 7502114 .
^ Jump up to: ^а ^б Го, Ю-Джин (2003). «Безопасные индексы» .
^ Jump up to: ^а ^б Чанг, Янь-Чэн; Митценмахер, Майкл (2005). «Сохранение конфиденциальности поиска по ключевым словам в удаленных зашифрованных данных». В Иоаннидисе, Джон; Керомитис, Ангелос; Юнг, Моти (ред.). Прикладная криптография и сетевая безопасность . Конспекты лекций по информатике. Том. 3531. Берлин, Гейдельберг: Springer. стр. 442–455. дои : 10.1007/11496137_30 . ISBN 978-3-540-31542-1 .
^ Камара, Сени; Папаманту, Харалампос; Редер, Том (16 октября 2012 г.). «Динамическое симметричное шифрование с возможностью поиска» . Материалы конференции ACM 2012 года по компьютерной и коммуникационной безопасности . ККС '12. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 965–976. дои : 10.1145/2382196.2382298 . ISBN 978-1-4503-1651-4 . S2CID 243046 .
^ Чейз, Мелисса; Камара, Сени (2010). «Структурированное шифрование и контролируемое раскрытие». В Абэ, Масаюки (ред.). Достижения в криптологии — ASIACRYPT 2010 . Конспекты лекций по информатике. Том. 6477. Берлин, Гейдельберг: Springer. стр. 577–594. дои : 10.1007/978-3-642-17373-8_33 . ISBN 978-3-642-17373-8 .
^ Ислам, Мухаммед; Кузу, Мехмет; Кантарджиоглу, Мурат. «Раскрытие шаблона доступа к шифрованию с возможностью поиска: разветвление, атака и смягчение последствий» (PDF) . Симпозиум по безопасности сетей и распределенных систем (NDSS) .
^ Кэш, Дэвид; Ярецкий, Станислав; Джутла, Чаранджит; Кравчик, Хьюго; Рошу, Марсель-Кэтэлин; Штайнер, Майкл (2013). «Высокомасштабируемое симметричное шифрование с возможностью поиска и поддержкой логических запросов». В Канетти Ран; Гарай, Хуан А. (ред.). Достижения криптологии – CRYPTO 2013 . Конспекты лекций по информатике. Том. 8042. Берлин, Гейдельберг: Springer. стр. 353–373. дои : 10.1007/978-3-642-40041-4_20 . ISBN 978-3-642-40041-4 .
^ Паппас, Василис; Крелл, Фернандо; Во, Бинь; Колесников Владимир; Малкин, Таль; Чхве, Сын Гёль; Джордж, Уэсли; Керомитис, Ангелос; Белловин, Стив (май 2014 г.). «Слепой провидец: масштабируемая частная СУБД». Симпозиум IEEE 2014 по безопасности и конфиденциальности . IEEE. стр. 359–374. дои : 10.1109/sp.2014.30 . ISBN 978-1-4799-4686-0 . S2CID 9165575 .
^ Jump up to: ^а ^б Амджад, Гус; Камара, Сени; Моатаз, Тарик (01 января 2019 г.). «Устойчивое к взлому структурированное шифрование» . Труды по технологиям повышения конфиденциальности . 2019 (1): 245–265. дои : 10.2478/popets-2019-0014 . S2CID 4047057 .
^ «Динамическое шифрование с возможностью поиска в очень больших базах данных: структуры данных и реализация – симпозиум NDSS» . Проверено 22 февраля 2022 г.
^ Камара, Сени; Моатаз, Тарик; Охрименко, Оля (2018). «Структурированное шифрование и подавление утечек» . В Шахаме, Ховав; Болдырева, Александра (ред.). Достижения криптологии – CRYPTO 2018 . Конспекты лекций по информатике. Том. 10991. Чам: Springer International Publishing. стр. 339–370. дои : 10.1007/978-3-319-96884-1_12 . ISBN 978-3-319-96884-1 . S2CID 51603585 .
^ «Возвращаясь к атакам, связанным со злоупотреблением утечками информации – симпозиум NDSS» . Проверено 22 февраля 2022 г.
^ «Практическое шифрование с динамическим поиском и небольшой утечкой – симпозиум NDSS» . Проверено 22 февраля 2022 г.
^ Граббс, Пол; Ристенпарт, Томас; Шматиков, Виталий (07.05.2017). «Почему ваша зашифрованная база данных небезопасна» . Материалы 16-го семинара по актуальным темам операционных систем . ХоОС '17. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 162–168. дои : 10.1145/3102980.3103007 . ISBN 978-1-4503-5068-6 . S2CID 10111288 .
^ Яо, Цзин; Чжэн, Ифэн; Го, Ю; Ван, Конг (06 октября 2020 г.). «SoK: Систематическое исследование атак при эффективном поиске зашифрованных облачных данных» . Материалы 8-го международного семинара по безопасности в блокчейне и облачных вычислениях . СБК '20. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 14–20. дои : 10.1145/3384942.3406869 . ISBN 978-1-4503-7609-9 . S2CID 222179683 .
^ Камара, Сени; Кати, Абделькарим; Моатаз, Тарик; Шнайдер, Томас; Трейбер, Амос; Йонли, Майкл (2021). «Криптоанализ зашифрованного поиска с помощью LEAKER — основа для оценки атак LEakage на реальные данные» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[:0-1] Jump up to: ^а ^б ^с Рассвет Сяодин Сун; Вагнер, Д.; Перриг, А. (2000). «Практические приемы поиска зашифрованных данных» . Продолжается симпозиум IEEE 2000 г. по безопасности и конфиденциальности. S&P 2000 . IEEE-компьютер. Соц. стр. 44–55. дои : 10.1109/secpri.2000.848445 . ISBN 0-7695-0665-8 . S2CID 2829840 .

[:1-2] Jump up to: ^а ^б ^с ^д ^и Куртмола, Реза; Гарай, Хуан; Камара, Сени; Островский, Рафаил (30 октября 2006 г.). «Симметричное шифрование с возможностью поиска» . Материалы 13-й конференции ACM «Компьютерная и коммуникационная безопасность» . ККС '06. Александрия, Вирджиния, США: Ассоциация вычислительной техники. стр. 79–88. дои : 10.1145/1180405.1180417 . ISBN 978-1-59593-518-2 . S2CID 961719 .

[3] Аморим, Ивоне; Коста, Иван (01 июля 2023 г.). «Использование шифрования с возможностью поиска посредством гомоморфного шифрования: комплексный анализ» . Математика . 11 (13): 2948. arXiv : 2306.14407 . дои : 10.3390/math11132948 . ISSN 2227-7390 .

[4] Гольдрейх, Одед; Островский, Рафаил (май 1996 г.). «Программная защита и моделирование на забывчивой оперативной памяти» . Журнал АКМ . 43 (3): 431–473. дои : 10.1145/233551.233553 . hdl : 1721.1/103684 . ISSN 0004-5411 . S2CID 7502114 .

[:2-5] Jump up to: ^а ^б Го, Ю-Джин (2003). «Безопасные индексы» .

[:3-6] Jump up to: ^а ^б Чанг, Янь-Чэн; Митценмахер, Майкл (2005). «Сохранение конфиденциальности поиска по ключевым словам в удаленных зашифрованных данных». В Иоаннидисе, Джон; Керомитис, Ангелос; Юнг, Моти (ред.). Прикладная криптография и сетевая безопасность . Конспекты лекций по информатике. Том. 3531. Берлин, Гейдельберг: Springer. стр. 442–455. дои : 10.1007/11496137_30 . ISBN 978-3-540-31542-1 .

[7] Камара, Сени; Папаманту, Харалампос; Редер, Том (16 октября 2012 г.). «Динамическое симметричное шифрование с возможностью поиска» . Материалы конференции ACM 2012 года по компьютерной и коммуникационной безопасности . ККС '12. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 965–976. дои : 10.1145/2382196.2382298 . ISBN 978-1-4503-1651-4 . S2CID 243046 .

[8] Чейз, Мелисса; Камара, Сени (2010). «Структурированное шифрование и контролируемое раскрытие». В Абэ, Масаюки (ред.). Достижения в криптологии — ASIACRYPT 2010 . Конспекты лекций по информатике. Том. 6477. Берлин, Гейдельберг: Springer. стр. 577–594. дои : 10.1007/978-3-642-17373-8_33 . ISBN 978-3-642-17373-8 .

[9] Ислам, Мухаммед; Кузу, Мехмет; Кантарджиоглу, Мурат. «Раскрытие шаблона доступа к шифрованию с возможностью поиска: разветвление, атака и смягчение последствий» (PDF) . Симпозиум по безопасности сетей и распределенных систем (NDSS) .

[10] Кэш, Дэвид; Ярецкий, Станислав; Джутла, Чаранджит; Кравчик, Хьюго; Рошу, Марсель-Кэтэлин; Штайнер, Майкл (2013). «Высокомасштабируемое симметричное шифрование с возможностью поиска и поддержкой логических запросов». В Канетти Ран; Гарай, Хуан А. (ред.). Достижения криптологии – CRYPTO 2013 . Конспекты лекций по информатике. Том. 8042. Берлин, Гейдельберг: Springer. стр. 353–373. дои : 10.1007/978-3-642-40041-4_20 . ISBN 978-3-642-40041-4 .

[11] Паппас, Василис; Крелл, Фернандо; Во, Бинь; Колесников Владимир; Малкин, Таль; Чхве, Сын Гёль; Джордж, Уэсли; Керомитис, Ангелос; Белловин, Стив (май 2014 г.). «Слепой провидец: масштабируемая частная СУБД». Симпозиум IEEE 2014 по безопасности и конфиденциальности . IEEE. стр. 359–374. дои : 10.1109/sp.2014.30 . ISBN 978-1-4799-4686-0 . S2CID 9165575 .

[:4-12] Jump up to: ^а ^б Амджад, Гус; Камара, Сени; Моатаз, Тарик (01 января 2019 г.). «Устойчивое к взлому структурированное шифрование» . Труды по технологиям повышения конфиденциальности . 2019 (1): 245–265. дои : 10.2478/popets-2019-0014 . S2CID 4047057 .

[13] «Динамическое шифрование с возможностью поиска в очень больших базах данных: структуры данных и реализация – симпозиум NDSS» . Проверено 22 февраля 2022 г.

[14] Камара, Сени; Моатаз, Тарик; Охрименко, Оля (2018). «Структурированное шифрование и подавление утечек» . В Шахаме, Ховав; Болдырева, Александра (ред.). Достижения криптологии – CRYPTO 2018 . Конспекты лекций по информатике. Том. 10991. Чам: Springer International Publishing. стр. 339–370. дои : 10.1007/978-3-319-96884-1_12 . ISBN 978-3-319-96884-1 . S2CID 51603585 .

[15] «Возвращаясь к атакам, связанным со злоупотреблением утечками информации – симпозиум NDSS» . Проверено 22 февраля 2022 г.

[16] «Практическое шифрование с динамическим поиском и небольшой утечкой – симпозиум NDSS» . Проверено 22 февраля 2022 г.

[17] Граббс, Пол; Ристенпарт, Томас; Шматиков, Виталий (07.05.2017). «Почему ваша зашифрованная база данных небезопасна» . Материалы 16-го семинара по актуальным темам операционных систем . ХоОС '17. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 162–168. дои : 10.1145/3102980.3103007 . ISBN 978-1-4503-5068-6 . S2CID 10111288 .

[18] Яо, Цзин; Чжэн, Ифэн; Го, Ю; Ван, Конг (06 октября 2020 г.). «SoK: Систематическое исследование атак при эффективном поиске зашифрованных облачных данных» . Материалы 8-го международного семинара по безопасности в блокчейне и облачных вычислениях . СБК '20. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 14–20. дои : 10.1145/3384942.3406869 . ISBN 978-1-4503-7609-9 . S2CID 222179683 .

[19] Камара, Сени; Кати, Абделькарим; Моатаз, Тарик; Шнайдер, Томас; Трейбер, Амос; Йонли, Майкл (2021). «Криптоанализ зашифрованного поиска с помощью LEAKER — основа для оценки атак LEakage на реальные данные» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]