Prova de conhecimento

Na criptografia, uma prova de conhecimento é uma prova interativa na qual o provador consegue "convencer" um verificador de que sabe algo. O que significa para uma máquina "saber algo" é definido em termos de computação. Uma máquina "sabe algo" se esse algo puder ser computado, dado à máquina como entrada. Como o programa do provador não necessariamente produz o conhecimento em si (como é o caso das provas de conhecimento zero), uma máquina com um programa diferente, chamado extrator de conhecimento, é introduzida para capturar essa ideia. Estamos principalmente interessados no que pode ser provado por máquinas limitadas em tempo polinomial. Nesse caso, o conjunto de elementos de conhecimento é limitado a um conjunto de testemunhas de alguma linguagem em NP.

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

Uma prova de conhecimento para a relação $R$ com erro de conhecimento $\kappa$ é um protocolo de duas partes com um provador $P$ e um verificador $V$ com as duas propriedades a seguir:

1. Completude: Se $(x,w)\in 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)\leftrightarrow V(x)\rightarrow 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: A validade requer que a probabilidade de sucesso de um extrator de conhecimento $E$ em extrair a testemunha, dado acesso oracular a um provador possivelmente malicioso ${\tilde {P}}$, seja pelo menos tão alta quanto a probabilidade de sucesso do provador ${\tilde {P}}$ em convencer o verificador. Essa propriedade garante que nenhum provador que não conheç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 $\kappa$ o erro de conhecimento. Uma prova de conhecimento é $\kappa$-válida se existir uma máquina de tempo polinomial $E$, dado acesso oracle a ${\tilde {P}}$, tal que para cada ${\tilde {P}}$, é o caso que $E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}$ e $\Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x)$.

O resultado $\bot$ significa que a máquina de Turing $E$ não chegou a uma conclusão.

O erro de conhecimento $\kappa (x)$ denota a probabilidade de que o verificador $V$ possa aceitar $x$, mesmo que o provador não conheça de fato uma testemunha $w$. O extrator de conhecimento $E$ é usado para expressar o que se entende por conhecimento de uma máquina de Turing. Se $E$ pode extrair $w$ de ${\tilde {P}}$, dizemos que ${\tilde {P}}$ conhece o valor de $w$.

Esta definição da propriedade de validade é uma combinação das propriedades de validade e validade forte. Para pequenos erros de conhecimento $\kappa (x)$, como por exemplo $2^{-80}$ ou $1/\mathrm {poly} (|x|)$, ela pode ser vista como sendo mais forte do que a solidez de provas interativas comuns.

Relação com provas interativas gerais

Para definir uma prova de conhecimento específica, é necessário não apenas definir a linguagem, mas também as testemunhas que o verificador deve conhecer. Em alguns casos, provar a pertinência a uma linguagem pode ser fácil, enquanto calcular uma testemunha específica pode ser difícil. Isso é melhor explicado usando um exemplo:

Seja $\langle g\rangle$ um grupo cíclico com gerador $g$ no qual se acredita que resolver o problema do logaritmo discreto seja difícil. Decidir a pertinência à linguagem $L=\{x\mid g^{w}=x\}$ é trivial, pois todo $x$ está em $\langle g\rangle$. No entanto, encontrar a testemunha $w$ tal que $g^{w}=x$ seja válido corresponde a resolver o problema do logaritmo discreto.

Protocolos

Protocolo de Schnorr

Uma das provas de conhecimento mais simples e frequentemente utilizadas, a prova de conhecimento de um logaritmo discreto, deve-se a Schnorr. O protocolo é definido para um grupo cíclico $G_{q}$ de ordem $q$ com gerador $g$.

Para provar o conhecimento de $x=\log _{g}y$, o provador interage com o verificador da seguinte forma:

1. Na primeira rodada, o provador se compromete com a aleatoriedade $r$; portanto, a primeira mensagem $t=g^{r}$ também é chamada de compromisso.
2. O verificador responde com um desafio $c$ escolhido aleatoriamente.
3. Após receber $c$, o provador envia a terceira e última mensagem (a resposta) $s=r+cx$ módulo reduzido à ordem do grupo.

O verificador aceita, se $g^{s}=ty^{c}$.

Podemos ver que esta é uma prova de conhecimento válida porque possui um extrator que funciona da seguinte maneira:

1. Simule o provador para gerar $t=g^{r}$. O provador está agora no estado $Q$.
2. Gere um valor aleatório $c_{1}$ e insira-o no provador. Ele gera $s_{1}=r+c_{1}x$.
3. Retorne o provador para o estado $Q$. Agora gere um valor aleatório diferente $c_{2}$ e insira-o no provador para obter $s_{2}=r+c_{2}x$.
4. Imprima $(s_{1}-s_{2})(c_{1}-c_{2})^{-1}$.

Como $(s_{1}-s_{2})=(r+c_{1}x)-(r+c_{2}x)=x(c_{1}-c_{2})$, a saída do extrator é precisamente $x$.

Este protocolo é de conhecimento zero, embora essa propriedade não seja necessária para uma prova de conhecimento.

Protocolos Sigma

Protocolos que possuem a estrutura de três movimentos acima (comprometimento, desafio e resposta) são chamados de protocolos sigma. A nomenclatura se origina de Sig, referindo-se ao zigue-zague que simboliza os três movimentos do protocolo, e MA, uma abreviação de "Merlin e Arthur". Os protocolos sigma existem para provar várias afirmações, como aquelas referentes a logaritmos discretos. Usando essas provas, o provador pode não apenas provar o conhecimento do logaritmo discreto, mas também que o logaritmo discreto possui uma forma específica. Por exemplo, é possível provar que dois logaritmos de $y_{1}$ e $y_{2}$ em relação às bases $g_{1}$ e $g_{2}$ são iguais ou preenchem alguma outra relação linear. Para os elementos a e b de $Z_{q}$, dizemos que o provador prova o conhecimento de $x_{1}$ e $x_{2}$ tais que $y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}$ e $x_{2}=ax_{1}+b$. A igualdade corresponde ao caso especial em que a =1 e b = 0. Como $x_{2}$ pode ser calculado trivialmente a partir de $x_{1}$, isso equivale a provar o conhecimento de um x tal que $y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}$.

Esta é a intuição por trás da seguinte notação, que é comumente usada para expressar o que exatamente é provado por uma prova de conhecimento.

$PK\{(x):y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}\}$,

afirma que o provador conhece um x que preenche a relação acima.

Aplicações

Provas de conhecimento são ferramentas úteis para a construção de protocolos de identificação e, em sua variante que não é interativa, esquemas de assinatura. Tais esquemas são:

• Assinatura de Schnorr

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

Ver também

• Protocolo criptográfico
• Prova de conhecimento zero
• Sistema de prova interativa