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), 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 $x$ uma declaração de linguagem $L$ em NP e $W(x)$ o conjunto de testemunhas de 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 seguintes:

1. Integridade: Se $(x,w)\in R$, então o provador $P$ que conhece a testemunha $w$ para $x$ é bem sucedido em convencer o verificador $V$ de seu conhecimento. Mais formalmente: $\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 $E$ em extrair a testemunha, dado ao oráculo acesso a um provador possivelmente malicioso ${\tilde {P}}$, deve ser pelo menos tão alta quanto a probabilidade de sucesso do provador ${\tilde {P}}$ em convencer o verificador. Esta propriedade garante que nenhum provador que não conheça a testemunha consiga convencer o verificador.

Detalhes na 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 valor público $x$ e $\kappa$ o erro de conhecimento. Uma prova de conhecimento é $\kappa$-válida se existe uma máquina de tempo polinomial $E$, dado ao oráculo acesso 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 à uma conclusão.

O erro de conhecimento $\kappa (x)$ denota a probabilidade de que o verificador $V$ pode aceitar $x$, mesmo que o provador de fato não conheça 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|)$ pode ser visto como sendo mais forte do que a solidez das provas interativas comuns.

Relação com provas interativas gerais

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

Protocolos

Protocolo Schnorr

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

A fim de 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 math>r</math>; portanto, a primeira mensagem $t=g^{r}$ também é chamada de confirmação.
2. O verificador responde com um desafio $c$ escolhido aleatoriamente.
3. Depois de receber $c$, o provador envia a terceira e última mensagem (a resposta) $s=r+cx$ módulo reduzido a ordem do grupo.

O verificador aceita, se $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 $t=g^{r}$. O provador está agora no estado math>Q</math>.
2. Gera valor aleatório $c_{1}$ e o insire no provador. Ele produz $s_{1}=r+c_{1}x$.
3. Retrocede o provador para declarar $Q$. Agora gera um valor aleatório diferente $c_{2}$ e o insire no provador para obter $s_{2}=r+c_{2}x$.
4. Produz $(s_{1}-s_{2})(c_{1}-c_{2})^{-1}$.

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

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

Protocolos Sigma

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 $\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 $y_{1}$ e $y_{2}$ em relação às bases $g_{1}$ e $g_{2}$ são iguais ou cumprem alguma outra relação linear. Para os elementos a e b de $Z_{q}$, dizemos que o provador prova conhecimento de $x_{1}$ e $x_{2}$ de modo 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 eb = 0. Como $x_{2}$ pode ser calculado trivialmente a partir de $x_{1}$ isso é equivalente a provar conhecimento de um x tal que $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, 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 cumpre a relação acima.

Aplicações

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.

Ver também

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