O secvență ciclică poate fi produsă cu
$$s_{i+1} = s_i^a \mod N$$
cu $N = P \cdot Q$ și $P = 2\cdot p+1$ și $Q = 2\cdot q\cdot r+1$ și $r = 2\cdot u \cdot v \cdot w +1$ cu $P,Q,p,q,r,u,v,w$ numere prime diferite
Acum putem proiecta un număr aleatoriu $x_R$ într-un subspațiu de dimensiune 2$(r-1)+4$ cu
$$s_R = x_R^{\beta} \mod N$$
$$\beta = 2\cdot p \cdot q \cdot n \mod \phi(N)$$
cu un factor $n$ la alegere.
Dacă acum folosim o rădăcină primitivă $\alpha$ din $r$ putem produce o secvență ciclică cu:
$$s_{R_{i+1}} = s_{R_i}^\alpha \mod N $$
În cele mai multe cazuri, va avea o lungime $r-1$. Dacă $s_r =0$ sau $s_r =1$ sau pentru $n \equiv r \mod \phi(N)$ obținem doar o lungime de ciclu de $1$. Acestea pot fi testate și ignorate (în total $4$ diferite astfel de valori).
Deci în aproape toate cazurile proiectăm valoarea aleatoare $x_R$ la un membru al uneia din două secvenţe cu lungime $r-1$.
De cele mai multe ori un membru al secvenței $S_1$ cu excepția cazului în care $X_R$ este un multiplu al $P \mod N$ decât va face parte din secvență $S_2$ (cu excepția cazurilor speciale menționate mai sus).
După cum am definit $r=2\cdot u \cdot v \cdot w +1$ cu numere prime $u,v,w$ putem folosi $r$rădăcina primitivă a lui $\alpha$ pentru a produce 3 direcții
$$\alpha_1 = \alpha^{2vw} \mod \phi(N)$$
$$\alpha_2 = \alpha^{2uw} \mod \phi(N)$$
$$\alpha_3 = \alpha^{uv} \mod \phi(N)$$
cu asta $\alpha_1$,$\alpha_2$,$\alpha_3$ span a $u \times v \times 2w$ spaţiu.
Trei funcții $f_1,f_2,f_3$ cu $f_d: s\mapsto s^{\alpha_d} \mod N$ poate traversa fiecare punct al secvenței ($f_0 : s\mapsto s^\alpha \mod N$).
Întrebare:
Valori date aleatoare $x_A$ și $x_B$ și cu aceasta proiectul lor ($x^\beta$) valori $s_A$, $s_B$ cât de greu ar fi de găsit $k$ în $s_B \equiv s_A^{\alpha^k} \mod N$ sau $k_1,k_2,k_3$ în $s_B \equiv s_A^{\alpha_1^{k_1}\cdot \alpha_2^{k_2} \cdot \alpha_3^{k_3} } \mod N$ (presupunând că fac parte din aceeași secvență)
Sau, cu alte cuvinte, există o modalitate mai rapidă decât aplicarea $f_0$ sau $f_1,f_2,f_3$ de mai multe ori până la meci?
(adversarul cunoaște și funcțiile inverse ale $f_d$ cu rudele lor $\bar{\alpha_d}$)
Scopul este de a cripta relația dintre punctele 3D fără a o reduce la o problemă 1D (cum este pentru $g^i \mod P_{rime}$)
întrebări secundare:
Cât de mare așa $r$ trebuie să fie în siguranță?
Ar cunoașterea de $\beta$, $\alpha$ ajuta adversarul să factorizeze $N$ (presupunând că am ales un factor important $n$)?
În cazul în care există o cale mult mai rapidă ar fi un factor $r=2u+1$ cu 3 rădăcină primitivă mai bine?
Rezolvarea procesului:
Pentru a fi în siguranță $N$ trebuie să fie suficient de mare pentru a evita factorizarea. Cu această abordare avem o scară $N$ cât de mare ne dorim, păstrând în același timp dimensiunea secvenței țintă $r-1$.
Fără factorizare, un adversar nu ar putea calcula $\phi(N)$ și cu asta nu poate face pași mari.
Pentru a găsi o potrivire a $s_A$, $s_B$ el poate calcula toți membrii unei suprafețe produse cu $f_1,f_2$ (aplicat $s_A$) și o linie cu $f_3$ (aplicat $s_B$).
Dacă definim calculul $f_d$ ca o etapă de calcul (cu cost constant) ar fi nevoie $O(u\cdot v +w)$ pași pentru a găsi o potrivire.
În cifre ar fi de ex. un 150 de biți $r$ cu $4096$ pic $N$ suficient? Dacă nu există o cale mai rapidă $\aproximativ 2^{100}$ pașii necesari pentru calcul $s_A$ din $s_B$.
Sau se poate face mai repede?
Exemple de numere (pentru testare):
$N = 4151547901$, $P = 54959$, $Q=75539 = 2\cdot179 \cdot 211 +1$
$r = 211 = 2 \cdot 3 \cdot 5 \cdot 7 +1$
$\beta = 2qp = 9837482$
$\alpha = 17, \alpha_1 = 882104001, \alpha_2 = 2662481205, \alpha_3 = 3818265481$
(unele legate întrebare cu mai multe informatii)
