置換向量

考慮我們有兩個向量 $ v_1, v_2 $ 大小的 $ n $ , 每個向量包含 $ n $ 元素。我們將向量置換為： $ \pi (k_1,v_1), \pi (k_2,v_2) $ . 在哪裡 $ \pi (k_i,v) $ 表示向量的排列， $ v $ , 使用鍵 $ k_i $ .

我使用上述技術（置換）來隱藏每個向量中元素的原始位置。我想將這兩個排列後的向量交給惡意伺服器，以進行一些計算。因此，我需要向它揭示兩個置換向量之間的關係；例如，排列中的位置 2 $ v_1 $ 與 permuted 中的第 6 位有關 $ v_2 $ .

問題：給定兩個置換向量， $ \pi (k_1,v_1), \pi (k_2,v_2) $ ，以及它們之間的映射，對手可以了解任一向量中元素的原始位置。

假設機率分佈 $ \pi_{k_1} $ 和 $ \pi_{k_2} $ 都是一致的（也就是說，每個排列可以採用任何特定設置的機率 $ 1/n! $ )，那麼不，對手沒有足夠的資訊來了解有關原始位置的任何資訊。即使我們假設對手可以執行無限計算，這仍然是正確的，並且我們不需要對兩者之間的任何可能相關性做出任何假設 $ \pi_{k_1} $ 和 $ \pi_{k_2} $

對於任何可能的排列 $ v_1 $ , 存在唯一排列 $ \pi_{k_1} $ 和一個獨特的排列 $ \pi_{k_2} $ 這與這種可能性是一致的。因為（根據假設），這種選擇 $ \pi_{k_1} $ 和 $ \pi_{k_2} $ 與任何其他可能的選擇一樣可能，攻擊者沒有獲得關於這種排列是否 $ v_1 $ 比任何其他排列的可能性更大或更小。

通過對稱性，這也適用於任何可能的排列 $ v_2 $ .

引用自：https://crypto.stackexchange.com/questions/25259