Prova de conhecimento

Na criptografia, uma prova de conhecimento é uma prova interativa na qual o provador consegue "convencer" um verificador de que o provador 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 pode ser calculado, dado a máquina como uma entrada. Como o programa do provador não expele necessariamente o conhecimento em si (como é o caso das provas de conhecimento zero^[1]), uma máquina com um programa diferente, chamado extrator de conhecimento, é introduzida para capturar essa ideia. Estamos principalmente interessados no que pode ser comprovado por máquinas de tempo polinomial limitado. Neste caso, o conjunto de elementos de conhecimento se limita a um conjunto de testemunhas de alguma linguagem em NP.

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

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

1. Integridade: Se ${\displaystyle (x,w)\in R}$, então o provador ${\displaystyle P}$ que conhece a testemunha ${\displaystyle w}$ para ${\displaystyle x}$ é bem sucedido em convencer o verificador ${\displaystyle V}$ de seu conhecimento. Mais formalmente: ${\displaystyle \Pr(P(x,w)\leftrightarrow V(x)\rightarrow 1)=1}$, isto é, dada a interação entre o provador P e o verificador V, a probabilidade de o verificador estar convencido é 1.
2. Validade: A validade requer que a probabilidade de sucesso de um extrator de conhecimento ${\displaystyle E}$ em extrair a testemunha, dado ao oráculo acesso a um provador possivelmente malicioso ${\displaystyle {\tilde {P}}}$, deve ser pelo menos tão alta quanto a probabilidade de sucesso do provador ${\displaystyle {\tilde {P}}}$ em convencer o verificador. Esta propriedade garante que nenhum provador que não conheça a testemunha consiga convencer o verificador.

Esta é uma definição mais rigorosa de validade:^[2]

Seja ${\displaystyle R}$ uma relação de testemunha, ${\displaystyle W(x)}$ o conjunto de todas as testemunhas para valor público ${\displaystyle x}$ e ${\displaystyle \kappa }$ o erro de conhecimento. Uma prova de conhecimento é ${\displaystyle \kappa }$-válida se existe uma máquina de tempo polinomial ${\displaystyle E}$, dado ao oráculo acesso a ${\displaystyle {\tilde {P}}}$, tal que para cada ${\displaystyle {\tilde {P}}}$, é o caso que ${\displaystyle E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}}$ e ${\displaystyle \Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).}$

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

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

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

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

Seja ${\displaystyle \langle g\rangle }$ um grupo cíclico com gerador ${\displaystyle g}$ no qual se acredita que resolver o problema de logaritmo discreto é difícil. Decidir a participação na linguagem ${\displaystyle L=\{x\mid g^{w}=x\}}$ é trivial, pois todo ${\displaystyle x}$ está em ${\displaystyle \langle g\rangle }$. No entanto, encontrar a testemunha ${\displaystyle w}$ de modo que ${\displaystyle g^{w}=x}$ se mantenha corresponde a resolver o problema de logaritmo discreto.

Uma das provas de conhecimento mais simples e frequentemente usadas, a prova de conhecimento de um logaritmo discreto, é devida a Schnorr.^[3] O protocolo é definido para um grupo cíclico ${\displaystyle G_{q}}$ da ordem ${\displaystyle q}$ com gerador ${\displaystyle g}$.

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

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

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

Podemos ver que esta é uma prova válida de conhecimento, pois possui um extrator que funciona da seguinte forma:

1. Simula o provador para produzir ${\displaystyle t=g^{r}}$. O provador está agora no estado math>Q</math>.
2. Gera valor aleatório ${\displaystyle c_{1}}$ e o insire no provador. Ele produz ${\displaystyle s_{1}=r+c_{1}x}$.
3. Retrocede o provador para declarar ${\displaystyle Q}$. Agora gera um valor aleatório diferente ${\displaystyle c_{2}}$ e o insire no provador para obter ${\displaystyle s_{2}=r+c_{2}x}$.
4. Produz ${\displaystyle (s_{1}-s_{2})(c_{1}-c_{2})^{-1}}$.

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

Esse protocolo passa a ser de conhecimento zero, embora essa propriedade não seja exigida para uma prova de conhecimento.

Os protocolos que têm a estrutura de três movimentos acima (compromisso, desafio e resposta) são chamados de protocolos sigma^{[carece de fontes?]}. A letra grega ${\displaystyle \Sigma }$ visualiza o fluxo do protocolo. Os protocolos Sigma existem para provar várias declarações, como aquelas pertencentes 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 tem uma forma específica. Por exemplo, é possível provar que dois logaritmos de ${\displaystyle y_{1}}$ e ${\displaystyle y_{2}}$ em relação às bases ${\displaystyle g_{1}}$ e ${\displaystyle g_{2}}$ são iguais ou cumprem alguma outra relação linear. Para os elementos a e b de ${\displaystyle Z_{q}}$, dizemos que o provador prova conhecimento de ${\displaystyle x_{1}}$ e ${\displaystyle x_{2}}$ de modo que ${\displaystyle y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}}$ e ${\displaystyle x_{2}=ax_{1}+b}$. A igualdade corresponde ao caso especial em que a = 1 eb = 0. Como ${\displaystyle x_{2}}$ pode ser calculado trivialmente a partir de ${\displaystyle x_{1}}$ isso é equivalente a provar conhecimento de um x tal que ${\displaystyle y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}}$.

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

${\displaystyle 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 cumpre a relação acima.

As provas de conhecimento são ferramentas úteis para a construção de protocolos de identificação e, em sua variante não interativa, os esquemas de assinatura. Esses esquemas são:

• Assinatura de Schnorr

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

• Prova de conhecimento zero
• Protocolo de segurança
• Sistema de prova interativa