Simulador exaustivo de protocolos de conhecimento zero no modelo Oracle aleatório

Em um artigo intitulado "Sobre a negação na cadeia de referência comum e no modelo aleatório do Oracle", Rafael Pass escreve:

Observamos que, ao provar a segurança de acordo com a definição padrão de conhecimento zero no modelo RO [Oracle aleatório], o simulador tem duas vantagens sobre um simulador de modelo simples, a saber:

1. O simulador pode ver em quais valores as partes consultam o oráculo.
2. O simulador pode responder a essas perguntas da maneira que escolher, desde que as respostas "pareçam" OK.

A primeira técnica, ou seja, a capacidade de "monitorar" consultas ao RO, é muito comum em todos os trabalhos referentes ao conceito de zero conhecimento no modelo de RO.

Agora, considere a definição de conhecimento zero de caixa preta ( PPT significa máquina de Turing probabilística em tempo polinomial ):

um PPT simulador S , de tal forma que ∀ (possivelmente batota) PPT verificador V * , ∀ comum de entrada x ∈ G , e ∀ aleatoriedade r , o seguinte são indistinguíveis:$\exists$$S$$\forall$$V^*$$\forall$$x\in L$$\forall$$r$

• a visão de enquanto interage com o provador P na entrada x e usando a aleatoriedade r ; $V^*$$P$$x$$r$
• a saída de nas entradas x e r , quando S recebe acesso em caixa preta a V ∗ . $S$$x$$r$$S$$V^*$

Aqui, quero exibir um verificador de trapaça , cujo trabalho é esgotar qualquer simulador que tente monitorar as consultas de RO:$V'$

Seja o simulador garantido pelo quantificador existencial na definição de conhecimento zero da caixa preta e seja q ( | x | ) um polinômio que limita o tempo de execução de S na entrada x . Suponha que S tente monitorar as consultas de V ∗ na RO.$S$$q(|x|)$$S$$x$$S$$V^*$

Agora, considere um trapaceiro , que primeiro consulta o RO por q ( | x | ) + 1 vezes (em entradas arbitrárias de sua escolha) e depois age arbitrariamente maliciosamente.$V'$$q(|x|)+1$

Obviamente, esgota o simulador S . Uma maneira simples de S é rejeitar esse comportamento malicioso, mas, dessa maneira, um distintivo pode facilmente distinguir a interação real da simulação. (Como na interação real, o provador P não pode monitorar as consultas de V ' e, portanto, não rejeitará com base no mero fato de que V ' está consultando demais.)$V'$$S$$S$$P$$V'$$V'$

Qual é a solução alternativa para o problema acima?

Editar:

Uma boa fonte para estudar ZK no modelo RO é:

Martin Gagné, Um Estudo do Modelo Oracle Aleatório, Ph.D. Tese, Universidade da Califórnia, Davis , 2008, 109 páginas. Disponível no ProQuest: http://gradworks.umi.com/33/36/3336254.html

Particularmente, fornece definições de caixa preta ZK no modelo RO na seção 3.3 (página 20), atribuídas a Yung e Zhao:

Moti Yung e Yunlei Zhao. Zero conhecimento interativo com oráculos aleatórios restritos. In Theory of Cryptography - TCC 2006 , LNCS 3876, pp. 21-40, 2006.

Há uma questão de por que alguém desejaria definir ZK de caixa preta no modelo aleatório do Oracle. Há pelo menos duas razões pelas quais as pessoas sugeriram a definição de conhecimento zero de caixa preta:

1) Para um resultado positivo, quando você diz que um simulador é "caixa-preta conhecimento zero" ele automaticamente dá-lhe uma agradável obrigado em seu tempo de execução (ou seja, , em oposição a p o l y ( t i m e ( V * ) ) ) e pode também ser útil saber que o simulador não "olhar para os intestinos de V * e não importa se V $poly(|x|) \cdot time(V*)$$poly(time(V*))$$V*$$V*$é implementado usando RAM, circuito, etc ... Embora um simulador de modelo de oráculo aleatório possa ser eficiente, obviamente não é uma caixa preta, porque é suposto observar de alguma forma a execução de e entender quando V ∗ está avaliando uma função de hash. Por esse motivo, há um sentido em que não faz sentido dizer que um simulador de modelo de oráculo aleatório é "caixa preta".$V*$$V*$

2) Para um resultado negativo, as pessoas usam o "simulador de caixa preta" para capturar uma grande classe de técnicas de prova. Nesse caso, você pode definir o simulador de caixa preta também no modelo aleatório do oráculo e a definição que faz sentido é o que David disse. Na verdade, para um resultado negativo, mesmo não no modelo de oráculo aleatório, é melhor se o resultado é válido mesmo se você permitir que o simulador tempo de execução. De fato, embora nem sempre seja afirmado, os resultados negativos que conheço possuem todas essa propriedade, pois o verificador de trapaça V $poly(time(V*))$$V*$ normalmente é um algoritmo polinomial fixo que executa algumas funções pseudo-aleatórias, enquanto o simulador pode ter qualquer tempo de execução polinomial.

Aqui está a minha opinião sobre o problema. Recentemente, não li nenhum artigo que lide com o conhecimento zero de caixa preta no modelo OR (aleatório), então estou apenas adivinhando o que eles significam e não o que está escrito lá. A resposta curta (suposição) é que o BB-ZK no modelo RO deve deixar o simulador executar o polinômio no tempo em | x | e o número de consultas de RO emitidas por V *, o verificador de trapaça.

Vamos tentar justificar esse palpite. Uma observação inicial é que o termo "provas de conhecimento zero de caixa preta no modelo de oráculo aleatório" precisa de uma análise mais detalhada para definir adequadamente. Os simuladores de caixa preta são definidos para funcionar com qualquer oráculo (ou seja, o verificador de trapaça como uma caixa preta), e sua única interface é através da entrada / saída do oráculo. Se apenas aumentarmos esse modelo para fornecer um RO a todas as partes (talvez permitindo que seus circuitos tenham portas RO), obteremos um modelo em que o simulador não pode programar o RO - em uma consulta oracle, tudo (incluindo as consultas RO) acontece "dentro" do oracle V * e, em seguida, retorna sua próxima mensagem. Se queremos permitir a programação do RO, precisamos modificar as interfaces: O simulador agora obtém um oráculo de entrada / saída para V * e nenhum oráculo aleatório. Em cada chamada para o oráculo V *, em vez de produzir a próxima mensagem, o oráculo pode produzir a próxima consulta para o RO, e o simulador pode dar a resposta ao RO chamando o oráculo novamente. Agora, isso permite a programação do RO, e também podemos permitir que o tempo de execução do simulador dependa do número de consultas ao RO.

Qualquer outra exploração do significado dessas definições é deixada ao leitor. Estou pensando sintaticamente.