Tại sao cổng AND lại là * trên Lược đồ BFV, Mã hóa đồng hình hoàn toàn?

Dựa theo Biểu diễn một hàm dưới dạng mạch FHE, cổng AND cho dữ liệu được mã hóa FHE chỉ là A*B, trong trường hợp bản rõ chỉ có 0 hoặc 1 hệ số.

Hãy nhớ rằng trên sơ đồ BFV FHE, nó mã hóa các đa thức và chúng ta có thể đặt giá trị tối đa cho các hệ số của đa thức. Vì vậy, nếu chúng ta đặt giá trị tối đa thành 1, thì chúng ta có thể thực hiện các cổng nhị phân một cách dễ dàng.Ví dụ:

  1 + 0x^1 + 1x^2 + 0x^3
+ 0 + 1x^1 + 1x^2 + 0x^3
  ______________________
  1 + 1x^1 + 0x^2 + 0x^3

Cho nên + thực chất là cổng OR cho các đa thức. Nhưng tôi đang đấu tranh để hiểu * như là AND, đặc biệt bởi vì phép nhân của các đa thức này là chế độ x^n +1, ở đâu N là bậc của đa thức. Vì vậy, nó không phải là một phép nhân đơn giản.

Tại sao VÀ = *?

Đầu tiên, lưu ý rằng BFV được diễn đạt theo cách truyền thống về Môn số học mạch, không phải mạch boolean. Ví dụ: bài báo ban đầu có một không gian tin nhắn có dạng $R_t := \mathbb{Z}_t[x] / (\Phi_n(x))$, ở đâu $\Phi_n$ là $n$đa thức cyclotomic (khi $n$ là một sức mạnh của hai điều này chỉ đơn giản là $x^n+1$). Điều này tương đối quan trọng vì các khối xây dựng cơ bản của các mạch số học là không phải HOẶC và VÀ, nhưng (bản mod $p$ phiên bản của) XOR và AND, hơi khác một chút.

Đối với các vấn đề của bạn với phép nhân BFV, tôi nghĩ rằng bạn đang đọc sai thông số kỹ thuật của BFV một chút. Thông thường (nói trong giấy ban đầu) không gian tin nhắn được chỉ định là $R_t$, như đã đề cập trước đó là một vành đa thức (khi $n$ là lũy thừa của 2) $\bmod x^n+1$. Vì vậy, để sơ đồ mã hóa của chúng ta hoàn toàn đồng hình, chúng ta cần có thể thực hiện phép cộng và phép nhân của không gian tin nhắn trên các bản mã. Phép nhân này của không gian tin nhắn là $\bmod x^n+1$ (và $\bmod t$, nhưng sao cũng được), như bạn đã chỉ ra. Điều này có nghĩa là số học $\bmod x^n+1$ là những gì được yêu cầu về mặt toán học để sơ đồ hoàn toàn đồng hình, do đó, sản phẩm có dạng đó được mong đợi và không phải là vấn đề đáng lo ngại.

Tất nhiên, các nhà thiết kế ứng dụng có thể không muốn sử dụng "số học hài hước" này. Tuy nhiên, đây là điều mà các nhà thiết kế thư viện sẽ giải quyết sau này. Ví dụ: một cách để "khắc phục" điều này (khá ngây thơ --- tôi đoán có nhiều giải pháp tốt hơn) là chỉ mã hóa các thông báo thành các số hạng đa thức không đổi. Tương đối đơn giản để thấy rằng "phép nhân hài hước" này trở thành phép nhân tiêu chuẩn khi bị giới hạn ở các đa thức không đổi.

Có những thứ khác người ta có thể làm, ví dụ người ta có thể cho phép đa thức có dạng $m(x) = m_0+m_1x$ nếu bạn biết độ sâu nhân của mạch mà bạn đang đánh giá nhiều nhất là $\log_2 n$, hoặc tổng quát hơn $m(x) = \sum_{i =0}^p m_i x^i$ nếu độ sâu nhân nhiều nhất là $\log_{1+p} n$. Điều này đơn giản là vì với giới hạn độ sâu này, người ta không thể tạo ra đa thức bậc $\geq n$, vì vậy thực tế là phép nhân có thể "bao quanh" không thành vấn đề. Tất nhiên, tôi chắc chắn rằng có những ý tưởng thông minh hơn về những gì người ta có thể làm để mô phỏng số học "tiêu chuẩn" với số học "vui nhộn" mà người ta có được, nhưng điều đó thực sự trực giao để hiểu BFV.

Của nó Mà còn đáng nói là bình luận của bạn

nhưng nó cần phải là hệ số khôn ngoan và trên đa thức, không phải và cho chính đa thức

có vẻ như bạn có thể đang tìm kiếm ý tưởng của nhúng chính tắc. Cụ thể, khoảng một thập kỷ trước, người ta đã nhận thấy rằng nếu chúng ta muốn một kiểu dữ liệu giống như mảng $[a_0,\dots,a_n]$ mà người ta có thể thực hiện số học (khôn ngoan) trên, thì các hệ số của đa thức thực sự là một lựa chọn khá tồi. Điều này là do (trong số những thứ khác) phép toán nhân tự nhiên trên các đa thức không dẫn đến phép nhân các hệ số cơ bản, nhưng tích chập của họ. Đặc biệt, người ta có cái đó

$$(a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2) = a_0b_0+(a_0b_1+b_0a_1)x + (a_0b_2+a_1b_1+a_2b_0)x^2+(a_1b_2+a_2b_1) x^3+a_2b_2x ^4$$

Đặc biệt, một không thu hồi sản phẩm $a_1b_1$. Người ta có thể khắc phục điều này bằng cách (về cơ bản) hấp dẫn một phiên bản của biến đổi Fourier, vì biến đổi Fourier thường có thể được viết dưới dạng đẳng cấu

$$\mathcal{F} : (R, +,\times)\to (R, +,\ast)$$

ví dụ. nó "hoán đổi" tích chập với phép nhân (hệ số khôn ngoan). Điều này có nghĩa là nếu thay vào đó, chúng ta mã hóa một thông điệp trong "sự nhúng chính tắc" (hoặc tương đương, chúng ta mã hóa "biến đổi Fourier" của thông điệp), thì các phép chập sẽ trở thành phép nhân theo từng phần tử (trong không gian thông điệp của chúng ta).

Tuy nhiên, tôi không tin rằng bài báo ban đầu của BFV làm được điều này, điều này tùy thuộc vào những gì bạn đang đọc về thông số kỹ thuật của BFV có thể dẫn đến nhầm lẫn. Nhưng tôi tin rằng đó là một tối ưu hóa tương đối phổ biến và có thể được coi là "chỉ" một mã hóa thông báo khác (có những lợi ích khác khi sử dụng nhúng chuẩn để bạn muốn phân tích lại giao thức theo nghĩa của nó).

Cổng AND đại diện cho phép nhân trong trường hệ số, trong trường hợp này là trường nhị phân của hai phần tử 0 và 1. Tương tự đối với trường này, phép cộng hoạt động giống như cổng XOR.

Nếu chúng ta biết cách cộng và nhân với các hệ số, chúng ta có thể mở rộng phép cộng và nhân các đa thức bằng cách sử dụng các tính chất của số học. Trong trường hợp cộng, điều này chỉ liên quan đến việc khớp các hệ số và cộng. Trong trường hợp phép nhân, chúng ta cần sử dụng luật phân phối. Trong ví dụ của bạn, viết # cho XOR và & cho AND, chúng ta phải ghép nối các hệ số có các đơn thức có lũy thừa bằng nhau

(1 + 0x^1 + 1x^2 + 0x^3)*(0 + 1x^1 + 1x^2 +0 x^3)

= (1&0) + (1&1 # 0&0)x^1 + (1&1 # 0&1 # 1&0)x^2 + (1&0 # 0&1 # 1&1 # 0&0)x^3 +

+ (0&0 # 1&1 # 0&1)x^4 + (1&0 # 0&1)x^5 + (0&0)x^6

= 0 + 1x^1 + 1x^2 + 1x^3 + 1x^4 + 0x^5 + 0x^6