zkSnark Giới thiệu bởi Maksym Petkus: Đa thức được xác định trên $Z$ hay nó được xác định trên $Z_n$?

Tôi đang đọc phần giải thích về zkSnark được viết bởi Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Ở đây anh ta có một đa thức $p(x) = x^3 â 3x^2 + 2x$

và mã hóa đồng cấu được định nghĩa là $E(c) = g^c \bmod 7$

Có một chút không rõ ràng về nơi đa thức được xác định trên $Z$ hoặc nó được định nghĩa trên $Z_7$ - nó để lại một chút mơ hồ trong văn bản.

Điều này quan trọng trong bước mà người xác minh đánh giá $E(h.t) = E(h)^t$. Tôi có thể giải thích rõ hơn câu hỏi của mình với $Z_{11}$ thay vì $Z_7$, vì vậy tôi đang sử dụng $Z_{11}$ phía dưới.

Hãy giả sử $E(c) = g^c \bmod 11$

Mẫu xác minh tại s = 14

$E(s^0)= 5, E(s^1)= 9, E(s^2) = 5, E(s^3) = 9$

Tục ngữ tính toán $E(p(s)) = (9 * 5^{-3} * 9^2) \bmod 11 = 9$

tính toán $E(h(s)) = 5$. Gửi E(p)= 9 và E(h) = 9 cho người xác minh

Người xác minh tính toán t(s=14) Xét hai trường hợp

Trường hợp 1: Đa thức đã hết $Z$ Trong trường hợp này, t(s=14) = (13*12) = 156 Cho nên $E(h)^t$ = $9^156 \bmod 11 = 9$

Vì vậy, nó xác minh -> $E(p) = E(h)^t$

Trường hợp2: Đa thức đã hết $Z_{11}$ Trong trường hợp này, t(s=14) = (13*12)%11 = 2 Cho nên $E(h)^t$ = $9^2 \bmod 11 = 4$. Ở đây nó không xác minh.

Lý do nó không xác minh là vì

$g^c \bmod m$ = $g^{c \bmod m-1} \bmod m$

tức là t(s) cần giảm đi 10 chứ không phải 11. Tuy nhiên nếu đa thức vượt quá $Z_{11}$, thì nó bị giảm đi 11 thay vì 10.

Vì vậy, dựa trên điều này, tôi nghĩ rằng đa thức được định nghĩa trên $Z$ thay vì kết thúc $Z_7$.

Tuy nhiên ở trang 7, ông viết

trong khi về mặt lý thuyết các hệ số đa thức $c_i$ có thể có một loạt các giá trị, trong thực tế, nó có thể khá hạn chế (6 trong ví dụ trước)

6 từ đâu đến đây? Nếu nó kết thúc $Z$, thì hệ số có thể là bất kỳ số nguyên nào. Nếu anh ấy viết nó giới hạn ở 6, thì nó phải vượt qua một số $Z_n$. Nếu nó đã kết thúc $Z_7$, thì nó sẽ bị giới hạn ở 7 chứ không phải 6. Nếu nó đã kết thúc $Z_6$, thì nó sẽ bị giới hạn ở mức 6 đô la.

Vậy là đa thức được xác định hay $Z$ hoặc nó được định nghĩa trên $Z_7$ hoặc nó được định nghĩa trên $Z_6$?

Những gì chúng tôi muốn cho các ứng dụng chung nhất là cho $p(x)$ được xác định trên $\mathbb Z$. Tuy nhiên, không có lược đồ mật mã đồng hình hữu hạn, tổng quát nào mà chúng ta có thể ánh xạ một cách tự động các phần tử của $\mathbb Z$. Thay vào đó, chúng ta phải ánh xạ vào một trường nguyên tố lớn (lưu ý rằng phần 3.2 không sử dụng miền tích phân), điều này đủ để chứng minh kiến ​​thức về $p(x)$ được xây dựng từ các nghiệm số nguyên nhỏ. Nhóm này được biểu diễn dưới dạng nhóm con thứ tự nguyên tố của bất kỳ nhóm mật mã nào chúng tôi đang sử dụng (chúng tôi có thể làm việc trong nhóm đầy đủ, nhưng như đã lưu ý, điều này dẫn đến vấn đề không phải là một miền tích hợp). Trong trường hợp của nhóm $(\mathbb Z/7\mathbb Z)^\times$, nhóm có thứ tự 6 và chúng tôi nghĩ rằng vì mục đích xác minh $p(x)$ được định nghĩa trên $\mathbb Z/6\mathbb Z$ nếu chúng tôi không quan tâm đến việc làm việc trong một miền tích hợp. Do đó, trong ví dụ mod 11 của bạn $p(x)$ nên được coi là một mod đa thức 10 (một lần nữa bỏ qua các vấn đề về miền không tách rời). Như bạn có thể nói, các ví dụ nhỏ như thế này gặp phải tất cả các vấn đề về sự mơ hồ, điều này sẽ khó xảy ra khi kích thước của nhóm con tăng lên tương ứng với kích thước và số lượng gốc.