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

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

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

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

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

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

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

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

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

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

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