Điểm:2

Liệu mức độ của vấn đề đa thức này để đạt được kiến ​​​​thức bằng không? câu hỏi PlonK

lá cờ in

tôi đang đọc báo PlonK và trong Vòng 1 của yêu cầu đạt được tri thức bằng 0 bằng cách cộng các bội số ngẫu nhiên (bậc một) của đa thức $Z_H = x^n - 1$ đến các đa thức bí mật.

Đây, $H$ là tập hợp chứa $n$-gốc rễ của sự thống nhất và được mô tả một cách cơ bản là $$H = \{\omega, \dots, \omega^{n-1}, \omega^n = 1\},$$ ở đâu $\omega$ là một nguyên thủy $n$-gốc rễ của sự thống nhất.

Vì vậy, cài đặt như sau: Chúng tôi có một đa thức bí mật $s(x)$ như vậy mà chúng ta phải đánh giá tại một số điểm ngẫu nhiên $z \in \mathbb{Z}_p$, bắt đầu $z$ và đánh giá $s(z)$ được biết đến một cách công khai.

Để tránh rò rỉ kiến ​​thức của $s(z)$, họ định nghĩa: $$s'(x) := (b_1x + b_2)Z_H(x) + s(x),$$ và họ tuyên bố rằng điều này là đủ để có được kiến ​​thức bằng không về $s(z)$.

Tôi có hai câu hỏi:

  1. Tại sao bội số của $Z_H(x)$ có độ một và không, ví dụ, bốn hoặc 69? Trong vòng 2 của PlonK, họ sử dụng chiến lược tương tự, nhưng với một đa thức bậc hai khác. Tại sao?
  2. Tại sao điều này đúng? Nếu $z \in H$, sau đó rõ ràng $s'(x)$ dẫn thông tin về $s(x)$, như $$s'(z) = s(z).$$
Vadym Fedyukovych avatar
lá cờ in
Về kiến ​​​​thức bằng không, ý bạn là thuật toán giả lập?
Bean Guy avatar
lá cờ in
@Vadym Ý tôi là che giấu thông tin theo lý thuyết
Vadym Fedyukovych avatar
lá cờ in
Re question 2: bạn có thể thấy tất cả các đa thức được đánh giá bên ngoài $H$ trong khi tạo bằng chứng không?
Bean Guy avatar
lá cờ in
@VadymFedyukovych Trong vòng tương lai ở PlonK, họ đánh giá các đa thức như $s'(x)$ bên ngoài $H$ và gửi đánh giá tới người xác minh. Mặt khác, một đánh giá của $s'(x)$ trong một phần tử của $H$ cũng sẽ cho thấy đánh giá của $s(x)$.
Vadym Fedyukovych avatar
lá cờ in
Chúng ta có thể đồng ý rằng (1) để rò rỉ thông tin về nhân chứng, cần phải đánh giá $s'()$ trên $H$, và (2) điều này xảy ra với xác suất không đáng kể? Ý bạn là gì với "nếu không"? "Không đủ điều kiện" ở trên được áp dụng cho chữ ký và cơ hội đoán một số khóa riêng tư.
Bean Guy avatar
lá cờ in
@VadymFedyukovych Vâng, chúng tôi hoàn toàn đồng ý. Mối quan tâm của tôi nhiều hơn là tại sao bậc của đa thức $b(x) = b_1x+b_2$ lại là $1$ chứ không phải, chẳng hạn như $0$ hoặc $2$.
Điểm:2
lá cờ kr
  1. bậc của đa thức làm mù mà bạn đang nhân với đa thức biến mất $Z_H$ phải được lấy mẫu từ $F_d[X]$ với $d$ lớn hơn hoặc bằng số lần đánh giá trong giao thức (lần mở). Mọi đánh giá được cung cấp cho trình xác minh đều làm rò rỉ một số thông tin về đa thức của bạn, vì vậy bạn cần ngăn chặn điều đó bằng cách chọn ngẫu nhiên đa thức của mình. giao thức Mir có một blogpost hay giải thích tại sao bạn không thể có $d$ nhỏ hơn số lần đánh giá. Tôi hiểu rằng đối với một nhân chứng cố định (đa thức là cố định ngoại trừ các yếu tố làm mù), bạn muốn có một hàm song ánh giữa các hệ số làm mù của bạn và các lỗ mở. Để chứng minh điều đó, hãy chứng minh rằng chức năng của bạn là tính từ và nội hàm.

  2. xác suất mà $z \in H$ là không đáng kể, nhưng bạn có thể thiết kế một giao thức ngăn cản bạn có $z \in H$ Tôi tin.

Bean Guy avatar
lá cờ in
Tôi không biết tại sao họ không chứng minh rằng điều này là đủ để đạt được kiến ​​thức bằng không trong giao thức PlonK. Ít nhất, họ có thể đã chỉ ra bài báo mà ý tưởng này dựa trên (tôi nghĩ nó liên quan đến một số bài báo của Groth, nhưng tôi không tìm thấy nó).

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.