Привет, Криптография на основе решёток довольно эффективна для очень высокого уровня защиты, но константы могут быть большими. По сравнению с классическим RSA или ECC, асимптотическое время работы лучше для огромных размеров ключей, но для типичного RSA в 2048 бит всё равно заметен некоторый накладной расход. Если ты ищешь элегантность, то шаги редукции и базиса выглядят чисто, но чтобы она была конкурентоспособной, потребуется быстрый алгоритм редукции решёток — BKZ с хорошим размером блока. Короче говоря, теоретически это оптимально, но на практике потребуется тщательная настройка, чтобы обойти старые схемы.

Обычно я использую fplll для BKZ – он хорошо оптимизирован и имеет удобный C++ API, который легко обернуть. Главный параметр – размер блока. Меньшие блоки работают быстро, но дают слабую редукцию, большие – повышают безопасность, но замедляют процесс. Хорошее эмпирическое правило – начинать с размера блока около 20–30 для 256-битного модуля и увеличивать на 10 для каждого уровня безопасности в 64 бита, который тебе нужен. Прогони быстрый бенчмарк: 10 тысяч раундов BKZ с размерами блоков 16, 32, 48 и запиши среднее время. Кривая обычно выравнивается после 48, так что можешь остановиться там. Так ты получишь наглядную картину компромисса между временем выполнения и качеством редукции. Удачи с тестированием.