En criptografía, unha proba de coñecemento cero (tamén coñecida como proba ZK ou ZKP) é un protocolo no que unha parte (o probador) pode convencer a outra (o verificador) de que unha determinada afirmación é certa, sen transmitirlle ao verificador ningunha información máis alá do mero feito de que esa afirmación é certa. A dificultade consiste en convencer da validez sen comunicar a información que permitiría comprobala directamente.
O coñecemento cero describe a información que recibe o verificador; non implica por si só que o probador coñeza un segredo. Unha proba de coñecemento require ademais que se poida extraer unha testemuña dun probador que consiga convencer coa probabilidade esixida pola definición. Esta propiedade é distinta da solidez, que impide aceptar afirmacións falsas. Versión dos autores datada o 26 de agosto de 1992, definición 3.1 e sección 4.5. Tampouco a imposibilidade de convencer terceiros é unha condición xeral: as probas non interactivas poden verificarse por máis dunha persoa.
As probas de coñecemento cero poden ser interactivas, cando o probador e o verificador intercambian mensaxes segundo un protocolo, ou non interactivas, cando abonda unha única mensaxe do probador. No modelo básico, sen unha cadea de referencia compartida nin outros recursos adicionais, as probas de coñecemento cero non interactivas só existen para linguaxes de BPP. Con recursos e hipóteses adicionais, como os modelos de cadea aleatoria común e de oráculo aleatorio, pódense construír probas de coñecemento cero non interactivas. A heurística de Fiat–Shamir substitúe os retos aleatorios do verificador por valores derivados dunha función hash; a súa seguridade debe xustificarse para o protocolo e o modelo empregados, e non transforma automaticamente calquera proba interactiva en segura. O modelo de cadea aleatoria común foi introducido por Blum, Feldman e Micali en 1988.
Exemplos abstractos A proba da carta vermella Un exemplo de proba de coñecemento cero sen matemáticas é o seguinte: Peggy quere probar a Victor que extraeu unha carta vermella dunha baralla estándar de 52 cartas, sen revelar cal é. Victor observa como Peggy saca unha carta ao azar da baralla barallada, pero ela mantén a carta boca abaixo para que el non a vexa.
Para probar que a súa carta é vermella sen revelar a súa identidade, Peggy colle as 51 cartas restantes e móstralle a Victor as 26 cartas negras (os 13 picos e os 13 trevos), unha a unha, nunha orde fixada que non dependa da carta oculta. As outras cartas permanecen ocultas. Como unha baralla estándar ten exactamente 26 cartas vermellas e 26 negras, e Peggy demostrou que todas as negras seguen na baralla, Victor pode concluír con certeza que a súa carta oculta debe ser vermella.
A proba é de coñecemento cero porque Victor só aprende que a carta de Peggy é vermella, pero non obtén ningunha información sobre se é un corazón ou un diamante, nin sobre cal das cartas vermellas é. A proba sería igual de convincente tanto se Peggy tivese o as de corazóns como o dous de diamantes. Ademais, mesmo se se gravase a interacción, a gravación non revelaría aos observadores futuros a carta concreta de Peggy.
Onde está Wally Un exemplo coñecido de proba de coñecemento cero é o de «Onde está Wally». Neste exemplo, o probador ten unha páxina dun libro infantil de Onde está Wally?, que amosa centos de personaxes de debuxos animados, dos cales só un é o personaxe visualmente distintivo de Wally. O probador quere probarlle ao verificador que sabe onde está Wally na páxina, sen revelarlle a súa localización.
Na versión descrita por Jack Murtagh, o probador cobre a páxina cun pano opaco moito maior ca o libro e despraza o libro por debaixo del para que o verificador perda a referencia da súa posición. Despois abre no pano un pequeno burato coa silueta da cara de Wally, de maneira que só se vexa o personaxe.
O verificador pode agora mirar a través do burato e ver a Wally, pero non pode ver ningunha outra parte da páxina. Polo tanto, o probador demostrou ao verificador que sabe onde está Wally, sen revelar ningunha outra información sobre a súa localización.
Trátase dunha ilustración física do concepto: ocultar o resto da páxina e a posición do libro permite mostrar o personaxe sen sinalar onde está na escena.
A cova de Alí Babá miniatura|dereita|alt=Esquema da cova con dúas rutas unidas por unha porta secreta; Peggy entra e Victor espera no exterior.|Peggy toma o camiño A ou o B, mentres Victor agarda fóra. miniatura|dereita|alt=Victor pide a Peggy que saia por unha das rutas da cova.|Victor escolle ao chou un camiño de saída. miniatura|dereita|alt=Peggy aparece pola ruta indicada por Victor.|Peggy aparece con fiabilidade na saída que Victor nomea.
Unha historia que presenta as ideas fundamentais das probas de coñecemento cero foi publicada en 1990 por Jean-Jacques Quisquater e outros no artigo «How to Explain Zero-Knowledge Protocols to Your Children». Coa colaboración de Tom Berson para a versión inglesa. As dúas partes son Peggy e Victor: Peggy é a probadora e Victor o verificador.
Nesta historia, Peggy descubriu a palabra secreta que serve para abrir unha porta máxica nunha cova. A cova ten forma de anel, coa entrada nun lado e a porta máxica bloqueando o lado oposto. Victor quere saber se Peggy coñece a palabra secreta; pero Peggy, sendo unha persoa moi reservada, non quere revelar o seu coñecemento (a palabra secreta) a Victor nin revelar o feito do seu coñecemento ao mundo en xeral.
Etiquetan os camiños desde a entrada como A e B. Primeiro, Victor agarda fóra da cova mentres Peggy entra. Peggy toma o camiño A ou o B; a Victor non se lle permite ver que camiño toma. Despois, Victor entra na cova e berra o nome do camiño polo que quere que ela volva, ben A ben B, escollido ao chou. Supoñendo que realmente coñece a palabra máxica, isto é doado: abre a porta, se é necesario, e volve polo camiño desexado.
Porén, supoñamos que non coñece a palabra. Entón, só podería volver polo camiño nomeado se Victor dese o nome do mesmo camiño polo que ela entrara. Como Victor escollería A ou B ao chou, ela tería un 50 % de probabilidades de acertar. Se repetisen este truco moitas veces, por exemplo 20 veces seguidas, a súa probabilidade de anticipar con éxito todas as peticións de Victor reduciríase a 1 entre 220, ou 9,54 × 10−7.
Así, superar todas as roldas proporciona evidencia contra a hipótese de que Peggy non coñece o segredo. O valor 2−20 é a probabilidade de superar os vinte retos sen coñecelo, baixo as condicións do exemplo; non é unha probabilidade posterior de que Peggy minta.
Observación externa Unha gravación que só amose a petición «A!» ou «B!» e a saída correspondente pode prepararse sen coñecer o segredo se as dúas persoas acordan antes a secuencia de peticións. Por iso, a cinta por si soa non permite distinguir esa simulación dunha interacción auténtica.
No relato orixinal, o reporteiro escolle a saída mediante un lanzamento de moeda filmado. Outra cadea produce unha cinta semellante cunha persoa que non coñece o segredo: grava moitos intentos, descarta os fallidos e conserva só os éxitos. Filmar a moeda non impide por si só simular a gravación deste xeito.
O exemplo ilustra a diferenza entre participar nos retos e recibir unha transcrición que tamén podería producirse sen o segredo. Non establece unha regra xeral sobre calquera observador presencial nin sobre todas as probas non interactivas.
Dúas bólas e o amigo daltónico Imaxinemos que Victor é daltónico (vermello-verde) mentres que Peggy non, e que Peggy ten dúas bólas: unha vermella e outra verde, pero idénticas en todo o demais. Para Victor, as bólas parecen completamente idénticas. Victor é escéptico respecto de que as bólas sexan realmente distinguibles. Peggy quere probarlle a Victor que as bólas son de feito de cores diferentes, pero nada máis. En particular, Peggy non quere revelar que bóla é a vermella e cal a verde.
O sistema de proba é o seguinte: Peggy dálle as dúas bólas a Victor e el colócaas detrás das costas. A continuación, colle unha das bólas, sácaa de detrás das costas e amósaa. Despois volve colocala detrás das costas e escolle amosar só unha das dúas bólas, escolléndoa ao chou con igual probabilidade. Pregúntalle a Peggy: «Cambiei a bóla?» Todo este procedemento repítese tantas veces como sexa necesario.
Mirando as cores das bólas, Peggy pode, por suposto, dicir con certeza se as cambiou ou non. Por outra banda, se as bólas fosen da mesma cor e, polo tanto, indistinguibles, a capacidade de Peggy de determinar se houbo cambio non sería mellor ca unha adiviñación aleatoria. Como a probabilidade de que Peggy acertase ao chou en identificar cada cambio/non cambio é do 50 %, a probabilidade de acertar ao chou en todos os cambios/non cambios aproxímase a cero.
Se Peggy só puidese adiviñar, a taxa de éxito converxería estatisticamente ao 50 %. O criterio do protocolo é acertar todos os retos: repetir vinte roldas con eleccións independentes limita a probabilidade de acertalos ao chou a 2−20.
A ilustración é de coñecemento cero no sentido de que Victor non aprende que bóla é a verde e cal a vermella nin como distinguilas pola cor.
Definición Unha proba de coñecemento cero dunha determinada afirmación debe satisfacer tres propiedades:
Completude: se a afirmación é certa, un probador honesto convencerá con probabilidade alta un verificador honesto (é dicir, un que segue correctamente o protocolo). Se a aceptación é segura, fálase de completude perfecta. Solidez: se a afirmación é falsa, entón ningún probador tramposo pode convencer un verificador honesto de que é certa, agás con certa probabilidade pequena. Coñecemento cero: se a afirmación é certa, o verificador non aprende información adicional. Isto formalízase esixindo que, para cada verificador eficiente, exista un simulador eficiente que, a partir da afirmación e do coñecemento previo do verificador, sen acceso ao probador nin á súa testemuña, produza unha vista que «se pareza» á dunha interacción real.
As dúas primeiras son propiedades dos sistemas de proba interactivos máis xerais. A terceira é a que fai que a proba sexa de coñecemento cero. A condición adicional de coñecemento dunha testemuña non debe confundirse con ningunha delas.
Os sistemas de proba interactivos poden admitir unha pequena probabilidade de aceptar unha afirmación falsa, chamada erro de solidez. A repetición secuencial permite reducir ese erro nas condicións apropiadas: por exemplo, acertar ao chou cen ou mil retos binarios uniformes e independentes ten probabilidade 1/2100 ou 1/21000, respectivamente. Isto non significa que as probas de coñecemento cero deixen de ser obxectos matemáticos nin que todos os protocolos teñan necesariamente erro non nulo. Nunha proba, a solidez esíxese mesmo fronte a probadores sen límite computacional; nun argumento, só fronte a probadores computacionalmente limitados.
Unha definición formal de coñecemento cero debe empregar algún modelo computacional; o máis habitual é o dunha máquina de Turing. Sexan P, V e S máquinas de Turing. Un sistema de proba interactivo dado por (P,V) para unha linguaxe L é de coñecemento cero perfecto con entrada auxiliar se, para calquera verificador de tempo polinómico probabilístico (PPT) , existe un simulador S de tempo esperado polinómico tal que:
onde indica igualdade de distribucións, non de execucións particulares. A vista do verificador inclúe a entrada, a aleatoriedade interna e as mensaxes recibidas. A cadea auxiliar z representa información previa dispoñible tamén para o simulador. O probador dunha proba pode modelarse sen límite computacional, mentres que o verificador e o simulador son eficientes; o tempo mídese no tamaño das entradas. O simulador reproduce a vista sen conversar co probador. A distinción entre tempo esperado e tempo estritamente polinómico é relevante nas construcións que empregan reinicios.