Исследование: операции и глубина для стандартного отклонения (CKKS/RNS)

Цель

Сформировать точное ТЗ для библиотеки: какие операции, ключи, глубина (levels) и масштабы (scale) нужны, чтобы вычислять дисперсию и стандартное отклонение над зашифрованными скалярами в CKKS/RNS. На выходе — краткий документ с формулами, графом операций и бюджетом уровней, чтобы после этого сразу разбить на имплементационные задачи.

Область

• Только один скаляр на шифртекст (без ротаций). Пакетирование/слот-редукции — отдельным этапом.
• Возвращаем стандартное отклонение (не только дисперсию) — потребуется аппроксимация sqrt.
• Без бутстраппинга.

Вопросы, на которые надо ответить

1. Определение: population vs sample

   • σ² = E[x²] − (E[x])² и s² = (Σ(x−x̄)²)/(N−1) — какую поддерживаем первой? (разобраться в целом как считать).
   • Требования к точности (абсолютная/относительная).

2. Формулы → HE-операции (минимальный набор)

   • Σx: последовательные add (глубину не тратит).
   • Σx²: либо ct×ct для каждого x с последующим add, либо хранить x² на приёме. Сравнить варианты по латентности/глубине.
   • Умножение на константу (1/N): ct×pt (scalar) с рескейлом.
   • (E[x])²: один ct×ct + relinearize + rescale.
   • variance: вычитание с выравниванием scale/level.
   • sqrt(variance): полиномиальная аппроксимация (Chebyshev/Ньютон), нормализация диапазона.
   • Нужные служебные шаги: relinearize, rescale, контроль scale drift, mod_down/up при необходимости.

3. Ключевой материал

   • Какие eval-ключи: RelinKey или Hybrid KeySwitch — оценить выгоду даже без ротаций.
   • Требования к сериализации ключей (для последующих задач).

4. Бюджет уровней (level budget) и масштабов

   • Посчитать глубину для двух сценариев:
     • A) Σx² считается «на лету» (каждый элемент: 1 умножение → −1 уровень).
     • B) x² предвычисляем и храним (онлайн только сумма).
   • (E[x])² — ещё 1 умножение → −1 уровень.
   • sqrt: оценить степень полинома/число итераций и сколько уровней это съест.
   • Рекомендация по длине цепочки модулей (кол-во 50–60-бит простых) и начальному scale (например, ~2^40).

5. Нормализация диапазона для sqrt

   • Оценить верхнюю границу дисперсии из ожидаемого диапазона значений (например, T в [Tmin, Tmax] → σ² ≤ (Tmax−Tmin)²/4).
   • Выбрать интервал аппроксимации и целевую ошибку.

6. Выравнивание scale/level

   • Правила: когда делать дополнительный rescale, как приводить E[x²] и (E[x])² к одному уровню перед вычитанием.
   • Порог отсечения отрицательных хвостов из-за округлений (ε-кламп).

Что должно быть на выходе (Acceptance Criteria)

• Документ docs/stddev-research.md (1–2 страницы), где есть:
  • Чёткий набор операций (список) для variance и stddev.
  • DAG операций (короткий псевдокод).
  • Таблица глубины (сколько уровней тратится на каждом шаге) и итоговый рекомендуемый бюджет уровней.
  • Требуемые ключи и их формат (в общих чертах).
  • Выбранный метод sqrt (Chebyshev или Ньютон) с целевыми ошибками.
  • Рекомендованные начальные параметры: степень, цепочка модулей, scale.
  • Явные критерии точности (|err| и/или rel err).
• Короткий список последующих задач для библиотеки (имена без API-деталей):
  ct_mul_relin_rescale, ct_mul_scalar, variance_eval, sqrt_eval, scale_align, level_budget_checks, keys_relin, keys_hybrid (опционально).

Подзадачи

• Согласовать определение (population / sample) и требования к точности.
• Сопоставить формулы со списком HE-операций (минимально необходимый набор).
• Рассчитать глубину и масштабы для сценариев A/B (таблица).
• Выбрать метод sqrt и степень/итерации под заданную ошибку.
• Оценить необходимость Hybrid KeySwitch в текущем сценарии (без ротаций).
• Сформировать рекомендации по параметрам (N, цепочка модулей, начальный scale).
• Написать docs/stddev-research.md и приложить псевдокод/DAG.