Care este cea mai mică, ciclică în 3 direcții, structură consistentă de valori aleatoare care poate fi ascunsă la mașina adversarilor? (cumva comparatie)

Sau mai general fiecare membru poate sa să facă parte din până la trei planuri euclidiene 2D cu 2 dimensiuni diferite fiecare.

(fiecare dintre aceste planuri este ciclic în două direcții ortogonale, ca un tor)

Având în vedere un singur membru, ar putea arăta ca o rețea de noduri:
(doar un nod cu un cartier afișat aici. Acei vecini au din nou vecini care nu sunt afișați aici)
(stânga: 1 plan, intersecția dreaptă a 2 planuri)
intersectia a 3 plane:

În ciuda acestui fapt, trebuie să existe o modalitate deterministă de a mapa vecinătatea unui nod la grafice plane la acele trei plane euclidiene 2D (cu densitate constantă a nodurilor). Deci vecinii nodului adiacent tind să fie și ei vecini și nu au $n$-creșterea cartierului care are nevoie de ex. spațiu hiperbolic pentru reprezentare.
Începând de la un singur nod $n$ și (în principal) urmărirea unei direcții de progres va duce la același nod din nou după (în cel mai bun caz) $C_n$ trepte. Deci este ciclic cu lungimea ciclului $C_n$. În cel mai bun caz, aceasta este egală pentru toate nodurile din toate direcțiile. Dar pentru a fi mai puțin strict este posibilă o anumită variație, atâta timp cât lungimea ciclului este similară cu nodurile din apropiere.

Obiectivul:
Găsirea unei astfel de structuri care să minimizeze lungimea ciclului $C$ (Cel mai bun $\le 2^{50}$) și numărul total de noduri $N$ (cel mai bun caz $N=C^3$ sau $\le 2^{150}$) menținând cât mai greu posibil să se calculeze relația dintre două noduri aleatorii (cel mai bun $\ge O(C^2)$ și $O(\sqrt[3]{N^2})$ sau în cifre $\ge 2^{100}$)

Specializat în metode criptografice:

Din câte știu eu în criptografie, există doar structuri care sunt mai specializate sau parțial mai generale decât o astfel de structură descrisă mai sus.
Dacă de ex. numărul de vecini de la un nod este setat la o valoare fixă ​​de 6, obținem o structură ca aceasta:
(stânga: intersecția a 3 planuri la un singur nod/număr, dreapta: fiecare nod/număr are această structură aici)

Acest lucru se poate realiza cu 3 generatoare și un adecvat $\bmod P$ după cum este enumerat mai jos.
Pentru fiecare fel voi adăuga câteva motive pentru care nu funcționează și firele (mei) aferente pentru mai multe detalii.

Comparație cu metodele criptografice testate:

1. Trei generatoare $q,r,s$ cu $\bmod P = 2\cdot Q \cdot R \cdot S +1$ și $q^Q \equiv r^R \equiv s^S \equiv 1 \bmod P$ $\text{ } $[1]

   • $-$ $P$ trebuie să fie foarte mare pentru a evita factorizarea $\gg 2^{150}$
   • $-$ cu cunoașterea dimensiunilor ciclurilor se poate reduce la o problemă mult mai ușoară cu Algoritmul PohligâHellman

2. Curbe eliptice cu 3 generatoare $F,G,H$ si cu aceste valori $i \cdot F + j \cdot G + k \cdot H$ [1] [2]

   • $-$ dimensiunea ciclului pentru fiecare direcție este pe întregul domeniu
   • $+$ sunt necesare doar un număr relativ mic
   • $-$ dar încă o dimensiune de domeniu/ciclu de $2^{200}$ necesare (numai dimensiunea ciclului țintă $2^{50}$)

3. AES sau cifru bloc similar:

   • $-$ separate în mai multe cicluri cu mărime necunoscută, numai distribuția este cunoscută [1]
   • $-$ unul pe sens? $\săgeată la dreapta $ domeniul de $2^{300}$ necesar și poate fi redus la o problemă de o singură dimensiune
   • $-$ concatena 3 AES la un singur membru? $\săgeată la dreapta $ mare $n$- vecinătate, similar cu utilizarea valorilor aleatorii $\săgeată la dreapta $ o potrivire la AES128 alternativ (mod ECB) poate fi găsită după $\aproximativ {2^{64}}$ trepte de progresie [2]

4. secvență cu 3 direcții $s_{ijk} = s_0^{\textstyle \beta^i\gamma^j\delta^k} \bmod (N=P\cdot Q)$ - greu de rezolvat pentru că $\phi(N)$ necunoscut

   • pentru $N=(2\cdot p +1)\cdot (2\cdot q +1)$ cu gens. $\beta, \gamma, \delta$ rădăcinile primitive ale $p,q$ [1]
     • $+$ $O(\sqrt[2]{C^3})$ (după cum știu)
     • $-$ dar numai dacă $\phi(N)$ este necunoscut. A ajunge $100$-biți de securitate $N$ trebuie să fie prin preajmă $2000$-bit dimensiune și cu aceasta $p, q$ iar dimensiunea ciclului crește și ea
   • pentru $N=(2\cdot p_s \cdot p_b +1)\cdot (2\cdot q_s \cdot q_b +1)$ proiectat să $\frac{(p_s-1)}{2}\cdot \frac{(q_s-1)}{2}$ cu $\gcd(e,\phi(N)) \ne 1$ dar $e$ greu de factorizat [2], $\beta,\gamma,\delta$ legate de puterea de $e$
     • $+$ $O(\sqrt[2]{C^3})$ (din câte știu eu) dacă $C$ necunoscut
     • $-$ aproape instantanee dacă durata ciclului $C$ este cunoscut (ceea ce este ușor de obținut pentru valorile țintă). $C$ ar trebui să fie $>2^{100}$

5. Reflexia geometriei peste câmp finit (triunghiuri [1], tetraedru [2] - ambele fără soluție) sau mai general un lanț de înmulțire a matricei. Pentru a lăsa $n$-cartierul care nu crește prea repede trebuie să fie invariant în ordinea înmulțirii lor. Deci ele pot fi reduse la $A^iB^jC^k$ - dar până acum nu am putut găsi astfel de matrici care să facă de asemenea $i,j,j$ greu de determinat

   • $-$ fie prea multe $n$-vecini sau prea ușor de calculat indici

Întrebare: Se poate face mai bine? Poate mai puțin de $N=2^{200}$ valorile să fie distribuite pe 3 dimensiuni cu o dimensiune a ciclului mai mică de $C=2^{65}$ fiecare în timp ce găsirea relației dintre doi membri durează cel puțin $2^{100}$ pașii de calcul (pentru majoritatea cazurilor)?
Pentru asta trebuie să fie mai greu decât $O(\sqrt{N})$ (cu $N<2^{200}$ și $C<2^{65}$)

Alte note:

• pe lângă 3 direcții în direcția înainte, trebuie să existe și inversul lor în direcția înapoi. Toate ar trebui să aibă aproximativ același timp de calcul.
• în cel mai bun caz, toate valorile aleatoare valide pot genera aceeași structură. Dar un mic ($<\aproximativ 10$) este posibil și un set de structuri similare disjunctive (ca în 4.).
• în caz de utilizare, o valoare de pornire aleatorie va fi generată și cheltuită iterativ cu cei mai apropiați vecini ai săi (după aceasta vecinii vecinilor și așa mai departe).Ele au rezultat în cele din urmă (după timp (aproape) nesfârșit pentru generație) în aceeași structură consistentă (secretă). Ar trebui să fie cât mai greu posibil să prioritizați orice direcție de progres pentru a atinge mai rapid o anumită valoare țintă. Deci, generarea de puncte aleatoare nu va funcționa. Următoarele valori generate ar trebui să fie întotdeauna apropiate de cele care au fost deja generate. Asta înseamnă, de asemenea, generarea $i-$Următoarea valoare nu este necesară (cum se poate face de obicei cu generatoare), un pas într-o direcție este suficient (ca în AES/block-cipher)
• nicio funcție de întindere, cum ar fi doar numărați fiecare $n$-al-lea membru ca valid (pentru a crește securitatea (mărimea mai mare a membrilor $N$) cu dimensiunea adevărată constantă a membrului $\frac{N}{n}$). Acesta va fi deja folosit. Ar trebui - din punct de vedere tehnic - posibil (dacă cineva își dorește cu adevărat) să se genereze un ciclu complet într-o direcție pe un PC standard într-un număr mic de ani CPU. Cu aceasta dimensiunea ciclului trebuie să fie mai mică decât $2^{60}$. Dar găsirea relației între oricare două valori țintă ar trebui să fie imposibilă în următorii 50 de ani. Să-l găsești pentru unele combinații este bine, chiar e bine să ai. Din câte știu eu $2^{100}$ pașii de calcul este o limită potrivită pentru aceasta.
• o etapă de calcul înseamnă orice fel de operație de bază (+-*/^) aplicată la două valori $<N$
• acei membri ai structurii pot fi orice ca numere, vectori, șiruri, matrici, chiar și imagini de artă ascii ar funcționa. Trebuie doar să existe o funcție pentru a genera o valoare pseudo-aleatorie fără a scurge informații legate de securitate. Generarea mai multor dintre ele nu ar trebui să dezvăluie nicio informație despre relația dintre ele. Deci ceva de genul $g^r$ cu un generator $g$ și $r$ valoarea aleatoare nu ar funcționa. Generarea lor nu trebuie să fie atât de rapidă, $<20$sec la un PC standard este suficientă.
• în cazul de utilizare țintă, acești membri vor servi drept semințe pentru RNG-uri. Structura acelor membri ca un aranjament pentru acele semințe.Unele secvențe de numere aleatorii generate de acele RNG-uri vor fi mai bune decât altele. Dacă s-au găsit singure foarte bune dintre ele, ar trebui să fie cât mai greu posibil să le conectați (= calculați unul din celălalt).
• adversarii vor fi egali cu utilizatorul normal. El are acces la tot codul sursă, variabile de timp de rulare, chei, variabile și așa mai departe. Ca lungime țintă a ciclului $C$ este destul de mic îl putem considera cunoscut și de adversar.
• câteva tehnici mai testate: automate celulare (fără inversă), teselare (nu deterministă sau prea ușor de rezolvat), criptare homomorfă (fără depășire/ciclu, nu funcționează dacă toate la computerul adversar).

Actualizați: Legat de comentariul lui fgrieu:

Vrem un grafic conexit nedirecționat de N noduri [?cu o reprezentare a unui vârf n ca un triplet de coordonate (sunt coordonatele întregi?)?]

Da, dar acele coordonate nu au origine globală. Dacă vrem să găsim o cale de la $n_1$ la $n_2$ începem de la $n_1$ și calculează cartierul său. Acestea au coordonate legate de $n_1$. De exemplu. $(0,1,0)$ ar putea însemna că am început de la $n_1$ și a aplicat o dată progresia pentru a 2-a dimensiune.
Nodul decalat între ele $n_1$ și $n_2$ este simetric și invariant pentru fiecare $n_i$ pornim de la.
Deoarece sunt ciclice în fiecare dimensiune, offset-ul poate fi doar $+/-$ jumătate din dimensiunea ciclului (în spațiul euclidian) pentru fiecare coordonată.
Numerele întregi nu sunt necesare. Numerele reale funcționează, de asemenea, atâta timp cât computerele le pot aproxima suficient de bine pentru a face distincția între diferitele noduri.
Netul se află la a 3-Torus astfel încât putem interpreta decalajul și ca diferență de unghi.

Pentru a fi clar, doar generarea de coordonate aleatoare nu funcționează. Ele trebuie să fie întotdeauna aproape de cele deja generate. Singura excepție este nodul de pornire. Acestea trebuie generate aleatoriu. Având în vedere două astfel de noduri de pornire (și toate variabilele interne), nu ar trebui să existe nici un indiciu despre cea mai bună direcție de progres.

Ar trebui să existe o procedură pentru a trece de la un nod la altul de-a lungul marginilor graficului, care atunci când este repetată duce la ciclul de lungime $C_n$ când pornind de la n

Incepand la $n$ și (în principal) înaintând într-o direcție (și, de exemplu, nu de atâtea ori înapoi) putem ajunge $n$ iarăşi după $C_n$ trepte. Acest lucru trebuie să fie posibil pentru cel puțin 2 direcții ortogonale și nu mai mult de 3 (înainte și înapoi fiecare).

Având în vedere două vârfuri aleatorii, ar trebui să fie greu să găsești o cale între cele două, necesitând efort pe melodia $\Omega(\sqrt[3]{N^2})$

De asemenea, poate fi mai greu, dar cred că acest lucru nu este posibil în structurile criptografice normale cu vecinătate fixă. În plasele generale ar putea fi mai greu. Problema principală este găsirea a ceva care nu se poate reduce la o problemă de dimensiune unică $C$ deoarece valoarea țintă este prea mică pentru asta. Asta înseamnă și $C$ este cunoscut adversarului (deoarece poate fi testat rapid).
Dar dacă nu confund notația, ar trebui să fie $o(C^2+C)$ (pentru vecinătate fixă, intersecția linie-plan este întotdeauna posibilă) și $\Omega(\sqrt{N})$ și $\Omega(C^{1,5})$ (numărul mediu de pași) altfel $N,C$ trebuie să fie prea mare.

$C_n$ trebuie să fie pe tonul de $O(\sqrt[3]{N})$ [dar este aceasta o limită superioară sau o limită inferioară pentru Cn?].

Ambii. Nu ca metoda prezentată folosind EC unde $N\aproximativ C_n$ și nu ca metoda folosind două AES unde $C_n$ ar putea fi $1$.
Poate fi ceva de genul $O(\sqrt[3]{N}\cdot f(\log(N)))$. Scopul principal este de a obține un $\max(C_n) < 2^{65}$ (și $\min(C_n) \ge 2^{50}$ (altfel ușor afaik)) cu $N<2^{200}$ și găsirea de la întâmplare $n_1$ la $n_2$ ar trebui să ia (în majoritatea cazurilor) cel puțin $2^{100}$ pași de progresie (dar posibil, până la $\aproximativ 10$ subseturile sunt ok).

Comentariul lui JAAAY legat:

localitate euclidiană sau planuri hiperbolice

Cu alte cuvinte, creșterea cartierului nu poate fi prea rapidă.
Cu (mult timp liber) am putea desena structura cartierului pe foi de hârtie (=plan euclidian).
Putem măsura o distanță (euclidiană) între noduri cu rigla noastră. Indiferent de câți vecini de vecini tragem, distanța medie dintre noduri ar trebui să rămână (aproximativ) egală.
Dacă lipim două margini opuse ale hârtiei, putem simula proprietatea ciclului pentru o direcție. Având în vedere această opțiune, distanța (min) dintre două noduri specifice este întotdeauna egală - indiferent de când am început să desenăm această structură. (După trasarea întregului ciclu în două direcții trebuie să tăiem hârtia la dimensiunea potrivită. La margine continuăm măsura la marginea opusă hârtiei).

Un nod poate fi doar pe maximum 3 foi. Dacă mai multe numere sunt pe două foi diferite (2-tori), toate se află pe o singură linie (1-tor) - ca la intersecția a doi 2-tori.