Оптимизация алгоритма расширения оснований в модулярном коде для гомоморфных шифров

Оптимизация алгоритма расширения оснований в модулярном коде для гомоморфных шифров

Бабенко М.Г. (ИСП РАН, Москва, Россия; СКФУ, Ставрополь, Россия)
Синицын А. А. (ИСП РАН, Москва, Россия)
Дерябин М.А. (ИПТ Самсунг, Сувон, Корея)

Аннотация

Гомоморфное шифрование позволяет обрабатывать данные без их расшифровки в удаленном пространстве (таком как облачной системы обработки данных). Несмотря на то, что это одна из ключевых перспективных технологий защиты персональных данных пользователей в современном мире, она сталкивается с проблемой низкой производительности. Для повышения скорости обработки данных большинство основных систем гомоморфного шифрования используют модулярный код через систему остаточных классов (СОК) как арифметическую основу для высокопроизводительных вычислений. Среди сложных операций, необходимых для гомоморфных шифров, особое место занимает операция расширения системы оснований СОК. Наибольшую популярность имеет ранее предложенный подход к этой операции, основанный на вычислении приближенного ранга числа в СОК использований числа с плавающей запятой. Для оптимизации алгоритма расширения оснований СОК ранее были получены оценки точности, с которой необходимо выполнять вычисления приближенного ранга числа, причем авторы использовали классическую теорию погрешности, не учитывающую свойства модулярного кода. Мы предлагаем теоретическое исследование позволявшее оценить точность вычисления приближенного ранга числа. Доказанная теорема позволяет уменьшить длину операндов более, чем в 3 раза по сравнению с оценками других авторов. Результаты моделирования показывают, что ранее предложенная оптимизация алгоритма позволяет повысить скорость алгоритма масштабирования чисел в системе остаточных классов в среднем на 46.15%.

Ключевые слова

система остаточных классов; расширения оснований в системы остаточных классов; Китайская теорема об остатках; ранг числа; аппроксимация ранга числа.

Издание

Труды Института системного программирования РАН, том 38, вып. 3, часть 1, 2026, стр. 33-44.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(3)-2

Для цитирования

Бабенко М.Г., Синицын А. А., Дерябин М.А. Оптимизация алгоритма расширения оснований в модулярном коде для гомоморфных шифров. Труды Института системного программирования РАН, том 38, вып. 3, часть 1, 2026, стр. 33-44. DOI: 10.15514/ISPRAS-2026-38(3)-2.

Полный текст статьи в формате pdf Вернуться к содержанию тома