pergunta sobre o trabalho simultâneo de ZK de Prabhakaran & Sahai

8

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 todosS
VxL, 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 )SVx
(P,V)(x) ".


Eu suponho que eles querem dizer (P,V)(x) 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 p:ωωSVSuponha que o esquema de compromisso estatisticamente vinculativo usado
seja tal que seja fácil calcular um predicado cujos compromissos têm uma probabilidade de aproximadamente12p(k)de satisfazer (por exemplo, compromissos Naor ou compromisso de um gerador pseudo-aleatório injetivo ).V1
A probabilidade de (P,V1)(x) suceder é obviamente aproximadamente 12p(k),
SV1
14p(k).
k(P,V1)(x) ter sucesso será mais do que 15p(k)
SV1
SV1(P,V1)(x).


Isso é um erro no jornal? Se não, o que estou perdendo?

Lev Reyzin
fonte

Respostas:

10

Eu sou um dos autores. Alguém me apontou para esta pergunta. Com base em uma leitura rápida, aqui está uma tentativa de responder à sua preocupação.

O que pode não estar muito claro nesta versão da descrição do simulador (esta foi a primeira vez que descrevi um simulador, e é certo que ele se parece muito com a linguagem de máquina) é que a visão gerada pelo simulador, afinal o empurrar e estourar da pilha corresponde apenas ao percurso pelas arestas rotuladas com L1 e R1. Portanto, mesmo que o verificador seja interrompido em outro lugar, ele é disparado e o simulador continua.

Eu recomendaria a versão do processo FOCS (ou uma versão ligeiramente expandida disponível na minha página inicial) sobre esta versão impressa. Em termos de descrição na versão de processo, a saída do simulador corresponde ao "encadeamento principal" da simulação e não inclui abortos que possam ocorrer nos blocos de antecipação. (Apenas olhando o artigo: veja a Figura 3 para uma ilustração.)

Espero que ajude.

-Manoj

Manoj Prabhakaran
fonte