小區間內的單向排列？
我想知道我們知道哪些具體的可計算函式
- 是可參數化大小的整數區間上的****排列 $ s $ , 對於相對較小的 $ s $ 大約開始 $ 2^{64} $ , 也許 $ 2^{256} $ ; 不失一般性，我們將區間轉換為 $ {0\dots s-1} $ ;
- 在前向方向上容易計算，但在後向方向上難以計算；我有興趣最大化品質因數 $ M $ 定義為從隨機點開始反向計算的預期工作量與正向計算的預期工作量之比（任何必要的預計算從 $ s $ 包括在上述工作量中）。
明顯的評論：優點 $ M $ 不能超過 $ s/2 $ ，這對應於通過強制正向計算逆排列。但是，我會滿足於更少的優點，並想知道有什麼限制，無論是理論上的還是實踐上的。
有什麼想法、想法或參考嗎？
注意：我想要任何一個排列 $ s\ge2^{64} $ , 但對一些輕度稀疏的值子集的限制 $ s $ 就足夠了，因為眾所周知的技術允許有效地轉換排列 $ \widehat P $ 在一定大小的區間內 $ \widehat s $ 略大於 $ s $ 成所需的排列 $ P $ 在一定大小的區間內 $ s $ ： 為了 $ x\in{0\dots s-1} $ 我們獲得 $ P(x) $ 作為第一個 $ y_j<s $ 和 $ y_0=\widehat P(x) $ 和 $ y_{j+1}=\widehat P(y_j) $ . 優點並沒有減少太多： $ M\ge s/\widehat s\cdot\widehat M $ 至少在啟發式上是成立的，如果我們忽略了尋找合適的工作所涉及的工作 $ \widehat s $ 從 $ s $ .
旁注（不是問題的一部分）：我實際上想要一個根據某些鍵的排列系列 $ K $ 並且與隨機排列沒有區別，即使在 $ K $ 可用，如之前的問題一樣；但這很容易從排列中獲得 $ P $ 與目前問題一樣，以及快速鍵控排列（即密碼） $ C_K $ 超過 $ {0\dots s-1} $ ，通過考慮 $ C_K\circ P $ ; 我們可以構造 $ C_K $ 從一個分組密碼 $ \lceil\log_2s\rceil $ 位塊，以及上述技術。我們也可以拉伸品質因數 $ M $ 即使當 $ K $ 可用，通過迭代 $ C_{K_j}\circ P_j $ 使用派生鍵 $ {K_j} $ 考慮到正向的性能限制，盡可能多地使用（略有不同 $ P_j $ ，只要需要保持優點；並且可能更輕 $ C_{K_j} $ ).
我目前的狀態（由於Ricky Demer的評論而有所改善）：
一個眾所周知的單向排列系列 $ P $ 是基於離散對數問題的難度 $ \mathbb Z_p $ . 如果 $ p=2\cdot s+3 $ 是素數，並且 $ (p-1)/2=s+1 $ 是素數，那麼 $ \forall g\in{2\dots p-2} $ ,
$$ P:x\mapsto \min\big((g^{x+1}\bmod p),p-(g^{x+1}\bmod p)\big)-2 $$ 是一個排列 $ {0\dots s-1} $ 並且很難在某種程度上反轉。然而GNFS和指數演算方法適用，因此優點 $ M $ 對於小 $ s $ 只是馬馬虎虎。我歡迎將價值的數字估計作為 $ s $ . 注：因數 $ 2 $ 在 $ p=2\cdot s+3 $ 給給定的功績帶來可喜的增長 $ s $ . 這裡有各種偏移量，以使每個 $ s $ 價值觀 $ P(x) $ 可能依賴於 $ g $ ，這是一個不錯的選擇（它允許選擇 $ g $ 充當小鍵或實例化函式族中成員之一的參數）。不需要檢查是否 $ g $ 是一個生成器（但有人建議它可能會以某種方式影響如何最好地反轉排列）。
另一種選擇可能是使用一個橢圓曲線組，該組可以有效地映射到一個區間，例如在這個答案中；然而，這似乎只適用於一些特殊的曲線，我並不完全清楚。我歡迎詳細資訊，尤其是關於：
- 這樣一個系統的工作，
- 優點是什麼（也許相對於 $ \mathbb Z_p $ 上面的方案），
- 橢圓曲線選擇允許從間隔映射到曲線，然後返回，足夠有效，不會扼殺優點，
- 如果有任何希望使用通用橢圓曲線組（或其他通用組）。
如Bernstein 的 SafeCurves 頁面所述，超奇異橢圓曲線的問題在於它們容易受到轉移攻擊（這會將橢圓曲線 DLP 減少為加法或乘法組 DLP）。
幸運的是，可以使用任意橢圓曲線建構單向排列 $ E $ 在場上 $ \mathbb{F}_p $ . 訣竅是採取聯合 $ E $ 及其二次扭曲 $ E’ $ . 具體來說，當以 Weierstrass 範式編寫時， $ E’ $ 精確填充由點的 x 座標形成的間隙 $ E $ . 特別是，我們有：
$$ |E| + |E’| = 2p+2 $$
並且可以從 $ E \cup E’ $ 到 $ {0, 1, \dots, 2p+1} $ 通過結合 $ x $ 與符號位 $ y $ （並做一些額外的捏造來處理無窮遠點和點 $ y = 0 $ ).
假設橢圓曲線 $ E $ 和 $ E’ $ 是循環群（帶有各自的生成器 $ G $ 和 $ H $ ) 和難以處理的 DLP，那麼我們可以定義一個單向雙射 $ {0, 1, \dots, 2p+1} $ 到 $ E \cup E’ $ 如下：
- 如果 $ x < |E| $ ，然後提高一個基點 $ G \in E $ 在原始曲線上的冪 $ x $ ;
- 如果 $ x \geq |E| $ ，然後提高一個基點 $ H \in E’ $ 在扭曲的曲線上的冪 $ x $ ;
我們可以用前面提到的雙向雙射來組合它 $ E \cup E’ $ 到 $ {0,1,\dots,2p+1} $ 在集合上產生單向排列 $ {0,1,\dots,2p+1} $ . 反轉此排列等效於在任一上求解橢圓曲線 DLP $ E $ 或者 $ E’ $ ，取決於輸入，所以最好選擇參數，使得兩者 $ E $ 及其二次扭曲 $ E’ $ 是安全曲線。
這個想法似乎最早出現在Kaliski 1991中，作者還證明（通過聯合界限）可以保證這樣一對循環曲線的存在 $ E, E’ $ .
在實踐中，您可以選擇 $ p = 2^{255} - 19 $ ，尋找一對合適的安全曲線，從而獲得區間上的單向排列 $ [0, 2^{256} - 37] $ 具有 128 位安全性。