Может ли злоумышленник найти один из соответствующих закрытых ключей с гораздо меньшими затратами, чем поиск закрытого ключа для конкретного ключа?
Нет, и это доказуемо (и не зависит от используемой технологии).
Предположим, что у нас есть черный ящик, который может принимать $к$ разные открытые ключи $a_1G, a_2G, ..., a_kG$, и восстановить $a_iG$ (для некоторых $я$) в $о(\sqrt{n})$ время.
Затем, вот как мы могли бы использовать этот черный ящик, чтобы, имея один открытый ключ $aG$, восстановить закрытый ключ $а$ в $о(\sqrt{n})$ время. Мы будем:
Выбирать $к$ случайные значения $r_1, r_2, ..., r_k$, и вычислить последовательность $r_1(aG), r_2(aG), ..., r_k(aG)$, который (путем определения $b_i = r_i а$) можно рассматривать как $b_1G, b_2G, ..., b_kG$
Дайте последовательность $b_1G, b_2G, ..., b_kG$, который восстановит $b_i$
Мы вычисляем $a = r_i^{-1}b_i$, и, таким образом, восстановить ключ.
Действия в дополнение к вызову черного ящика $ О (к) $ времени, которым можно пренебречь при разумных размерах $к$.
Обратите внимание, что последовательность $b_1G, b_2G, ..., b_kG$ распределен равномерно, и, следовательно, даже если черный ящик является вероятностным, он все равно позволит нам восстановить открытый ключ.
