Постквантовая криптография — это не просто математика, это поле битвы аппаратного обеспечения. Векторизация SIMD проводит четкую грань: некоторые схемы масштабируются, другие застревают. Вот как, по данным @PrivacyScaling, архитектура ЦП влияет на производительность PQC. 🧵

@PrivacyScaling Постквантовая криптография (PQC) требует эффективности и отказоустойчивости. Схемы на основе решеток доминируют в этом пространстве благодаря их структурной совместимости с современными оптимизациями процессоров, в частности, с векторизацией SIMD.

@PrivacyScaling Векторизация — SIMD (Single Instruction, Multiple Data) — позволяет процессорам применять одну операцию к нескольким точкам данных одновременно. Это имеет решающее значение для ускорения полиномиальных операций в криптографии на основе решеток.

@PrivacyScaling Схемы решетки выражают криптографические операции в виде умножения матричных векторов на полиномиальные кольца типа Z[x]/(xⁿ + 1). Они могут быть преобразованы с помощью теоретико-числового преобразования (NTT), уменьшая сложность с O(n²) до O(n log n).

@PrivacyScaling Полиномиальное сложение, умножение и NTT могут быть векторизованы. Например, 64 коэффициента могут быть обработаны в двух инструкциях AVX2 с использованием 256-битных регистров с 16-битными линиями.

@PrivacyScaling Схемы, основанные на изогении, напротив, устойчивы к векторизации. Их основной примитив — вычисление изогений между эллиптическими кривыми — не разлагается на SIMD-распараллеливаемые структуры.

@PrivacyScaling Оптимизации криптографии на основе изогении черпают вдохновение из традиционной криптографии на основе эллиптических кривых, включая редукцию и инверсию Монтгомери, кривые Эдвардса и методы полевой арифметики, такие как представление радикса-2²⁹.

@PrivacyScaling Тем не менее, усиление SIMD ограничено в операциях с эллиптическими кривыми — обычно до 9 полос против 64+ в операциях с решеткой. Таким образом, решетчатая криптография обеспечивает больший параллелизм и пропускную способность.

@PrivacyScaling Performance отдает предпочтение решеткам. Тем не менее, схемы, основанные на изогении, по-прежнему предлагают компактные размеры ключей/сигнатур. Такие схемы, как SQIsign, избегают известных атак (например, Castryck-Decru), не показывая изображения точек.

@PrivacyScaling Вердикт: криптография на основе решеток сегодня лучше подходит для оптимизации на уровне процессора. Но компромиссы — производительность и компактность — оставляют место для нескольких парадигм PQC и путей внедрения.

@PrivacyScaling По мере развития стандартизации криптографическое проектирование с учетом аппаратного обеспечения будет играть решающую роль. Непрерывный бенчмаркинг и анализ реализации определят реальный мир