有沒有地穴。方法F,g,hF,G,Hf,g,h通勤和尋找XXx給定的c=F一世GjHķ(×)C=F一世GjHķ(X)c=f^ig^jh^k(x)比O(我+j+k)○(一世+j+ķ)O(i+j+k)但只有<2256<2256<2^{256}價…
是否有任何加密方法 $ f,g,h $ 可以以任何順序應用於輸入 $ x $ 同時仍然產生相同的結果 $ r $ : $$ f(g(h(x)))=h(g(f(x)))=ghf(x)=fhg(x)=hfg(x)=gfh(x) = r $$
它們的反函式相同： $$ f^{-1}(g^{-1}(h^{-1}(r)))=h^{-1}(g^{-1}(f^{-1}(r)))=g^{-1}(h^{-1}(f^{-1}(r))) =…= x $$
如果現在 $ f,g,h, $ 被申請;被應用 $ i,j,k $ - 輸入的倍數 $ x $ 尋找/計算 $ x $ 給定的 $ c $ $$ c=f^i(g^j(h^k(x))) $$ 應該盡可能地困難，並且需要超過 $ O(|i|+|j|+|k|) $ 腳步。
此外方法 $ f,g,h $ 保留格式： $ X \mapsto X $ ，所以每個輸出都可以作為新的輸入。
不同值的數量 $ |X| $ 應盡可能小，同時仍保持足夠的安全性。
最大尺寸應為： $$ |X| < 2^{256} $$
更多節點：
計算 $ f,g,h $ 並且它們的逆需要為每個輸入花費相似的時間（獨立於 $ i,j,k $ ).
此外 $ f,g,h $ 必須產生一個循環 $ f(f(….f(x)…)) = x $ 有大小 $ F,G,H $ 和 $ F\approx G \approx H \gg 1 $
並且隨機 $ x $ 可以在不知道秘密參數的情況下生成 $ f,g,h $ （對手可以訪問正在執行的程式碼）。
目標：給定兩個隨機 $ x_1,x_2 $ 和 $ x_2=f^ig^jh^k(x_1) $ 計算/發現 $ i,j,k $ 應該盡可能用力，而不同的數量 $ x $ 應該盡可能小。
不是最好的，但有一些組合 $ x_1,x_2 $ 可能沒有任何 $ i,j,k $ ， 方法 $ f,g,h: X_d \mapsto X_d $ 和 $ d<\approx 10 $
目標安全 $ \approx 2^{100} $ 步驟（= 的計算次數 $ f,g $ 或者 $ h $ （或等價物））需要。
與完美 $ f,g,h $ （如果它們存在）它應該只需要 $ |X| \approx 2^{150} $ （例如線的交點 $ f^l(x_1) $ 帶錶面 $ g^mh^n(x_2) $ ）
（對手沒有量子電腦）
相關問題： 如果我們忽略最大域大小 $ |X|<2^{256} $ 我非常相似的問題的答案導致了一個很大的問題 $ |X| $ 避免因式分解。我正在尋找盡可能小的 $ |X| $ .
這是一個似乎可以滿足您所陳述的所有要求的想法。現在，它不符合其他合理的加密要求；但是你從來沒有要求過他們。
想法是這樣的：我們在一個適當大小的橢圓曲線組（比如 P224）中工作，組大小 $ q $ （這是素數），並選擇三個發電機 $ F, G, H $ （具有未知關係；可能使用 Hash2Curve 方法生成）；和：
$$ f(X) = F + X $$
$$ g(X) = G + X $$
$$ h(X) = H + X $$
這些操作顯然是通勤的，我們有 $ f^i(g^j(h^k(X))) = iF + jG + kH + X $ .
通過您的要求：
如果現在 $ f,g,h $ ， 被申請;被應用 $ i,j,k $ - 輸入的倍數 $ x $ 尋找/計算 $ x $ 給定的 $ c = f^i(g^j(h^k(x))) $ 應該盡可能地困難，並且需要超過 $ O(|i|+|j|+|k|) $ 腳步。
我假設，在這個要求中，攻擊者不知道 $ i, j, k $ （他確實知道相對范圍）。在這種情況下，我能找到的最好的搜尋來驗證一個值 $ c $ 需要 $ O( \sqrt{i \cdot j \cdot k } ) $ 時間（假設 $ i \cdot j \cdot k < q $ ， 明顯地）; 這大於 $ O(i + j + k) $ . 這個搜尋是通過採取 $ 0F, 1F, …, iF $ , $ 0G, 1G, …, jG $ , $ 0H, 1H, …, kG $ ，將它們分成兩個列表，其中三個列表中的任何三個項目的總和可以表示為兩個列表中的項目的總和，然後應用“大步/小步”樣式算法。
此外方法 $ f,g,h $ 保留格式： $ X \rightarrow X $ ，所以每個輸出都可以作為新的輸入。
只要你很酷 $ X $ 作為橢圓曲線點的集合，我們在這裡很好。
最大尺寸應為： $ |X|<2^{256} $
對於 P-224，這是真的。
計算 $ f,g,h $ 並且它們的逆需要為每個輸入花費相似的時間（獨立於 $ i,j,k $ ).
我們在這裡很好
此外 $ f,g,h $ 必須產生一個循環 $ f(f(….f(x)…))=x $ 有大小 $ F,G,H $ 和 $ F \approx G \approx H \gg 1 $
真的; $ f, g, h $ 都有秩序 $ q $ , 遠大於 1
您可以輕鬆選擇範圍 $ i, j, k $ 從而達到目標安全性。
現在，這個想法沒有提供的一件事是，給定 $ c, x $ 和 $ c = f^i(g^j(h^k(x))) $ , 計算起來很簡單 $ c’ = f^i(g^j(h^k(x’))) $ . 但是，你從來沒有要求這很難……