Практические реализации членства в частном наборе

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

Представьте, что у вас есть набор (без повторяющихся элементов), например. S1 = {'а', 'б', 'с'}.

Вы хотите поделиться частным (и в идеале небольшим по размеру и с защитой целостности) представлением этого набора с другой стороной (у которой могут быть предварительно общие ключи с вами), где они могут проверить (да или нет), если какой-либо элемент по их выбору например 'б' является частью набора S1.

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

Направления до сих пор

Казалось бы, хеширование набора было бы идеальным (в отличие от простого шифрования) из-за ограничений по размеру.

Если мы хотим выполнять непрозрачные проверки членства, вероятно, потребуется какое-то гомоморфное шифрование.

Я читал о Private-Set-Intersection и Private-Set-Membership, однако найденные мной реализации не минимальны и имеют другие «кухонные» функции, которые нежелательны.

Немного чтения до сих пор

• https://engineering.fb.com/2019/03/01/security/homomorphic-hashing/ (https://eprint.iacr.org/2019/227.pdf)
• https://github.com/google/частное-членство
• Более быстрое пересечение частного набора на основе Расширение ОТ (pdf)
• Эффективное приватное сопоставление и пересечение множеств (pdf)
• Более быстрое пересечение несбалансированного множества (pdf)

Вам просто нужен забывчивый PRF. Алиса вычисляет и отправляет $F_k(x)$ для всех $x \в S$, куда $F$ является ПРФ. Алиса и Боб используют протокол OPRF, чтобы позволить Бобу учиться $F_k(у)$ по стоимости $у$ по его выбору. Если $y \в S$ тогда Боб увидит совпадение со значениями, отправленными Алисой. Если $у\не\в S$ то псевдослучайность $F$ подразумевает, что $\{ F_k(x) \mid x \in S \}$ все выглядит случайным даже учитывая $F_k(у)$. Другими словами, эти значения ничего не пропускают о конкретных значениях $х$ в $S$.

Существует простой получестный протокол OPRF для PRF. $F_k(x) = H(x)^k$, куда $Ч$ это случайный оракул. Это работает следующим образом:

• Боб выбирает случайным образом $г$ и отправляет $Y = H(y)^r$ Алисе.
• Алиса отправляет $Z = Y^k = H(y)^{rk}$ к Бобу.
• Боб вычисляет вывод $Z^{1/r} = H(y)^k = F_k(y)$.

Защищенные от вредоносного ПО OPRF ненамного дороже. Вы можете найти несколько здесь и здесь.

Это то, над чем я работаю.

Я хотел бы, чтобы «маленький» ниже был намного меньше, чем то, что следует. Но это будет работать для ваших целей для набора двоичных строк $S$, криптографический хэш $Ч(х)$и общий ключ $к$.

$H(S)=\text{сортировка} \{H(x) | х \в S\}$. Назовите это публичным свидетелем $S$. Вы можете скрыть размер набора, включив случайные хэши в заданный модуль длины. Это будет публичный свидетель, не честный, но дающий основную идею.

Предполагая размер $х$ обычно намного больше, чем $Ч(х)$, представление свидетеля $Ч(С)$ за $S$ мало по сравнению с представлением для $S$.

Если вы хотите ограничить это теми, у кого есть предварительно общий симметричный ключ k: (я использую $+$ для добавления, чтобы отличить от набора «такой, что»)

$H^2(k+S)=\text{sort} \{H(k+H(k+x)) | х \в S\}$. Добавьте контрольную сумму с ключом для проверки целостности.

$\text{свидетель для S}: H^2(k+S) + H(k+H^2(k+S))$

Опять же, чтобы скрыть размер $S$ вы всегда можете добавить случайные хэши к максимальному размеру или (несовершенно) к модулю размера.

Проверка членства: отправить $(n,H(k+n) \bigoplus H(k+x))$ куда $n$ является возрастающим числом (может подразумеваться, например, как метка времени). Получатель может раскрыть $Ч(к+х)$ а затем вычислить $Ч(к+Н(к+х))$ чтобы увидеть, есть ли он в наборе свидетелей.