保序加密如何工作？
顯然，保序加密 (OPE) 是一種加密數據的方法，因此可以在不解密加密項目的情況下對加密項目進行有效的不等式比較。
我最近在各個地方（包括這裡）遇到了這個術語，但我不知道這種加密方案應該如何工作。我能想到的任何允許對加密數據進行此類比較的明顯方法都會導致災難性的安全故障。
當然，我認為與傳統加密相比，OPE 必須涉及某種安全權衡，但鑑於它似乎正在被積極研究和使用，它似乎必須有可能以一種至少保留一定程度有用的方式來實現安全。我只是不明白怎麼做。
鑑於快速的 Google 搜尋沒有找到任何方便的 Wikipedia 文章或其他流行的 OPE 總結，我想在深入研究學術文獻之前，我會嘗試在這裡詢問一個。（在最壞的情況下，我可能會在以後嘗試回答我自己的問題，如果沒有其他人能打敗我。）
所以，總而言之，我的問題是：保序加密是如何工作的，它提供了哪些安全屬性？
在過去的幾周里，我已經非常熟悉該領域的最新工作。我還按照 Boldyreva 等人在“保序對稱加密”中提出的算法建構了一個原型保序加密方案。我將嘗試解釋我剛剛實現的方法，這需要對離散機率和超幾何分佈有所了解。
讓 $ M $ 和 $ N $ 是兩個正整數，使得 $ M < N $ . 首先考慮一個隨機保序單射函式 $ [M] $ 到 $ [N] $ ， 在哪裡 $ [M] = {1, 2, … , M} $ 和 $ [N] = {1, 2, … , N} $ . 現在，選擇 $ M $ 要點 $ [N] $ 隨機並按順序排列。我們的單射函式 $ f:[M] \to [N] $ 就是這個有序集合。加密 $ i \in [M] $ ，只需輸出 $ i $ - 此列表的第一個元素。顯然我們不能將其用作真正的加密方案，我們可能需要隨機生成數十億個數字！那麼我們該如何進行呢？
我們注意到我們不需要提前完成整個函式。如果我們能想出一種方法，只在我們需要它作為密文時生成有序集合中的一個元素，那我們就太棒了。這稱為延遲採樣函式。為了對我們提出的函式進行惰性採樣，我們首先需要稍微不同地看待範圍空間。
讓我們堅持使用我們的隨機保序單射函式 $ f $ ，我們將其視為範圍內元素的有序列表。如果範圍內的元素在列表中，則將其視為“已標記”，如果不在，則將其視為“未標記”。現在把範圍內的所有元素，標記的和未標記的，想像成一個巨大的箱子裡的球。如果我們在沒有替換的情況下抽出球，則數字 $ x $ 我們繪製的“標記”球 $ y $ 樣本可以通過超幾何分佈來表徵。HGD 有 PMF
$$ \frac{\binom{y}{x} \binom{N-y}{M-x}}{\binom{N}{M}} $$ 如果您不知道 PMF 是什麼，請不要擔心。我們真正需要了解的是 OPF 和 HGD 之間的聯繫，即我們可以通過將範圍點視為 a標記球數為的超幾何實驗 $ M $ 和未標記的球是 $ N-M $ . 同樣重要的是要知道，我們可以有效且確定性地對 HGD 進行採樣，即給定 $ y $ , $ M $ , $ N $ , 和一些隨機硬幣 $ cc $ 我們總是可以生成一個 $ x $ 描述了我們大小樣本中標記的球的數量 $ y $ .
我們很接近，我保證。我們已經奠定了基礎，我們只需要弄清楚如何從中獲得加密方案。
我們的加密方案很自然地遵循上述內容。給定一個明文 $ m \in [M] $ 和一把鑰匙 $ k $ 我們可以懶惰地對 OPF 進行採樣並生成密文 $ n \in [N] $ 通過遞歸搜尋域和範圍，如下所示：
從整個域開始 $ [M] $ 和範圍 $ [N] $ . 稱呼 $ y \leftarrow \frac{N}{2} $ 我們的範圍差距。現在使用我們的密鑰 $ k $ 我們生成一些偽隨機硬幣並將它們與我們的 HGD 採樣程序一起 $ y $ , $ M $ ， 和 $ N $ . 這給了我們一個 $ x \le y $ 描述了我們的保序函式的點數小於 $ y $ . 呼叫這個 $ x $ 我們的領域差距。現在因為 $ m $ -我們的 OPF 的第一個點是密文 $ m $ , 我們知道如果 $ m \lt x $ 我們需要在域中小於或等於的點上遞歸 $ x $ 並且小於或等於 $ y $ . 如果 $ x \lt m $ ，我們在域的點上遞歸大於 $ x $ 和 $ y $ . 當我們的域只剩下一個點時，我們將擁有一組點作為我們的範圍，我們的密文可以在其中駐留。選擇這個集合的一個點並輸出它。
所以畢竟，這只是一個花哨的二分搜尋？？？有點，是的。如果您想了解所有雜亂的細節以及如何確保其安全，請閱讀原始 OPE 論文或查看 CryptDB 實現。我的 java 實現也將很快開源，所以你也可以檢查一下。
保序加密有幾個注意事項。要了解所有詳細資訊，請閱讀 Alexandra Boldyreva、Nathan Chenette 和 Adam O’Neill 的*《Order-Preserving Encryption Revisited：改進的安全分析和替代解決方案*》 （在 CRYPTO 2011 會議記錄中，或此處的全文）的後續文章。它分析隨機 OPF 的安全性並描述其洩漏特徵。他們最明顯的問題結果與對手猜測密文的底層明文在明文空間中的位置的能力有關。直覺地說，**某些攻擊者可以在給定密文的情況下學習明文的一半。**對於某些應用程序，這種以安全換取功能的交易是可以接受的，但無論如何，重要的是要知道在使用這些方案時會得到什麼。
如果您想在上面澄清某些內容，請發表評論，我將嘗試進行有說服力的編輯。