Эффективные модульные решетки и их кратчайшие векторы

Основная информация

• ID статьи: 2402.10305
• Название: Effective module lattices and their shortest vectors
• Авторы: Nihar Gargava, Vlad Serban, Maryna Viazovska, Ilaria Viglino
• Классификация: math.NT (теория чисел), cs.IT (теория информации), math.IT (математическая теория информации)
• Время публикации: препринт arXiv, подано в феврале 2024 г., обновлено в октябре 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2402.10305v2

Аннотация

В данной работе используются результаты предыдущих исследований 1 для доказательства строгих вероятностных границ для кратчайших векторов модульных решеток над числовыми полями. Кроме того, путем установления асимптотических формул для подсчета матриц фиксированного ранга с элементами из алгебраических целых чисел и ограниченной евклидовой длиной, авторы доказывают приближенную формулу Роджерса для дискретных наборов модульных решеток, полученных из алгебраических кодов. Это, в свою очередь, означает, что оценки моментов из 1 и указанные выше границы для кратчайших векторов также применимы к достаточно большим дискретным наборам модульных решеток.

Исследовательский контекст и мотивация

Предпосылки проблемы

1. Центральная проблема криптографии решеток: Проблема кратчайшего вектора (SVP) является центральной в криптографии решеток, заключаясь в поиске длины кратчайшего ненулевого вектора в решетке. Существование быстрых алгоритмов остается открытым вопросом с публичными конкурсами, приглашающими исследователей представить свои алгоритмы.
2. Известные результаты для случайных решеток: Для решеток Хаара теорема 1 дает точное предсказание длины кратчайшего вектора: $1-\frac{\log\log d}{d} \leq \frac{\lambda_1(\Lambda)}{\gamma(d)} \leq 1+\frac{\log\log d}{d}$ где $\gamma(d) \approx \sqrt{\frac{d}{2\pi e}}$ — радиус единичного объема шара в $d$-мерном пространстве.
3. Особенности модульных решеток: Модульные решетки — это решетки с дополнительной алгебраической структурой, широко применяемые в эффективной криптографической реализации, такие как обучение с ошибками на кольцах (Ring-LWE) и проблема коротких целых решений (SIS).
4. Исследовательские вызовы: Установление асимптотических оценок, аналогичных теореме 1, для модульных решеток значительно сложнее, так как требует понимания поведения при росте степени числового поля.

Основные вклады

1. Вероятностные границы для кратчайших векторов модульных решеток: Доказано, что для модульных решеток ранга $t$ при $t \geq 27$ существуют строгие вероятностные границы, аналогичные случайным решеткам (теорема 3).
2. Эффективная формула Роджерса: Установлена приближенная формула Роджерса для дискретных наборов модульных решеток, построенных из алгебраических кодов (теорема 15).
3. Асимптотические формулы для подсчета матриц: Обобщены результаты Кацнельсона на общие числовые поля, получены асимптотические формулы для подсчета матриц фиксированного ранга (теорема 4).
4. Мост между теорией и практикой: Доказано, что теоретические результаты применимы к эффективным конструкциям из алгебраических кодов, имеющим вычислительное и теоретико-кодовое значение.

Подробное описание методов

Определение задачи

Исследование вероятностного распределения длины кратчайшего вектора $\lambda_1(\Lambda)$ в модульных решетках $\Lambda \subseteq K^t \otimes \mathbb{R}$ ранга $t$ над числовым полем $K$, в частности асимптотическое поведение при росте степени числового поля.

Основная теоретическая база

1. Модульное пространство решеток

Модульная решетка определяется для пары $(g,M)$, где $g \in GL_t(K \otimes \mathbb{R})$, $M \subseteq K^t$ — конечно порожденный $O_K$-модуль, удовлетворяющий: $\text{vol}(K^t \otimes \mathbb{R}/(g^{-1} \cdot M)) = 1$

с внутренним произведением: $\langle x,y \rangle = |\Delta_K|^{-\frac{2}{\deg K}} \text{tr}(x\bar{y})$

2. Классификация по классам Штейница

Каждая модульная решетка имеет класс Штейница $[\Lambda] \in \text{cl}(K)$, определяемый классами дробных идеалов: $[\Lambda] = [I] \in \text{cl}(K)$ где $I$ порождается всеми определителями $t$-элементных наборов векторов из $M$.

3. Конструкция поднятия алгебраических кодов

Для неразветвленного простого идеала $P \subseteq O_K$ и размерности $s$ определяется: $L(P,s) = \{\beta\pi_P^{-1}(S) | S \subseteq k_P^t \text{ — } s\text{-мерное } k_P\text{-подпространство}\}$ где $\beta = N(P)^{-(1-\frac{s}{t})\frac{1}{[K:\mathbb{Q}]}}$ обеспечивает единичный кообъем.

Технические инновации

1. Эффективизация формулы Роджерса

Ключевая техника заключается в доказательстве того, что для достаточно больших $N(P)$: $\frac{1}{\#L(P,s)} \sum_{\Lambda \in L(P,s)} \left(\sum_{v \in \Lambda^n} g(v)\right) \to \sum_{m=0}^n \sum_{\substack{D \in M_{m \times n}(K) \\ \text{rk}(D)=m \\ D \text{ — строчно-редуцированная}}} \mathcal{D}(D)^{-t} \int_{x \in K_R^{t \times m}} g(xD)dx$

2. Обработка явления понижения ранга

Лемма 13 решает критическую проблему понижения ранга: когда $x \in M_{t \times n}(O_K)$ удовлетворяет $\text{rk}(\pi_P(x)) < \text{rk}(x)$, имеет место: $\|x\| \geq C N(P)^{\frac{1}{m[K:\mathbb{Q}]}}$

Это гарантирует, что для достаточно больших $N(P)$ матрицы с пониженным рангом выталкиваются из носителя функции $g$.

3. Тонкий анализ подсчета матриц

Предложение 19 устанавливает критическую асимптотическую оценку: $\left|\sum_{\substack{A \in M_{t \times n}(O_K) \\ \text{rk}(A)=m}} g(\beta A)\beta^{mtd} - \sum_{D \in R_{m,n}(K)} \frac{1}{\mathcal{D}(D)^t} \int_{M_{t \times m}(K_R)} g(xD)dx\right| \ll \beta^\delta$

Экспериментальная установка

Теоретическая схема верификации

Данная работа в основном является теоретической, но предоставляет следующую верификацию:

1. Выбор числовых полей: Основное внимание уделяется круговым полям $K = \mathbb{Q}(\mu_k)$, так как они удовлетворяют свойству Богомолова.
2. Диапазон параметров:
   • Ранг $t \geq 27$ (техническое ограничение, возможно не оптимальное)
   • Размерность $s$ удовлетворяет $1-\frac{s}{t} < \frac{1}{n}$
3. Асимптотический режим: Рассматривается поведение при $k \to \infty$, соответствующее степени $d = \phi(k) \to \infty$.

Результаты экспериментов

Основные результаты

Теорема 3 (границы для кратчайших векторов модульных решеток)

Для фиксированного $t \geq 27$, кругового поля $K = \mathbb{Q}(\mu_k)$, $d = t \cdot \deg K = t\phi(k)$, случайная по Хаару модульная решетка единичного кообъема $\Lambda \subseteq K^t \otimes \mathbb{R}$ удовлетворяет:

При $k \to \infty$ с вероятностью $1-o(1)$: $1-\frac{\log\log k}{d} \leq \frac{k^{-\frac{1}{d}}\lambda_1(\Lambda)}{\gamma(d)} \leq 1+\frac{\log\log k}{d}$

Теорема 4 (асимптотическая формула подсчета матриц)

Для $m \leq n < t$, пусть $N(T;m,n,t,K)$ обозначает число матриц размера $n \times t$ с коэффициентами в $O_K$, рангом $m$ и нормой каждого элемента, ограниченной $T$, тогда: $N(T;m,n,t,K) = C \cdot T^{mt \deg K} + O(T^{mt \deg K - 1 + \varepsilon})$

Результаты оценок моментов

Теорема 38 (общие оценки моментов)

Для класса числовых полей $S$, удовлетворяющих свойству Богомолова, существуют явные константы такие, что $n$-й момент удовлетворяет: $\omega_K^n \cdot m_n\left(\frac{V}{\omega_K}\right) \leq \mathbb{E}[(\#B \cap \Lambda \setminus \{0\})^n] \leq \omega_K^n \cdot m_n\left(\frac{V}{\omega_K}\right) + E_{n,t,K} \cdot (V+1)^{n-1}$

где член ошибки $E_{n,t,K} \leq C \cdot (td)^{(n-2)/2} \cdot \omega_K^{n^2/4} \cdot Z(K,t,n) \cdot e^{-\varepsilon \cdot d(t-t_0)}$.

Предложение 39 (точные результаты для второго момента)

Для круговых полей $K_i = \mathbb{Q}(\zeta_{k_i})$, $t \geq 27$, шара $B$ объема $V$: $V^2 + V \cdot k_i \leq \mathbb{E}[(\#B \cap \Lambda \setminus \{0\})^2] \leq V^2 + V \cdot k_i \cdot (1 + C \cdot e^{-\varepsilon \cdot d_i(t-t_0)})$

Связанные работы

Классические результаты

1. Роджерс (1947): Первое рассмотрение эффективной версии теоремы о среднем значении Зигеля
2. Кацнельсон (1994): Подсчет матриц фиксированного ранга над $\mathbb{Q}$
3. Шмидт (1967): Оценки высоты алгебраических подпространств

Современные разработки

1. Алгоритмы редукции решеток: Полный анализ алгоритма BKZ
2. Криптография модульных решеток: Проблемы Ring-LWE и модульного LWE
3. Теория равнораспределения: Равнораспределение точек Гекке

Позиционирование вклада данной работы

Данная работа обобщает классическую формулу Роджерса на эффективные конструкции модульных решеток, устанавливая мост между теорией и вычислениями.

Заключение и обсуждение

Основные выводы

1. Теоретический прорыв: Впервые установлены вероятностные границы для кратчайших векторов модульных решеток, аналогичные случайным решеткам
2. Методологические инновации: Разработаны новые техники для работы с поднятиями алгебраических кодов
3. Прикладная ценность: Предоставлена теоретическая основа для криптографии решеток

Ограничения

1. Технические ограничения: Условие $t \geq 27$ может быть не оптимальным, есть место для улучшений
2. Ограничения на числовые поля: Основные результаты применимы к полям, удовлетворяющим свойству Богомолова
3. Вычислительная сложность: Константы в практических вычислениях могут быть значительными

Направления будущих исследований

1. Улучшение границ: Снижение требования на $t$ до более практичных значений (например, 3, 4, 5)
2. Расширение класса полей: Рассмотрение более общих числовых полей
3. Алгоритмические приложения: Преобразование теоретических результатов в практические алгоритмы редукции решеток

Глубокая оценка

Достоинства

1. Техническая глубина: Искусное решение технических трудностей, таких как понижение ранга
2. Теоретическая полнота: Установлен полный каркас от теории к приложениям
3. Инновационность: Впервые применена эффективизация формулы Роджерса к модульным решеткам
4. Практическая значимость: Предоставлены важные теоретические инструменты для криптографии решеток

Недостатки

1. Ограничения параметров: Требование $t \geq 27$ может быть чрезмерно строгим для практических приложений
2. Сложность доказательств: Технические доказательства достаточно сложны, что затрудняет восприятие
3. Отсутствие численной верификации: Не приведены конкретные численные эксперименты для проверки теоретических результатов

Влияние

1. Теоретический вклад: Значительный прогресс в теории модульных решеток
2. Перспективы приложений: Важное значение для криптографии решеток и теории кодирования
3. Методологическая ценность: Разработанные техники могут быть применены к другим связанным проблемам

Области применения

1. Криптография решеток: Анализ безопасности криптосистем на основе модульных решеток
2. Теория кодирования: Конструкция эффективных кодов коррекции ошибок
3. Приложения в теории чисел: Исследование диофантовых приближений над числовыми полями

Библиография

Данная работа в основном опирается на предыдущие исследования авторов 1 Gargava, Serban, Viazovska. "Moments of the number of points in a bounded set for number field lattices" (arXiv:2308.15275v2, 2023), а также цитирует классические работы Роджерса (1947), Кацнельсона (1994), Шмидта (1967) и других.

Общая оценка: Это высокачественная теоретическая математическая работа, достигшая значительного прогресса в теории модульных решеток. Несмотря на высокие технические требования и некоторые ограничения параметров, она предоставляет важную теоретическую основу для криптографии решеток и смежных областей. Основная ценность работы заключается в установлении моста между теорией и практическими конструкциями, что имеет существенное значение для развития данной области.