Tôi đã nghĩ ra một sơ đồ FHE khá đơn giản nhưng không hoạt động, nhưng tôi không thể hiểu nó bị hỏng như thế nào. Bất kỳ trợ giúp với điều này được đánh giá cao!

Phần một

Đầu tiên, lưu ý rằng nếu chúng ta có một trường abelian mà việc tính toán phép nghịch đảo của phép nhân là khó khăn, thì chúng ta có thể xây dựng một sơ đồ đồng cấu cho phép cộng và phép nhân một cách tầm thường. Giả sử tin nhắn mà chúng ta muốn mã hóa là $m$. Sau đó, chúng tôi lấy mẫu một số yếu tố ngẫu nhiên, $e$ (để chúng ta biết $e^{-1}$) và văn bản mật mã của chúng ta đơn giản trở thành $c=m\cdot e$. Chúng tôi cung cấp cho máy chủ $m \cdot e$ và $e$. Lưu ý rằng vì rất khó để tìm nghịch đảo nhân, nên máy chủ không thể tính toán đơn giản $e^{-1}$ và sau đó nhân nó với $m\cdot e$. Dù sao đi nữa, giả sử máy chủ muốn thực hiện phép cộng với văn bản mật mã và một số hằng số $a$. Họ chỉ đơn giản là tính toán $a \cdot e$, rồi thêm cái này vào $m\cdot e$ để có được $(a+m)\cdot e$. Nếu đây không phải là hằng số (một số tin nhắn được mã hóa khác), chúng ta chỉ cần cộng các tin nhắn lại với nhau. Phép nhân phức tạp hơn một chút. Bây giờ, chúng ta sẽ cần theo dõi xem có bao nhiêu âeâ trong văn bản mật mã của mình. Khi khách hàng lần đầu tiên cung cấp cho máy chủ $c$, số mũ của $e$ chỉ đơn giản là $1$, vì vậy chúng tôi có thể lưu trữ điểm dữ liệu đó dưới dạng $(c,1)$. Nếu chúng ta có một văn bản mật mã khác $câ = mâ e$, và chúng tôi muốn nhân chúng lại với nhau, chúng tôi có thể tìm thấy rằng $(c,1) \cdot (câ,1) = (c\cdot câ,2)$. Lưu ý rằng những gì máy chủ thực sự có là $(m \cdot mâ)e^2$. Khi máy chủ trả lại giá trị này cho máy khách, nó sẽ trả lại $(c\cdot câ,2)$, nói với khách hàng rằng có hai $e$s trong sản phẩm. Do đó, nó có thể đơn giản nhân lên $c\cdot câ$ qua $e^{-2}$ để có được $m \cdot mâ$. Bây giờ nếu tính toán không kết thúc ở đó thì sao? Điều gì sẽ xảy ra nếu máy chủ có ba bản mã, $c_1,c_2,c_3$, và nó muốn tính toán $c_1\cdot c_2+c_3$. Đầu tiên nó sẽ tính toán $c_1 \cdot c_2 = (c_1c_2,2)$. Bây giờ nó muốn tính toán $(c_1c_2,2) + (c_3,1)$. Để làm được điều này, nó phải tính toán $c_3\cdot e$ để có được $(c_3,2)$, và sau đó nó chỉ có thể làm $(c_1c_2,2) + (c_3,2)=(c_1c_2+c_3,2)$. Khi máy chủ trả lại giá trị này, máy khách chỉ cần nhân với $e^{-2}$ và có $m_1m_2+m_3$.

Phần hai

Để thực sự tìm thấy một trường mà chúng ta không thể tính toán nghịch đảo là rất khó. Giải pháp mà tôi nghĩ ra (mà tôi không tự tin lắm), là tận dụng thực tế là bạn chỉ có thể tính toán nghịch đảo trong $\mathbb{F}_p$ nếu bạn biết thứ tự của lĩnh vực này. Nếu không thì điều đó là không thể. Do đó, khách hàng có thể đang làm việc với các số nguyên $\mod p$, nhưng nó sẽ không bao giờ nói điều này với máy chủ. Sau đó, nó sẽ chọn một số ngẫu nhiên $e$, tính toán $m\cdot e \mod p$, đưa nó cho máy chủ và máy chủ có thể thực hiện tất cả các tính toán của nó với số. Nếu kết quả của phép tính là $R$, máy chủ chỉ có thể trả lại $(R,n)$ cho khách hàng (trong đó $n$ là số lượng $e$s), và sau đó máy khách có thể tính toán đơn giản $R e^{-n} \mod p$ để có được câu trả lời. Lý do tại sao điều này hoạt động là vì modulo-ing hoàn toàn đồng hình; bạn có thể thực hiện ở giữa quá trình tính toán, ở mỗi bước tính toán hoặc đơn giản là chỉ thực hiện ở phần cuối. Về bản chất, khách hàng thực hiện modulo ngay từ đầu, che giấu $m$, và sau đó nó cho phép các máy chủ của nó thực hiện các tính toán trên đó. Khi nhận được kết quả, nó chỉ tính modulo. Điều này sẽ tương đương với việc máy chủ thực hiện tất cả các tính toán trong số học mô-đun toàn bộ thời gian, nhưng chúng tôi thực hiện việc này mà không cho máy chủ biết điều gì $p$ Là. Thật không may, điều này là không hiệu quả bởi vì những con số này có thể phát triển để có độ dài tùy ý. Để khắc phục sự cố này, khách hàng có thể tính toán một số số nguyên tố khác, $q$, trong giai đoạn khởi tạo, và sau đó tính toán $N=pq$. khách hàng cho $N$ đến máy chủ (lưu ý rằng theo giả định RSA, điều này không tiết lộ gì về $p$). Sau đó, máy chủ có thể thực hiện tất cả các tính toán của nó theo modulo $N$, và do đó, nó sẽ không có các số nguyên có kích thước dài tùy ý. Lý do điều này hoạt động là vì $N$ là bội số của $p$, nếu $x \equiv a \mod N$, sau đó $x \equiv a \mod p$ (xem nhận xét về bài này, đó là điều đã cho tôi nguồn cảm hứng cho ý tưởng này).

Tính toán nghịch đảo của một cái gì đó $\bmod N$ không phải là đặc biệt khó khăn không may. Đặc biệt, $x^{-1}\bmod N$ là giá trị trong $\mathbb{Z}_N$ như vậy mà $xx^{-1}\equiv 1\bmod N$. Lưu ý rằng nếu chúng ta biết số nguyên $a, b$ như vậy mà

$$aN + bx = 1$$

sau đó $x^{-1}\equiv b\bmod N$. Điều này là do phương trình trên $\bmod N$ Là $ bx\tương đương 1\bmod N$, Vì thế $b$ là "thứ nhân với $x$ để có được 1 $\bmod N$", tức là nghịch đảo của nó.

Làm thế nào chúng ta có thể nhận được $a, b$ như vậy mà $aN + bx = 1$? Các thuật toán euclide mở rộng sẽ cho chúng tôi $a, b$ như vậy mà $aN+bx= \mathsf{gcd}(x, N)$. Không may, $x$ không thể đảo ngược $\bmod N$ tương đương với $\mathsf{gcd}(x, N) = 1$, vì vậy thuật toán euclide mở rộng tính nghịch đảo $\bmod N$và phá vỡ hệ thống mật mã của bạn khá hiệu quả (nó giống như $O((\log N)^3)$ iirc).