哪個是最小的、在 3 個方向上循環的、可以隱藏在對手機器上的隨機值的一致結構？（一些比較）
或更一般地，每個成員可以是最多三個 2D 局部歐幾里德平面的一部分，每個平面具有 2 個不同的維度。（這些平面中的每一個都是在兩個正交方向上循環的，就像一個圓環）
僅給定一個成員，它可能看起來像一個節點網路：（
此處僅顯示一個帶有一些鄰域的節點。這些鄰域的鄰域也未在此處顯示）
（左：1 個平面，2 個平面的右交點） 3 個平面的交點：
儘管需要一些確定性的方法將節點的鄰域映射到這三個 2D 歐幾里德平面上的平面圖（具有恆定的節點密度）。所以相鄰節點的鄰居往往也是鄰居並且沒有 $ n $ - 需要例如雙曲空間來表示的鄰域增長。
從一個節點開始 $ n $ 並且（主要）遵循一個前進方向將在（最好的情況下）之後再次導致相同的節點 $ C_n $ 腳步。所以它是具有循環長度的循環 $ C_n $ . 在最好的情況下，這對於所有方向上的所有節點都是相等的。但為了不那麼嚴格，只要循環長度與附近節點相似，一些變化是可能的。
目標：
找到這樣一種結構，使循環長度最小化 $ C $ （最好的 $ \le 2^{50} $ ) 和總節點數 $ N $ （最好的情況 $ N=C^3 $ 或者 $ \le 2^{150} $ ），同時盡可能難以計算兩個隨機節點之間的關係（最好 $ \ge O(C^2) $ 和 $ O(\sqrt[3]{N^2}) $ 或數字 $ \ge 2^{100} $ )專門用於加密方法：
據我所知，在密碼學中，只有比上述結構更專業或部分更通用的結構。
例如，如果將來自一個節點的鄰居數設置為固定值 6，我們會得到這樣的結構：（
左：3 個平面在單個節點/編號處的交點，右：每個節點/編號在此處都有此結構 ）可以用 3 個發生器和一個合適的
$ \bmod P $ 如下所列。
對於每種類型，我將添加一些無法解決的原因以及（我的）相關執行緒以獲取更多詳細資訊。
與經過測試的加密方法的比較：
- 三台發電機 $ q,r,s $ 和 $ \bmod P = 2\cdot Q \cdot R \cdot S +1 $ 和 $ q^Q \equiv r^R \equiv s^S \equiv 1 \bmod P $ $ \text{ } $ $$ 1 $$
- $ - $ $ P $ 需要很大以避免因式分解 $ \gg 2^{150} $
- $ - $ 在知道循環大小的情況下，使用Pohlig-Hellman 算法可以將其簡化為一個更容易的問題
- $ - $ 每個方向的循環大小跨越整個域
- $ + $ 只需要相對較少的數字
- $ - $ 但仍然是域/週期大小 $ 2^{200} $ 需要（僅目標週期大小 $ 2^{50} $ )
- AES 或類似的分組密碼：
- $ - $ 在多個未知大小的循環中分離，只有分佈是已知的$$ 1 $$
- $ - $ 每個方向一個？ $ \rightarrow $ 領域 $ 2^{300} $ 需要並且可以簡化為一維問題
- $ - $ 將 3 個 AES 連接到單個成員？ $ \rightarrow $ 大的 $ n $ -neighborhood，類似於只使用隨機值 $ \rightarrow $ 之後可以找到交替 AES128（ECB 模式）的匹配 $ \approx {2^{64}} $ 進步的步驟$$ 2 $$
- 3方向序列 $ s_{ijk} = s_0^{\textstyle \beta^i\gamma^j\delta^k} \bmod (N=P\cdot Q) $ - 很難解決，因為 $ \phi(N) $ 未知
- 為了 $ N=(2\cdot p +1)\cdot (2\cdot q +1) $ 與氏族。 $ \beta, \gamma, \delta $ 的原始根源 $ p,q $ $$ 1 $$
- $ + $ $ O(\sqrt[2]{C^3}) $ （我所知道的）
- $ - $ 但只有當 $ \phi(N) $ 是未知的。到達 $ 100 $ 位安全 $ N $ 需要在身邊 $ 2000 $ -位大小和這個 $ p, q $ 並且週期大小也增加了
- 為了 $ N=(2\cdot p_s \cdot p_b +1)\cdot (2\cdot q_s \cdot q_b +1) $ 預計 $ \frac{(p_s-1)}{2}\cdot \frac{(q_s-1)}{2} $ 和 $ \gcd(e,\phi(N)) \ne 1 $ 但 $ e $ 難以分解$$ 2 $$, $ \beta,\gamma,\delta $ 與權力有關 $ e $
- $ + $ $ O(\sqrt[2]{C^3}) $ （據我所知）如果 $ C $ 未知
- $ - $ 如果週期長度幾乎是即時的 $ C $ 是已知的（目標值很容易推導）。 $ C $ 需要是 $ >2^{100} $
- 有限域上的幾何反射（三角形$$ 1 $$, 四面體$$ 2 $$- 兩者都沒有解決方案）或更一般的矩陣乘法鏈。讓 $ n $ - 鄰域不會增長太快，它們需要在乘法順序上保持不變。所以它們可以簡化為 $ A^iB^jC^k $ - 但到目前為止我找不到任何這樣的矩陣 $ i,j,j $ 難以確定
- $ - $ 要麼太多 $ n $ -neighbors 或太容易計算索引
**問題：**可以做得更好嗎？可以小於 $ N=2^{200} $ 值沿 3 個維度分佈，循環大小小於 $ C=2^{65} $ 每次找到兩個成員之間的關係確實至少需要 $ 2^{100} $ 計算步驟（大多數情況下）？
為此，它需要比 $ O(\sqrt{N}) $ （和 $ N<2^{200} $ 和 $ C<2^{65} $ )
進一步說明：
- 除了正向的 3 個方向之外，它們反向的反向也需要存在。所有人都應該有大約相同的計算時間。（編輯：類似於 fgrieu 的想法，如果兩個方向（及其逆方向）具有相同的計算時間就足夠了。更改易於計算的兩個方向可能需要更多的計算時間）
- 在最好的情況下，所有有效的隨機值都可以生成相同的結構。但是一個小（ $ <\approx 10 $ ) 一組不相交的相似結構（如 4.）也是可能的。
- 在案例中，將生成一個隨機起始值，並用它最近的鄰居迭代地消耗（之後是鄰居的鄰居等等）。它們最終（在（幾乎）無窮無盡的生成時間之後）形成了相同的一致（秘密）結構。應該盡可能難地優先考慮任何進展方向以更快地達到某個目標值。所以只生成隨機點是行不通的。生成的下一個值應始終接近已生成的值。這也意味著生成 $ i- $ 不需要下一個值（因為它通常可以使用生成器完成），朝一個方向邁出一步就足夠了（如在 AES/分組密碼中）
- 沒有拉伸功能，比如只計算每個 $ n $ -th 成員為有效（以增加安全性（更高的成員大小 $ N $ ) 具有恆定的真實成員大小 $ \frac{N}{n} $ ）。這將已經被使用。它應該 - 從技術上講 - 可能（如果有人真的想要的話）在標準 PC 上以少量 CPU 年在一個方向上生成一個完整的周期。有了這個週期大小需要小於 $ 2^{60} $ . 但在未來 50 年內，找到任何兩個目標值之間的關係應該是不可行的。為某些組合找到它很好，擁有它甚至很好。據我所知 $ 2^{100} $ 計算步驟是一個合適的邊界。
- 計算步驟是指應用於兩個值的任何類型的基本操作 (+-*/^) $ <N $
- 這些結構成員可以是數字、向量、字元串、矩陣之類的任何東西，甚至 ascii 藝術圖片也可以。只需要一些函式來生成偽隨機值而不會洩露安全相關資訊。生成多個它們不應洩露有關它們之間關係的任何資訊。所以像 $ g^r $ 帶發電機 $ g $ 和 $ r $ 隨機值行不通。生成它們不需要那麼快， $ <20 $ 標準 PC 上的 sec 就足夠了。
- 在目標案例中，這些成員將作為 RNG 的種子。這些成員的結構作為這些種子的安排。這些 RNG 生成的一些隨機數序列會比其他的更好。如果發現其中一個非常好的，則應該盡可能難以連接它們（=從另一個中計算一個）。
- 對手將等於普通使用者。他可以訪問所有原始碼、執行時變數、鍵、變數等。作為目標週期長度 $ C $ 非常小，我們也可以認為它被對手所知。
- 一些經過更多測試的技術：元胞自動機（無逆）、曲面細分（不確定或太容易解決）、同態加密（無溢出/循環，如果在對手 PC 上不起作用）。
**更新：**與 fgrieu 的評論相關：
我們想要一個 N 個節點的無向連通圖
$$ ?with a representation of a vertex n as a triplet of coordinates (are coordinates integers?)? $$
是的，但這些座標沒有全球原點。如果我們想從 $ n_1 $ 至 $ n_2 $ 我們從 $ n_1 $ 併計算它的鄰域。那些有與相關的座標 $ n_1 $ . 例如 $ (0,1,0) $ 可能意味著我們從 $ n_1 $ 並應用了第 2 維的級數一次。
之間的節點偏移量 $ n_1 $ 和 $ n_2 $ 是對稱且不變的 $ n_i $ 我們是從。
由於它們在每個維度上都是循環的，因此偏移量只能是 $ +/- $ 每個座標的一半循環大小（在歐幾里得空間中）。
整數不是必需的。只要電腦可以將實數近似到足以區分不同節點的程度，實數也可以工作。
網位於3-Torus處，因此我們也可以將偏移解釋為角度差。
需要明確的是，僅生成隨機座標是行不通的。它們總是需要接近那些已經生成的。唯一的例外是起始節點。那些需要隨機生成。給定兩個這樣的起始節點（和所有內部變數），應該沒有關於最佳進展方向的提示。
應該有一些過程可以沿著圖邊從一個節點移動到另一個節點，這在迭代時會導致長度循環 $ C_n $ 從 n 開始時
開始於 $ n $ 並且（主要）朝著一個方向前進（例如，不會再向後退很多次），我們可以到達 $ n $ 之後再次 $ C_n $ 腳步。這需要對於至少 2 個正交方向且不超過 3 個（每個向前和向後）是可能的。
給定兩個隨機頂點，應該很難找到兩者之間的路徑，需要努力調整 $ \Omega(\sqrt[3]{N^2}) $
它也可能更難，但我認為這在具有固定鄰域的普通密碼結構中是不可能的。在一般網路中，它可能更難。主要問題是找到不能簡化為單維大小問題的東西 $ C $ 因為目標值太小了。這也意味著 $ C $ 對手知道（因為它可以被快速測試）。
但如果我沒有混淆符號，它應該是 $ o(C^2+C) $ （對於固定鄰域，線平面相交總是可能的）和 $ \Omega(\sqrt{N}) $ 和 $ \Omega(C^{1.5}) $ （平均步數）否則 $ N,C $ 需要太大。
$ C_n $ 需要調整 $ O(\sqrt[3]{N}) $
$$ but is that an upper bound or a lower bound for Cn? $$.
兩個都。不像所示的方法使用 EC where $ N\approx C_n $ 並且不喜歡使用兩個 AES 的方法，其中 $ C_n $ 可能 $ 1 $ .
可能有類似的東西 $ O(\sqrt[3]{N}\cdot f(\log(N))) $ . 主要目標是獲得一個 $ \max(C_n) < 2^{65} $ （和 $ \min(C_n) \ge 2^{50} $ （否則很容易afaik）） $ N<2^{200} $ 並從隨機中找到 $ n_1 $ 至 $ n_2 $ 應該（在大多數情況下）至少 $ 2^{100} $ 進展的步驟（但可能，最多 $ \approx 10 $ 子集沒問題）。
相關 JAAAY 的評論：
歐幾里得局部性或雙曲線平面
換句話說，鄰里增長不能太快。
利用（大量空閒時間），我們可以將鄰域結構繪製到紙上（=歐幾里得平面）。
我們可以用尺子測量節點之間的（歐幾里得）距離。無論有多少鄰居的鄰居，我們繪製節點之間的平均距離應該保持（大約）相等。
如果我們將兩個相對的紙邊粘在一起，我們可以模擬一個方向的循環屬性。考慮到這個選項，兩個特定節點之間的（最小）距離總是相等的——無論我們是否開始繪製這個結構。（在兩個方向上畫完完整的循環後，我們必須將紙張切割成適當的尺寸。在邊界處，我們繼續在紙張的相反邊界處測量）。
一個節點最多只能在 3 張紙上。如果多個數字在兩張不同的紙上（2-tori），它們都位於一條線上（1-torus） - 就像在兩個 2-tori 的交點處。
與 fgrieu 的回答相關的更新
為了更好地概述這裡，V2 的略微修改版本（在兩個方向上的成本進展相似）： $$ f(d_1,d_2,c) = \begin{cases}(d_1+1 \bmod \sqrt{s}, d_2,c)\(d_1 , d_2+1\bmod \sqrt{s},c)\end{cases} $$ 和 $ c\in [0,s^2) $ 有連接 $$ D(t-1-E(d_1+d_2\cdot \sqrt{s}+c\cdot s)) = v $$ 有效連接如果 $ v<s^3 $ 並解碼 $ (d_1’,d_2’,c’) $ 抓住 $ (c \bmod 3) \ne (c’ \bmod3) $
優點：
- 週期大小 $ \sqrt{s} $ 和總節點數 $ s^3 $ 可以任意小
- 易於在 2 個方向上計算
- 獨特點
- 節點之間定義明確的連接/蠕蟲連結
缺點：
週期大小之間的巨大差異 $ \sqrt{s} $ 和飛機總數 $ s^2 $
單個平面之間的路徑查找是微不足道的
- 給定 2 個隨機節點，如果它們是同一平面的一部分，則可以快速測試它們
- 給定一個平面的 1 個節點，該平面的所有其他節點都可以計算為 $ O(1) $
兩個平面的交點只是單點而不是 $ 1 $ -環面。多合一周期與需求衝突。為了解決這個問題，我們可以使用某種選擇功能 $ \sqrt{s} $ 值（由於 $ \sqrt{s} $ 很小）。
這樣一個節點只能有一個連接。如果我們使用 3 BC 併計算： $$ D_j(t-1-E_i(d_1+d_2\cdot \sqrt{s}+c\cdot s)) = v $$ 這 $ i $ ’th BC 用於如果 $ c \bmod 3 = i $ . 除了 $ v<s^3 $ 解碼點 $ (d_1’,d_2’,c’) $ 也需要持有 $ (c’ \bmod 3) = j $ 如果 $ D_j $ 的解密 $ j $ -th BC 已被使用。
Afaik 這應該對安全性沒有重大影響，或者？
Afaik2 安全性應該接近 $ O(s^{1.8}) $ 對於所有這些。更多細節可以在這裡找到。
不是最佳的，但比迄今為止所有其他測試的要好。關於更難檢查兩個隨機點是否在同一平面內的想法，減少循環大小之間的比率 $ \sqrt{s} $ 和飛機數量 $ s^2 $ 或替代方法（仍然）受歡迎。
再次感謝 fgrieu 和所有其他讀者。
![[圖1]](https://i.stack.imgur.com/u7aw1.png)
半熟的東西。讓 $ s $ 是某個整數，的倍數 $ 3 $ ， 按照…的順序 $ 2^{50} $ . 讓集合是三元組 $ (x,y,z)\in[0,s)^3 $ ， 和 $ N=s^3\approx2^{150} $ 元素。定義$$ f(x,y,z)=\begin{cases}(x+3\bmod s,y,z)&\text{ if }x+y+z\bmod3=0\(x,y+3\bmod s,z)&\text{ if }x+y+z\bmod3=1\(x,y,z+3\bmod s)&\text{ if }x+y+z\bmod3=2\\end{cases} $$
迭代 $ f $ 從任何起點產生一個循環 $ C_{(x,y,z)}=s/3 $ . 有 $ 3s^2 $ 迄今為止如此不連貫的循環， $ s^2 $ 在圓環的每個方向。
仍然存在通過罕見的“蠕蟲連結”連接週期。
V1：定義那個點 $ (x,y,z) $ 連接到點 $ (x’,y’,z’) $ 通過蠕蟲連結當先
- $ H(x+s,y+s^2z)\equiv H(x’+s,y’+s^2z’)\pmod t $ 為了 $ H $ 一些寬散列（SHA-256 可以）和 $ t\gg s^3 $ 一些參數。
- 和 $ (x,y,z)\ne(x’,y’,z’) $ 和 $ f(x,y,z)\ne(x’,y’,z’) $ 和 $ f(x’,y’,z’)\ne(x,y,z) $ （即這些點是不同的，並且沒有通過正常連結連接）
我們想要 $ t $ 足夠大，以壓倒性的機率將集合連接起來，但又足夠低，以至於在計算上難以導航。正確的球場可能是 $ t\approx s^{3.8} $ 或者那個曲子上的東西。
V2：使用可能的密鑰分組密碼，允許找到一個點連接到的位置（如果有的話）。製作（按格式保留加密）從 $ [0,t) $ 至 $ [0,t) $ 甚至 $ t\gg2s^3 $ , 加密 $ E $ 和解密 $ D $ . 觀點 $ (x,y,z) $ 連接到 $ (x’,y’,z’) $ 通過蠕蟲連結當先
- $ E(x+s,y+s^2z)+E(x’+s,y’+s^2z’)=t-1 $
- $ f(x,y,z)\ne(x’,y’,z’) $ 和 $ f(x’,y’,z’)\ne(x,y,z) $ （即這些點沒有通過正常連結連接；有 $ t $ 甚至確保它們是不同的）。
找到連接到的點 $ (x,y,z) $ , 計算 $ D(t-1-E(x+s,y+s^2z)) $ ，如果那在 $ [0,t) $ 將其解碼為 $ (x’,y’,z’) $ , 並檢查 $ f(x,y,z)\ne(x’,y’,z’) $ 和 $ f(x’,y’,z’)\ne(x,y,z) $ .
較大的 $ t $ ，最小連接的集合是。我再試一次 $ t\approx s^{3.8} $ 並從那裡精煉。
或許可以調整一些東西，使每個循環都具有最少數量的蠕蟲連結，從而減少蠕蟲連結，同時保持集合以壓倒性的機率連接。