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

Как BDD может решить LWE, если матрица A имеет полный ранг?

флаг us
Sam Jaques

Я пытаюсь выяснить, как именно решение различных общих задач решетки может решить LWE и, в частности, BDD. Все, что я нашел, говорит о том, что, поскольку образец LWE $(A,b=As+e\mod q$), то решетка $L_q(A)=\{v : \существует x:Ax=v\mod q\}$ содержит $Как$, так $b$ находится на расстоянии $\Верт е\Верт$ этой решетки. Следовательно, если решатель BDD может решить для расстояний до $\Верт е\Верт $, на входе $b$ он должен вернуться $Как$.

Однако, если $А$ является $n\n$ матрица (типа как у Фродо), то с большой вероятностью $А$ имеет полный ранг выше $\mathbb{F}_q$. Таким образом, все векторы в $\mathbb{F}_q^n$ находятся в промежутке $А$, так $L_q(A)=\mathbb{Z}^n$. Затем, поскольку $е$ также целочисленный вектор, $b\inL_q(A)$, так что BDD бесполезен: на входе $b$, он бы вернулся $b$.

Может ли BDD решить LWE здесь? Является ли приближенный SVP-решатель более естественным?

52
0 + 0
Chris Peikert avatar
флаг in
Chris Peikert
Для Фродо и ему подобных вектор коэффициентов $x$ точки решетки является «коротким», поэтому $Ax$ не покрывает все $\mathbb{Z}_q^n$. См. представленное FrodoKEM моделирование этой «нормальной формы» LWE как проблемы BDD для подходящей настройки решетки и близлежащего вектора BDD.
0
Ответить
Sam Jaques avatar
флаг us
Sam Jaques
В представлении FrodoKEM объясняется, как BDDwDGS сводится к LWE, затем приводятся атаки, основанные на uSVP, но я не могу найти атаку, основанную непосредственно на BDD (т. е. сокращение от LWE до BDD). Я нашел сокращение от uSVP до BDD, так что можно было сделать LWE=>uSVP=>BDD, но это все?
0
Ответить
Chris Peikert avatar
флаг in
Chris Peikert
Раздел 5.2.2 имеет сокращение LWE
0
Ответить
Sam Jaques avatar
флаг us
Sam Jaques
Я видел это и пережевывал детали (в моем последнем комментарии, вероятно, было => назад). Таким образом, uSVP может решить LWE в нормальной форме довольно напрямую, но BDD должен сначала «пройти» uSVP, чтобы решить LWE?
0
Ответить
Chris Peikert avatar
флаг in
Chris Peikert
Не уверен, что вы имеете в виду под «BDD должен…» LWE — это просто проблема BDD среднего случая. Обратите внимание, что в разделе 5.2.3 рассматривается атака LWE/BDD, которая не проходит через uSVP.
0
Ответить
Sam Jaques avatar
флаг us
Sam Jaques
Мой первоначальный вопрос заключается в том, как рассматривать LWE как проблему BDD в среднем случае, учитывая, что используемая естественная решетка ($L_q(A)$) содержит выборку LWE $b$. В разделе 5.2.3, кажется, прямо используются короткие векторы решетки — $(v,w)\in \hat{\Lambda}$. Мой конкретный вопрос: если у меня есть решатель BDD и образец LWE нормальной формы $(A,b=As+e)$, какую решетку $L$ и какой близкий вектор $t$ я даю решателю BDD?
0
Ответить
Chris Peikert avatar
флаг in
Chris Peikert
Хорошо. Соответствующая решетка — это «$q$-ичная проверочная решетка» целочисленных векторов $z$ таких, что $[A \mid I]z = 0 \pmod{q}$. Цель $b = As + e = [A \mid I] (s,e)$ представляет собой «синдром», который задает класс смежности по решетке, полученный небольшим сдвигом решетки, по короткому вектору $(s,e )$.(Это эквивалентная концепция задачи BDD: для заданной решетки и смежного класса, полученного небольшим сдвигом, найти этот сдвиг.) Хорошее упражнение — записать явный базис для этой решетки и преобразовать $b$ в явный целевой вектор BDD в объемлющем пространстве решетки.
1
Ответить
Sam Jaques avatar
флаг us
Sam Jaques
О отлично! Именно об этом я и спрашивал, спасибо.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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