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: $\mathrm{Pr}(P(x,w)\leftrightarrow V(x)\to 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 \{\mathrm{\perp }\}$ e $\mathrm{Pr}(E^{\tilde{P}(x)}(x)\in W(x))\ge \mathrm{Pr}(\tilde{P}(x)\leftrightarrow V(x)\to 1)-\kappa (x).$

O resultado $\mathrm{\perp }$ 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{p}\mathrm{o}\mathrm{l}\mathrm{y}(|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 $⟨g⟩$ 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 $⟨g⟩$. 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=t{y}^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 sigmaPredefinição:Citation needed. A letra grega $\mathrm{\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}\wedge y_2=g_2^{x_2}$ e $x_2=a{x}_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\wedge 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\wedge 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