Iată o idee care pare să îndeplinească toate cerințele dvs. Acum, nu îndeplinește alte cerințe criptografice rezonabile; totuși nu le-ai cerut niciodată.
Iată ideea: lucrăm într-un grup de curbă eliptică de dimensiuni adecvate (de exemplu, P224) cu dimensiunea grupului $q$ (care este prim) și alegeți trei generatoare $F, G, H$ (cu relații necunoscute; poate generat folosind o metodă Hash2Curve); și:
$$f(X) = F + X$$
$$g(X) = G + X$$
$$h(X) = H + X$$
Evident, aceste operațiuni fac naveta, iar noi am făcut-o $f^i(g^j(h^k(X))) = iF + jG + kH + X$.
Trecând prin cerințele dvs.:
Dacă acum $f,g,h$, este aplicat $i,j,k$-de ori la o intrare $x$ găsirea/calcularea $x$ pentru dat $c = f^i(g^j(h^k(x)))$ ar trebui să fie cât mai greu posibil și cu aceasta luând mai mult decât $O(|i|+|j|+|k|)$ trepte.
Presupun că, în această cerință, atacatorul nu cunoaște valorile $i, j, k$ (El cunoaște intervalul relativ). În acest caz, cea mai bună căutare pe care o pot găsi pentru a verifica o valoare $c$ ia $O( \sqrt{i \cdot j \cdot k } )$ timp (presupunând $i \cdot j \cdot k < q$, evident); aceasta este mai mare decât $O(i + j + k)$. Această căutare se face prin luarea $0F, 1F, ..., iF$, $0G, 1G, ..., jG$, $0H, 1H, ..., kG$, împărțindu-le în două liste în care suma oricăror trei elemente din cele trei liste poate fi exprimată ca o sumă a doi dacă elementele din listă și apoi aplicând un algoritm de stil „pas mare/pas mic”.
Mai mult, metodele $f,g,h$ păstrează formatul: $X \rightarrow X$, astfel încât fiecare ieșire poate servi ca intrare nouă.
Atâta timp cât ești cool cu $X$ fiind setul de puncte de curbă eliptică, suntem bine aici.
Dimensiunea maximă ar trebui să fie: $|X|<2^{256}$
Cu P-224, acest lucru este adevărat.
Tehnica de calcul $f,g,h$ iar inversele lor trebuie să dureze un timp similar pentru fiecare intrare (independent de $i,j,k$).
Suntem bine aici
În plus $f,g,h$ trebuie să producă un ciclu ca $f(f(....f(x)...))=x$ cu dimensiunea $F,G,H$ cu $F \aprox G \aprox H \gg 1$
Adevărat; $f, g, h$ toate au ordine $q$, care este mult mai mare decât 1
Puteți selecta cu ușurință intervale pentru $i, j, k$ astfel încât securitatea țintă să fie îndeplinită.
Acum, singurul lucru pe care această idee nu îl oferă este că, dat $c, x$ cu $c = f^i(g^j(h^k(x)))$, este banal de calculat $c' = f^i(g^j(h^k(x')))$. Cu toate acestea, nu ai cerut niciodată să fie greu...
