Private Set Membership 的實際實現
問題陳述
想像一下你有一個集合（沒有重複的元素），例如
S1 = {'a', 'b', 'c'}.您希望與另一方（可能與您擁有預共享密鑰）共享此集合的私有（理想情況下是小尺寸和完整性保護）表示，他們可以驗證（是或否）他們選擇的某些元素eg
'b'是集合的一部分S1。可以用來解決這個問題的最簡單的密碼原語組合是什麼？
到目前為止的路線
由於大小限制，散列集合似乎是理想的（而不是簡單地加密）。
如果我們希望進行不透明的成員資格檢查，可能需要某種同態加密。
我已經閱讀了 Private-Set-Intersection 和 Private-Set-Membership，但是我發現的實現並不是最小的，並且具有其他不可取的“廚房水槽”功能。
到目前為止的一些閱讀
你只需要一個不經意的PRF。Alice 計算並發送Fķ(X) $ F_k(x) $ 對所有人X∈小號 $ x \in S $ ， 在哪裡F $ F $ 是一個PRF。Alice 和 Bob 使用 OPRF 協議讓 Bob 學習Fķ(是) $ F_k(y) $ 為了一個值是 $ y $ 他的選擇。如果是∈小號 $ y \in S $ 然後 Bob 將看到與 Alice 發送的值匹配。如果是∉小號 $ y \not\in S $ 那麼偽隨機性F $ F $ 暗示{Fķ(X)∣X∈小號} $ { F_k(x) \mid x \in S } $ 即使給定，所有看起來都是隨機的Fķ(是) $ F_k(y) $ . 換句話說，這些值不會洩露任何關於X $ x $ 在小號 $ S $ .
PRF 有一個簡單的半誠實 OPRF 協議Fķ(X)=H(X)ķ $ F_k(x) = H(x)^k $ ， 在哪裡H $ H $ 是一個隨機預言機。它是這樣工作的：
- Bob 隨機選擇r $ r $ 並發送是=H(是)r $ Y = H(y)^r $ 給愛麗絲。
- 愛麗絲發送從=是ķ=H(是)rķ $ Z = Y^k = H(y)^{rk} $ 給鮑勃。
- Bob 計算輸出從1/r=H(是)ķ=Fķ(是) $ Z^{1/r} = H(y)^k = F_k(y) $ .
這是我一直在努力的事情。
我希望下面的“小”比下面的要小得多。但這適用於您的一組二進製字元串小號 $ S $ , 加密雜湊H(X) $ H(x) $ , 和預共享密鑰ķ $ k $ .
H(小號)=種類{H(X)|X∈小號} $ H(S)=\text{sort} {H(x) | x \in S} $ . 稱其為公眾證人小號 $ S $ . 您可以通過將隨機散列包含到給定長度模數來隱藏集合的大小。這將是一個沒有誠信的公開證人，但給出了基本的想法。
假設大小X $ x $ 通常遠大於H(X) $ H(x) $ , 證人的代表H(小號) $ H(S) $ 為了小號 $ S $ 與表示相比很小小號 $ S $ .
如果您想將此限制為具有預共享對稱密鑰 k 的使用者：（我使用+ $ + $ 用於附加以區別於集合“這樣”）
H2(ķ+小號)=種類{H(ķ+H(ķ+X))|X∈小號} $ H^2(k+S)=\text{sort} {H(k+H(k+x)) | x \in S} $ . 附加密鑰校驗和以進行完整性檢查。
S的見證人:H2(ķ+小號)+H(ķ+H2(ķ+小號)) $ \text{witness for S}: H^2(k+S) + H(k+H^2(k+S)) $
再次，隱藏大小小號 $ S $ 您始終可以將隨機散列添加到最大大小或（不完美地）添加到大小模數。
檢查成員資格：發送(n,H(ķ+n)⨁H(ķ+X)) $ (n,H(k+n) \bigoplus H(k+x)) $ 在哪裡n $ n $ 是一個遞增的數字（它可能是隱含的，例如時間戳）。收件人可以發現H(ķ+X) $ H(k+x) $ 然後計算H(ķ+H(ķ+X)) $ H(k+H(k+x)) $ 看看它是否在見證集中。