Рейтинг:2

Вопрос новичка о NTRUEncrypt: маленький r(x) и проблема ближайшего вектора

флаг us

В NTRUEncrypt с общесистемными параметрами $(N, р, д)$, пусть открытый ключ Боба будет $ч(х).$

Для шифрования открытого текста $м(х)$ коэффициенты которого малы, Алисе нужно сгенерировать случайный $ г (х), $ чьи коэффициенты тоже должны быть маленькими, и вычисляет зашифрованный текст $c(x) = r(x) \times h(x) + m(x) \bmod q.$

Считается трудным найти $м(х)$ от $с(х)$ и эта трудность предположительно основана на задаче ближайшего вектора (CVP).

Мой вопрос: почему $ г (х) $ должны иметь маленькие коэффициенты в шифровании? Кажется, даже когда $ г (х) $ имеет большие коэффициенты, находя $м(х)$ от $с(х)$ по-прежнему связан с проблемой ЦВД; Это правда?

Рейтинг:1
флаг ru

Смысл создания коэффициентов $ г (х) $ small не для того, чтобы усложнить жизнь злоумышленнику, а для того, чтобы сделать жизнь возможной для предполагаемого получателя.

Напомним, что $ч(Х)$ выбирается в форме $$h(X)\equiv \frac{g(X)p}{f(X)}\pmod q$$ где коэффициенты $ф(Х)$ и $г(Х)$ маленькие и секретные, $р$ является простым малым относительно $q$ и $q$ велика по сравнению со всеми малыми величинами.

Теперь рассмотрим расшифровка который начинается с умножения $с(Х)$ к $ф(Х)$ дать $$c(X)f(X)\equiv r(X)g(X)p+m(X)f(X)\pmod q$$ если коэффициенты $f$, $г$, $м$ и $г$ все малы, то с большой вероятностью можно написать $$c(X)f(X)= r(X)g(X)p+m(X)f(X)$$ над целыми числами без редукции по модулю $q$ путем округления коэффициентов в сторону 0 (т.е. приведения в интервал $[-q/2,q/2]$). С другой стороны, если $ г (Х) $ имеет любое большое (относительно $q$) коэффициентов, мы почти наверняка не сможем этого сделать.

Если наш процесс округления прошел успешно, мы можем удалить вклад $ г (Х) $ путем уменьшения по модулю $р$ а потом восстановить $м(Х)$.

Обратите внимание, что успешность процесса округления не гарантируется по мере роста степени, поэтому NTRUEncrypt имеет вероятность сбоя, зависящую от размера коэффициента и степени, которую мы должны стараться поддерживать на низком уровне. Отметим также, что отказ может зависеть от выбора $м(Х)$ что может позволить злоумышленнику активно получать информацию о закрытом ключе (опять же с вероятностью, которую мы пытаемся сохранить небольшой).

Вы правы, что $r(X)\pmod q$ могут быть восстановлены путем решения CVP, независимо от размера его коэффициентов (при условии, что коэффициенты $м(Х)$ маленькие).

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

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