Usando provas baseadas em jogos em provas baseadas em simulação

8

A segurança baseada em simulação fornece uma definição de segurança mais natural e mais poderosa do que a segurança baseada em jogos. Vi as abordagens baseadas em simulação usarem as provas baseadas em jogos para provar a segurança de algumas partes do protocolo. Por exemplo, para avaliar a segurança de um protocolo quanto à complexidade redonda ou ao total de mensagens trocadas durante a execução do protocolo, é adotada uma abordagem baseada em jogos, mas a segurança do protocolo em relação à estrutura (no meu estudo, a estrutura UC) é comprovado pelo paradigma Ideal / Real (isto é, abordagem baseada em simulação).

Pergunta : Em que circunstâncias podemos usar uma abordagem baseada em jogos para provar a segurança de uma parte do protocolo ou de todo o protocolo quando o design do protocolo deve estar em conformidade com uma abordagem de simulação? Podemos usar essa abordagem a qualquer momento, por qualquer motivo, desde que não seja relevante para a segurança de todo o protocolo em relação à estrutura baseada em simulação?

Deixe-me explicar através de um exemplo: estou estudando um protocolo de troca de chaves de grupo na estrutura UC (baseada em simulação), mas o protocolo usa esquemas de criptografia que são CCA-Secure (comprovado por um jogo entre adversário e alguns oráculos) ou CCA2- seguras (comprovadas também por uma abordagem baseada em jogos), as assinaturas devem ser existencialmente imperdoáveis ​​(abordagem baseada em jogos também) e, finalmente, o custo de comunicação do protocolo é calculado e a análise da segurança do protocolo é feita através de 10 ou 11 jogos entre adversário e simulador. Finalmente, são feitas provas para mostrar que o protocolo está em conformidade com os regulamentos da UC.

Yasser Sobhdel
fonte
Esta é uma pergunta interessante. Novamente, estou fora do meu campo, mas é surpreendente para mim que uma abordagem baseada em simulação seja mais poderosa do que uma abordagem baseada em jogos. Você tem uma referência para esta ou alguma intuição?
Dave Clarke
5
Dave, não é de surpreender que as definições baseadas em simulação sejam mais fortes que as definições baseadas em jogos. Em uma definição baseada em simulação, é necessário que nada seja aprendido com a interação (além da funcionalidade pretendida), enquanto que em uma definição baseada em jogo o requisito de segurança é explícito (pense na imperdoabilidade das assinaturas digitais). Portanto, em princípio, é possível aprender algo interagindo com um esquema que é seguro no jogo, desde que isso não viole o requisito explícito de segurança (por exemplo, aprender algumas informações secretas que não ajudam na falsificação da assinatura).
Alon Rosen

Respostas:

6

Um artigo que lida com a questão é Jogos e a impossibilidade de Funcionalidade Ideal Realizável por Datta et al., Mas não parece abordar a questão com total generalidade. Não conheço nenhuma declaração geral que garanta a segurança baseada em simulação de todo o protodol com base em propriedades específicas de segurança baseadas em jogos de seus subprotocolo - protocolos (a menos que as definições baseadas em jogos impliquem segurança baseada em simulação, nesse caso o genérico teoremas de composição de Canetti devem ser aplicados).

No entanto, existem casos específicos nos quais é possível obter segurança baseada em simulação a partir da segurança baseada em jogos. O exemplo mais revelador, a meu ver, é um argumento de conhecimento zero (ZK) de rodada constante para NP de Feige e Shamir (ver, por exemplo, o doutorado de Feige ), que se baseia em subprotocolo de testemunha indistinguishabille (WI) e oculta (WH) . WI e WH são (sem dúvida) definições baseadas em jogos, e ainda assim todo o protocolo pode ser ZK (que é a mãe de todas as definições baseadas em simulação, pelo menos para protocolos interativos).

Alon Rosen
fonte
1
Bem dito! Sugiro a leitura do artigo de Feige-Shamir (provas de conhecimento zero em duas rodadas) em vez da tese de Feige, pois é muito mais direto ao ponto.
MS Dousti 16/11/10
Obrigado! Exatamente o que eu estava procurando. @ Sadegh: Obrigado também. Você está atuando como meu editor: D
Yasser Sobhdel 16/11/2010