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

Ошибки для $\mathsf{LWE}$

флаг in
C.S.

Почему мы принимаем гауссовские ошибки в $\mathsf{LWE}$?

Почему, например, мы не берем равномерные ошибки?

49
0 + 0
Рейтинг:2
avatar Crypto
флаг in
Stanley

Есть несколько основных причин, по которым мы используем гауссианы для ошибок:

  • Это упрощает жесткие доказательства безопасности, или, по крайней мере, большинство доказательств надежности основаны на распределении ошибок по Гауссу.

  • Они создают малые векторы, которые точно аппроксимируют равномерное распределение ошибок для любой решетки (см. здесь)

Есть проблемы с истинными гауссовыми распределениями, в основном из-за того, что их нельзя очень эффективно выбирать. Вот почему мы склонны использовать распределения, подобные Гауссу, как вы выразились.

0 + 0
Mark avatar
флаг ng
Mark
стоит отметить, что «истинные гауссианы» здесь следует читать как истинные *дискретные* гауссианы. На самом деле чрезвычайно эффективно выбирать настоящие *непрерывные* гауссианы, скажем, с помощью [преобразования Бокса-Мюллера](https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform). Затем их можно [округлить] (https://eprint.iacr.org/2017/1025), чтобы получить распределение, близкое к дискретному гауссову, которого часто бывает достаточно. Обратите внимание, что при этом что-то теряется --- вам нужна более точная выборка. Это количественно определено на странице 37 связанной статьи.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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