Atacurile multi-țintă ale cheilor publice ECC

Poate un adversar să găsească în mod rezonabil una dintre cheile private care se potrivesc la un cost mult mai mic decât găsirea cheii private pentru una anume?

Nu, și asta se poate demonstra (și este independent de tehnologia folosită)

Să presupunem că avem o cutie neagră care ar putea lua $k$ diferite chei publice $a_1G, a_2G, ..., a_kG$, și recuperați $a_iG$ (pentru unii $i$) în $o(\sqrt{n})$ timp.

Apoi, iată cum am putea folosi acea cutie neagră pentru a avea o cheie publică $aG$, recuperați cheia privată $a$ în $o(\sqrt{n})$ timp. Ne-ar:

• Selectați $k$ valori aleatorii $r_1, r_2, ..., r_k$, și calculați secvența $r_1(aG), r_2(aG), ..., r_k(aG)$, care (prin definirea $b_i = r_i a$) poate fi privit ca $b_1G, b_2G, ..., b_kG$

• Dați secvența $b_1G, b_2G, ..., b_kG$, care se va recupera $b_i$

• Noi calculăm $a = r_i^{-1}b_i$, și astfel recuperați cheia.

Pașii în plus față de invocarea cutiei negre parcurg $O(k)$ timp, care poate fi ignorat pentru dimensiuni rezonabile $k$.

Rețineți că secvența $b_1G, b_2G, ..., b_kG$ este distribuit uniform și, prin urmare, chiar dacă cutia neagră este probabilistică, ne va permite totuși să recuperăm cheia publică.