Cách rẻ nhất để chứng minh rằng hai khóa riêng khác nhau được biết bởi cùng một người?

Giả sử rằng có hai cặp khóa ECC không liên quan ($Pub_1$, $Priv_1$) và ($Pub_2$, $Priv_2$). Alice tuyên bố rằng cô ấy biết cả hai $Priv_1$ và $Priv_2$, nhưng Bob không tin cô ấy và nghĩ rằng $Priv_2$ chỉ được biết đến với Eve, bạn của Alice.

Bob yêu cầu Alice chứng minh rằng cô ấy kiểm soát cả hai khóa riêng. Bây giờ, Bob biết rằng nếu Eve thực sự kiểm soát $Priv_2$, cô ấy sẵn sàng thông đồng với Alice để tạo ra bằng chứng rằng Alice kiểm soát cả hai. Nhưng anh ấy cũng biết rằng lòng tin của Eve có hạn—Eve sẽ không thực sự sẵn lòng nói cho Alice biết khóa riêng $Priv_2$.

Bằng chứng nào Alice có thể cung cấp cho Bob rằng cô ấy (hoặc ít nhất là cùng một người) biết cả hai $Priv_1$ và $Priv_2$? Lưu ý rằng ví dụ. một chữ ký lồng nhau như ví dụ. $Sig_1(Sig_2(tin nhắn))$ là không đủ, bởi vì Eve chỉ có thể tạo ra $Sig_2(tin nhắn)$ và đưa nó cho Alice để gói vào $Sig_1$ mà không bao giờ tiết lộ $Priv_2$.

Một vấn đề phức tạp khác: bằng chứng cần hoạt động hiệu quả trên đường cong secp256k1. (Tôi đã xem xét sử dụng zkSNARK cho việc này, nhưng các thư viện SNARK mà tôi thấy không hoạt động hiệu quả trên đường cong đó.)

Điều này dường như về mặt lý thuyết là không thể. Theo như tôi có thể nói, không có sự khác biệt giữa việc biết $priv_2$ và thông đồng với ai đó biết $priv_2$.

Giả sử một số giao thức chứng minh $\Pi$ tồn tại giữa người chứng minh (A) và người xác minh (B), đáp ứng các yêu cầu được mô tả. Luôn luôn có một cách để $A(priv_1)$ và $E(priv_2)$ câu kết với nhau để thực hiện $\Pi$ theo một cách mà $A$ không học được gì về $priv_2$. $A$ và $E$ chỉ cần chạy một số giao thức MPC để tính toán phản hồi tiếp theo cho $B$.

Tính bảo mật của giao thức MPC đảm bảo rằng $A$ không học gì hơn ngoài đầu vào của chính nó $priv_1$ và các kết quả đầu ra, đó là những phản hồi đối với $B$, mà mọi người đều có thể nhìn thấy. Và nếu $\Pi$ là không có kiến ​​​​thức để $B$ (thường mong muốn), sau đó $A$ không học được gì từ các câu trả lời.

Tuyên bố miễn trừ trách nhiệm: Tôi không có bằng chứng bảo mật cho chương trình này. Những lời chỉ trích đều được hoan nghênh.

Để đơn giản hóa ký hiệu, tôi gọi hai cặp khóa (riêng tư, công khai) $(a, A = a\cdot G)$ và $(b, B = b\cdot G)$ trên điểm cơ sở $G$. Chữ thường là số vô hướng, chữ hoa là điểm EC. $H_s()$ có nghĩa là băm và giảm (sửa đổi thứ tự của $G$) thành vô hướng. Tất cả các hoạt động giữa các đại lượng vô hướng (chẳng hạn như phép trừ và phép nhân) được điều chỉnh theo thứ tự của $G$.

Đầu tiên, khai báo $D = a\cdot b\cdot G$.

để cho $m = H_s(\text{"tin nhắn đang được ký"})$ dưới dạng tin nhắn một lần sẽ ngăn việc sử dụng lại chữ ký này trong các ngữ cảnh.

Để chứng minh $D$ thực sự được xây dựng đúng cách, hãy sử dụng chữ ký Schnorr mở rộng:

Chữ ký là $(Đ, c, r)$ ở đâu $k$ là một đại lượng ngẫu nhiên, $c = H_s(m \mathbin\| k\cdot G \mathbin\| k\cdot B)$ và $r = k - c\cdot a$.

Chữ ký được xác minh bằng cách kiểm tra $c \overset{?}{=} H_s(m \mathbin\| r\cdot G + c\cdot A \mathbin\| r\cdot B + c\cdot D)$ và bằng cách kiểm tra $D$ là một điểm hợp lệ và không phải là điểm ở vô cực.

Điều này chứng minh cả rằng $a$ được biết đến, và điều đó $a$ vừa là khóa riêng của điểm $A$ trên điểm máy phát điện $G$, và cũng là khóa riêng của điểm $D$ trên điểm máy phát điện $B$. Vì vậy $D$ được chứng minh là $a\cdot b\cdot G$.

Cuối cùng, chúng ta cần tạo chữ ký thứ hai chứng minh rằng ai đó biết cả hai $a$ và $b$. Chúng ta có thể làm điều đó bằng cách chứng minh kiến ​​thức về khóa bí mật của điểm $D$ trên điểm cơ sở $G$ (do đó chứng minh kiến ​​thức về $a\cdot b$).

Chữ ký là $(c', r')$ ở đâu $k'$ là một đại lượng ngẫu nhiên, $c' = H_s(m \mathbin\| k'\cdot G)$ và $r' = k' - c'\cdot a\cdot b$.

Chữ ký được xác minh bằng cách kiểm tra $c' \overset{?}{=} H_s(m \mathbin\| r'\cdot G + c'\cdot D)$.

Nếu Alice thông đồng với Eve mà Eve không tiết lộ $b$, Alice sẽ phải tiết lộ khóa riêng của mình $a$ đến đêm giao thừa. Kiến thức về $k'$ bởi một trong hai người thông đồng sẽ cho phép người thông đồng đó tính toán khóa riêng của người thông đồng kia. Tính bảo mật của sơ đồ này phụ thuộc vào việc Alice không thể thông đồng với Eve về mặt toán học để xây dựng $r'$ sao cho Alice hoặc Eve sau đó có thể xác định bằng toán học khóa riêng của người kia.

Do đó, chữ ký tổng thể là $(D, c, r, c', r')$ và là $5\cdot 32 = 160$ byte.