hoạt động một khe trên đa thức đồng cấu đầy đủ SIMD

Dựa theo https://eprint.iacr.org/2011/133.pdf và nhiều bài báo khác, có một đẳng cấu giữa không gian của đa thức và các hệ số của nó. Vì vậy, ít nhất là trong sơ đồ BFV, chúng ta có thể làm:

$$p(x) = [a_1, a_2, ..., a_3]$$ $$\phi(p(x)) = [\phi(a_1), \phi(a_2), ..., \phi(a_3)]$$

Vì vậy, áp dụng một thao tác cho đa thức cũng giống như áp dụng cho tất cả các phần tử, giống như SIMD hoạt động trên CPU. Đây cũng là tự biến hình Galois trong một số sơ đồ.

Bây giờ, giả sử tôi chỉ muốn thao tác trên phần tử thứ hai, vì vậy bằng cách nào đó tôi tìm cách giải nén nó bằng bitmask và do đó tôi nhận được:

$$p_2(x) = [0, \phi(a_2), ..., 0]$$

bây giờ tôi có thể hoạt động trên $p_2(x)$ để sửa đổi $\phi(a_2)$ tuy nhiên tôi muốn. Có cách nào để đưa nó trở lại $p(x)$ với những sửa đổi của tôi? Tôi cũng nghĩ rằng một số hoạt động mà tôi làm trên p_2(x) có thể làm cho các phần tử khác khác không, đây cũng là một thách thức.

Có một cách đơn giản để làm điều này. Cụ thể, bạn đã đề cập rằng bạn có quy trình trích xuất bitmask. Do đó, đưa ra $p(x)$, $p_2(x)$, và $p_2'(x)$ (các hoạt động đồng hình của bạn được áp dụng cho $p_2$), để cho $p_3(x)$ là kết quả của việc áp dụng cùng một bitmask cho $p_2'$. Sau đó, thật dễ dàng để xác minh rằng

$$p(x) - p_2(x) + p_3(x)$$

cung cấp cho bạn kết quả bạn muốn.

Điều này làm giảm mọi thứ thành hai quy trình "trích xuất bitmask", đánh giá đồng hình (dường như không thể tránh khỏi) và một vài bổ sung (sẽ rẻ). Sau đó, có những câu hỏi tự nhiên:

• trích xuất một bitmask có đủ không?
• Làm thế nào một người có thể áp dụng trích xuất bitmask một cách hiệu quả?

Nếu vị trí bạn muốn tính toán là công cộng, nó sẽ đủ để nhân với một đa thức hằng số phù hợp (với các hệ số 0/1), đưa ra tổng chi phí nhân là 1 cho mỗi lần trích xuất mặt nạ bit. Bitmask riêng dường như kém hiệu quả hơn --- tôi có thể nghĩ ra thứ gì đó sử dụng $O(n)$ phép nhân (nhưng ít nhất có độ sâu 1), về cơ bản bằng cách tính toán phép nhân của boolean 0/1 (được mã hóa) cho mỗi chỉ mục để "chọn" đúng chỉ mục, sau đó thêm mọi thứ vào cuối.

Tôi không biết làm thế nào ở trên so sánh với nhà nước-of-the-nghệ thuật mặc dù.

Điều đáng nói là nếu hoạt động của bạn trên $p_2(x)$ làm không phải phụ thuộc vào các tọa độ khác $\phi(a_i)$ (nhưng có thể đơn giản là "ghi đè" chúng), người ta có thể loại bỏ một trong (cụ thể là thao tác đầu tiên) trích xuất bitmask. Tất nhiên, điều này phụ thuộc vào chức năng cụ thể mà bạn đang đánh giá.