Dați (de exemplu) numere prime diferite $p,q$ cu 2 USD p+1 USD, și 4 USD p+3 USD prim de asemenea (la fel pentru $q$).
Lăsa
$$N = (4 p+3)\cdot (4 q+3)$$
Cu aceasta secvența
$$s_{i+1} = s_i^4 \mod N$$
vom avea $p\cdot q$ elemente (în majoritatea cazurilor) pentru $s_0 = r^4 \mod N$ pentru aproape toate valorile aleatorii $r$.
În funcție de ales $r$ cele legate $s_0 = r^4 \mod N$ va fi (aproape întotdeauna) un membru al 1 din 4 secvențe disjunse de lungime $p \cdot q$.
Întrebare:
$\text{ }\mathrm{ I }.$ Există o modalitate ușoară de a verifica dacă este aleatorie $r$ conduce la un membru al secvenței $S_1,S_2,S_3,S_4$?
$\mathrm{II}.$ Sau putem produce aleatoriu $r'$ care sunt toți membri ai aceleiași secvențe?
(Ambele fără a scurge informații secrete. Cele legate $s_0$ sau altul $f(r)$ poate fi de asemenea comparat)
(Reducerea acestuia la mai puțin de 4 secvențe cu aceeași dimensiune ar fi de asemenea utilă.)
Mai multe detalii: Dacă o facem $\mathrm{II}.$ trebuie să garantăm și cele aferente $s_0$ nu urmați o ordine cunoscută. De exemplu. dacă producem $r'$ cu un membru de secvență fix ales $s_m$ și $r' = s_m^{4^r} \mod N$ știm întotdeauna poziția exactă legată de $s_m$ pentru fiecare $r$ $\mapsto s_{m+r+1}$.
cazuri speciale: Pentru unii $r$ succesiunea va avea doar $p,q$ sau $1$ element. Le ignorăm aici. Pentru a evita asta trebuie să alegem $r$ cu
$$r\în[2,N-1] $$
$$r\mod (4 p+3)\not=0 $$
$$ r\mod (4 q+3)\not=0 $$
$$ r \not\in\{r_*^{2p+1} \mod N \}\land r \not\in\{r_*^{2q+1} \mod N \}$$
The adversar va putea, de asemenea, să genereze acei membri aleatori la mașina sa. Se dau 2 aleatoriu $r$ el nu ar trebui să cunoască distanța indice dintre cele legate $s_0$ printre secvența țintă. Dacă el știe cumva pentru 2 la întâmplare $r$ el nu ar trebui să fie capabil să o calculeze cu ușurință pentru o a treia întâmplare $r$ (În cele mai multe cazuri). Exponentul $\alpha = 4$ poate fi înlocuit cu un echivalent greu de calculat.
Exemplu: $N= 7849=47 \cdot 167$ va produce $4$ secvențe cu lungime $451 = 11 \cdot 41$
(plus cazuri speciale de lungime $11,41,1$)
