Регистрация Войти
Рейтинг:1
JamDiveBuddy avatar Crypto

Как определить, больше ли точка, чем n/2?

флаг cn
JamDiveBuddy

Как мы можем определить, является ли закрытый ключ, связанный с точкой на EC, меньше или больше 1/2 $n$, куда $n$ порядок?

84
1 + 4
fgrieu avatar
флаг ng
fgrieu
Первым шагом к определению чего-либо является определение этого. Как вы _определяете_, что точка $P$ кривой "меньше, чем $n/2$"? Вы имеете в виду $\exists x\in\mathbb N$ с $x\cdot G=P$ и $x
7
Ответить
JamDiveBuddy avatar
флаг cn
JamDiveBuddy
да, это то, что я имею в виду. Где x меньше n/2.
0
Ответить
kodlu avatar
флаг sa
kodlu
Пожалуйста, отредактируйте вопрос, уточнив, что
2
Ответить
Fractalice avatar
флаг in
Fractalice
Это определение плохо определено, поскольку $[x]P = [x+n]P$. Хотя определение @fgrieu в порядке)
0
Ответить
Рейтинг:4
poncho avatar Crypto
флаг my
poncho

Как мы можем определить, является ли закрытый ключ, связанный с точкой на EC, меньше или больше, чем $1/2 п$, куда $n$ порядок?

Очевидный способ — вычислить дискретный журнал закрытого ключа (достижимый в $O(\sqrt{n})$ шаги и сравнить.

Кроме того, можно показать, что нет значительно более дешевого способа — учитывая Oracle, который, учитывая точку, вычисляет, где дискретный журнал больше или меньше, чем $1/2 п$, мы можем вычислить дискретный журнал с $\log_2{n}$ запросы (плюс несколько относительно дешевых операций); следовательно, этот Oracle не может быть дешевле, чем $1 / \log_2{n}$ раз дешевле, чем описанный выше наивный подход.

0 + 1
István András Seres avatar
флаг cf
István András Seres
Иными словами, это невозможно, если DLog не прост. Говоря более формально, старший бит дискретного логарифма является хардкорным битом [Blum-Micali '81]. Кроме того, вы можете сгенерировать PRNG из этого хардкорного бита.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.