Многоключевой поиск по зашифрованным данным

From CryptoWiki
Jump to: navigation, search

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

Contents

1 Введение

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

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

Raluca Ada Popa and Nickolai Zeldovich (MIT CSAIL) представляют криптографическую схему, которая позволяет клиенту давать единственный поисковый маркер серверу, но все еще позволяет серверу искать слово того маркера в документах, зашифрованных с различными ключами. Эта схема называется Многоключевой поиск по зашифрованным данным [1]. Наглядно, схема скрывает содержание документа и слов, которые каждый ищет, и единственная информация, которую изучает сервер, - является ли некоторое искомое слово, найденным словом в документе.

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

Большинство исследований по поиску по зашифрованным данным [15,11, 5, 8, 4, 9, 6, 3, 17, 16, 14, 12, 7] сосредоточены на том случае, когда данные шифруются с тем же самым ключом, и обдумываются различные аспекты полученной криптосистемы, такие как открытый - в сравнении с секретным ключом, более дорогие вычисления, таких как конъюнкция и дизъюнкция, индексируемые схемы и другие.

На сколько известно работа Lopez-Alt и др. [13] является единственной работой, учитывающей вычисления по данным, зашифрованным с различными ключами. Они разрабатывают схему полного гомоморфного шифрования (FHE). Однако расшифрование требует, чтобы все стороны объединились и выполнили протокол MPC. Для схемы многоключевого поиска по зашифрованным данным требуется, чтобы клиент получил все ключи, по которым данные зашифрованы так, что клиент все еще должен проделать работу, пропорциональную количеству ключей, а это нужно избежать. Кроме того, из-за семантической безопасности FHE, сервер не учится, соответствует ли документ ключевому слову.

Работа Bao и др. [3], считают установку, где пользователи имеют разные ключи, но все данные шифруются с помощью одной клавиши и поиск происходит по каналу передачи данных, зашифрованных одним ключом. Никто не может непосредственно применять их схему к многоключевой настройки путем создания экземпляра схемы для каждого ключа, так как это приводит к многим поисковым маркерам; причина заключается в том, что поисковые маркеры привязаны к различным секретам для каждого различного ключа.

2 Постановка задачи

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

Определение 2.1 (Граф доступа). Граф доступа G = (U, D, Е) состоит из множества пользователей U, множества документов D, а также множества ребер Е, где ребро е называется парой (i, j) для i ∈ U
и j ∈ D, обозначающее, что пользователь i имеет доступ к документу j. Обозначим через е ∈ G означает, что е ∈ E.
Рисунок 1 — Пример графа доступа

Если какому-то пользователю не был предоставлен доступ к документу, пользователь не должен быть в состоянии прочитать содержимое этого документа или выполнить поиск в этом документе, даже если пользователь вступает в сговор с сервером. Настройки полностью распределены. Каждый пользователь создает свой ключ и нет доверенной стороны выбора ключей, и нет глобального доверенного пользователя. Кроме того, не существует доверенная сторона, создающая ключи документа или помогающая с предоставлением доступа к документам.

Функциональная цель состоит в том, чтобы позволить пользователю искать слова по всем документам, к которым он может получить доступ, скажем из n документов, даже если эти документы шифруются под разными ключами. Обратите внимание, что пользователь имеет доступ ко всем ключам для этих n документов, но пользователь должен дать только один маркер поиска на сервере, а не n маркеров. Рассмотрим более конкретную модель для такого многоключевого поиска . Обозначим ключ пользователя i с ukj, и ключ документа j с kj. Учтите, что пользователь, скажем Алиса, (с ключом ukj) имеет n зашифрованных документов на сервере, и каждый зашифрован по ключу для kj от 1…n. Алиса хочет найти слово w во всех документах, на которые у нее есть доступ, так что она использует ukА , вычисляет маркер для слова w. Для того, чтобы позволить серверу соответствовать маркерам слов зашифрованныx с k1,…,kn, Алиса дает серверу некоторую публичную информацию под названием дельта. Алиса обеспечивает одну дельту для каждого ключа kj, обозначается ΔukA,kj. Сервер может использовать ΔukA,kj для преобразования поиска маркера под ключом ukА в поисковой маркер под kj. Этот процесс называется регулировкой. Таким образом, сервер может получить маркеры для слова w при k1,…,kn, в то время как только получает один маркер от Алисы, а затем выполняет традиционный одноключевой поиск с новыми маркерами.

Многоключевой поиск обеспечивает гарантии эффективности над одноключевым поиском. Если T общее количество слов, которые Алиса ищет, она дает O (n + T) части информации на сервер: n дельт и Т-маркеров, размер которых зависит только от параметра безопасности. В противоположность этому, если Алиса использует одноключевой поиск по зашифрованным данным, она дает O (nT) части информации на сервер, потому что она обеспечивает n маркеров, по одному для каждого ключа kj, для каждого из Т слов.

3 Синтаксис и определения безопасности

Определение 3.1 (многоключевой поиск). Схема многоключевого поиска  МК является кортежем алгоритмов (MK.Setup, MK.KeyGen, MK.Delta, MK.Token, MK.Enc, MK.Adjust, MK.Match) следующим образом:
• params ← MK.Setup (1^κ): принимает в качестве входных данных параметр безопасности и выводит общесистемные параметры.
• k ← MK.KeyGen (params): принимает в качестве входных данных параметры системы и выдает секретный ключ, который может стать ключом для пользователя или документа.
• Δ ← MK.Delta (k1, k2): принимает в качестве входных данных два ключа и выводит дельта.
• tk ← MK.Token (k, w): принимает в качестве входных данных ключ k и слово w и выводит результаты поиска маркера tk.
• c ← MK.Enc (k, w): принимает в качестве входных данных ключ k и слово w и выводит шифртекст c.
• stk ← MK.Adjust (tk, Δ): принимает в качестве входных данных маркер tk и дельта Δ и выводит поисковый маркер tk'.
• b ← MK.Match (stk, с): принимает в качестве входных данных маркер поиска stk и шифртекст с и выводит бит b. 

Корректность. Для любого многочлена n (·), для всех достаточно больших параметров безопасности k, для всех w ̸≠ w' ∈ {0, 1}^n(κ),
Ris5.png

Корректность говорит, что при поиске слова w, зашифрование этого слова w в какой-то документ будет соответствовать (после настройки маркера для w к ключу документа), но зашифрование иного слова w' не будет соответствовать поискy. Для простоты алгоритм расшифровки схемы не включен, но схема многоключевого поиска может быть легко увеличена с помощью алгоритма расшифрования, присоединяя к каждому шифртексту полученному в MK.Enc, симметричный ключ семантического безопасноого шифрования с тем же ключом в качестве аргумента MK.Enc.

Замечание 3.2. В альтернативном синтаксисе, каждый пользователь имеет открытый ключ pk, и алгоритм MK.Delta принимает в качестве входных данных открытый ключ пользователя вместо своего закрытого
ключа. Алгоритм шифрования открытым ключом MK.Delta имеет то преимущество, что, когда пользователь, скажем, Алиса, хочет дать доступ другому пользователю, скажем Бобу, Алиса может
просто вычислить дельта документа для Боба и предоставить его серверу.
Тем не менее, по своей сути, такая многоключевая схема не может скрыть искомое слово, потому что функциональность схемы позволяет провести атаку по словарю. Предположим, что противник хочет
узнать, что ищет Алиса, и пусть рkA будет открытым ключом Алисы. Злоумышленник может создать документ с некоторыми ключевыми k и зашифровать в этом документе, каждое слово словаря с помощью
ключа k. Затем противник может произвести дельту для Алисы к этому документу путем вычисления ΔA: = MK.Delta (рkA, k). Теперь для каждого поискового маркера tk Алисы, противник вычисляет stk: =
MK.Adjust (tk,ΔA) и использует stk, чтобы найти соответствие в зашифрованном словаре. После того, как найдено совпадение, противник знает какое слово искал пользователь.

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

Сопоставим эти свойства с двумя играми, скрытие данных и скрытие маркера, которые выражают эти цели.

3.1 Cкрытие данных (Data hiding)

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

Определение 3.3 (игра скрытие данных). Сокрытие данных игра между претендентом Ch и противником Adv о значениях параметров безопасности k и общественных параметров params.
• Ch вычисляет params ← CSetup (1^κ) и обеспечивает их Adv.
• Adv предоставляет граф доступа G с пользователями, пронумерованных 1 и документов, пронумерованных 0 до Ch вместе с ключами kj для каждого документа с j> 0.
• Ch генерирует k0 ← MK.KeyGen (1^κ, params) для документа 0. Тогда для каждого пользователя i, он генерирует uki ← MK.KeyGen (1^κ) и для каждого ребра (i, j) ∈ G, она обеспечивает MK. Дельта (uki, kj) для Adv.
• Шаг Задача: Adv выбирает w0*, w1* ← {0, 1}n(κ) и обеспечивает w0*, w1* к гл. Ch выбирает случайный бит b и обеспечивает MK.Enc (k0, wb*) Adv.
• Адаптивный шаг: Adv делает следующие запросы к Ch адаптивно. ℓ-го запрос	 может быть:
 1. "шифровать wℓ к документу 0": Ch возвращает MK.Enc (k0, wℓ).
 2. "Маркер для слова wℓ для пользователя i": Ch возвращает MK.Token (uki, wℓ).
• Adv выводит b', его предположение для b.
Ограничение на Adv: для всех запросов маркера wℓ для пользователя i, если (i, 0) ∈ G, то она должна быть, что wℓ ∉ { w0*, w1*}.
Adv выигрывает игру, если b'= b. Пусть winAdv (κ) случайная величина с указанием Adv,  выиграет ли игру параметр безопасности k.


Определение 3.4. Схема мнокоглючевого поиска скрывает данные, если для всех РРТ противниками Adv, для всех достаточно больших k, Pr [winAdv (κ)] <1/2 + negl (k).

• Тот факт, что Adv может предоставить ключи для всех документов кроме одной модели, что противник может украсть ключи документа или создавать документы, но такие действия не должны позволять Adv, узнавать информацию о документе, которым он не владеет.

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

• Обратите внимание, что Adv может задать маркеры для слов, которые являются частью проблемы (например, w0 или w1) для пользователей, которые не имеют дельту в документе 0. Это гарантирует, что любой пользователь i, не имеющий дельта документа не может найти этот документ.

• Нельзя позволить Adv спрашивать зашифрования запросов к документам i для i> 0, так как Adv имеет соответствующие секретные ключи и может зашифровать сам по себе.

3.2 Скрытие маркера (Token hiding)

Скрытие маркера требует, чтобы противник не мог узнать слово по которому выполняется поиск.

Определение 3.5. u-free документ в определенном графе является документом, без края от пользователя u в этом графе. u-free документ в определенном графе является пользователь, который имеет края
только к u-free документам в этом графе.

Пользователь 0 будет бросать пользователю вызов, для которого Adv будет отличать маркеры. Назовем 0-free пользователей и 0-free документы просто как "free users" и "free documents".

Определение 3.6 (Игра скрытия маркера). Игра между претендентом Ch и противной Adv c значениеями параметра безопасности k и общественных параметров params.
• Ch вычисляет params ← CSetup (1^κ) и обеспечивает их Adv.
• Adv предоставляет график доступа G с пользователями, пронумерованных 0 и документов, пронумерованных 1, а также с помощью клавиш uki для каждого свободного пользователя i и kj для каждого
свободного документа j.
• Ch генерирует uki ← MK.KeyGen (1^κ) для каждого несвободного пользователя i, kj ← MK.KeyGen (1^κ) для каждого несвободного документа j. Для каждого ребра (i, j) ∈ G, Ch посылает MK.Delta (uki, kj) для Adv.
• Адаптивный шаг. Adv делает следующие запросы к Ch адаптивно. При запросе ℓ:
 1. "шифровать wℓ для документа j": Ch возвращает MK.Enc (kj, wℓ).
 2. "Токен wℓ для пользователя i" с i> 0: получает MK.Token (uki, wℓ).
• Шаг Задача: Adv посылает w0* и w1* Ch и получает MK.Token (uk0, wb*) для случайной битовой b.
• Adv повторяет адаптивный шаг.
• Adv выводит b', его предположение для b.
Ограничение на Adv: Для каждого "символическими wℓ для пользователя i" запроса: wℓ ∉ { w0*, w1*} или пользователь i свободен. Для каждого "шифровать wℓ для документа j" запроса: wℓ ∉ { w0*, w1*} или документ j свободен.
Adv выигрывает игру, если b'=b. Пусть winAdv^token (k) случайная величина с указанием выигрывает ли Adv игру для параметра безопасности k.


Определение 3.7. Схема многоключевого поиска является скрывающей маркер, если для всех РРТ противниками Adv, для всех достаточно больших k, Pr [winAdv^token(κ) ]<1/2 + negl (κ).
Как и прежде, причиной Adv может забрать ключи, чтобы обозначить, что Adv может повредить некоторым пользователям или документам, или может даже создавать узлы в графе доступа.
Ограничения на игру такие, что противник не может отличить тривиальный вызов слова, так как функциональность схемы отличает их (либо потому, что есть совпадение поиска или маркер является
детерминированным).

4 Конструкция схемы

Пусть H: {0, 1} * → G1 и H2: GT × GT → {0, 1}* будут хэш-функции, смоделированные как случайные оракулы. Схема многоключевого поиска выглядит следующим образом:

• params ← MK.Setup(1κ ): возвращает (p, G1, G2, GT , e, g1, g2, gT ) ← CSetup(1^κ). • k ← MK.KeyGen(params): возвращает k ← Zp. • ∆ ← MK.Delta(k1, k2): возвращает ∆ = g^(k2/k1) ∈ G2. • tk ← MK.Token(k, w): возвращает tk = H(w)^k ∈ G1. • c ← MK.Enc(k, w): Рисунок r ← GT . На выходе c = (r, H2(r, e(H(w), g2)^k)). • tk′ ← MK.Adjust(tk, ∆): возвращает tk′ = e(tk, ∆) ∈ GT . • b ← MK.Match(tk, c): Пусть c = (r, h). Возвращает H2(r,tk) ?= h.

Замечание 6.1 (Альтернативные конструкции). Использование асимметричных пар здесь имеет решающее значение для обеспечения безопасности.
С симметричных парой (G1 = G2), есть атака, которая может определить искомое слово: дано Н(w), Н(w)^к и Н(w2), можно выделить H(w2)^k из R путем вычисления пересекающихся пар и,
таким образом, может сделать атаку по словарю. Асимметричные группы запрещают применение пар между элементами G1.
Другой способ, чтобы скрыть поиск маркера - использовать группы композитного порядка и умножить случайный элемент R ∈ Gh маркером слова. Можно также имитировать группы составного порядка сo
стандартными группами с использованием ортогональных методов векторного пространства Фримена и Lewko, что обеспечивает более высокую скорость реализации.  
Замечание 6.2 (Индексированный поиск). Если схема шифрования была детерминированной, было бы проще для поиска совпадений, так как индекс может быть построен над данными. Для того, чтобы сделать
схему таким способом, можно изменить только MK.Enc выход е(H (w), g2)^к. Если пользователь должен убедиться, что нет повторений слов w в документе зашифрованным с тем же ключом, что делает
шифрование детерминированным результат примерно в одних и тех же гарантиях.

5 Реализация

Схема реализована на C ++ и использует библиотеку PBC [2] для реализации кривой 2 типа (тип D в библиотеке) [10]. Ниже приведены результаты оценки на AMD Opteron (TM) Процессор 2,4 ГГц, работает на одном ядре, когда схема шифрования слов среднего размера, генерируется случайным образом. Схема имеет скромные накладные расходы.

Алгоритм MK.KeyGen MK.Delta MK.Token MK.Enc MK.Adjust MK.Match
Время (мс) 0.35 6.3 0.89 6.3 5.5 0.0021

Основание доказательств

Схема может быть доказана под вариантами Decisional Diffie-Hellman и External DiffieHellman, оба из которых являются стандартными предположениями.

Определение (Вариант билинейного Диффи-Хеллмана (BDHV) предположение). Для всех PPT алгоритмов Adv, для каждого достаточно большого параметра безопасности k,
|Pr[params ← CSetup(1^κ); a,b,c ← Zp : Adv(params, g1^a, g2^b, g2^1/a, g1^c, e(g1, g2)^abc) = 1] − 
Pr[params ← CSetup(1^κ); a,b,c ← Zp, R ← GT : Adv(params, g1^a, g2^b, g2^1/a, g1^c, R) = 1]| 
= negl(κ).


Определение (Вариант внешнего Диффи-Хеллмана (XDHV) предположение). Для всех PPT алгоритмов Adv, для каждого достаточно большого параметра безопасности k,
|Pr[params ← CSetup(1^κ); a,b,c,m ← Zp : Adv(params, g1^a, g1^b, g1^ab, g2^ca, g2^cd, g1^d, g2^1/d) = 1] − 
Pr[params ← CSetup(1^κ); a,b,c,m ← Zp, R ← GT : Adv(params, g1^a, g1^b, R, g2^ca, g2^cd, g1^d, g2^1/d) = 1]| 
= negl(κ).

Глоссарий

Библиография

Перейти к списку использованных источников.


Вялов А.А. Группа С12-503 (Б09-01)

2016