Giảm định lượng sơ đồ nhận dạng của Schnorr thành DLP

Câu hỏi

tôi tìm kiếm một tốt hơn về mặt định lượng bằng chứng của định lý 13.11 trong Katz và Lindell's Giới thiệu về mật mã học hiện đại (3^thứ phiên bản) (hoặc gần như tương đương, định lý 19.1 trong Dan Boneh và Victor Shoup có sẵn miễn phí Một khóa học sau đại học về mật mã học ứng dụng). Bằng chứng là về sơ đồ nhận dạng Schnorr cho một nhóm chung $\mathcal G$ theo thứ tự chính $q=\lvert\mathcal G\rvert$ và máy phát điện $g\in\mathcal G$, đối với khiếu nại:

Nếu vấn đề logarit rời rạc là khó so với $\mathcal G$, thì sơ đồ nhận dạng Schnorr là an toàn.

Đề án đi:

• Prover (P) rút khóa riêng $x\gets\mathbb Z_q$, tính toán và xuất bản khóa công khai $y:=g^x$, với tính toàn vẹn giả định.
• Tại mỗi lần nhận dạng:
  1. Châm (P) hòa $k\gets\mathbb Z_q$, tính toán và gửi $I:=g^k$
  2. Người xác minh (V) vẽ và gửi $r\gets\mathbb Z_q$
  3. Prover (P) tính toán và gửi $s:=r\,x+k\bmod q$
  4. Người xác minh (V) kiểm tra xem $g^s\;y^{-r}\;\overset?=\;I$

Bằng chứng được đưa ra là bằng cách đối lập. Chúng tôi giả sử một thuật toán PPT $\mathcal A$ đó, đưa ra $y$ nhưng không $x$, xác định thành công với xác suất không biến mất. Chúng tôi xây dựng thuật toán PPT sau $\mathcal A'$:

1. Chạy $\mathcal A(y)$, được phép truy vấn và quan sát bảng điểm trung thực $(I, r, s)$, trước khi đến bước tiếp theo.
2. Khi nào $\mathcal A$ đầu ra $I$, chọn $r_1\gets\mathbb Z_q$ và đưa nó cho $\mathcal A$, đáp ứng với $s_1$.
3. Chạy $\mathcal A(y)$ lần thứ hai với cùng một băng ngẫu nhiên và bản ghi trung thực, và khi nó xuất ra (giống nhau) $I$, chọn $r_2\gets\mathbb Z_q$ với $r_2\ne r_1$ và cho $r_2$ đến $\mathcal A$.

   Sau cùng, $\mathcal A$, trả lời với $s_2$.

4. tính toán $x:=(r_1-r_2)^{-1}(s_1-s_2)\bmod q$, giải DLP.

Giả sử bước 2 hoàn thành với xác suất $\epsilon$. Tôi hiểu rằng bằng chứng của cuốn sách thiết lập bước 3 hoàn thành với xác suất ít nhất $\epsilon^2-1/q$, tại sao bước 4 giải quyết được DLP, tại sao $\epsilon^2$ xuất hiện và tại sao chúng ta cần một lượng lớn $q$ để tiếp cận điều đó.

Chúng ta có thể đạt được mức giảm thuyết phục hơn về mặt định lượng đối với DLP không?

Những điều không hài lòng là: $\epsilon^2$, có thể chuyển thành xác suất thành công thấp. Chúng tôi muốn giảm khi xác suất thành công tăng tuyến tính với thời gian sử dụng, với xác suất thấp. Ngoài ra, xác suất thành công được lấy trung bình trên tất cả $y\in\mathcal G$, không phải cho một vấn đề DLP cụ thể.

Để làm cho vấn đề đầu tiên trở nên cụ thể: nếu $\mathcal A$ thành công với xác suất $\epsilon=2^{-20}$ Trong $1$ thứ hai, bằng chứng cho thấy chúng ta có thể giải một DLP trung bình với xác suất như $2^{-40}$ Trong $2$ giây. Điều đó không hữu ích trực tiếp, ngay cả khi chúng ta có thể biến nó thành xác suất $1/2$ Trong $2^{40}$ giây (11 thế kỷ). Chúng tôi muốn xác suất $1/2$ Trong $2^{21}$ giây (25 ngày).

câu trả lời dự kiến

Đây là nỗ lực của tôi, cho những lời chỉ trích. Tôi tuyên bố rằng chúng tôi có thể giải quyết bất kỳ DLP cụ thể nào trong $G$ với thời gian dự kiến $2t/\epsilon$ (và với xác suất $>4/5$ trong khoảng thời gian $3t/\epsilon$), cộng với thời gian cho các tác vụ đã xác định, giả sử một thuật toán $\mathcal A$ xác định cho một khóa công khai ngẫu nhiên trong thời gian $t$ với xác suất không biến mất $\epsilon$, và $q$ đủ lớn, chúng tôi có thể giảm giá khi đạt được một giá trị cụ thể trong một lựa chọn ngẫu nhiên trong $\mathbb Z_q$.

Yêu cầu bằng chứng:

Đầu tiên chúng tôi xây dựng một thuật toán mới $\mathcal A_0$ rằng khi nhập mô tả của thiết lập $(\mathcal G,g,q)$ và $h\in\mathcal G$

• chọn ngẫu nhiên đều $u\gets\mathbb Z_q$
• tính toán $y:=h\;g^u$
• chạy thuật toán $\mathcal A$ với đầu vào $y$ đóng vai trò là khóa công khai ngẫu nhiên
• bất cứ khi nào $\mathcal A$ yêu cầu một bảng điểm trung thực $(I, r, s)$
  • chọn ngẫu nhiên đều $r\gets\mathbb Z_q$ và $s\gets\mathbb Z_q$
  • tính toán $I:=g^s\;y^{-r}$
  • cung cấp $(I, r, s)$ đến $\mathcal A$, có thể phân biệt được với bản ghi trung thực cho khóa công khai $y$
• nếu $\mathcal A$ đầu ra $I$ trong thời gian chạy được phân bổ của nó $t$, cố gắng xác thực
  • (lưu ý: chúng tôi sẽ bắt đầu lại từ đây)
  • chọn ngẫu nhiên đều $r\gets\mathbb Z_q$ và chuyển nó đến $\mathcal A$
  • nếu $\mathcal A$ đầu ra $s$ trong thời gian chạy được phân bổ của nó $t$
    • Séc $g^s\;y^{-r}\;\overset?=\;I$ và nếu vậy, kết quả đầu ra $(u,r,s)$
    • nếu không, hủy bỏ mà không có kết quả.

thuật toán $\mathcal A_0$ là một thuật toán PPT cho bất kỳ đầu vào cố định nào $h\in\mathcal G$ có ở mỗi lần chạy xác suất $\epsilon$ đến đầu ra $(u,r,s)$, bởi vì $\mathcal A$ được chạy trong các điều kiện xác định $\epsilon$.

Chúng tôi tạo ra một thuật toán mới $\mathcal A_1$ mà trên đầu vào các thiết lập $(\mathcal G,g,q)$ và $h\in\mathcal G$

• Chạy lặp đi lặp lại $\mathcal A_0$ với đầu vào đó cho đến khi nó xuất ra $(u,r_1,s_1)$. Mỗi lần chạy có xác suất $\epsilon$ để thành công, do đó bước này dự kiến ​​sẽ yêu cầu $t/\epsilon$ thời gian chạy $\mathcal A$.
• Khởi động lại $\mathcal A_0$ từ điểm khởi động lại đã lưu ý (tương đương: chạy lại từ đầu với cùng một đầu vào và băng ngẫu nhiên cho đến điểm khởi động lại, với độ ngẫu nhiên mới sau điểm khởi động lại), cho đến khi nó xuất ra $(u,r_2,s_2)$. Mỗi lần chạy có xác suất ít nhất $\epsilon$ để thành công (bằng chứng sau từ định lý về xác suất thành công không giảm của thuật toán Tôi cố gắng hỏi một tài liệu tham khảo cho), do đó, bước này dự kiến ​​sẽ không yêu cầu nhiều hơn $t/\epsilon$ thời gian chạy $\mathcal A$.
• Trong trường hợp (được cho là rất có khả năng xảy ra) $r_1\ne r_2$, tính toán và xuất $z:=s_1-s_2-u\bmod q$.

Trong kết quả đó, cả hai lần chạy của $\mathcal A_0$ mà sản xuất $(u,r_1,s_1)$ và $(u,r_2,s_2)$ đã kiểm tra $g^{s_i}\;y^{-{r_i}}=I$ với $y=h^u$ cho cùng $u$ và $I$ điều đó $\mathcal A_0$ xác định, và $h$ chúng tôi đã đưa ra ở đầu vào của $\mathcal A_1$. Vì vậy $\mathcal A_1$ thành lập $z$ với $h=g^z$, do đó giải quyết DLP tùy ý $h$. Đó là thời gian chạy dự kiến ​​dành cho $\mathcal A$ nhiều nhất là $2t/\epsilon$, và phần còn lại làm cho $\mathcal O(\log(q))$ hoạt động nhóm cho mỗi lần chạy $\mathcal A$ và mỗi bảng điểm trung thực mà nó yêu cầu.

$\lfloor3/\epsilon\rfloor$ chạy của $\mathcal A$ là đủ để ít nhất hai trong số họ thành công với xác suất tốt hơn $1-4\,e^{-3}>4/5$: xem cốt truyện này $1-(1-\epsilon)^{\lfloor3/\epsilon\rfloor}-\lfloor3/\epsilon\rfloor\,\epsilon\,(1-\epsilon)^{\lfloor3/\epsilon\rfloor-1} $

$ \newcommand{\sR}{\mathcal{R}} \newcommand{\sG}{\mathcal{G}} \newcommand{\sB}{\mathcal{B}} $

Đây là phân tích chính xác tốt nhất mà tôi có thể đưa ra -- nó sử dụng Bổ đề tách, nhưng vẫn quyết định gõ nó lên với hy vọng ai đó có thể thấy nó hữu ích (vui lòng chỉ ra bất kỳ lỗi nào).

(Phân tích bên dưới dành cho phiên bản DLP cố định, nhưng các ý tưởng có thể được mở rộng dễ dàng.)

Bổ đề tách [Bổ đề 1, PS]: Để cho $\sG\subseteq\sR_-\times\sR_+$ được như vậy mà $$\Pr_{(\rho_-,\rho_+)\in\sR_-\times\sR_+}[(\rho_-,\rho_+)\in\sG]\geq\epsilon.$$ Bất cứ gì $\beta<\epsilon$, định nghĩa $$\sB:=\left\{(\rho_-,\rho_+)\in\sR_-\times\sR_+:\Pr_{\rho_+'\in\sR_+}[(\rho_-,\ rho_+')\in\sG\right\}.$$ Các giữ sau đây:

1. $\Pr[\sB|\sG]\geq\beta/\epsilon$ và
2. $\Pr_{\rho_+'\in\sR_+}[(\rho_-,\rho_+')\in\sG|(\rho_-,\rho_+)\in\sB]\geq \epsilon-\ phiên bản thử nghiệm.$

Đây, $\sG$ là tập hợp các đồng tiền ngẫu nhiên 'tốt' theo nghĩa những đồng tiền này dẫn đến đối thủ thành công và $\sB\subseteq\sG$ là tập hợp con của các đồng tiền ngẫu nhiên 'tốt hơn' theo nghĩa là tua lại và phát lại bằng cách sử dụng những đồng tiền này có khả năng thành công. Kết luận đầu tiên của bổ đề là một đồng xu tốt thì tốt hơn với xác suất ít nhất là $\beta/\epsilon$ và kết luận thứ hai là việc lấy mẫu lại một đồng tiền tốt hơn sẽ dẫn đến một đồng tiền tốt với xác suất ít nhất là $\epsilon-\beta$.

Việc phân tích phần đầu tiên của quy giản rất đơn giản: xác suất mà tất cả các $1/\epsilon$ thực thi thất bại là $1-(1-\epsilon)^{1/\epsilon}$. Giả sử, wlog, rằng lần thực hiện cuối cùng đã thành công. Hãy biểu thị số xu được đối thủ sử dụng trong lần thực hiện này trước và sau điểm tua lại bằng $\rho_-$ và $\rho_+$, tương ứng. Theo Bổ đề tách, xác suất để ít nhất một trong các lần phát lại thành công là $$\frac{\beta}{\epsilon}\left((1-(1-(\epsilon-\beta))^{1/\epsilon}\right).$$ Đây, $\beta/\epsilon$ là xác suất mà lần thực hiện cuối cùng (mà chúng ta biết là tốt) tốt hơn (theo kết luận $1$) và $(\epsilon-\beta)$ bên trong dấu ngoặc là xác suất lấy mẫu lại của đồng xu tốt hơn dẫn đến đồng xu tốt (theo kết luận $2$).

Để tối ưu hóa phương trình trên, hãy đặt $\beta=\epsilon(1-\epsilon)$ (gần với $\epsilon$). Điều này mang lại xác suất thành công $(1-\epsilon)(1-(1-\epsilon^2)^{1/\epsilon})$.

[PS]: Pointcheval và Stern, Đối số bảo mật cho chữ ký số và chữ ký mù, JoC 2000.

Hãy để tôi cố gắng trả lời câu hỏi của bạn :)

Trước hết, theo mô tả của bạn (tôi không có cuốn sách bạn đề cập), câu hỏi này thuộc về lý thuyết bảo mật có thể chứng minh được. Ý tưởng chung về bảo mật có thể chứng minh được là: giả sử rằng có một thuật toán/đối thủ Một có thể phá vỡ một kế hoạch dựa trên tiền điện tử với xác suất không đáng kể e, sau đó là người mô phỏng/người thách thức S có thể giải quyết một trường hợp của vấn đề toán học, sơ đồ dựa trên bằng cách tương tác với Một với xác suất không đáng kể **e' <= e** được xác định bởi xác suất thất bại.

Hơn nữa, quy trình chứng minh bảo mật phải dựa trên trò chơi/mô hình tấn công đối thủ, chẳng hạn như IND-CPA, EUF-CMA, v.v., xác định khả năng của đối thủ trong mô hình cụ thể đó. Vì vậy, tôi nghĩ rằng bằng chứng được đưa ra trong phần câu hỏi của bạn dựa trên EUF-DCMA và bằng chứng trong phần câu trả lời của bạn dựa trên EUF-CMA.

Trong một thế giới mô phỏng được tạo bởi trình giả lập, trình giả lập có thể có một số siêu năng lực, nhờ đó nó có thể giải quyết một trường hợp của một vấn đề khó khăn trong thế giới thực theo đầu ra của đối thủ. Siêu năng lực trong chứng minh trên được gọi là tua lại, nổi tiếng tua lại bổ đề mô phỏng, để trích xuất giá trị bí mật từ đầu ra của đối thủ.

Bây giờ, chúng ta hãy xem bằng chứng ban đầu. Để giải quyết DLP, trình giả lập sẽ tua lại Một tại bước 3. đó là Một đã được chạy hai lần, do đó xác suất trích xuất thành công x Là $e'=e*e=e^2$, do đây là một sự kiện liên tục. Hơn nữa, trong bước 3, xác suất của $r_1=r_2$ Là $1/q$. Vì vậy, chúng ta cũng cần phải trừ $1/q$ để sửa xác suất thành công cuối cùng $e'=e^2-1/q$.

Quá trình chứng minh bảo mật là một loại thử nghiệm tư duy, giống như Schroedinger's Cat (có thể không phù hợp), chúng ta không cần đưa nó vào thử nghiệm thực tế. Chỉ cần giảm tính bảo mật của sơ đồ xuống một hoặc nhiều vấn đề khó khăn là đủ.

Quá trình chứng minh mà bạn tuyên bố là rất thú vị và ngoài tầm hiểu biết của tôi. có một điều tuyệt vời sách để hiểu thêm về bảo mật có thể chứng minh được.