A equivalência de duas definições de completude e solidez em sistemas interativos de prova

11

A integridade e a integridade dos sistemas interativos de prova são definidas informalmente como:

  • Completude: se uma afirmação é verdadeira, o provador honesto pode convencer o verificador honesto desse fato whp .

  • Solidez: Se uma afirmação é falsa, o provador de trapaça não pode convencer o verificador honesto (da validade da afirmação falsa) que

O termo "whp" é interpretado como "com probabilidade maior que (digamos) 2/3" ou "com probabilidade maior que o recíproco de qualquer polinômio". Parece irrelevante para a discussão a seguir como qual interpretação de "whp" escolher.

A parte complicada é como a probabilidade é calculado: Em algumas fontes, a probabilidade é tomado sobre as moedas aleatórios de tanto o provador e o verificador. Em outras fontes, a probabilidade é calculada apenas sobre as moedas aleatórias do verificador. O último é geralmente justificado como: "sejam quais forem as moedas aleatórias do provador, o verificador toma a decisão certa".

Para mim, as duas definições de probabilidade parecem equivalentes; ainda não posso provar isso. Estou certo? Você pode provar que eles são equivalentes?

cc.complexity-theory interactive-proofs Incrível
fonte
2
você também deve considerar se está se referindo a moedas "públicas" ou "privadas". Na definição de moedas públicas, tanto o provador quanto o verificador conhecem os resultados das escolhas aleatórias e, para moedas privadas, o provador não conhece as escolhas aleatórias do verificador. Neste último caso, você se preocupa apenas com o que o verificador faz sem olhar para o provador, porque ele simplesmente não conhece os lançamentos aleatórios de moedas.
Marcos Villagra
@Marcos: Dê uma olhada na definição original de provas interativas, que é uma moeda "privada" na natureza. A última frase da primeira coluna da página 293, sublinhada, afirma que "as probabilidades são assumidas apenas sobre os lançamentos de moedas de B". (Aqui, B é o verificador.) Por outro lado, a versão do diário do artigo mencionado acima permite que as probabilidades sejam tomadas sobre os lançamentos de moedas de ambas as partes. Essa pode ser a fonte da confusão, certo?
MS Dousti 11/05/11
@Sadeq: Entendo, eu não sabia dessa diferença entre as versões da revista e da conferência. Ainda assim, para moedas privadas, não vejo sentido em levar em consideração os lançamentos das moedas dos provadores, porque ele pode decidir não contar ao verificador sobre isso. O verificador é o encarregado de decidir a aceitação ou rejeição, e ele pode não saber o que o provador está fazendo.
Marcos Villagra 11/11
1
@Marcos: Você está certo, mas o mesmo raciocínio se aplica às provas de moedas públicas; já que nesses sistemas os lançamentos das moedas do provador ainda são privados (somente as moedas do verificador são públicas). Em geral, pode-se considerar um provador determinístico: como o provador é todo-poderoso, ele não precisa de aleatoriedade e pode escolher a resposta ideal deterministicamente. No entanto, esse tipo de raciocínio não funciona se considerarmos sistemas de conhecimento zero, nos quais a estratégia do fornecedor deve ser probabilística (caso contrário, seu conhecimento vazaria).
MS Dousti
2
(Continua) Se o provador for randomizado, acho que a formulação adequada é calcular a probabilidade dos lançamentos de moedas do provador e do verificador: Enquanto, como Marcos disse, o verificador é o responsável pela decisão final, sua decisão é feito (entre outros) com base nas mensagens vindas do provador. Dado o fato de o provador ser randomizado, seus lançamentos de moedas certamente afetam as mensagens que ele envia. Portanto, os lançamentos de moedas do fornecedor afetam a probabilidade de aceitação. Estou certo?
MS Dousti

Respostas:

6

O provador é "todo-poderoso e possui recursos computacionais ilimitados", por isso não precisa de bits aleatórios. Assim, a única aleatoriedade é a aleatoriedade do verificador.

Se o provador usar bits aleatórios, deverá substituí-los pela sequência de bits aleatórios que provavelmente fará com que o verificador aceite (isso é verdade para o provador honesto e desonesto). Além disso, o provador pode determinar essa sequência de bits ideal porque o provador é "todo-poderoso".

Tyson Williams
fonte
1
Como eu disse em um comentário acima, isso só é verdade quando você considera apenas as provas interativas. No entanto, as coisas são muito diferentes se você levar em conta outras propriedades, como "zero conhecimento", que é naturalmente conectado a provas interativas.
MS Dousti 25/05
1
Continua: Especificamente, Oren provou o seguinte: "... sob a definição de entrada auxiliar de conhecimento zero, a aleatoriedade do provador é essencial para a não trivialidade dos sistemas de prova de conhecimento zero. Em outras palavras, qualquer idioma que possui um sistema de prova de conhecimento zero de entrada auxiliar no qual o provador é determinístico para o BPP ". (Consulte a seção 4.5 do Oren para obter mais informações.) Portanto, nem sempre você pode assumir que P é determinístico.
MS Dousti 25/05