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

Рассмотрим услугу $S$ который получает хэши документов от ряда поставщиков. Если два хэша совпадают, он уведомляет поставщиков. Мы не хотим, чтобы кто-либо из службы мог идентифицировать документы. Однако объем документа на самом деле довольно мал (~миллиарды), поэтому возможна атака по словарю.

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

Возможен ли другой путь?

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

Поэтому, чтобы избежать этой атаки, между провайдерами должен быть какой-то секрет, который неизвестен центральной службе.

Обратите внимание, что для 10 миллиардов 128-битных хэшей потребуется всего 150 ГБ дискового пространства. Поэтому вы можете решить, что провайдерам лучше просто делиться своими хэшами напрямую друг с другом. Вы можете использовать одуванчик протокола, чтобы при объявлении новых хэшей провайдер, первоначально объявляющий какой-либо конкретный хеш, скрывал свою личность.

Если клиенты могут совместно использовать секретный ключ, мы можем использовать полностью гомоморфные схемы для достижения этой цели. Позволять $k_{prv}$ закрытый ключ клиентов и $k_{паб}$ это открытый ключ, который есть у сервера.

• Всякий раз, когда хэш $h_i$ отправляется на сервер в зашифрованном виде $e_i =E(k_{pub},h_i)$ (предпочтительно TFHE) клиентом.
• Сервер использует Схема равенства FHE $С$ который возвращает зашифрованный $Е(1)$ если они равны.

    разрешение = E (k_pub, 0)
    для каждого E(h_j) в диапазоне (1,i-1):
         cur = C(h_i, h_j,k_pub) //сравнить
         res = FHE_Add(res,cur,k_pub) // накапливаем результат.

   вернуть разрешение

• Теперь сервер отправляет $res$ как ответ клиенту(ам).

• Клиент расшифровывает и проверяет, что

  • если $рез=0$ это означает, что хэш не выходит на сервер.
  • если $res\neq 0$ затем хэш на сервере.

Примечания:

• Это похоже на то, что Монитор паролей Microsoft.
• Клиенты могут использовать стандартный метод открытого ключа для совместного использования $k_{prv}$ и $k_{паб}$
• Этот протокол требует, чтобы сервер получестный.
• На сервере есть слепое вычисление что они ничего не узнают из зашифрованных, вычисленных значений и, однако, из результата;
• Если клиент отправляет новые данные для загрузки, не спрашивая о существовании, сервер может сделать вывод, что предыдущего хэша не существовало.