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

13

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:SVxLr

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

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.Sq(|x|)SxSV

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.Vq(|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.)VSSPVV

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.

MS Dousti
fonte
Eu acho que você pode querer dizer "exaustivo" em vez de "exaustivo".
Dave Clarke
Eu peço desculpa mas não concordo. Eu quis dizer que encontrei uma maneira de "esgotar" o simulador de protocolos ZK ... Não existe o simulador "exaustivo".
MS Dousti 20/09/10
Foi mal. Eu li exaustivo como um adjetivo, não um verbo.
Dave Clarke

Respostas:

10

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 poeuy(|x|)tEume(V)poeuy(tEume(V))VVé 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".VV

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 poeuy(tEume(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.

Boaz Barak
fonte
1
O mesmo vale para a "simulação universal" ZK? Afinal, a caixa preta ZK é um tipo de simulação universal ZK, cujo tempo de execução é fixo antes que seja determinado. (No entanto, o ZK sem caixa preta é um tipo de ZK de simulação universal, no qual S pode observar as "entranhas" de V *) #V
MS Dousti
Consulte a pergunta editada para algumas referências.
MS Dousti 23/09/10
1
VV
1
Adiei a responder ao seu comentário, pois queria ler mais. Em particular, li o artigo de Yung e Zhao (citado acima) e observei que eles usavam ZK de caixa preta no modelo RO para obter um resultado positivo, enquanto você dizia "não faz sentido dizer que um modelo de oráculo aleatório simulador é 'caixa preta' ". O resultado deles é filosoficamente problemático ou devemos relaxar a definição de caixa preta?
MS Dousti 26/09/10
4

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.

David Cash
fonte
1
Obrigado pela resposta David. Independentemente da capacidade do simulador de programar o RO, ele deve ser capaz de "monitorá-lo". Portanto, toda consulta oracle do V * perde o tempo de M pelo menos. Sua grande idéia é alterar o modelo para "deixar o simulador executar o polinômio no tempo em | x | e o número de consultas de RO emitidas por V *". Esse não é o modelo padrão, mas eu o vejo como uma solução razoável. No entanto, eu acho que os "gigantes" da comunidade deve reconhecer a autenticidade de tal modelo em primeiro lugar ...
MS Dousti
1
Você pode citar uma fonte que define com precisão "o modelo padrão"? (Esse termo é frequentemente usado como sinônimo de "nenhum oráculo aleatório ou outras modificações estão presentes no modelo de computação", mas não acho que seja isso que você quis dizer.) Minha expectativa é que eu tenha esboçado a definição do que seria considerado padrão e, se não, podemos descobrir isso sem nenhum "gigante" certificando ativamente nosso raciocínio.
David Cash
1
Certamente, por "modelo padrão", eu quis dizer a "definição padrão" de ZK no modelo RO. Você pode se referir ao artigo de Rafael Pass (citado na pergunta), ou à sua tese de mestrado (intitulada "Variantes alternativas de provas de conhecimento nulo") ou ao artigo de Wee no AsiaCrypt 2009 ("Conhecimento nulo no modelo aleatório do Oracle, revisitado") . Nenhum deles definiu ZK de "caixa preta" no modelo RO (todos eles mencionaram a entrada auxiliar ZK), embora nenhum referisse "polinômio de execução no tempo em | x | e o número de consultas de RO feitas por V *". Por isso, acho que você está
propondo
Consulte a pergunta editada para algumas referências.
MS Dousti 23/09/10