Sobre a técnica de prova das assinaturas de Boneh-Lynn-Shacham Gap

8

No artigo "Assinaturas curtas do emparelhamento Weil" de Boneh, Lynn e Shacham, eu estava examinando a prova de segurança como qualquer outra assinatura.

Mas a técnica usada neste artigo é bastante única. Em vez de usar a interação normal do desafiante e do adversário, eles dividiram a prova em 6 jogos, em que cada jogo é estendido seqüencialmente dos jogos anteriores.

Não sei por que eles usaram essa abordagem em vez do jogo normal. Esse tipo de prova de segurança ajuda a reduzir a probabilidade mais facilmente ou eles acabaram de fornecê-la do ponto de vista "fácil de ler e entender"?

Obrigado!

reference-request cr.crypto-security Maverickgugu
fonte

Respostas:

11

A técnica de "pular" de um jogo para outro e provar a segurança através de uma "sequência de jogos" não é nova. Em particular, existem vários documentos que discutem essas técnicas e as exemplificam através de várias provas de segurança. Os exemplos famosos são:

Com relação à sua pergunta, uso uma citação do último artigo citado acima:

Em uma prova de salto de jogo, observamos que um invasor executando em um ambiente de ataque específico tem uma probabilidade desconhecida de sucesso. Em seguida, alteramos lentamente o ambiente de ataque até que a probabilidade de sucesso do invasor possa ser calculada. Também limitamos o aumento na probabilidade de sucesso do invasor causado pelas alterações no ambiente de ataque. Assim, podemos deduzir um limite para a probabilidade de sucesso do invasor no ambiente original.

Assim, a razão para usar vários jogos é que, em cada jogo, simplificamos o cálculo de uma probabilidade desconhecida, sem alterá-la de maneira significativa. Isso continua até chegarmos a um jogo em que o cálculo da probabilidade é bastante fácil.

MS Dousti
fonte
Obrigado pelas referências !! vou comentar depois de estudar estes papéis para uma melhor imagem. Mas, para mantê-lo mais abstrato, essas provas sequenciais baseadas em jogos podem ser convertidas em uma única prova de jogo e calcular a probabilidade como um todo?
Maverickgugu
@ Maverickgugu: De nada! Regenerando sua pergunta: Às vezes é possível converter vários jogos em um, mas a prova fica mais complicada. (Se bem me lembro, a primeira ou a segunda referência citada em minha resposta menciona um desses jogos.) Mas, em geral, essa prova pode se tornar altamente complexa e até impossível de ser realizada. Acho que você pode resolver isso tentando mesclar os 6 jogos na prova de Boneh-Lynn-Shacham e vendo por si mesmo onde o problema surge.
MS Dousti 12/10
@Sadiq Dousti: No artigo de Shoup, ele mencionou "Além disso, mesmo quando essa técnica é aplicável, é apenas uma ferramenta para organizar uma prova - as idéias reais para uma análise criptográfica de construção e segurança devem vir de outros lugares". Com esse argumento, tentei condensar os 6 jogos para 1 na prova de Boneh-Lynn-Shacham e não consigo encontrar nenhuma dificuldade na fusão. Eu senti que estava apenas combinando claramente todas as condições extras e eventos de falha, o que dá uma probabilidade final. Você pode me ajudar com qualquer informação sutil que estou perdendo?
Maverickgugu
@ Maverickgugu: Por favor, envie-me a prova mesclada por e-mail. Você pode encontrar minhas informações de contato aqui .
MS Dousti 30/10/11
2

A idéia de usar uma sequência de jogos como parte de uma prova reducionista de segurança antecede as referências fornecidas (está implícita em trabalhos que datam do início dos anos 80, se não antes, e explícitos pelo menos no final dos anos 90).

user686
fonte
Se eu puder sugerir uma melhoria, você pode adicionar alguns exemplos como trabalhos nos quais a idéia de "sequência de jogos" está implícita (minha resposta já cobre alguns dos exemplos explícitos).
MS Dousti