Nếu tôi hiểu đúng, bạn muốn có một cách để chứng minh, đưa ra một danh sách $\{A, B, C, D, \cdots\}$ của các khóa công khai, rằng một số khóa đã cho $K$ là "thẻ" tương ứng với một cặp khóa từ danh sách này mà không tiết lộ khóa nào. Hãy để tôi gọi đây là "thẻ hợp lệ".
Để đơn giản, giả sử rằng $K$ là thẻ của Alice và Bob. Alice hoặc Bob có thể chứng minh rằng $K$ là một thẻ hợp lệ, sử dụng các kỹ thuật chứng minh không có kiến thức tiêu chuẩn. Theo trực giác thì là thế này:
(1) Nếu cặp $(A,B)$ không được phép ẩn, thì Bob chỉ có thể thực hiện một bằng chứng không biết rằng $(G,A,B,K)$ là một bộ Diffie-Hellman, sử dụng nhân chứng của anh ta $b$ (như vậy mà $G^b = B$ và $A^b = K$). Có bằng chứng không kiến thức tiêu chuẩn cho mối quan hệ này, xem ví dụ câu trả lời của tôi đây.
(2) Để giữ ẩn cặp, ta thay câu: thay vào chứng minh “$(G,A,B,K)$ là một bộ Diffie-Hellman", Bob chứng minh mệnh đề "$(G,A,B,K)$ là một bộ Diffie-Hellman, HOẶC $(G,A,C,K)$ là một bộ Diffie-Hellman, HOẶC $(G,A,D,K)$ là một bộ Diffie-Hellman...", v.v. (đối với mỗi cặp khóa công khai riêng biệt). Sau đó, sử dụng CD HAY thủ thuật, chúng ta có thể chuyển đổi bằng chứng không kiến thức cho quan hệ Diffie-Hellman thành bằng chứng không kiến thức cho OR của nhiều quan hệ Diffie-Hellman (đặc biệt, bằng chứng thu được sẽ không tiết lộ mệnh đề nào trong OR là đúng một).
Trên đây là giải pháp đơn giản nhất, trực tiếp nhất. Tất nhiên, nó rất tốn kém: chi phí của bằng chứng tăng lên khi $n\cdot(n-1)/2$ lần chi phí của một bằng chứng Diffie-Hellman (hoặc $n$ lần nếu chúng tôi có thể tiết lộ danh tính của một trong hai bên liên quan đến thẻ $K$). Có các giải pháp để giảm chi phí, nhưng chúng sử dụng các kỹ thuật mã hóa tiên tiến hơn đáng kể. Một ví dụ điển hình là một trong nhiều bằng chứng cho phép chính xác loại bằng chứng OR này, nhưng với giao tiếp logarit trong số lượng mệnh đề OR.
Điều cuối cùng: nếu bạn muốn mọi người kiểm tra bằng chứng và không muốn thực hiện lại bằng chứng với mọi người, thì bạn có thể làm cho bằng chứng không tương tác trong mô hình tiên tri ngẫu nhiên bằng cách sử dụng biến đổi Fiat-Shamir; theo cách này, nó trở nên có thể kiểm chứng công khai. Ngoài ra, lưu ý rằng khi một bên gửi bằng chứng này, điều này sẽ luôn làm rò rỉ thông tin: ví dụ: thực tế là Bob gửi bằng chứng rằng $K$ là một thẻ hợp lệ luôn tiết lộ rằng Bob có thể tự kiểm tra điều đó ngay từ đầu, điều đó có nghĩa là khóa công khai của Bob là một trong những khóa liên quan. Nó có thể ổn trong kịch bản của bạn, nhưng bạn phải rõ ràng với điều đó.
