Криптографически безопасный поиск значения в наборе

Я ищу элегантное решение, казалось бы, тривиальной проблемы поиска определенного значения в известном наборе значений без раскрытия того, какое значение мы ищем. Позвольте мне описать это классическим способом:

Алиса скоро будет отмечать свой день рождения, и она хочет знать, у кого-нибудь в ее классе день рождения в тот же день, что и у нее. К сожалению, единственный человек, который знает даты рождения всех людей в классе (кроме Алисы), — это Мэлори. Как Алиса могла спросить Мэлори, празднует ли кто-нибудь день рождения в тот же день, не назвав свою собственную дату?

Предположение:

1. Мэлори готова помочь Алисе, и она законно ответит на любые вопросы. Тем не менее, она может ответить только да или нет.
2. Алиса спросит Мэлори один раз. Мэлори не может повлиять на Алису, чтобы она снова задала тот же вопрос.Хотя в будущем Алиса может сама спросить о других датах (например, о дне рождения Боба).
3. Алисе не нужно и не хочется знать даты рождения всех в классе. Она хотела бы получить ответ от Мэлори, задав единственный вопрос.

Довольно простой способ решить эту проблему — применить хэш. Алиса хэширует свой день рождения и передает эту информацию Мэлори, в то же время прося ее хэшировать дни рождения всех людей, которых она знает, и сообщить ей, если они совпадают. Проблема в том, что Мэлори, который хотел бы знать день рождения Алисы, может перечислить все возможные даты (поскольку энтропия ввода мала) и проверить одну за другой, совпадают ли какие-либо с тем, о чем спрашивала Алиса. Я хотел бы устранить эту угрозу.

Я подумал о применении сопоставления «один ко многим» к дню рождения. Поскольку одна дата может быть представлена ​​несколькими значениями, атака перечислением становится невозможной. Первая проблема заключается в том, что я не вижу простого способа позволить Мэлори провести элементарное математическое сравнение с ее набором дат. Вторая проблема заключается в том, что если такое сравнение может быть выполнено, Мэлори по-прежнему может создать новый набор и снова выполнить операцию поиска (что фактически приводит к атаке перечислением). Таким образом, сопоставление «один ко многим», которое применяет Алиса, должно быть параметризовано уникальной характеристикой множества, в котором Мэлори будет искать.

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

Вы описываете проблему 1 из $n$ Незаметный перевод с $n=366$ если требуется, чтобы Алиса не получала посторонней информации. Методы Колесникова и др. в их статье «Эффективный пакетный забывчивый PRF с применением к частному пересечению множеств» дает представление о том, что возможно.

Если для Алисы приемлемо получение дополнительной информации, то проблема заключается в одном из поиск частной информации. Обзорная статья Островского и Скита «Обзор поиска конфиденциальной информации в одной базе данных: методы и приложения» обеспечивает хороший обзор.

Второй, более простой подход, благодаря комментарию @Mikero:

Алиса выбирает равномерно случайный закрытый ключ $b$. У Алисы день рождения $к$й день года. Алиса отправляет $A = bH_p(k)$ Мэлори, где функция $H_p()$ означает хэшировать ввод и интерпретировать результат как точку EC.

Мэлори выбирает равномерно случайный закрытый ключ $е$. У Мэлори есть функция $F_e(i)$ который выводит $eH_p(i)$ если хотя бы один человек родился в этот день года, а в противном случае выводит случайно выбранный балл ЕС.

Для каждого значения $я$ такой, что $0\leq i \leq 365$, Мэлори посылает $F_e(i)$ Алисе. Кроме того, Мэлори посылает $Q = eA$ Алисе.

Алиса вычисляет $Z = b^{-1}Q == b^{-1}eA == b^{-1}ebH_p(k) == eH_p(k)$.

Затем Алиса проверяет, $Z$ соответствует любому из 366 выходов $F_e(i)$ который Мэлори отправил Алисе. Если есть совпадение, Алиса делит день рождения с кем-то еще.

Объяснение: Мы создали "1-OPRF", что означает не обращающую внимания псевдослучайную функцию, которую Алиса может запросить один раз с помощью Мэлори вслепую, но которую Мэлори может запрашивать много раз.

PRF просто Мэлори ослепляет точку EC $H_p(i)$ (куда $H_p(i)$ представляет определенный день $я$ года в качестве балла ЕС), со своим закрытым ключом $е$, вычислив $eH_p(i)$. Из-за проблемы дискретного журнала эллиптической кривой ни один наблюдатель (включая Алису) не может предсказать результат $eH_p(i)$ для любой $я$ без знания секрета $е$. Это означает, что если в определенный день никто не родился, Алиса не может сказать, что Мэлори прислал случайную точку EC вместо реального результата PRF, потому что результат PRF непредсказуем для Алисы.

Алиса ослепляет свой ввод в PRF, выбирая ослепляющий фактор. $b$ и отправка $bH_p(k)$ Мэлори вместо отправки (и, таким образом, раскрытия) $к$. Алиса снимает ослепление ответа, обращая умножение с помощью $b$, и, таким образом, может запрашивать PRF, не зная Мэлори о входных данных, которые использует Алиса.

Следствием этого является то, что Мэлори отправил Алисе список баллов EC, который включает только истинный результат PRF для тех дней в году, когда родился хотя бы еще один человек. Кроме того, Алиса может вслепую запросить в PRF выходные данные о своем конкретном дне рождения и может увидеть, появляется ли этот результат в списке возможных выходных данных PRF, отправленных ей Мэлори.

Мэлори не научился $к$, и Алиса не может узнать ничего, кроме того, совпадает ли ее день рождения хотя бы с одним человеком.

Один подход заключается в том, чтобы сделать 1 из n забывчивая передача. Мэлори отправит Алисе список из 366 зашифрованных логических значений (чтобы учесть дни рождения 29 февраля), где каждое логическое значение будет означать, есть ли у кого-либо день рождения в этот день года.Алиса сможет расшифровать только одно из 366 логических значений и, таким образом, сможет узнать только, есть ли у кого-либо еще день рождения в этот день года.

Статья в Википедии, на которую я ссылался в абзаце выше, ссылается на несколько подходов к реализации для достижения переноса без внимания 1 из n. Вот один из подходов, который я придумал только что (благодаря @IlmariKaronen за очень элегантное улучшение):

Алиса родилась в день $к$ года, где $0\leq k\leq 365$. Алиса отправляет открытый ключ $P = xG-kH$ в Мэлори, где $х$ является равномерно случайным скалярным закрытым ключом. $Ч$ рассчитывается как $H = H_p(G)$, где функция $H_p()$ означает хэшировать значение и интерпретировать результат как точку EC. Выбор $Ч$ таким образом означает дискретный журнал $Ч$ w.r.t. $G$ непознаваемо, т. $ч$ не может быть известно так, что $H==hG$.

Мэлори вычисляет 366 открытых ключей $\{Q\}$ формы $Q_i=P+iH$ для всех значений $я$ куда $0\leq i\leq 365$.

Закрытый ключ, соответствующий каждому открытому ключу $Q_i$ будет $q_i == x - kh + ih == x+(i-k)h$.

Поскольку мы уже продемонстрировали, что $ч$ непознаваемо, это означает, что $q_i$ будут известны Алисе только тогда, когда $я==к$, в таком случае $q_k$ будет равно $х$.

Таким образом, Мэлори вычислит 366 открытых ключей, для которых Мэлори может быть уверен, что Алиса может знать только закрытый ключ, соответствующий одному из них.

На каждый день года $я$, Мэлори использует схему Эль-Гамаля следующим образом: Мэлори выбирает равномерно случайный скаляр $e_i$, и предоставляет Алисе пару $(E_i, F_i)$ куда $E_i = e_iG$, $F_i = e_iQ_i + H_p(v_i)$ и где $v_i$ будет указано как $0$ если ни у кого нет дня рождения в этот день года, или как $1$ если хотя бы у одного человека день рождения в этот день года.

Расшифровать $v_k$, Алиса вычисляет $V_k = F_k - xE_k$. Затем Алиса проверяет, $V_k\overset{?}{=}H_p(0)$ или же $V_k\overset{?}{=}H_p(1)$, и, таким образом, знает, если $v_k$ является $0$ или же $1$. Это работает, потому что $q_k==x$ и $Q_k==xG$, и другие $xE_k==x\cdot e_kG==e_k\cdot xG==e_kQ_k$.

Алиса сможет определить, только если кто-то еще родился в этот день. $к$ года, и Мэлори не сможет определить $к$.

Существует новый поиск частной информации с полностью гомоморфными системами,

• 2014 Эффективный по пропускной способности PIR от NTRU Яркин Дорез, Б. Сунар, Гейт Хаммури

Это частная схема шифрования, которая может использовать значение индекса $я$ из массива на получестном сервере. Сервер ничего не узнает и возвращает только значение по индексу $я$. Мы можем изменить это как;

1. Мэллори шифрует все существующие дни рождения $b_i$, $0 \leq i \leq 366 $ с открытым ключом FHE Алисы. (Шифрование $366\cdot 8$ биты, не обязательно все дни, достаточно существующих дней рождения и это экономит место в больших наборах.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, b_i)$$

   Если мы используем побитовые (HLibe, TFHE), то каждый $c_i$ размер массива 8.

2. Алиса посылает свой день рождения $А$ зашифрована ее открытым ключом для Мэллори (шифрование 8-битное).

   $$a = \operatorname{FHE-Enc}(A_{pub}, A)$$

3. Мэллори казнит Схема равенства FHE в каждый зашифрованный день рождения

   $$t_i = \operatorname{FHE-Compare}(A_{pub}, c_i,a)$$

4. Мэллори ИЛИ ЖЕ результаты с FHE с использованием подхода бинарного дерева для уменьшения глубины схемы (возможно с суммированием вместо ИЛИ ЖЕ) и вернуть результат обратно Алисе.

   $$o = \operatorname{FHE-OrAll}(A_{pub}, [t_0,\ldots,t_n])$$

5. Алиса расшифровывает полученное кусочек со своим закрытым ключом;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • если $б=1$ тогда есть хотя бы один студент с датой $А$
   • если $б=0$ тогда нет студента с датой $А$.

Что гарантируется;

1. Мэллори не может узнать, что такое запрошенные данные $А$ поскольку он зашифрован с помощью FHE, существует семантическая безопасность.
2. Мэллори не может вывести запрошенные данные из результата по той же причине, что и выше; от $(А,о)$.
3. Схема не раскрывает ничего о внутренностях данных, кроме того, какая функция вычисляется — схема вычисляет наличие данных, не раскрывая результат.
4. Алиса узнает только о существовании дня рождения и не более того! Алиса получает только один бит $b$, есть или нет. Это не возвращает количество одинаковых дней рождения.
5. Алиса запрашивает только один раз.
6. Мэллори отправляет шифрование только в один бит $b$! Таким образом, довольно эффективная схема.

1. Мэллори подготавливает битовый массив размером 366, инициализированный нулем. $$B = [b_0,b_1,\ldots,b_{366}] = 0$$

2. Мэллори установил существующие дни рождения на 1. Нравится; $$B = [0,0,1,\ldots,0] $$

3. Мэллори шифрует битовый массив открытым ключом Алисы (открытый ключ FHE) и получает еще один массив размером 366.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, B[i]) \;\; \текст{для}\; 0\leq i \leq 366 $$

4. Алиса подготавливает еще один битовый массив размером 366, где только ее день рождения установлен на 1, а остальные установлены на 0. $$A = [0,0,0,\ldots,1,\ldots,0] $$

5. Аналогично Мэллори, Алиса получает массив со своим открытым ключом и отправляет полученный массив Мэллори.

   $$a_i = \operatorname{FHE-Enc}(A_{pub}, A[i]) \;\; \текст{для}\; 0\leq i \leq 366 $$

6. Мэллори разумно выполняет компонент операции FHE-AND на зашифрованных массивах. $$c_i = \operatorname{FHE-И}(A_{pub}, A[i], B[i])$$

7. Мэллори ИЛИ ЖЕ бит результирующего массива и вернуть результат обратно Алисе.

   $$b = \operatorname{FHE-OrAll}(A_{pub}, [c_0,\ldots,c_{366}])$$

8. Алиса расшифровывает полученное кусочек со своим закрытым ключом;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • если $б=1$ тогда есть хотя бы один студент с датой $А$
   • если $б=0$ тогда нет студента с датой $А$.

Что гарантируется;

1. То же, что и основная схема.
2. На этот раз вместо 9-битного шифрования Алиса шифрует 366-битное (~40-кратное увеличение начальной стоимости/времени отправки).
3. Мэллори, с другой стороны, получил много улучшений по времени и памяти.
   1. Нет необходимости в тяжелой операции FHE-равенства.
   2. Размер хранимого зашифрованного текста был уменьшен на ~40.
4. Результат, с другой стороны, по-прежнему является 1-битным шифрованием.
5. Эта схема экономит много времени на процессе.