是否有一種方法可以加密循環值集的值之間的關係並使用偽 RNG 從該集合中生成值？（全部在使用者 PC 上）
有沒有偽RNG和函式 $ f $
1.) RNG 產生一個值 $ v_0 $ 在……之外 $ N $ 不同的值（設置 $ S $ ）。
2.) 獨立於RNG的功能 $ f $ 生成 $ v_{i+1}=f(v_i) $
要求：
$ \bullet $ $ v_{i+N} = v_i $
$ \bullet $ $ \forall i $ : $ {v_{i+k}, 1\le k \le N} = S $
$ \bullet $ $ v_{i+j} = f^j(v_i) $ 所以它需要 $ O(N) $ 計算（難以計算）
所有這些都是在使用者 PC 上計算的。他可以訪問所有變數。給定由 RNG 生成的兩個隨機值，使用者不應該知道如何計算第一個中的第二個（= 多久 $ f $ 需要申請）。
**問題：**是否有任何密碼方法具有這種條件？
進一步說明：
(*..) …在進一步的文本中表示可選的簡化
$ \bullet $ 每個 $ v_0 $ 是同一周期的一部分（*或最多 10 個相同大小的周期中的一個 (+/-5%)）
$ \bullet $ 應該沒有更快的計算方法 $ v_{i+j} $ 在……之外 $ v_{i} $ 除了在 $ j $ $ (\mod n) $ 步驟（或 $ N-j $ 步驟）（*線性加速小於 5 倍是可以的）
$ \bullet $ (*函式的結果集 $ f $ 可以大於那些 $ N $ 值（最多約 1000 次）（以及循環大小），但需要存在一個有效的函式來證明它是否是其中之一 $ N $ 值。）
$ \bullet $ 需要一種有效的方法來（偽）隨機生成值 $ v_0 $ （*並非所有值 $ S $ 需要由RNG生成，但至少 $ N^{2/3} $ )
$ \bullet $ （*RNG不需要在這些人之間均勻分佈 $ N $ 值（但它可以）。如果沒有一個值的機率遠高於包含所有值的 80% 的任何子集的 1000 倍，那很好。）
例子
$ \bullet $ 使用未知方法：
具有函式的隨機循環置換（循環大小為 N） $ f $ 它會在該循環中生成下一個值，並且 RNG 可以是 1 到 1 之間的隨機數 $ N $ .
$ \bullet $ 太容易計算：
離散對數 $ \mathbb{Z}/N\mathbb{Z} $ 帶素數 $ N $ 和一個原始根 $ g $ 作為發電機 $ f(v)=v⋅g $ . RNG 只會給出一個隨機值 $ 1 $ 和 $ N−1 $ . 如果現在使用者得到兩個這樣的隨機值，他不知道如何計算其中一個（與 $ g $ ) 即使他知道所有內部變數。但是大約可以解決 $ O(\sqrt{N}) $ 腳步。對於計算速度太快的小數字。我正在尋找類似的東西，但 $ O(N) $ （或更大）。
範例案例：
_
_
綠色方塊是價值 $ v_0 $ 由 RNG 生成。
AF 是集合的成員 $ S $ .
在每張圖片中，從一個值到下一個值的關係是相等的（模 9）。
例如，要從值 D 到 E，它總是向右 1 個正方形，下面是 1 個正方形。
如果現在 $ N=80 $ 和 $ f $ 提供循環排列中的下一個值（大小為 N），可以生成以下藍色方塊，如下所示
： $ v_{i+1} = f(v_i) $ 然後水平移動 $ = v_{i+1} \mod 9 $ 和垂直 $ = \operatorname{roundDown}(v_{i+1}/9) $
這可能導致同一位置有多個值，但循環中接近的值也共享幾乎相等的其他值。週期另一端的價值仍然共享一半以上的價值。不需要此屬性，始終相等的值會更好。
如果現在只給定兩個隨機值，例如 D 和 G，那麼應該盡可能難以推導出 G 從 D 開始的位置。
網格將是 3D 和大約 100k x 100k x 100k 的圖塊。需要約 $ 10^{12} $ 獨特的價值觀。只需要對標準 PC 安全（>10.000 小時計算時間，而不是超級電腦、網格、硬體）
除了“下一個”功能 $ f $ 逆也可以存在。除了單個函式之外，每個維度的函式都可以存在。如果是這種情況，則僅計算相鄰的正方形。它需要獨立於函式執行的順序，並且不應該存在（簡單的）方法將給定值減少到其維度值。否則找到兩個隨機值之間的方式太容易了。
如果評估 $ f $ 使用電腦時間 $ t $ ，蠻力攻擊平均需要時間 $ Nt/2 $ . 讓這個大於 $ T=36\cdot10^6 $ 秒，與 $ N\approx10^{12} $ ， 我們需要 $ t>72\cdot10^{-6} $ ，也就是幾十萬個 CPU 指令。人為地減慢了執行的速度 $ f $ 在程序中將無濟於事。 $ f $ 必須本質上很慢，以便攻擊者很慢；並且可控地慢，以便我們可以調整使用者程序的安全性和速度之間的折衷。
範例應用程序表明 $ S $ 是一個更大集合的隨機子集 $ M\approx10^{15} $ 元素。我們將其視為 $ [0,M) $ ， 和 $ M\ge2N $ .
我只針對安全要求的簡化版本：給定 RNG 生成的兩個隨機值，猜測步驟數 $ f $ 從一個到另一個，如果用少得多 $ T $ 幾秒的計算時間，準確的機率很低。為此：
- 選擇一個整數參數 $ \alpha $ （更大的會減慢 $ f $ ）。找一個素數 $ p\approx\alpha N $ 和 $ q=(p-1)/2 $ 主要 （ $ p $ 是一個安全的素數並且 $ q $ 索菲熱爾曼素數），還有 $ 2^q\bmod p=p-1 $ （也許 $ \log_2p $ 非常接近一個簡單的分數）。
- 定義函式 $ b $ 在片場 $ [1,p) $ 作為 $ x\mapsto b(x)=2x\bmod p $ . 功能 $ b $ 是一個循環置換 $ [1,p) $ .
- 定義函式 $ c $ 在片場 $ [N,2N) $ 迭代地應用 $ b $ （至少一次）直到結果出現 $ [N,2N) $ ，並返回此結果。功能 $ c $ 是一個循環置換 $ [N,2N) $ . 實施見註釋。
- 建立一個排列 $ g $ 的 $ [0,M) $ 使用標準的格式保留加密技術。 $ S $ 是整數的集合 $ v $ 在 $ [0,M) $ 和 $ N\le g^{-1}(v)<2N $ .
- 將RNG定義為繪圖 $ u $ 均勻隨機地 $ [N,2N) $ 並返回 $ g(u) $ .
- 定義函式 $ f $ 在集合之上 $ S $ 作為 $ f(v)=g(c(g^{-1}(v))) $ . 它循環 $ N $ 要點 $ S $ 確切地說 $ N $ 腳步。
給定隨機 $ v $ , $ v’ $ 由 RNG 生成，可以估計有多少步 $ f $ 有必要從 $ v $ 至 $ v’ $ : 我們計算 $ u=g^{-1}(v) $ 和 $ u’=g^{-1}(v’) $ ， 然後 $ y=u^{-1},u’\bmod p $ ，然後求解 $ x $ 離散對數問題 $ 2^x\bmod p=y $ （這仍然很容易，考慮到數量級 $ N $ 和 $ \alpha $ ）。多少步的合理猜測 $ f $ 有必要從 $ v $ 至 $ v’ $ 是 $ x,N/p $ 四捨五入到最接近的整數。然而，該估計對於中度而言準確的機率很低 $ alpha $ （遠小於 $ N $ )，並且我希望顯著改進它會帶來可觀的成本。
注意：有時間/記憶體權衡可能用於評估 $ c $ 比瑣碎更快：
uint64_t c(uint64_t x) { do { x += x; if (x>=p) x -= p; } while( x>=2*N || x<N ); return x; }並且程序應該使用這些，以增加 $ \alpha $ 在功能上可以容忍的情況下，最大限度地提高蠻力攻擊的成本。