Prova de conhecimento

Na criptografia, uma prova de conhecimento (proof of knowledge) é um sistema de prova interativa no qual o provador consegue "convencer" um verificador de que ele sabe algo. O significado de uma máquina abstrata "saber algo" é definido em termos de computação. Uma máquina "sabe algo" se esse algo puder ser computado, dada a própria máquina como entrada. Como o programa do provador não necessariamente cospe o conhecimento em si (como é o caso de provas de conhecimento zero), uma máquina com um programa diferente, chamada de extrator de conhecimento, é introduzida para capturar essa ideia. Estamos interessados principalmente no que pode ser provado por máquinas limitadas a tempo polinomial. Neste caso, o conjunto de elementos de conhecimento é limitado a um conjunto de testemunhas de alguma linguagem formal em NP.

Seja ${\displaystyle x}$ uma afirmação da linguagem ${\displaystyle L}$ em NP, e ${\displaystyle W(x)}$ o conjunto de testemunhas para 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 a seguir:

1. Completude (Completeness): Se ${\displaystyle (x,w)\in R}$, então o provador ${\displaystyle P}$ que conhece a testemunha ${\displaystyle w}$ para ${\displaystyle x}$ consegue convencer o verificador ${\displaystyle V}$ de seu conhecimento. Mais formalmente: ${\displaystyle \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 (Validity): A validade exige que a probabilidade de sucesso de um extrator de conhecimento ${\displaystyle E}$ em extrair a testemunha, dado o acesso de oráculo 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. 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 ${\displaystyle R}$ uma relação de testemunha, ${\displaystyle W(x)}$ o conjunto de todas as testemunhas para o valor público ${\displaystyle x}$ e ${\displaystyle \kappa }$ o erro de conhecimento. Uma prova de conhecimento é ${\displaystyle \kappa }$-válida se existir uma máquina de tempo polinomial ${\displaystyle E}$, dado o acesso de oráculo a ${\displaystyle {\tilde {P}}}$, tal que para cada ${\displaystyle {\tilde {P}}}$, ocorra 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 a uma conclusão.

O erro de conhecimento ${\displaystyle \kappa (x)}$ denota a probabilidade de o verificador ${\displaystyle V}$ aceitar ${\displaystyle x}$, embora o provador na verdade não conheça uma testemunha ${\displaystyle w}$. O extrator de conhecimento ${\displaystyle E}$ é usado para expressar o que se entende pelo conhecimento de uma máquina de Turing. Se ${\displaystyle E}$ puder 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. Para erros de conhecimento pequenos ${\displaystyle \kappa (x)}$, como por exemplo ${\displaystyle 2^{-80}}$ ou ${\displaystyle 1/\mathrm {poly} (|x|)}$, ela pode ser vista como sendo mais forte do que a corretude (soundness) de provas interativas comuns.

Relação com provas interativas gerais

Para definir uma prova de conhecimento específica, é necessário definir não apenas 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 computar uma testemunha específica pode ser difícil. A melhor forma de explicar isso é por meio de um exemplo:

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

Protocolos

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, esquemas de assinatura. Exemplos de tais esquemas são:

• Assinatura de Schnorr

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

Ver também

• Corretude (prova interativa)
• Protocolo criptográfico
• Prova de conhecimento zero
• Prova de senha com conhecimento zero
• Sistema de prova interativa
• Tópicos em criptografia

Referências