Новый алгоритм семейства LLL с квантизированной Gram/Lovász-геометрией и exact-сертификатами

Аннотация

LLL-редукция давно стала одним из базовых инструментов вычислительной математики, теории чисел, криптографии и анализа решёток. Обычно LLL воспринимается как “чёрный ящик”: на вход подаётся целочисленный базис, внутри выполняется последовательная редукция, на выходе получается новый базис, который удовлетворяет классическим условиям LLL.

Но в практических задачах всё чаще возникает другая постановка. Нам нужен не просто один запуск LLL, а управляемый процесс исследования целого семейства решёток: с разными масштабами, embedding-параметрами, весами, подвыборками строк и гипотезами о скрытой структуре. В такой ситуации важно не только редуцировать базис, но и понимать:

где в базисе находятся потенциальные геометрические дефекты;
какие Lovász-позиции наиболее информативны;
какие варианты решётки стоит запускать первыми;
можно ли независимо проверить результат;
можно ли отделить эвристику от математической истины.

Так появилась система Q-LLL — Quantized-Certified Lattice Reduction.

Главная идея Q-LLL:

квантизированная геометрия наблюдает,
exact-арифметика принимает решения,
сертификат доказывает результат.

Q-LLL не заменяет классическое определение LLL-reduced базиса. Напротив, он сохраняет классическую exact-корректность. Новизна находится в другом: мы строим новую модель управления LLL-редукцией, где выбор редукционных действий направляется квантизированной Gram/Lovász-картой, а каждое изменение базиса подтверждается exact-проверкой.

1. Почему вообще понадобилось переосмыслить LLL

Классический LLL — один из самых известных алгоритмов редукции решёток. Он принимает базис решётки и постепенно улучшает его геометрию, выполняя size reduction и swap-операции, пока базис не удовлетворит Lovász-условию.

В учебной постановке задача выглядит просто:

дан один базис B
→ запустить LLL
→ получить редуцированный базис B'

Но в реальных исследовательских и прикладных сценариях часто возникает не один базис, а целое семейство вариантов:

B₁, B₂, B₃, ..., B_N

Эти варианты могут отличаться:

размерностью;
масштабами;
embedding weight;
границами ошибок;
подвыборками строк;
порядком строк;
целевой конструкцией;
параметрами backend-а.

И здесь появляется новая проблема:

если вариантов сотни или тысячи, запускать тяжёлый backend на всех — дорого и нерационально.

Нужен слой, который заранее посмотрит на геометрию решёток и скажет:

этот вариант выглядит перспективно;
этот — почти наверняка бесполезен;
в этом базисе сильный Lovász-дефект здесь;
эту позицию стоит проверить первой.

Именно эта задача привела нас к Q-LLL.

2. Классический LLL за несколько минут

Пусть дан базис решётки:

$B = (b_1, b_2, \ldots, b_n), \quad b_i \in \mathbb{Z}^m.$

Для него строится Gram–Schmidt ортогонализация:

$b_i^* = b_i - \sum_{j<i} \mu_{i,j} b_j^*,$

где:

$\mu_{i,j} = \frac{\langle b_i, b_j^* \rangle}{|b_j^*|^2},$

а также:

LLL-редуцированный базис должен удовлетворять двум основным условиям.

Первое — size reduction:

$|\mu_{i,j}| \le \frac{1}{2}, \quad j < i.$

Второе — Lovász condition:

$\delta D_{k-1} \le D_k + \mu_{k,k-1}^2 D_{k-1}.$

Для удобства введём Lovász slack:

$\Delta_k(B) =D_k + \mu_{k,k-1}^2 D_{k-1} - \delta D_{k-1}.$

Если:

$\Delta_k(B) < 0,$

то позиция (k) нарушает Lovász condition, и swap между соседними векторами $(b_{k-1})$ и является допустимым редукционным действием.

Интуитивно:

Lovász slack — это численная мера того, насколько локально базис нарушает LLL-геометрию.

Чем сильнее отрицательное значение $(\Delta_k)$ , тем более выражен локальный дефект.

3. Что делает обычный LLL

Классический LLL действует локально и последовательно:

1. Берём позицию k.
2. Делаем size reduction.
3. Проверяем Lovász condition.
4. Если условие нарушено — делаем swap.
5. Возвращаемся назад.
6. Если условие выполнено — идём дальше.

Это красивая и доказанная схема.

Но она отвечает только на вопрос:

как последовательно довести базис до LLL-reduced состояния?

Она не отвечает на другие вопросы:

где самый сильный дефект?
какую позицию стоит проверить первой?
какой из вариантов решётки наиболее перспективен?
можно ли заранее увидеть структуру без полного exact GSO?

Для этих вопросов нужен другой слой — слой наблюдения.

4. Идея Q-LLL

Q-LLL добавляет к классическому LLL новый объект:

квантизированный Gram/Lovász oracle.

Он строит приближённую карту геометрии базиса:

basis B
→ approximate Gram matrix
→ approximate GSO
→ approximate Lovász slack
→ ranked candidate positions

Но при этом есть жёсткое правило:

oracle не имеет права самостоятельно менять базис.

Он только предлагает:

позиция k выглядит подозрительно;
там вероятен Lovász-дефект;
проверь её первой.

Затем включается exact gate:

если exact Δ_k < 0,
то swap разрешён;
иначе кандидат отклоняется.

Таким образом, Q-LLL можно описать как:

LLL с новым механизмом выбора кандидатов,
но со старой строгой математической проверкой результата.

5. Чем Q-LLL отличается от классического LLL

Компонент	Классический LLL	Q-LLL
Финальный критерий reduced-базиса	классический	классический
Size reduction	exact	exact
Lovász decision	exact	exact
Порядок проверки позиций	последовательный	через quantized Lovász ranking
Approximate слой	нет	есть, advisory-only
Сертификат результата	обычно внешний/неявный	proof-carrying certificate
Independent verifier	обычно не часть workflow	встроен
Работа с семействами вариантов	не является целью	часть архитектуры
Evidence/reporting	не является целью	часть системы

Главное:

Q-LLL не меняет математику корректности LLL. Он меняет механику управления редукцией.

6. Quantized Gram/Lovász oracle

Теперь главный вопрос:

как построить approximate Lovász-карту дешевле или информативнее, чем полный exact-анализ?

Для этого Q-LLL использует квантизированное представление геометрии строк базиса.

Упрощённая схема:

integer basis rows
→ normalization
→ randomized projection / orthogonal transform
→ low-bit scalar quantization
→ approximate Gram matrix
→ approximate GSO
→ approximate Lovász slack
→ top-K candidates

Иными словами, oracle строит приближённую карту внутренних произведений между строками базиса. Из этой карты получается approximate Gram matrix, затем approximate GSO, затем approximate Lovász slack.

На этом этапе мы не утверждаем:

approximate slack = exact slack.

Мы утверждаем другое:

approximate slack может дать полезный ranking signal.

Далее точность результата обеспечивает exact gate.

7. Откуда взялась идея квантизированной геометрии

Одним из источников математического вдохновения стала идея low-bit сохранения геометрии векторов. В TurboQuant рассматривается задача онлайн-векторного квантования с контролем MSE и ошибки скалярного произведения. Там используются случайное вращение, scalar quantization, Lloyd-Max codebooks, а product-mode строится как MSE-квантизатор на (b-1) бит плюс QJL на остатке, что даёт несмещённую оценку inner product.

Но Q-LLL переносит эту идею в другой мир.

TurboQuant работает с задачей:

евклидовы векторы
→ low-bit representation
→ сохранить MSE / inner product

Q-LLL работает с задачей:

целочисленный lattice basis
→ approximate Gram
→ approximate GSO
→ approximate Lovász slack
→ exact-certified reduction

То есть мы используем не “готовую теорему для LLL”, а сам принцип:

если можно квантизированно наблюдать внутренние произведения, то можно построить приближённую карту Gram/Lovász-геометрии.

И дальше эта карта используется только как advisory layer.

8. Почему approximate слой не принимает решений

Это центральный инженерный и математический принцип Q-LLL.

Approximate слой может ошибаться. Он может переоценить или недооценить Lovász slack. Он может неправильно ранжировать кандидатов. Он может быть нестабильным на плохо обусловленном базисе.

Поэтому он не имеет права делать basis-changing operation.

В Q-LLL действует правило:

oracle proposes;
exact gate decides;
certificate proves.

На практике это означает:

1. Oracle предлагает позицию k.
2. Q-LLL вычисляет exact Lovász slack Δ_k.
3. Если Δ_k < 0, swap разрешается.
4. Если нет, кандидат отклоняется.
5. В конце весь базис проверяется exact certificate.

Это позволяет объединить две вещи:

скорость и направленность approximate наблюдения;
строгость exact-математики.

9. Evidence mode

В системе есть специальный режим evidence.

В нём запрещены:

fallback;
unsafe approximate swaps;
debug/uniform codebooks;
approximate mutation без exact gate.

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

В evidence mode результат должен содержать:

{
  "algorithm_class": "q-lll",
  "valid": true,
  "transform_matches": true,
  "exact_certified_mutations": true,
  "fair_scheduler": true,
  "final_exact_certificate": true,
  "fallback": false,
  "exact_gso_calls_during_oracle": 0
}

Поле:

exact_gso_calls_during_oracle = 0

особенно важно. Оно показывает, что quantized oracle не “подглядывал” в exact GSO при построении ranking signal.

10. Fair scheduler

Что происходит, если oracle ошибся и не предложил рабочий candidate?

Для этого в Q-LLL есть fair scheduler.

Идея:

1. Сначала пробуем top-K candidates от oracle.
2. Если ни один не проходит exact gate,
   запускаем fair exact scan.
3. Если нарушение Lovász существует,
   exact scan его найдёт.
4. Если нарушений нет,
   final certificate завершит алгоритм.

Таким образом, плохой oracle может ухудшить эффективность, но не ломает корректность и не должен приводить к зависанию.

Это важное отличие от “опасной эвристики”.

11. Proof-carrying certificates

Один из главных результатов системы — proof-carrying certificate.

Идея проста:

результат алгоритма должен быть проверяем независимо от алгоритма.

Сертификат содержит:

input basis hash;
output basis hash;
transform matrix U;
delta;
first_norm2;
min_lovasz_slack;
oracle diagnostics;
evidence flags.

Verifier проверяет:

U * B_in = B_out;
U unimodular;
exact size reduction;
exact Lovász conditions;
exact first_norm2;
exact min Lovász slack;
fallback=false;
unsafe approximate swaps=false;
exact_gso_calls_during_oracle=0.

Это переводит результат из категории:

“программа сказала, что всё хорошо”

в категорию:

“результат можно независимо перепроверить”.

Для этого реализованы два независимых verifier-слоя:

cmd/qlllverify/main.go
scripts/verify_qlll_certificate.py

12. Мини-пример: как работает Q-LLL

Представим базис из 10 строк.

Обычный LLL будет двигаться примерно так:

k = 2
k = 3
k = 4
...

Он проверяет позиции по порядку.

Q-LLL делает иначе.

Сначала строится approximate Lovász-карта:

k=2:   Δ̂ = +0.12
k=3:   Δ̂ = +0.05
k=4:   Δ̂ = -0.01
k=5:   Δ̂ = +0.20
k=6:   Δ̂ = -0.34
k=7:   Δ̂ = -0.08
k=8:   Δ̂ = +0.02
k=9:   Δ̂ = -0.15

Oracle говорит:

самая подозрительная позиция: k=6

Q-LLL не верит oracle на слово. Он вычисляет exact slack:

Δ_6 = -17/104

Это действительно нарушение. Значит swap разрешён.

Если бы exact slack оказался положительным, Q-LLL отклонил бы candidate и попробовал следующий.

В конце verifier проверяет весь output basis. Поэтому даже если oracle ошибался по дороге, финальный результат остаётся exact-certified.

13. Математическая устойчивость: eta_delta

Чтобы перейти от эвристики к контролируемой теории, мы ввели оценку ошибки Lovász slack.

Пусть есть exact Gram matrix:

и approximate Gram estimate:

$\widehat{G} = G + E.$

Ошибка Gram переходит в ошибку GSO:

Gram error
→ μ error
→ D error

А затем в ошибку Lovász slack:

$|\widehat{\Delta}*k - \Delta_k| \le \eta*\Delta(k).$

В системе введён computable benchmark/theory layer для оценки:

eta_mu(i,j);
eta_D(i);
eta_Delta(k);
margin_stable;
sign_preserved_when_margin_stable.

Если exact violation имеет margin:

$-\Delta_k > \eta_\Delta(k),$

то знак нарушения устойчив:

$\widehat{\Delta}_k < 0.$

Это важный шаг. Он позволяет говорить не только:

oracle часто угадывает

а:

в margin-stable случаях есть математическая причина, почему знак должен сохраняться.

14. Что уже реализовано

Текущая система включает:

Q-LLL API;
CLI ./turbolll qlll;
reduce -algo qlll;
batch-qlll JSONL mode;
oraclebench;
proof-carrying certificates;
independent verifier;
release attestation;
claim matrix;
pilot contour;
review package;
Python client;
competitor harness;
benchmark runners.

Есть buyer/auditor package:

00_EXECUTIVE_SUMMARY.md
01_CLAIM_MATRIX.md
02_Q_LLL_THEORY.md
03_REPRODUCIBILITY_GUIDE.md
04_EVIDENCE_REPORT.md
05_SECURITY_BOUNDARY.md
06_LIMITATIONS.md
07_BENCHMARK_RESULTS.md
08_IP_AND_LICENSE_NOTES.md
09_THIRD_PARTY_DEPENDENCIES.md
10_RELEASE_INTEGRITY.md

Это важно: система оформлена не как набор скриптов, а как проверяемый reference package.

15. Reference evidence corpus

Для Q-LLL подготовлен reference corpus из шести семейств:

random;
qary;
hnp-like;
ill-conditioned;
near-reduced;
adversarial-scaled.

Для каждого reference case фиксируются:

valid=true;
transform_matches=true;
fallback=false;
final_exact_certificate=true;
exact_certified_mutations=true.

Это минимальный эталонный набор, который показывает:

Q-LLL работает на разных типах базисов;
результаты проходят exact certificate;
transform matrix корректен;
fallback не используется.

16. Oracle benchmark

Для измерения качества quantized oracle есть oraclebench.

Он считает:

candidate recall;
random top-k baseline;
Lovász rank lift;
mean normalized Gram error;
mean cosine error;
ApproxGSO repair diagnostics;
exact candidate runtime;
quantized oracle runtime;
exact_gso_calls_during_oracle.

В bounded release grid получен checkpoint:

cases: 60
hit_at_k: 57/60
random_hit_at_k: 0/60
exact_gso_calls_during_oracle: 0

Это не утверждение, что Q-LLL быстрее всех. Это другой результат:

quantized oracle несёт реальный ranking signal и не использует exact GSO внутри построения oracle.

17. Full-grid инфраструктура

Для более сильной доказательной базы подготовлен full oracle grid:

6 families
dimensions: 16, 32, 64, 96
qbits: 1, 2, 3, 4
projections: srht, gaussian, orthogonal
estimators: mse, prod

Всего:

576 planned cases.

Runner поддерживает:

resume;
checkpointing;
timeout;
failure accounting;
planned_cases;
completed_cases;
failed_cases.

Это переводит benchmark из ручного smoke-теста в воспроизводимый экспериментальный контур.

18. TurboLattice Router

Q-LLL решает задачу внутри одного базиса. Но в практических задачах часто нужно выбрать из множества вариантов.

Для этого есть TurboLattice Router.

Он работает так:

lattice variants
→ feature extraction
→ visibility score
→ top-k selection
→ backend execution
→ recovery/no-recovery evidence

В HNP-like задачах это особенно важно, потому что варианты отличаются:

sample count;
secret scale;
embedding weight;
error bounds;
row ordering;
diagonal balance;
lattice model.

Router не заменяет backend. Он решает:

куда запускать backend первым.

19. Связь с nonce-observatory

Для nonce-observatory Q-LLL является ключевым lattice-core.

Общая схема:

signatures
→ protocol validation
→ nonce-family hypotheses
→ feature contracts
→ HNP/lattice variants
→ TurboLattice Router
→ Q-LLL / backend reduction
→ proof-carrying certificate
→ recovery/no-recovery evidence

То есть nonce-observatory превращается из системы наблюдения в full-stack proof-carrying audit platform.

Без Q-LLL:

мы видим структуру и ранжируем риск.

С Q-LLL:

мы строим lattice workflow,
редуцируем,
проверяем,
сертифицируем,
выдаём доказательный отчёт.

20. Отрицательный результат как часть метода

В одном из последних запусков Q-LLL использовался как backend для signature-HNP pubkey recovery workflow, проверяя на сигнатурах из сети, абсолютно случайных, без подтвержденной уязвимости.

Результат:

Q-LLL variants tested: 80/180
Q-LLL OK: 80
timeouts: 0
failed: 0
fallback=false
exact_gso_calls_during_oracle=0
confirmed d → pubkey matches: 0

Это важно правильно прочитать.

Это не означает:

Q-LLL не работает.

Это означает:

Q-LLL backend работает;
редукции exact-certified;
ложных подтверждений нет;
текущая bounded-HNP/direct-extraction модель не дала подтверждённый d.

Для научной системы отрицательный результат — тоже результат, если он проверяем.

Следующий слой для такого workflow:

synthetic positive controls;
enumeration;
Babai/CVP;
small row combinations;
transform-U analysis;
fplll/flatter comparison;
BKZ backend.

21. Что именно является новым

В Q-LLL новизна не в одном компоненте, а в их связке.

1. Quantized Gram/Lovász observability

Мы строим квантизированную карту геометрии базиса:

Gram
→ GSO
→ Lovász slack
→ candidate ranking

2. Exact-certified scheduler

Редукционные действия выбираются не последовательным индексом, а через ranking.

Но выполняются только после exact gate.

3. Proof-carrying LLL output

Результат несёт сертификат, который проверяется независимо.

4. Margin-stability layer

Для approximate slack вводится computable eta_delta.

Это позволяет отделять устойчивые случаи от нестабильных.

5. Lattice-variant routing

Q-LLL соединяется с TurboLattice Router для работы не с одной матрицей, а с семейством вариантов.

6. Интеграция с nonce-observatory

Система становится мостом от наблюдаемых nonce-инвариантов к proof-carrying lattice evidence.

22. Сравнение с существующими инструментами

fplll / fpylll

fplll — зрелый и сильный backend. Он остаётся одним из главных стандартов для LLL/BKZ/SVP/CVP.

Q-LLL не обязан конкурировать с ним как “быстрее на одном запуске”.

Отличие Q-LLL:

certified scheduler;
quantized Lovász observability;
proof-carrying certificates;
evidence mode;
nonce/HNP integration.

Правильная роль:

fplll может быть backend;
Q-LLL может быть orchestration/certification layer.

FLINT / NTL / Sage

Эти системы сильны как математические библиотеки и среды.

Q-LLL отличается тем, что является специализированным reference standard для:

exact-certified reduction;
certificate verification;
lattice intelligence;
audit/evidence workflow.

flatter

flatter интересен как быстрый reducer. Q-LLL может использовать такие backends как часть workflow, но сам фокусируется на наблюдении, управлении и сертификации.

Polynonce / leakage-specific methods

Специализированные методы могут быть сильнее в своём конкретном leakage-классе.

Q-LLL шире: это не одна атака и не один leakage-template, а инфраструктура для построения, маршрутизации, редукции и проверки lattice-гипотез.

23. Чего мы не утверждаем

Для честности и воспроизводимости важно явно указать границы.

Мы не утверждаем:

Q-LLL универсально быстрее fplll;
Q-LLL даёт лучший Hermite factor;
Q-LLL заменяет BKZ;
Q-LLL автоматически решает любой HNP;
Q-LLL гарантирует recovery на реальных корпусах;
теоремы TurboQuant автоматически доказывают superiority Q-LLL;
все perturbation constants полностью закрыты формально.

Мы утверждаем:

Q-LLL — новый exact-certified LLL-family algorithm;
классическая LLL-корректность сохраняется;
candidate selection управляется quantized Gram/Lovász oracle;
basis-changing операции проходят exact gate;
результат проверяется independent verifier;
oracle не подглядывает в exact GSO;
система выдаёт proof-carrying evidence.

Это достаточно сильный и честный claim.

24. Почему это важно инженерно

Большая часть исследовательского кода страдает от одной проблемы:

получился результат, но непонятно,
как его проверить,
как повторить,
где границы,
что было exact,
а что было эвристикой.

Q-LLL строился наоборот.

В системе есть:

claim matrix;
security boundary;
proof certificates;
independent verifier;
release attestation;
public/internal report split;
pilot contour;
review package.

Это делает Q-LLL не просто алгоритмом, а инженерным стандартом проверки результата.

25. Roadmap

Ближайшие шаги:

1. Завершить full oracle grid.
2. Завершить full HNP sweep по easy/medium/hard/extreme.
3. Сделать ablation report по HNP scoring features.
4. Добавить synthetic positive controls для signature-HNP.
5. Добавить Q-LLL + enumeration/CVP postprocessing.
6. Сравнить Q-LLL/fplll/flatter на identical variants.
7. Интегрировать Q-LLL в nonce-observatory как first-class lattice core.
8. Подготовить внешнюю technical review версию.
9. Уточнить paper-grade eta_delta constants.
10. Собрать reproducible Docker/Nix package.

Особенно важный следующий шаг:

если HNP-структура искусственно создана и известна, pipeline должен находить секрет и подтверждать его exact-проверкой.

Это будет positive-control доказательство solver-completeness.

26. Заключение

Q-LLL родился из простой идеи:

LLL-редукцию можно сделать не только exact-корректной, но и наблюдаемой.

Мы не меняем классический Lovász-критерий. Мы меняем то, как алгоритм видит и выбирает редукционные действия.

Итоговая архитектура:

integer lattice basis
→ quantized Gram/Lovász oracle
→ ranked candidates
→ exact Lovász gate
→ exact-certified mutation
→ fair scheduler
→ final exact certificate
→ independent verifier

Главное достижение:

approximate geometry стала advisory-слоем,
а exact certificate остался источником истины.

Для nonce-observatory это особенно важно, потому что появляется полный путь:

подписи
→ наблюдаемые nonce-инварианты
→ lattice hypotheses
→ Q-LLL/TurboLattice
→ proof-carrying recovery/no-recovery evidence.

Самая короткая формула Q-LLL:

Q-LLL — это exact-certified LLL-family algorithm, в котором редукцией управляет квантизированная Gram/Lovász-геометрия, а результат доказывается независимым сертификатом.

И в этом, на мой взгляд, находится главное открытие: LLL можно рассматривать не только как процедуру редукции, но и как процесс, которым можно управлять через наблюдаемую квантизированную геометрию, не теряя exact-корректности.

Q-LLL: как мы сделали LLL-редукцию наблюдаемой, управляемой и проверяемой