Provas de conhecimento zero explicadas Parte 2: Provas de conhecimento zero não interativas

[ware_item id=33][/ware_item]

Exemplo não interativo de provas de conhecimento zero: Sudoku e baralho


Na parte 1 de nossa série de provas de conhecimento zero, explicamos como uma prova de conhecimento zero poderia funcionar quando o verificador e o provador interagem entre si..

Uma prova interativa de conhecimento zero tem a vantagem de que apenas o verificador pode estar absolutamente convencido de que o provador tem o conhecimento. Mas isso também pode ser uma desvantagem.

Se os espectadores e os observadores não puderem verificar a reivindicação, o provador precisará interagir com todos os verificadores de forma independente - o que leva tempo e consome muitos recursos..

Nesta parte 2, examinaremos provas não interativas de conhecimento zero.

Provas de conhecimento zero não interativas

O motivo das provas não interativas de conhecimento zero é permitir que um grande número de observadores verifique a prova com eficiência.

Nem sempre precisamos tornar as provas de conhecimento zero não interativas. Muitas vezes, é possível encontrar um verificador confiável, que ateste a integridade da prova.

Exemplo não interativo de provas de conhecimento zero: Sudoku e baralho

Sudoku é um jogo com dificuldade variável, mas regras relativamente simples. Cada uma das 9 linhas, 9 colunas e 9 setores (conforme indicado pela linha preta grossa) deve conter cada número de 1 a 9 exatamente uma vez.

Imagine que a solução para um quebra-cabeça sudoku é particularmente difícil de obter e leva dias para que até um supercomputador calcule.

Mas alguém (o provador) afirma ter a solução para o quebra-cabeça e está disposto a vendê-lo por um preço. Como eles podem provar que têm a solução, sem revelá-la, para que o verificador esteja preparado para fazer o pagamento?

A prova:

O provador precisa de 27 cartas de baralho (de qualquer naipe) numeradas de 1 a 9 a 243 no total.

Agora, o provador coloca três cartões com o número correspondente à solução correta de Sudoku em cada caixa. Por exemplo, se a resposta correta da caixa for 7, o provador colocará 3 cartas de baralho com o valor 7.

Em uma tabela de Sudoku, algumas respostas serão visíveis. Nestas caixas respondidas, as cartas de baralho são colocadas virado para cima. Nas caixas de Sudoku vazias, as cartas são colocadas de bruços.

Para provar que as cartas com a face para baixo estão todas na posição correta (sem revelar a solução), o provador deve:

  • Pegue o cartão superior de todos os linha e faça 9 pilhas
  • Pegue o cartão superior de todos os coluna e faça 9 pilhas
  • Pegue os cartões restantes de cada setor e faça 9 pilhas

Pedidos de provas de conhecimento nulo

Cada pilha é então embaralhada e virada.

Todo número entre 1 e 9 deve aparecer em todas as linhas, colunas e setores do Sudoku. Portanto, se cada pilha das cartas do provador (das pilhas de linhas, colunas e setor) contiver cada uma das cartas com valor de 1 a 9, sabemos que eles devem ter a solução.

Pedidos de provas de conhecimento nulo

É certo que o campo relativamente jovem de provas de conhecimento zero ainda não encontrou a aceitação que possa merecer. Eles podem, no entanto, provar ser altamente valiosos.

Muitos problemas matemáticos são semelhantes a um quebra-cabeça do Sudoku (por exemplo, o problema da coloração do gráfico). Se pudermos usar o princípio acima e aplicá-lo com êxito a uma variedade de problemas, poderemos usar e negociar recursos computacionais e problemas matemáticos com mais eficiência. Ou talvez resolva os dilemas matemáticos mais rapidamente.

Parabéns a Ronen Gradwohl, Moni Naor, Benny Pinkas e Guy Rothblum

Provas de conhecimento zero explicadas Parte 2: Provas de conhecimento zero não interativas
admin Author
Sorry! The Author has not filled his profile.