Система остаточных классов (RNS)

Китайская теорема об остатках (CRT)

Система остаточных классов (Residue Number System, RNS) является непозиционной системой целых чисел, основанной на китайской теореме об остатках (CRT). В такой системе целое число $x$ представляется его остатками $x_i = x \mod p_i$ по базису взаимно простых чисел $\mathcal{B} = \{p_0, \ldots, p_{k-1}\}$. Множество $\mathcal{B} = \{p_0, \ldots, p_{k-1}\}$ формирует базис RNS, состоящий из $k$ каналов. Модули $p_i$ обычно выбираются с учетом ширины слова $w$, которая соответствует целевой архитектуре. Важным преимуществом такой системы является то, что операции сложения, вычитания и умножения могут выполняться параллельно в каждом канале: $$ z_i = x_i \circ y_i \mod p_i, \text{ где } \circ \in \{+, -, \times\} $$ Традиционно рассматриваются системы $\{2^n-2^s\pm1, 2^n, 2^n-1\}$

Ряд работ по использованию RNS в доказательствах ZKP и FHE:

• [2016/510] A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes
• [2018/117] An Improved RNS Variant of the BFV Homomorphic Encryption Scheme
• [2018/931] A Full RNS Variant of Approximate Homomorphic Encryption

• Исходники на GitHub
• Полный текст включает описания алгоритмов расширения и сжатия базиса, преобразования из RNS в позиционную систему

Обозначения

Для целого числа $q \geq 2$ мы отождествляем кольцо $\mathbb{Z}_q$ с его отображением на симметричном интервале $\mathbb{Z} \cap [-q/2, q/2)$. Для произвольного действительного числа $x$ мы обозначаем через $[x]_q$ отображение $x$ на этот интервал, а именно, действительное число $x' \in [-q/2, q/2)$, такое что $x' - x$ делится на $q$. Мы также обозначаем через $\lfloor x \rfloor$, $\lceil x \rceil$ и $\lfloor x\rceil$ округление $x$ вниз, вверх и до ближайшего целого числа, соответственно. Векторы мы обозначаем жирным шрифтом, и расширяем нотации $\lfloor \mathbf{x} \rfloor$, $\lceil \mathbf{x} \rceil$, $\lfloor\mathbf{x}\rceil$ на векторы поэлементно.

Мы выбираем множество из $k$ взаимно простых модулей $\{p_0, \dots, p_{k-1}\}$, где все числа целые больше 1, и пусть их произведение равно $P = \prod_{i=0}^{k-1} p_i$.

Для всех $i \in \{0, \dots, k-1\}$ мы также обозначаем $$ \hat{p}_i = P / p_i \in \mathbb{Z} \quad \text{и} \quad \tilde{p}_i = \hat{p}_i^{-1} \pmod{q_i} \in \mathbb{Z}_{q_i}, $$ где $\tilde{p}_i \in [-p_i/2, p_i/2)$ и $\hat{p}_i \cdot \tilde{p}_i = 1 \pmod{p_i}$.

Теорема об остатках (CRT)

Обозначим представление целого числа $x \in \mathbb{Z}_p$ относительно базиса RNS $\{p_0, \dots, p_{k-1}\}$ через $x \sim (x_0, \dots, x_{k-1})$, где $x_i = [x]_{p_i} \in \mathbb{Z}_{p_i}$. Формула, выражающая $x$ через $x_i$, имеет вид $$ x = \sum_{i=0}^{k-1} x_i \cdot \tilde{p}_i \cdot \hat{p}_i \pmod{P}~. $$

Эта формула может быть использована более чем одним способом для «реконструкции» значения $x \in \mathbb{Z}_p$ из $[x]_\mathcal{B}$. В данной работе мы используем следующие два факта: $$ x = \sum_{i=0}^{k-1} [x_i \cdot \tilde{p}_i]_{p_i} \cdot \hat{p}_i - e \cdot P \quad \text{для некоторого } e \in \mathbb{Z}, $$ и $$ x = \sum_{i=0}^{k-1} x_i \cdot \tilde{p}_i \cdot \hat{p}_i - e' \cdot P \quad \text{для некоторого } e' \in \mathbb{Z}, $$ где сумма во второй формуле берётся по $x_i \cdot \tilde{q}_i \cdot \hat{q}_i \in \big[-\cfrac{q_i q}{4}, \cfrac{q_i q}{4}\big)$.

Представление RNS в кольце

Пусть $\mathcal{B} = \{p_0, \ldots, p_{k-1}\}$ — это базис взаимно простых чисел, и пусть $P = \prod_{i=0}^{k-1} p_i$. Обозначим через $[\cdot]_\mathcal{B}$ отображение из $\mathbb{Z}_P \mapsto \mathbb{Z}_{p_0} \times \mathbb{Z}_{p_1} \times \cdots \times \mathbb{Z}_{p_{k-1}}$, определённое как $a \mapsto [a]_\mathcal{B} = ([a]_{p_i})_{0 \leq i \le k}$ -- отображение из множества целых чисел на множество остатков в базисе взаимно простых чисел. Это изоморфизм кольца по Теореме об остатках (CRT), и $[a]_\mathcal{B}$ называется представлением числа $a \in \mathbb{Z}_P$ в системе остаточных классов (RNS). Основное преимущество представления RNS заключается в возможности выполнения компонентных арифметических операций в малых кольцах $\mathbb{Z}_{p_i}$, что снижает асимптотическую и практическую вычислительную сложность. Этот изоморфизм кольца над целыми числами может быть естественным образом расширен до изоморфизма в кольце полиномов $[ \cdot ]_\mathcal{B} : \mathcal{R}_P \to \mathcal{R}_{p_0} \times \cdots \times \mathcal{R}_{p_{k-1}}$ путём пересчета коэффициентов над циклическими кольцами.

Расширение базиса CRT

Пусть $x \in \mathbb{Z}_P$ задано в представлении CRT $(x_0, \dots, x_{k-1})$, и предположим, что мы хотим расширить базис CRT, вычислив $[x]_q \in \mathbb{Z}_q$ для некоторого другого модуля $q > 1$. Используя уравнение (2), мы хотели бы вычислить $$ [x]_q = \left[ \left( \sum_{i=0}^{k-1} [x_i \cdot \tilde{p}_i]_{p_i} \cdot \hat{p}_i \right) - e \cdot P \right]_q~. $$ Основная сложность здесь заключается в вычислении $e$, которое является целым числом в $\mathbb{Z}_k$. Формула для $e$ выглядит так: $$ e = \left\lfloor \frac{\sum_{i=0}^{k-1} [x_i \cdot \tilde{p}_i]_{p_i} \cdot \hat{p}_i}{P} \right\rceil = \left\lfloor \sum_{i=0}^{k-1} [x_i \cdot \tilde{p}_i]_{p_i} \cdot \frac{\hat{p}_i}{P} \right\rceil = \left\lfloor \sum_{i=0}^{k-1} \frac{[x_i \cdot \tilde{p}_i]_{p_i}}{p_i} \right\rceil. $$

Чтобы получить $e$, мы вычисляем для каждого $i \in \{0, \dots, k-1\}$ элемент $\xi_i := [x_i \cdot \tilde{p}_i]_{p_i}$ используя арифметику целых чисел, а затем рациональное число $z_i := \xi_i / p_i$ в формате с плавающей точкой одинарной точности. Затем суммируем все $z_i$ и округляем результат, чтобы получить $e$. {округление к меньшему для чисел без знака, проверить}: $$ e+{x\over P} = \sum_{i=0}^{k-1} \frac{\xi_i}{p_i}, \quad e = \left\lfloor\sum_{i=0}^{k-1} \frac{\xi_i}{p_i}\right\rfloor, $$ -- в такой форме должно быть справедливо для модульной арифметики без знака [23].

После того как мы получили значение $e$, а также все $\xi_i$, мы можем напрямую вычислить уравнение (2) по модулю $q$, чтобы получить $$ [x]_q = \left[ \left( \sum_{i=0}^{k-1} \xi_i \cdot [\hat{p}_i]_q \right) - e \cdot [P]_q \right]_q~. $$ Заметим, если все значения $[\hat{p}_i]_q$ представить в качестве элементов вектора, то вычисление сводится к операции скалярного произведения векторов размерности $k$ по модулю $q$.