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

Решающее предположение Диффи-Хеллмана о группе квадратичных вычетов

флаг yt
Sean

Рассмотрим решение Диффи-Хеллмана (DDH) по $QR_n$ (квадратичная группа вычетов над $n=pq$ куда $р$ и $q$ являются безопасными простыми числами). Согласно статье Боне, DDH должно быть трудно $QR_n$ (https://link.springer.com/chapter/10.1007/BFb0054851):

[DDH] Учитывая три случайных выборки $г^х, г^у, г^г$ трудно сказать, если $ г = х * у $.

Мне интересно: если дать доп. $х^2$ $мод$ $n$, эта проблема еще не решена $QR_n$? (Интуиция такова, что вычисление корня $х^2$ сложно, поэтому интуитивно этот квадрат не должен давать дополнительной информации для решения DDH. Исключением может быть утечка символов Якоби/Лежандра, но случайный выбор $z$ можно исправить соответственно?).

109
0 + 8
Ievgeni avatar
флаг cn
Ievgeni
учитывая $x^2$ или $g^{x^2}$?
1
Ответить
poncho avatar
флаг my
poncho
"так что интуитивно этот квадрат не должен пропускать никакой дополнительной информации"; на самом деле, с точки зрения доказуемости, все наоборот - если бы это было легко вычислить, ничего бы не утекло (злоумышленник мог бы вычислить это сам, поэтому передача значения злоумышленнику ничего не говорит ему, что он т уже знаю). Наиболее очевидный контрпример, значение $g^{xy}$ также сложно вычислить, но если указать и это значение, задача злоумышленника становится тривиальной. Я не говорю, что присвоение значения $g^{x^2}$ упрощает задачу злоумышленника; Я говорю, что это не тривиально, чтобы показать.
0
Ответить
Sean avatar
флаг yt
Sean
Учитывая $x^2$ (не $g^{x^2}$). Итак, мой вопрос: если с учетом этого дополнительного $ x ^ 2 $, будет ли решение DH по-прежнему сложным (в контексте группы квадратичных вычетов)
0
Ответить
Ievgeni avatar
флаг cn
Ievgeni
но мы можем легко вычислить квадратные корни из $x^2$ в $\mathbb{R}$, и один из этих корней будет равен $x^2$. Таким образом, легко проверить, является ли это ddh-кортежем или нет.
0
Ответить
Geoffroy Couteau avatar
флаг cn
Geoffroy Couteau
Интересный вопрос! Я не вижу очевидного сведения к стандартным предположениям. Предложение: вы могли бы начать с рассмотрения упрощенной версии задачи, где при заданном $x^2 \bmod \phi(n)/4$ ваша задача состоит в том, чтобы отличить $g^x$ от случайного элемента $\mathsf {QR}_n$.
0
Ответить
Sean avatar
флаг yt
Sean
Относительно комментария Левгени: Но в $QR_n$ это $n$ является составным RSA, тогда попытка найти корень квадратного остатка эквивалентна разложению $n$ на множители. См., например, статью Куто о еврокриптове17: https://link.springer.com/chapter/10.1007/978-3-319-56614-6_11.
0
Ответить
Sean avatar
флаг yt
Sean
Вот аналогичный вопрос, который я разместил вчера: -- какая разница, что модуль равен $\phi(n)/4$ или $n$? https://crypto.stackexchange.com/questions/91786/группа-квадратичного-остатка-по-блюму-целому
0
Ответить
Sean avatar
флаг yt
Sean
Теперь я вижу точку $\phi(n)/4$ -- для $x$ в показателе степени $g^x$. Трудность здесь в том, что если выставить тотиент $\phi(n)$, то $n$ будет факторизовано. Что мы могли бы сделать, так это попросить доверенный сервер предоставить $r \phi(n)$, где $r$ — большое случайное целое число. Таким образом получается $x^2$, конгруэнтное над $r\phi(n)$. Таким образом, задача немного меняется: \n Учитывая $x^2 \mod \phi(n)/4*r$, где $r$ и $\phi(n)$ неизвестны, можно ли отличить $g^ x$ с эффективным алгоритмом?
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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