Извлечение образца из RLWE в LWE

В этой статье я рассмотрю трюк, используемый в FHE, называемый извлечением выборки. Вкратце, он позволяет частично преобразовать шифротекст в схеме Ring Learning With Errors (RLWE) в схему Learning With Errors (LWE). Здесь приведены другие статьи, которые я написал о других строительных блоках FHE, хотя они не являются предварительными требованиями для этой статьи. Переключение модуля в LWE Переключение ключа в LWE Разложение гаджета в FHE Умножение негациклических многочленов Оценка безопасности Ring Learning With Errors LWE и RLWE Первые две статьи в списке выше определяют задачу Learning With Errors (LWE).