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

Группа квадратичного вычета над целым числом Блюма

флаг yt
Sean

Позволять $х$ быть случайным элементом из $QR_n$, группа квадратичных вычетов над целым числом Блюма n (где $n=p*q$ и $р$ и $q$ являются безопасными простыми числами), и $г$ генератор $QR_n$. Являются ли следующие вычислительно неразличимыми?

$$(х^2 \мод п, г^х) (r^2 \mod n, g^x)$$

Интуиция такова, что это трудно вычислить $х$ от $х^2$ и $г^х$. Можно ли это свести к некоторым стандартным предположениям?

69
0 + 4
Ievgeni avatar
флаг cn
Ievgeni
Он пропускает $\mod$ ?
0
Ответить
Sean avatar
флаг yt
Sean
Это верно. Я внес исправления.
0
Ответить
Fractalice avatar
флаг in
Fractalice
Как представляется $x\in QR_n$? Например.Если выборка производится равномерно из $[0; n\cdot ord(g))$, то они неразличимы, так как $x^2$ и $g^x$ независимы (так как $x \mod n$ и $x \mod ord(g)$ независимы).
2
Ответить
Sean avatar
флаг yt
Sean
Большое спасибо за инфу? А как насчет x^2 \mod \totient(n) дано. Тогда, я думаю, аргумент не будет применяться?
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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