Provas simultâneas de zero conhecimento com complexidade redonda logarítmica
Os números das páginas são do próprio papel e não do pdf.
Na página 3,
"Diz-se que um sistema interativo de prova é zero de caixa preta (computacional)
se houver uma máquina de oráculo de tempo polinomial probabilística tal que, para qualquer verificador de tempo polinomial probabilístico V ∗ e para todos
, a distribuição
da saída produzida por na entrada x é computacionalmente indistinguível da visão do verificador no final da interação ( P , V ) ( x )
".
Eu suponho que eles querem dizer no final, caso contrário, este
apenas define o zero conhecimento computacional do Verificador honesto.
Na página 7,
"Se o simulador não for interrompido até que todas as sessões terminem (ou o
terminem verificador termine), ele exibirá a exibição do verificador nesse ponto."
A partir do terceiro parágrafo da página 8,
"Se o contador de profundidade indicar que estamos apenas um nível acima das folhas, o
simulador terá que aguardar as próximas duas mensagens de preâmbulo, ou seja, ele terá que passar pelas
duas folhas e retornar. Para isso, o simulador continua modificando a visão atual
, deixando o testador (modificado) e o verificador executados até que duas mensagens de preâmbulo cheguem ".
Parece-me que isso não pode funcionar, já que a mensagem do provador
nessa fase é apenas um compromisso estatisticamente vinculativo.
Deixei Suponha que o esquema de compromisso estatisticamente vinculativo usado
seja tal que seja fácil calcular um predicado cujos compromissos têm uma probabilidade de aproximadamentede satisfazer (por exemplo, compromissos Naor ou compromisso de um gerador pseudo-aleatório injetivo ).
A probabilidade de suceder é obviamente aproximadamente ,
.
ter sucesso será mais do que
.
Isso é um erro no jornal? Se não, o que estou perdendo?
fonte