Naor – Reingoldova pseudonáhodná funkce - Naor–Reingold pseudorandom function - Wikipedia

V roce 1997 Moni Naor a Omer Reingold popsal efektivní konstrukce pro různé kryptografické primitivy v soukromém klíči i kryptografie veřejného klíče. Jejich výsledkem je konstrukce efektivní pseudonáhodná funkce. Nechat p a l být prvočísla s l |p-1. Vyberte prvek G ∈ ${ displaystyle { mathbb {F} _ {p}} ^ {*}}$ z multiplikativní pořadí l. Pak pro každého (n + 1)-dimenzionální vektor A = (A₀,A₁, ..., A_n)∈ ${ displaystyle ( mathbb {F} _ {l}) ^ {n + 1}}$ definují funkci

{ displaystyle f_ {a} (x) = g ^ {a_ {0} cdot a_ {1} ^ {x_ {1}} a_ {2} ^ {x_ {2}} ... a_ {n} ^ {x_ {n}}} in mathbb {F} _ {p}}

kde X = X₁ … X_n je bitová reprezentace celé číslo X, 0 ≤ X ≤ 2ⁿ⁻¹, v případě potřeby s některými dalšími úvodními nulami.^[1]

Příklad

Nechat p = 7 a l = 3; tak l |p-1. Vybrat G = 4 ∈ ${ displaystyle { mathbb {F} _ {7}} ^ {*}}$ multiplikativní objednávky 3 (od 4³ = 64 ≡ 1 mod 7). Pro n = 3, A = (1, 1, 2, 1) a X = 5 (bitová reprezentace 5 je 101), můžeme vypočítat ${ displaystyle f_ {a} (5)}$ jak následuje:

{ displaystyle f_ {a} (x) = g ^ {a_ {0} cdot a_ {1} ^ {x_ {1}} a_ {2} ^ {x_ {2}} ... a_ {n} ^ {x_ {n}}} in mathbb {F} _ {p}}

{ displaystyle f_ {a} (5) = 4 ^ {1 cdot 1 ^ {1} 2 ^ {0} 1 ^ {1}} = 4 ^ {1} = 4 in mathbb {F} _ { 7}}

Účinnost

Hodnocení funkce ${ displaystyle f_ {a} (x)}$ v Naor – Reingold stavbu lze provést velmi efektivně. Výpočet hodnoty funkce ${ displaystyle f_ {a} (x)}$ v daném okamžiku je srovnatelný s jedním modulární umocňování a n-modulární násobení. Tuto funkci lze vypočítat paralelně pomocí prahových obvodů s omezenou hloubkou a velikostí polynomu.

The Naor – Reingold funkce může být použita jako základ mnoha kryptografické systémy včetně symetrické šifrování, ověřování a digitální podpisy.

Zabezpečení funkce

Předpokládejme, že útočník vidí několik výstupů funkce, např. ${ displaystyle f_ {a} (1) = g ^ {a_ {1}}, f_ {a} (2) = g ^ {a_ {2}}, f_ {a} (3) = g ^ {a_ { 1} a_ {2}}}$ , ... ${ displaystyle f_ {a} (k) = g ^ {a_ {1} ^ {x_ {1}} a_ {2} ^ {x_ {2}} ... a_ {n} ^ {x_ {n}} }}$ a chce počítat ${ displaystyle f_ {a} (k + 1)}$ . Předpokládejme pro jednoduchost X₁ = 0, pak musí útočník vyřešit výpočetní Diffie – Hellman (CDH) mezi ${ displaystyle f_ {a} (1) = g ^ {a_ {1}}}$ a ${ displaystyle f_ {a} (k) = g ^ {a_ {2} ^ {x_ {2}} ... a_ {n} ^ {x_ {n}}}}$ dostat ${ displaystyle f_ {a} (k + 1) = g ^ {a_ {1} a_ {2} ^ {x_ {2}} tečky a_ {n} ^ {x_ {n}}}}$ . Obecně se stěhuje z k na k + 1 změní bitový vzor, pokud k + 1 je síla 2, lze exponenta rozdělit ${ displaystyle f_ {a} (k + 1)}$ takže výpočet odpovídá výpočtu Diffie – Hellman klíč mezi dvěma dřívějšími výsledky. Tento útočník chce předpovědět další sekvence živel. Takový útok by byl velmi špatný - ale je také možné ho zahnat tím, že se zapojíte skupiny s tvrdým Problém Diffie – Hellman (DHP).

Příklad:Útočník vidí několik výstupů funkce, např. ${ displaystyle f_ {a} (5) = 4 ^ {1 ^ {1} 2 ^ {0} 1 ^ {1}} = 4 ^ {1} = 4}$ , stejně jako v předchozím příkladu, a ${ displaystyle f_ {a} (1) = 4 ^ {1 ^ {0} 2 ^ {0} 1 ^ {1}} = 4 ^ {1} = 4}$ . Poté chce útočník předpovědět další prvek sekvence této funkce, ${ displaystyle f_ {a} (6)}$ . Útočník však nemůže předpovědět výsledek ${ displaystyle f_ {a} (6)}$ z vědění ${ displaystyle f_ {a} (1)}$ a ${ displaystyle f_ {a} (5)}$ .

Existují další útoky, které by byly velmi špatné pro generátor pseudonáhodných čísel: uživatel očekává, že z výstupu získá náhodná čísla, takže stream by samozřejmě neměl být předvídatelný, ale ještě více by měl být nerozeznatelný od náhodného řetězce. Nechat ${ displaystyle { mathcal {A}} ^ {f}}$ označit algoritmus ${ displaystyle { mathcal {A}}}$ s přístupem k věštci pro vyhodnocení funkce ${ displaystyle f_ {a} (x)}$ . Předpokládejme rozhodný předpoklad Diffie – Hellman platí pro ${ displaystyle mathbb {F} _ {p}}$ , Naor a Reingold ukaž to pro každého pravděpodobnostní polynomiální čas algoritmus ${ displaystyle { mathcal {A}}}$ a dostatečně velký n

{ displaystyle { text {Pr}} [{ mathcal {A}} ^ {f_ {a} (x)} (p, g) až 1] - { text {Pr}} [{ mathcal { A}} ^ {R} (p, g) na 1]}

je zanedbatelný.

První pravděpodobnost je převzata volbou semene s = (p, g, a) a druhá pravděpodobnost je převzata náhodným rozdělením indukovaným na p, g ${ displaystyle { mathcal {I}} { mathcal {G}} (n)}$ , generátor instance a náhodný výběr funkce ${ displaystyle R_ {a} (x)}$ mezi množinou všech ${ displaystyle {0,1 } ^ {n} to mathbb {F} _ {p}}$ funkce.^[2]

Lineární složitost

Jedno přirozené měřítko toho, jak užitečná může být sekvence kryptografické účely je jeho velikost lineární složitost. Lineární složitost an n-prvková sekvence W (X), X = 0,1,2,…,n - 1, přes prsten ${ displaystyle { mathcal {R}}}$ je délka l nejkratší lineární relace opakování W (X + l) = A_l−1 W (X +l−1) +… + A₀ W (X), X = 0,1,2,…, n – l -1 s A₀,…, A_l−1 ∈ ${ displaystyle { mathcal {R}}}$ , což je touto sekvencí uspokojeno.

Pro některé ${ displaystyle gamma}$ > 0,n ≥ (1+ ${ displaystyle gamma}$ ) ${ displaystyle log l}$ , pro všechny ${ displaystyle delta> 0}$ , dostatečně velký l, lineární složitost posloupnosti ${ displaystyle f_ {a} (x)}$ , 0 ≤ x ≤ 2^n-1, označeno ${ displaystyle L_ {a}}$ splňuje

{ displaystyle L_ {a} geqslant { begin {cases} l ^ {1- delta , !} & { text {, pokud}} gamma , ! geqslant 2 l ^ { left ({ tfrac { gamma , !} {2- delta , !}} right)} & { text {, if}} gamma , ! <2 konec {případů}}}

pro všechny kromě možná nanejvýš ${ displaystyle 3 (l-1) ^ {n- delta}}$ vektory a ∈ ${ displaystyle ( mathbb {F} _ {l}) ^ {n}}$ .^[3] Svázaná práce má nevýhody, konkrétně se nevztahuje na velmi zajímavý případ ${ displaystyle log p cca log n přibližně {n.}}$

Rovnoměrnost distribuce

Statistické rozdělení ${ displaystyle f_ {a} (x)}$ je exponenciálně blízko k rovnoměrné rozdělení pro téměř všechny vektory A ∈ ${ displaystyle ( mathbb {F} _ {l}) ^ {n}}$ .

Nechat ${ displaystyle { mathbf {D}} _ {a}}$ být rozpor sady ${ displaystyle {f_ {a} (x) | 0 leq x leq 2 ^ {n-1} }}$ . Pokud tedy ${ displaystyle n = log p}$ je bitová délka p pak pro všechny vektory a ∈ ${ displaystyle ( mathbb {F} _ {l}) ^ {n}}$ svázaný ${ displaystyle { mathbf {D}} _ {a} leq Delta (l, p)}$ drží, kde

{ displaystyle Delta (l, p) = { begin {cases} p ^ { left ({ tfrac {1- gamma , !} {2}} right)} l ^ { left ({ tfrac {-1} {2}} vpravo)} log ^ {2} p & { text {if}} l geqslant p ^ { gamma , !} p ^ { vlevo ({ tfrac {1} {2}} right)} l ^ {- 1} log ^ {2} p & { text {if}} p ^ { gamma , !}> l geqslant p ^ { left ({ tfrac {2} {3}} right)} p ^ { left ({ tfrac {1} {4}} right)} l ^ { left ({ tfrac {-5} {8}} right)} log ^ {2} p & { text {if}} p ^ { left ({ tfrac {2} {3}} right)}> l geqslant p ^ { left ({ tfrac {1} {2}} right)} p ^ { left ({ tfrac {1} {8}} right)} l ^ { left ({ tfrac {-3} {8}} right)} log ^ {2} p & { text {if}} p ^ { left ({ tfrac {1} {2}} right)}> l geqslant p ^ { left ({ tfrac {1} {3}} right)} end {cases}}}

a

{ displaystyle gamma = 2,5- log 3 = 0,9150 cdots}

Ačkoli se zdá, že tato vlastnost nemá žádné bezprostřední kryptografické důsledky, inverzní fakt, totiž nejednotná distribuce, pokud je pravdivá, by měl katastrofální důsledky pro aplikace této funkce.^[4]

Sekvence v eliptické křivce

The eliptická křivka Zajímavá je také verze této funkce. Zejména to může pomoci zlepšit kryptografickou bezpečnost příslušného systému. Nechat p > 3 je prvočíslo a nechť E je eliptická křivka ${ displaystyle mathbb {F} _ {p}}$ , pak každý vektor A definuje a konečná posloupnost v podskupina ${ displaystyle langle G rangle}$ tak jako:

{ displaystyle F_ {a} (x) = (a_ {1} ^ {x_ {1}} a_ {2} ^ {x_ {2}} tečky a_ {n} ^ {x_ {n}}) G}

kde ${ displaystyle x = x_ {1} tečky x_ {n}}$ je bitová reprezentace celého čísla ${ displaystyle x, 0 leq x leq 2 ^ {n-1}}$ . The Naor – Reingold sekvence eliptické křivky je definována jako

{ displaystyle u_ {k} = X (f_ {a} (k)) ; { mbox {kde}} X (P) { mbox {je úsečka}} P v E.}

^[5]

Pokud rozhodný předpoklad Diffie – Hellman drží, index k nestačí k výpočtu ${ displaystyle u_ {k}}$ v polynomiálním čase, i když útočník provádí polynomiálně mnoho dotazů na náhodný věštec.

Viz také

Poznámky

^ Naor, M., Reingold, O. „Číselně-teoretické konstrukce účinných pseudonáhodných funkcí“, Proc 38. IEEE Symp. o nadacích Comp. Sci, (1997), 458–467.
^ Boneh, Dan. „The Decision Diffie – Hellman Problem,“ ANTS-III: Proceedings of the Third International Symposium on Algorithmic Number Theory, 1998,48–63.
^ Shparlinski, Igor E. „Lineární složitost pseudonáhodné funkce Naor – Reingold,“ Inform. Process Lett, 76 (2000), 95–99.
^ Shparlinski, Igor E. „O uniformitě distribuce pseudonáhodné funkce Naor – Reingold,“ Finite Fields and their Applications, 7 (2001), 318–326
^ Cruz, M., Gomez, D., Sadornil, D. "O lineární složitosti Naor – Reingoldovy sekvence s eliptickými křivkami," Finite Fields and their Applications, 16 (2010), 329–333

Reference

Naor, Moni; Reingold, Omer (2004), „Číselně-teoretické konstrukce účinných pseudonáhodných funkcí“, Časopis Asociace pro výpočetní techniku, 51 (2): 231–262, doi:10.1145/972639.972643, S2CID 8665271.
Shparlinski, Igor (2003), Kryptografické aplikace teorie analytického čísla: složitost dolní hranice a pseudonáhodnost (první vydání), Birkhäuser Basel, ISBN 978-3-7643-6654-4
Goldreich, Oded (1998), Moderní kryptografie, pravděpodobnostní důkazy a pseudonáhodnost (první vydání), Springer, ISBN 978-3-540-64766-9

[NaorReingold-1] Naor, M., Reingold, O. „Číselně-teoretické konstrukce účinných pseudonáhodných funkcí“, Proc 38. IEEE Symp. o nadacích Comp. Sci, (1997), 458–467.

[DDHBoneh-2] Boneh, Dan. „The Decision Diffie – Hellman Problem,“ ANTS-III: Proceedings of the Third International Symposium on Algorithmic Number Theory, 1998,48–63.

[ShparlinskiLinearComplexity-3] Shparlinski, Igor E. „Lineární složitost pseudonáhodné funkce Naor – Reingold,“ Inform. Process Lett, 76 (2000), 95–99.

[ShparlinskiUniformity-4] Shparlinski, Igor E. „O uniformitě distribuce pseudonáhodné funkce Naor – Reingold,“ Finite Fields and their Applications, 7 (2001), 318–326

[EllipticNaor-5] Cruz, M., Gomez, D., Sadornil, D. "O lineární složitosti Naor – Reingoldovy sekvence s eliptickými křivkami," Finite Fields and their Applications, 16 (2010), 329–333

[1]

[2]

[3]

[4]

[5]