TL, DR: một sự kết hợp của đơn giản $\Sigma$-protocols có thể chứng minh câu lệnh ghép này mà không cần kiến thức. Tuy nhiên, bằng chứng là hơi lớn.
Trước tiên, hãy chia nhỏ câu lệnh ghép của bạn thành các câu lệnh đơn giản hơn. Quan sát rằng về cơ bản, bạn muốn chứng minh kiến thức bằng không cho $C_1=m^e$ và $C_2=g^m$ rằng mối quan hệ sau đây $\mathcal{R}(x,\omega)$ ($x$ là tham số công khai và $\omega$ là nhân chứng) cho rằng: $$\mathcal{R}=\{((C_1,C_2),(m,l)):m\in QR_{N}\land C_1=m^e\bmod{N}\land C_2=g^m \bmod{p}\}, $$
ở đâu $l$ là căn bậc hai của $m\bmod{N}$, tức là, nhân chứng là $(m,l)$ đôi. Để đơn giản, hãy sử dụng ký hiệu sau cho các câu lệnh cơ bản: $$\mathcal{R}_1=\{((C_1,C_2),(m,l)):m\in QR_{N}\}, $$
$$\mathcal{R}_2=\{((C_1,C_2),(m,l)): C_1=m^e\bmod{N}\}, $$
$$\mathcal{R}_3=\{((C_1,C_2),(m,l)):C_2=g^m\bmod{p}\}. $$
Lưu ý rằng cả hai câu lệnh cơ bản $\mathcal{R}_2$ và $\mathcal{R}_3$ dễ chứng minh với $\Sigma$-giao thức, vì cả hai quan hệ đều chứng minh kiến thức về một tiền ảnh theo một nhóm đồng hình (tức là, của $w$ thỏa mãn $x=\phi(w)$). Trong trường hợp $\mathcal{R}_2$ nhóm đồng hình $\phi(\omega)=\omega^e$, trong khi ở $\mathcal{R}_3$, đồng cấu là $\phi(\omega)=g^{\omega}$. Đây là những phát biểu khá chuẩn và bạn có thể tìm cách chứng minh tiền ảnh của một phép đồng hình trong Banger và cộng sự. hoặc trong sách Boneh-Shoup, trong số nhiều người khác.
Để chứng minh $\mathcal{R}_1$ có một chút khó khăn ngay từ cái nhìn đầu tiên, vì $m$ cần được giữ bí mật và chúng tôi muốn chứng minh rằng $m$ là dư lượng bậc hai, tức là, $m\in QR_N$. Trong hầu hết các triển khai của hệ thống mật mã RSA $e$ là số lẻ (tôi cho rằng đây cũng là trường hợp trong ứng dụng của bạn), vì vậy $C_1=m^e\in QR_{N} \iff m\in QR_{N}$. Tôi cũng cho rằng người mã hóa biết $l$, một trong những căn bậc hai của $m$, vì hệ số hóa chưa được biết. Nếu bộ mã hóa không biết một $l$, thì nó không thể chứng minh rằng nó là dư bậc hai, bởi vì nó không biết phân tích thành nhân tử. Với cuộc thảo luận này, bây giờ $\mathcal{R}_1$ về cơ bản đòi hỏi phải chứng minh tuyên bố sau: $$\mathcal{R}_1=\{((C_1),(l)):C_1=l^{2e}\bmod{N}\}, $$
đó lại là một bằng chứng về kiến thức về tiền ảnh của một nhóm đồng hình. Chúng tôi biết làm thế nào để chứng minh tuyên bố này.
Để kết hợp tất cả những thứ này để có được bằng chứng không kiến thức cho câu lệnh ghép $\mathcal{R}$, người xác minh chỉ cần gửi cùng một thử thách ngẫu nhiên cho tất cả các câu lệnh cơ bản (mặc dù thử thách ngẫu nhiên là khác nhau giữa các lần lặp lại giao thức!).
kích thước của bằng chứng là gì? Vì $\Sigma$-Các giao thức trong nhóm không rõ thứ tự, độ sai số cao nên cần lặp lại $\Sigma$-giao thức nhiều lần để đạt được mức độ hợp lý của âm thanh. Trong mỗi lần lặp lại, sai số âm thanh giảm đi $\xấp xỉ 1/2$. Do đó, giao thức phải được lặp lại tuần tự để nhận được lỗi kiến thức đủ nhỏ (ví dụ: $80$ lặp lại tuần tự được yêu cầu để có được một lỗi kiến thức của $1/2^{80}$). Điều này sẽ dẫn đến một bằng chứng bao gồm $2*2*80=320$ nhóm các phần tử cho $3$ các câu lệnh cơ bản (2 trong số các câu lệnh xảy ra trong một nhóm RSA, do đó chúng ta cần lặp lại nhiều lần).
Để tránh giới hạn hiệu quả này, bạn cần sử dụng một chuỗi tham chiếu chung để giảm kích thước bằng chứng. Nhìn thấy Banger và cộng sự.
Hy vọng, điều này sẽ giúp! Hãy cho tôi biết nếu tôi để lại bất kỳ vùng màu xám nào trong câu trả lời!
