Relinearization keys (Hybrid): типы и хранение

Цель

Реализовать полноценный пайплайн умножения двух шифртекстов CKKS/RNS:

• Работаем сразу в NTT-форме (без возврата в коэффициентное представление).
• Для сокращения размеров/шума использовать HybridKey (универсальный тип для релинеаризации и ротаций).
• После умножения выполняется релинеаризация и рескейл, чтобы гарантировать корректный масштаб и понижение уровня.

Результат (Acceptance Criteria)

• Новый тип HybridKey:
  • содержит параметры для гибридного ключевого переключения;
  • поддерживает сериализацию/десериализацию (через serde).
• API:
  • Ciphertext::mul_with_hybrid(&self, &Ciphertext, &HybridKey) -> Ciphertext
  • Постусловия:
    • результат в NTT-форме;
    • масштаб выровнен (≈ исходный target scale);
    • уровень уменьшен на 1.
• Внутренний пайплайн:
  1. Точечное умножение коэффициентов в NTT-области.
  2. Применение HybridKey для релинеаризации (снижение размерности).
  3. Рескейл: отбрасывание одного простого модуля, нормализация масштаба.
• Трассировка (spans): op="mul_ct", поля degree, levels_before/after, scale_before/after, elapsed_us.

Подзадачи

1. HybridKey: структура и хранение

   • Определить поля: базис разложения, вспомогательные простые, матрицы для переключения.
   • Реализовать Serialize/Deserialize.

2. Генерация HybridKey

   • На стороне KeyGen создать HybridKey для заданного секретного ключа и конфигурации.
   • Юнит-тест: сериализация/десериализация → идентичность.

3. Релинеаризация через HybridKey

   • Реализовать процедуру apply_hybrid_key(ct, &HybridKey).
   • Проверка: выходной шифртекст имеет ожидаемую размерность.

4. Рескейл после умножения

   • Добавить утилиту для корректного scale-down: деление на последний модуль, обновление scale.
   • Проверка: scale близок к исходному target (± ε).

5. Интеграция в пайплайн

   • Функция mul_with_hybrid объединяет шаги: умножение → релинеаризация → рескейл.
   • Юнит-тест: на маленькой степени (например, N=8) сравнить результат с эталоном из SageMath.

6. Тесты корректности

   • Случайные значения: сравнить дешифрованный результат с обычным float-умножением (погрешность ≤ 1e-3).
   • Проверить, что уровень действительно уменьшился на 1.
   • Проверить сохранение NTT-формы.

7. Документация

   • Обновить README/docs: пояснить роль HybridKey и отличие от обычного RelinKey.
   • Добавить схему пайплайна (умножение → HybridKey → рескейл).