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.

Detalhes na definição

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.

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 ${\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.

Protocolos

Protocolo Schnorr

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.

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 ${\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.

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

Referências

1. Shafi Goldwasser, Silvio Micali e Charles Rackoff. A complexidade do conhecimento dos sistemas de prova interativos (em inglês). Anais do 17º simpósio de teoria da computação, Providence, Rhode Island. 1985. Esboço, projeto. Resumo estendido (em inglês)
2. Mihir Bellare, Oded Goldreich: Sobre a definição de provas de conhecimento (em inglês). CRYPTO 1992: 390 à 420
3. C. P. Schnorr, Identificação e assinaturas eficientes para cartões inteligentes, em G Brassard, Avanços na criptologia – Crypto '89, 239 à 252 (em inglês), Springer-Verlag, 1990. Notas de aula em ciência da computação, número 435
4. Esquemas de assinatura de grupo eficientes para grandes grupos (em inglês)