Dacă am înțeles bine, vrei o modalitate de a demonstra, având o listă $\{A, B, C, D, \cdots\}$ de chei publice, că unele chei date $K$ este „eticheta” corespunzătoare unei perechi de chei din această listă, fără a dezvălui care dintre ele. Permiteți-mi să numesc asta „etichetă validă”.
Pentru simplitate, să presupunem că $K$ este eticheta lui Alice și Bob. Fie Alice, fie Bob pot dovedi asta $K$ este o etichetă validă, folosind tehnici standard de demonstrare a cunoștințelor zero. Intuiția este următoarea:
(1) Dacă perechea $(A,B)$ nu trebuia să rămână ascuns, atunci Bob putea doar să facă o dovadă fără cunoștințe că $(G,A,B,K)$ este un tuplu Diffie-Hellman, folosindu-și martorul $b$ (astfel încât $G^b = B$ și $A^b = K$). Există dovezi standard de cunoștințe zero pentru această relație, vezi, de exemplu, răspunsul meu Aici.
(2) Pentru a păstra perechea ascunsă, schimbăm afirmația: în loc să dovedim "$(G,A,B,K)$ este un tuplu Diffie-Hellman”, Bob demonstrează afirmația „$(G,A,B,K)$ este un tuplu Diffie-Hellman, OR $(G,A,C,K)$ este un tuplu Diffie-Hellman, OR $(G,A,D,K)$ este un tuplu Diffie-Hellman..." și așa mai departe (pentru fiecare pereche de chei publice distincte). Apoi, folosind CDS OR-truc, putem converti dovada zero-cunoștințe pentru relația Diffie-Hellman într-o dovadă zero-cunoaștere pentru un OR a mai multor relații Diffie-Hellman (în special, demonstrația rezultată nu va dezvălui care dintre afirmațiile din OR este adevărată unu).
Cele de mai sus este cea mai simplă, cea mai directă soluție. Desigur, este scump: costul probei crește pe măsură ce $n\cdot(n-1)/2$ de ori costul unei singure dovezi Diffie-Hellman (sau $n$ ori dacă putem scurge identitatea uneia dintre cele două părți implicate în etichetă $K$). Există soluții de reducere a costurilor, dar folosesc tehnici criptografice mult mai avansate. Un bun exemplu sunt una din multe dovezi care permit tocmai acest tip de demonstrații OR, dar cu comunicare logaritmică în numărul de clauze OR.
Ultimul lucru: dacă doriți ca toată lumea să verifice dovada și nu doriți să refacă dovada cu toată lumea, atunci puteți face ca dovada să nu fie interactivă în modelul de oracol aleatoriu folosind transformarea Fiat-Shamir; în acest fel, devine verificabil public. De asemenea, rețineți că atunci când o parte trimite această dovadă, aceasta va scurge întotdeauna informații: de ex. faptul că Bob trimite dovada că $K$ este o etichetă validă dezvăluie întotdeauna că Bob ar putea verifica asta în primul rând, ceea ce înseamnă că cheia publică a lui Bob este una dintre cheile implicate. Ar putea fi ok în scenariul tău, dar trebuie să fii clar cu asta.
