Prova de conhecimento

Na criptografia, uma prova de conhecimento (proof of knowledge) é um sistema de prova interativa no qual o provador consegue "convencer" um verificador de que detém uma determinada informação. O significado de uma máquina abstrata "saber algo" é definido em termos computacionais: uma máquina "sabe algo" se essa informação puder ser computada tomando a própria máquina como entrada. Como o programa do provador não necessariamente revela o conhecimento em si (como ocorre nas provas de conhecimento zero), introduz-se uma máquina com um programa distinto, chamada de extrator de conhecimento, para formalizar essa ideia. Esse conceito restringe-se principalmente ao que pode ser provado por máquinas limitadas a tempo polinomial. Nesse contexto, o conjunto de elementos de conhecimento limita-se a um conjunto de testemunhas de alguma linguagem formal em NP.

Seja x uma afirmação da linguagem L em NP, e W(x) o conjunto de testemunhas para x que devem ser aceitas na prova. Isso permite definir a seguinte relação: R={(x,w):x∈L,w∈W(x)}.

Uma prova de conhecimento para a relação R com erro de conhecimento κ é um protocolo de duas partes entre um provador P e um verificador V que satisfaz as duas propriedades a seguir:

  1. Completude (Completeness): Se (x,w)∈R, então o provador P, que conhece a testemunha w para x, consegue convencer o verificador V de seu conhecimento. Mais formalmente: Pr⁡(P(x,w)↔V(x)→1)=1, ou seja, dada a interação entre o provador P e o verificador V, a probabilidade de o verificador ser convencido é 1.
  2. Validade (Validity): A validade exige que a probabilidade de sucesso de um extrator de conhecimento E em extrair a testemunha, dado o acesso de oráculo a um provador possivelmente malicioso P~, seja pelo menos tão alta quanto a probabilidade de sucesso do provador P~ em convencer o verificador. Essa propriedade garante que nenhum provador que desconheça a testemunha consiga convencer o verificador.

Detalhes sobre a definição

Esta é uma definição mais rigorosa de Validade:

Seja R uma relação de testemunha, W(x) o conjunto de todas as testemunhas para o valor público x e κ o erro de conhecimento. Uma prova de conhecimento é κ-válida se existir uma máquina de tempo polinomial E, com acesso de oráculo a P~, tal que, para todo P~, tenha-se EP~(x)(x)∈W(x)∪{⊥} e Pr⁡(EP~(x)(x)∈W(x))≥Pr⁡(P~(x)↔V(x)→1)−κ(x).

O símbolo ⊥ indica que a máquina de Turing E não chegou a uma conclusão (ou falhou na extração).

O erro de conhecimento κ(x) representa a probabilidade de o verificador V aceitar x mesmo quando o provador, na verdade, não conhece uma testemunha w. O extrator de conhecimento E é utilizado para formalizar o que se entende pelo conhecimento de uma máquina de Turing: se E conseguir extrair w a partir de P~, dizemos que P~ conhece o valor de w.

Essa definição da propriedade de validade combina os conceitos de validade e validade forte. Para erros de conhecimento negligenciáveis κ(x), como 2−80 ou 1/poly(|x|), ela pode ser considerada mais forte do que a solidez (soundness) de provas interativas comuns.

Relação com provas interativas gerais

Para especificar uma prova de conhecimento, é necessário definir não apenas a linguagem, mas também as testemunhas que o provador deve conhecer. Em alguns casos, provar a pertinência a uma linguagem pode ser fácil, enquanto computar uma testemunha específica é computacionalmente difícil. O exemplo a seguir ilustra essa diferença:

Seja ⟨g⟩ um grupo cíclico com gerador g no qual se presume que o problema do logaritmo discreto seja difícil. Decidir a pertinência à linguagem L={x∣gw=x} é trivial, já que todo elemento x∈⟨g⟩ pertence a ela. No entanto, encontrar a testemunha w tal que gw=x equivale a resolver o problema do logaritmo discreto.

Protocolos

Protocolo de Schnorr

Uma das provas de conhecimento mais simples e amplamente utilizadas, a prova de conhecimento de um logaritmo discreto, foi proposta por Claus Schnorr. O protocolo é definido sobre um grupo cíclico Gq de ordem q com gerador g.

Para provar o conhecimento de x=loggy, o provador interage com o verificador em três etapas:

  1. Na primeira rodada, o provador compromete-se com um valor aleatório r; por isso, a primeira mensagem t=gr é chamada de compromisso (commitment).
  2. O verificador responde com um desafio (challenge) c escolhido aleatoriamente.
  3. Após receber c, o provador envia a terceira e última mensagem (a resposta ou response) s=r+cx, calculada módulo a ordem do grupo (q).

O verificador aceita a prova se gs=tyc.

Podemos confirmar que se trata de uma prova de conhecimento válida porque existe um extrator que opera da seguinte maneira:

  1. Simula o provador para obter a saída t=gr. O provador encontra-se agora no estado Q.
  2. Gera um valor aleatório c1 e o fornece como entrada ao provador, obtendo a saída s1=r+c1x.
  3. Retrocede o provador ao estado Q, gera um novo valor aleatório c2≠c1 e o fornece ao provador para obter s2=r+c2x.
  4. Calcula e retorna (s1−s2)(c1−c2)−1modq.

Como (s1−s2)=(r+c1x)−(r+c2x)=x(c1−c2), a saída do extrator é exatamente x.

Este protocolo também é uma prova de conhecimento zero, embora essa propriedade não seja um requisito obrigatório para uma prova de conhecimento.

Protocolos Sigma

Protocolos que seguem essa estrutura de três movimentos (compromisso, desafio e resposta) são denominados protocolos sigma. O nome deriva da letra grega Sigma (Σ), cujo formato em zigue-zague simboliza os três passos da interação, ou ainda de Sig (assinatura) e MA, abreviação de "Merlin-Arthur". Existem protocolos sigma para provar diversas afirmações, especialmente aquelas relacionadas a logaritmos discretos. Por meio dessas provas, o provador pode demonstrar não apenas o conhecimento do logaritmo discreto, mas também que ele satisfaz determinadas restrições algébricas. Por exemplo, é possível provar que dois logaritmos de y1 e y2 nas bases g1 e g2 são iguais ou obedecem a alguma relação linear. Para elementos a e b de ℤq, dizemos que o provador demonstra o conhecimento de x1 e x2 tais que y1=g1x1∧y2=g2x2 e x2=ax1+b. A igualdade corresponde ao caso particular em que a=1 e b=0. Como x2 pode ser computado de forma trivial a partir de x1, isso equivale a provar o conhecimento de um x tal que y1=g1x∧y2=(g2a)xg2b.

Essa é a intuição por trás da seguinte notação, amplamente usada na literatura para expressar o que está sendo demonstrado em uma prova de conhecimento:

PK{(x):y1=g1x∧y2=(g2a)xg2b},

que afirma que o provador conhece um valor x que satisfaz a relação especificada.

Aplicações

As provas de conhecimento são ferramentas fundamentais para a construção de protocolos de identificação e, em sua variante não interativa, de esquemas de assinatura digital, como a Assinatura de Schnorr.

Elas também são amplamente empregadas na construção de sistemas de assinatura de grupo e de credenciais digitais anônimas.

Ver também