不經意的多項式評估和編碼有效載荷
我正在嘗試解析這篇論文。我想我確實理解了這種基於不經意多項式評估的私有集合交集的一般概念。我能夠基於直接的指數 El Gamal 加密生成一個可行的原型。
協議的逐點介紹可以在 4.2 PM Semi-Honest Protocol 一節中找到。第 2 步中的那句話讓我印象深刻。它說
…（也可以通過計算 Enc(rP(y) + (y|py)) 來加密一些額外的有效載荷數據 py。如果 y 在交集中，C 會獲得 py。）
我變得安靜興奮，因為這就是我要找的東西，但是符號“|” 沒有得到解釋，我找不到它應該是什麼。假設這個想法是在根 P(y) 的情況下計算為 0，因此 ENC(rP(y) + y) = ENC(y)。這意味著我對添加的“y”值所做的任何事情都會阻止 C（客戶端）找到與她自己的私有集匹配的值。
這是我不知道的 Paillier 加密的一些特殊屬性（我還不太了解這個加密系統），還是我可以使用指數 El Gamal 加密系統來處理它？
該欄只是字元串的連接。只要您願意將事物視為位串和組元素，這裡使用的加密方案就沒有什麼特別之處。
沒有這些有效載荷，協議的思想如下。Bob 發送一組 $ Z $ 的密文。愛麗絲將她的輸出計算為 $ { \mathsf{Dec}(z) \mid z \in Z } \cap X $ . Alice & Bob 共享的項目將由 Alice 以這種方式輸出。Alice 和 Bob 不共享的項目將產生一個隨機值 $ \mathsf{Dec}(z) $ ，因此它們被 Alice 輸出的可能性可以忽略不計。
現在，使用有效載荷，假設各方正在對以下項目進行 PSI $ \ell $ 位長。現在愛麗絲將計算她的輸出為 $ { \mbox{first $\ell$ bits of } \mathsf{Dec}(z) \mid z \in Z } \cap X $ . 仍然存在這樣的情況，即任何未由各方共享的項目，Alice 輸出的可能性微乎其微（其第一個輸出的可能性微乎其微） $ \ell $ 位匹配 Alice 的一項）。但是您可以使用剩餘的位來編碼每個項目的有效負載。
這假設 ElGamal/Paillier 組大到足以編碼這個額外長度的字元串。但不失一般性，您總是可以：
- 縮短項目：就通用雜湊函式達成一致，並對項目的雜湊值進行 PSI。
- 縮短有效載荷：make $ p_y $ 用於對稱密鑰加密的短密鑰，並使用此密鑰發送您的實際（可能是巨大的）有效負載的加密。
**編輯：**哦，剛剛看到你正在使用指數El-Gamal。您將不得不在語法上而不是概念上改變事物。例如，讓 $ V $ 是按位表示為 item+payload 字元串的組元素 $ y | p_y $ . 現在 $ V $ 有一些離散的日誌（存在但很難計算） $ V = g^v $ . 我聲稱 Bob 應該加密 $ rP(y) + v $ 在指數中。幸運的是你不必知道 $ v $ 要做到這一點，只需獲得一個 ElGamal 加密 $ g^{rP(y)} $ 以你已經知道的方式，並使用它的同態屬性乘以 $ V $ , 做一個標準的 ElGamal 加密 $ g^{rP(y)} \cdot V $ . 當愛麗絲解密時，她要麼看到一個隨機的東西，要麼她得到群元素 $ V $ . 而不是試圖推理 $ V $ 的離散對數，Alice 可以只看位表示 $ V $ 並通過是否 $ y $ 是前綴。
這一切的原因是有效載荷無法在指數中傳達（Alice 永遠無法取回它）。相反，它必須出現在她的標準 ElGamal 解密結果中。在指數 ElGamal 中，您可以測試解密是否等於您已經知道的值（在指數中），您無法解密以學習對您來說新的指數中的值。