使用 Pallier 密碼系統後如何獲得前 10 位數字
假設我
Integers使用 pallier 密碼系統加密了 1000。因為每次我使用 pallier 加密一個數字時，我都使用
rZ* 中的隨機元素，所以加密的數字不再按順序排列，即：我們有 2<3 但 Enc(2) 與 pallier 並不一定意味著它是 < 然後是 Enc(3) 與 pallier。那麼， 當數字被加密時，如何
Integers從這 1000 個數字中獲得前 10 個最大的數字呢？Integers
那麼， 當數字被加密時，如何
Integers從這 1000 個數字中獲得前 10 個最大的數字呢？Integers這很容易; 用私鑰解密，然後挑出前10個明文…
如果您沒有私鑰（並且無法與擁有私鑰的人互動），那麼我們希望這是不可能的。我說“希望”，因為如果可能的話，那麼您可以僅使用公鑰來推斷 Paillier 密文的內容（因此，Paillier 將是不安全的）。
假設我們確實有辦法從 1000 人中找出前 10 名；這是我們如何測試密文 $ C $ 看看它是否是明文 $ P $ 是 $ > k $ 或者 $ < k $ （對於任意整數 $ k $ ); 我們將加密值 $ k $ 999次，並給出這999個密文，加上密文 $ C $ 我們正在測試尋找前 10 名的方法——如果我們試圖推斷的明文是 $ P > k $ ， 然後 $ C $ 將是10個之一；如果 $ P < k $ ， 它不會。
使用該技術，我們可以進行二分搜尋以減少 $ P $ 到兩個值的範圍 $ k, k+1 $ ; 然後我們可以同態添加 $ C $ 到自己，然後最後一次執行上述測試，看看是否 $ 2P $ 大於或小於 $ 2k+1 $ - 這給了我們最終的答案。
我們希望有人無法做到這一點，因此我們希望您要求解決的問題是不可行的。