Вычислительные методы в дискретной математике

Алгоритм выборки для решёток Барнса — Уолла

Е. М. Мельничук


Аннотация: Решётки Барнса — Уолла, благодаря своим свойствам, представляют большой интерес в контексте их применения в криптографии. В частности, они могут быть использованы для построения схемы цифровой подписи на базе задачи об изоморфизме решёток. При этом для рассматриваемых решёток возникает необходимость построения эффективного алгоритма дискретной гауссовой выборки. Решётки Барнса — Уолла могут быть построены с использованием квадратичных конструкций, что позволяет применить для них алгоритм $k$-инговой гауссовой выборки при $k=2$ и $4$. Мы обобщаем данный подход и приводим алгоритм дискретной гауссовой выборки для решёток Барнса — Уолла на основе итеративной квадратичной конструкции. Построенный алгоритм позволяет для произвольного $n\in \mathbb{N}$ выбрать $x\in \text{BW}_N$, где $N=2^n$, используя цепочку решёток $(1+i)^n \text{BW}_1\subset (1+i)^{n-1} \text{BW}_1 \subset \ldots \subset \text{BW}_1$ в соответствии с дискретным гауссовым распределением.

Ключевые слова: теория решёток, решётки Барнса — Уолла, алгоритм гауссовой выборки для решёток Барнса — Уолла.

УДК: 519.7

DOI: 10.17223/2226308X/18/59