Я придумал довольно простую схему FHE, которая не должна работать, но я не могу понять, как она ломается. Любая помощь в этом приветствуется!
Первая часть
Во-первых, заметим, что если бы у нас было абелево поле, в котором вычисление мультипликативного обратного было бы затруднительным, то мы могли бы тривиально построить гомоморфную схему для сложения и умножения. Допустим, сообщение, которое мы хотим зашифровать, $м$. Затем мы выбираем случайный элемент, $е$ (такие, что мы знаем $е^{-1}$), и наш зашифрованный текст просто становится $c=m\cdot е$. Мы отдаем сервер $м \cdot е$ и $е$. Обратите внимание, что, поскольку трудно найти обратное мультипликативное значение, сервер не может просто вычислить $е^{-1}$ а затем умножьте это на $м\cточка$. В любом случае, предположим, что сервер хочет выполнить дополнение с зашифрованным текстом и некоторой константой. $а$. Они бы просто вычислили $а \cdot е$, а затем добавьте это в $м\cточка$ получить $(а+м)\cdot е$. Если бы это не была константа (какое-то другое зашифрованное сообщение), мы могли бы просто сложить сообщения вместе. Умножение немного сложнее. Теперь нам нужно отслеживать, сколько букв «е» в нашем зашифрованном тексте. Когда клиент впервые дает серверу $с$, показатель степени $е$ просто $1$, поэтому мы можем сохранить эту точку данных как $(с,1)$. Если у нас есть другой зашифрованный текст $câ = mâ e$, и мы хотим перемножить их вместе, мы можем найти, что $(c,1) \cdot (câ,1) = (c\cdot câ,2)$. Обратите внимание, что на самом деле сервер $(м \cdot мâ)e^2$. Когда сервер возвращает это значение клиенту, он возвращает $(c\cdot câ,2)$, который сообщает клиенту, что есть два $е$с в продукте. Поэтому можно просто умножить $c\cdot câ$ к $е^{-2}$ получить $ м \cdot м $. А что, если вычисления на этом не заканчиваются? Что, если бы на сервере было три зашифрованных текста, $с_1,с_2,с_3$, и он хотел вычислить $c_1\cdot c_2+c_3$. Сначала он будет вычислять $c_1 \cdot c_2 = (c_1c_2,2)$. Теперь он хочет вычислить $(c_1c_2,2) + (c_3,1)$. Для этого необходимо вычислить $c_3\cdot e$ получить $(с_3,2)$, а затем он может просто сделать $(c_1c_2,2) + (c_3,2)=(c_1c_2+c_3,2)$. Когда сервер возвращает это значение, клиент может просто умножить на $е^{-2}$ и имеют $m_1m_2+m_3$.
Часть вторая
На самом деле найти поле, в котором мы не можем вычислить обратное, сложно. Решение, которое я придумал (в котором я не очень уверен), состоит в том, чтобы использовать тот факт, что вы можете вычислять инверсии только в $\mathbb{F}_p$ если вы знаете порядок поля. Иначе это невозможно. Следовательно, клиент может работать с целыми числами $\мод р$, но он никогда не сообщит об этом серверу. Затем он выберет случайный $е$, вычислить $m\cdot e \mod p$, отдайте его серверу, и сервер сможет выполнять все свои вычисления с числом. Если результат вычислений $R$, сервер может просто вернуть $(R,n)$ клиенту (где $n$ это количество $е$s), и тогда клиент может просто вычислить $R e^{-n} \mod p$ чтобы получить ответ. Причина, по которой это работает, заключается в том, что модуляция полностью гомоморфна; вы можете сделать это в середине вычисления, на каждом шаге вычисления или просто сделать это в конце. По сути, клиент выполняет по модулю в начале, маскируя $м$, а затем позволяет своим серверам выполнять над ним вычисления. Когда он возвращает результат, он просто вычисляет модуль. Это было бы эквивалентно тому, что сервер все время выполняет все вычисления в модульной арифметике, но мы делаем это, не сообщая серверу, что именно. $р$ является. К сожалению, это неэффективно, потому что эти числа могут вырасти до сколь угодно большой длины. Чтобы решить эту проблему, клиент может вычислить какое-нибудь другое простое число, $q$, на этапе инициализации, а затем вычислить $N=pq$. Клиент дает $N$ на сервер (обратите внимание, что по предположению RSA это ничего не говорит о $р$). Затем сервер мог бы выполнять все свои вычисления по модулю $N$, и, таким образом, в нем не будет целых чисел, которые вырастают до сколь угодно длинного размера. Причина, по которой это работает, заключается в том, что, поскольку $N$ является кратным $р$, если $x \экв\мод N$, тогда $x \эквивалентно\mod p$ (посмотрите комментарий к эта почта, что и натолкнуло меня на эту идею).
