Protocolo de autenticação Schnorr

Na criptografia , o protocolo de autenticação Schnorr (in) (frequentemente abreviado protocolo Schnorr ) é uma divulgação de conhecimento de prova zero descrita em 1989 por Schnorr, cuja segurança depende da dificuldade do problema do logaritmo discreto e usado para provar o conhecimento de um logaritmo discreto, isto é , dado , provar que sabemos o expoente em um grupo gerado por . ${\ displaystyle g ^ {a}}$ $no$ $G$ $g$

Este protocolo pode ser derivado em uma assinatura digital , tornando a prova não interativa pelas heurísticas de Fiat-Shamir . Este esquema de assinatura digital foi patenteado nos Estados Unidos sob a Patente dos EUA 4.995.082 que expirou emFevereiro de 2008.

Como outras provas de conhecimento zero , o protocolo de Schnorr é um protocolo Σ: um protocolo entre dois algoritmos interativos P e V (para Provador e Verificador) em três fases: engajamento, desafio e resposta.

Configurações públicas

Um número primo. Notamos que ele define um grupo de pedidos gerado por , observado multiplicativamente a seguir. $q$ $G$ $q$ $g$
Um elemento de grupo , de ordem Este é um gerador de um subgrupo de ordem de $g$ ${\ displaystyle q.}$ $q$ $G$
${\ displaystyle q, g}$ são públicos.

Dados conhecidos apenas pelo Provador

Um número inteiro aleatório de . $s$ ${\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}$
O provador calcula e é tornado público, certificado por uma autoridade confiável , enquanto é mantido em segredo. ${\ displaystyle v = g ^ {s}}$ $v$ $s$

Primeiro, P lança uma etapa de engajamento:

P desenha aleatoriamente um inteiro de . $r$ ${\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}$
P calcula e envia para V ${\ displaystyle R = g ^ {r}}$ $R$

Então começa a fase de desafio:

V puxa um número inteiro na e envia-a para P $vs$ ${\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}$

Finalmente, a fase de resposta:

P calcula e envia para V . ${\ displaystyle a = rc \ cdot s}$

V aceita se e somente se ao final do protocolo a relação for verificada. ${\ displaystyle R = g ^ {a} \ cdot v ^ {c}}$

Evidência de segurança

Para provar a segurança de um protocolo Σ, é suficiente provar a integridade, robustez especial e não divulgação da propriedade do conhecimento sob um verificador honesto.

Integridade

A integridade (ou correção) requer que, para um curso honesto do protocolo, o verificador esteja sempre satisfeito.

Isso é verificado pela condição de aceitação de V que o dá , que é sempre verificado se o protocolo foi executado com honestidade. ${\ displaystyle g ^ {a} \ cdot v ^ {c} = g ^ {rc \ cdot s} \ cdot g ^ {s \ cdot c} = g ^ {r} = R}$

Robustez especial

A robustez especial diz que existe um extrator de conhecimento que opera em tempo polinomial , dado duas transcrições de aceitação e sob os mesmos parâmetros públicos, então o extrator retorna o segredo . ${\ displaystyle (R, c, a)}$ ${\ displaystyle (R, c ', a')}$ $s$

Este extrator é construído da seguinte maneira no caso do protocolo Schnorr: ele irá calcular e retornar , porque este valor corresponde ao logaritmo discreto do par . Com efeito, as transcrições e sendo aceites, as relações e são verificadas, dando-se assim desde então . ${\ displaystyle {\ frac {a-a '} {c'-c}}}$ $v$ $g$ ${\ displaystyle (R, c, a)}$ ${\ displaystyle (R, c ', a')}$ ${\ displaystyle R = g ^ {a} \ cdot v ^ {c}}$ ${\ displaystyle R = g ^ {a '} \ cdot v ^ {c'}}$ ${\ displaystyle g ^ {\ left ({\ frac {a-a '} {c'-c}} \ right)} = v}$ ${\ displaystyle c \ not = c '}$

Não divulgação de conhecimento sob um verificador honesto

Esta propriedade é caracterizada pela existência de um simulador probabilístico que opera em tempo polinomial que, dado onde é distribuído como um desafio correto, então o simulador retorna uma transcrição distribuída como uma transcrição verdadeira para . Observe que o simulador não precisa de sigilo. ${\ displaystyle (v, c)}$ $vs$ ${\ displaystyle (R, c, a)}$ $v$

Aqui, o simulador irá portanto gerar a resposta antes do compromisso: ele irá puxar uniformemente e irá gerar para que verifique a condição de aceitação, ou seja , e retornará . Podemos notar que se distribui uniformemente já que seu logaritmo discreto de acordo com a base é. E por construção é distribuído como uma resposta de aceitação a . $no$ ${\ displaystyle \ mathbb {Z} _ {q} ^ {\ star}}$ $R$ ${\ displaystyle R = g ^ {a} \ cdot v ^ {c}}$ ${\ displaystyle (R, c, a)}$ $R$ $g$ $no$ ${\ displaystyle (R, c)}$

Tamanho do parâmetro

A especificação da patente indica que o grupo deve ser escolhido como um subgrupo de pelo menos 140 bits de um grupo onde é um número primo de 512 bits para 72 bits de segurança. $G$ $\ Z_p$ $p$

Esquema de assinatura

A heurística Fiat-Shamir pode ser usada para transformar o esquema de identificação em uma assinatura digital .

Para isso, uma função hash criptográfica (família de) é introduzida nos parâmetros públicos, e no momento do desafio, a seleção aleatória de é substituída pela avaliação onde corresponde à mensagem a ser assinada. A assinatura corresponde ao casal ; no momento da verificação, é recalculado , pois o verificador testa se e aceita se a verificação passa. A descrição completa é fornecida abaixo. ${\ displaystyle {\ mathcal {H}}: G \ times \ {0,1 \} ^ {*} \ to \ mathbb {Z} _ {q} ^ {\ star}}$ $vs$ ${\ displaystyle c \ gets {\ mathcal {H}} (R, m)}$ ${\ displaystyle m \ in \ {0,1 \} ^ {*}}$ ${\ displaystyle (c, a)}$ $R$ ${\ displaystyle R '= g ^ {a} \ cdot v ^ {c}}$ ${\ displaystyle {\ mathcal {H}} (R ', m) = c}$

Descrição

Uma assinatura digital é fornecida por um trio de algoritmos (GenClefs, Signer, Verify) .

Geração de chave:

Os parâmetros públicos ( e ) são gerados da mesma forma que para o protocolo Σ. $q$ $g$
Uma função hash é então gerada e adicionada aos parâmetros públicos. ${\ displaystyle {\ mathcal {H}}: G \ times \ {0,1 \} ^ {*} \ to \ mathbb {Z} _ {q} ^ {\ star}}$
Para gerar um par de chaves (vk, sk) ( v para verificação es para assinatura), o signatário começa puxando uniformemente um número e o definirá como sua chave secreta. ${\ displaystyle s \ in \ mathbb {Z} _ {q} ^ {\ star}}$
O signatário irá então calcular e publicá-lo como sua chave pública. ${\ displaystyle v = g ^ {s}}$

Assinatura ( sk, m ):

Para assinar uma mensagem, o signatário começará por sorteio um número aleatório, e definirá . ${\ displaystyle r \ in \ mathbb {Z} _ {q} ^ {\ star}}$ ${\ displaystyle R = g ^ {r}}$
O "desafio" será gerado como e a resposta calculada como . ${\ displaystyle c = {\ mathcal {H}} (R, m)}$ ${\ displaystyle a = rc \ cdot {\ mathsf {sk}} \ in \ mathbb {Z} _ {q}}$
Finalmente a assinatura é devolvido: . ${\ displaystyle \ sigma = (c, a)}$

Verificação ( vk, m, σ ):

Para verificar a assinatura , o usuário primeiro recalcular usando a chave pública: . ${\ displaystyle \ sigma = (c, a)}$ $R$ ${\ displaystyle R '= g ^ {a} \ cdot {\ mathsf {vk}} ^ {c}}$
O usuário aceitará se e somente se . ${\ displaystyle {\ mathcal {H}} (R ', m) ~ {\ overset {?} {=}} ~ c}$

Eficiência

Isso resulta em um tamanho de assinatura seguindo as recomendações mínimas de patentes para 72 bits de segurança. ${\ displaystyle | c | + | a | = 280 {\ mbox {bits}} = 35 {\ mbox {bytes}}}$

Segurança comprovada

Pointcheval e Stern mostraram em 1996 que a heurística Fiat-Shamir é segura no modelo de oráculo aleatório se o esquema de identificação subjacente for seguro.

Apêndices

Bibliografia

[Feige Fiat and Shamir 1988] (en) Uriel Feige, Amos Fiat and Adi Shamir , " Provas de identidade com conhecimento zero " , Journal of Cryptology ,1988( DOI 10.1007 / BF02351717 )
[Fiat e Shamir 1986] (en) Amos Fiat e Adi Shamir , " How To Prove Yourself: Practical Solutions to Identification and Signature Problems " , Crypto 1986 ,1986( leia online [PDF] )
[Schnorr 1989] (en) Claus-Peter Schnorr , " Efficient Identification and Signature for Smart Cards " , Theory and Application of Cryptology , Springer,1989( leia online )
[Pointcheval and Stern 1996] (en) David Pointcheval e Jacques Stern , " Security Proofs for Signature Schemes " , Eurocrypt ,1996( leia online [PDF] )

links externos

[Damgård 2010] (en) Ivan Damgård, “ On Σ-Protocols ” , notas da aula [PDF] ,2010