Protocolos Sigma e identificação de Schnorr

Um protocolo Sigma tem 3 mensagens: (1) Compromisso: o provador envia um compromisso com um valor aleatório. (2) Desafio: o verificador envia um desafio aleatório. (3) Resposta: o provador envia uma resposta calculada a partir do desafio e do segredo. O verificador aceita ou rejeita.

O provador conhece o segredo x (chave privada); chave pública = g^x mod p (ou ponto X = x*G em uma curva elíptica). Objetivo: demonstrar conhecimento de x sem revelá-lo. Esta é uma prova de conhecimento do logaritmo discreto.

(1) O provador escolhe um r aleatório e envia o compromisso R = r*G. (2) O verificador envia o desafio c (inteiro aleatório). (3) O provador envia a resposta s = r + c*x. (4) O verificador verifica se s*G == R + c*X. Se sim, aceita. O provador conhece x; a resposta s só pode ser calculada com x.

Completude: um provador honesto sempre satisfaz s*G = r*G + c*x*G = R + c*X. Solidez: duas transcrições com o mesmo R, mas com desafios diferentes c e c', produzem s e s', a partir dos quais é possível recuperar x = (s-s')/(c-c') — portanto, um trapaceiro não consegue produzir duas respostas válidas para o mesmo R.

Simulador (sem conhecer x): escolha s e c aleatórios e defina R = s*G - c*X. Essa distribuição de transcrições (R, c, s) é válida. O verificador não consegue distinguir transcrições reais das simuladas — Schnorr oferece conhecimento zero para verificadores honestos.

Torne Schnorr não interativo: substitua o desafio do verificador por c = resumo(R || mensagem). O provador calcula c por conta própria e responde. Resultado: uma prova com 2 elementos (R, s) que qualquer pessoa pode verificar. Este é o esquema de assinatura de Schnorr.

Assinar(x, m): r ← aleatório; R = r*G; c = resumo(R||m); s = r + c*x. Assinatura = (R, s). Verificar: s*G == R + resumo(R||m)*X. Compacta (64 octetos para P-256), verificável em lote e com segurança demonstrável no ROM. Adotada no Taproot do Bitcoin (BIP-340).

C = r*G + v*H, onde H é um segundo gerador independente. Compromete o valor v usando a aleatoriedade r. Vinculação: não é possível abrir o compromisso para um v diferente (logaritmo discreto). Ocultação: C tem distribuição uniforme. Usado em provas de intervalo baseadas em Schnorr e em Bulletproofs.

Demonstrar conhecimento de x1 AND x2 simultaneamente: execute dois protocolos de Schnorr com o mesmo desafio (compartilhe o desafio por meio de Fiat-Shamir). O verificador aceita somente se ambas as subprovas forem válidas. Isso permite demonstrar várias afirmações em uma única interação.

Demonstrar conhecimento de x1 OR x2 sem revelar qual deles: use o simulador para um dos ramos a fim de calcular uma transcrição falsa e depois divida o desafio entre os dois. O verificador vê duas transcrições aparentemente válidas cuja soma é igual ao desafio real. São chamadas de «assinaturas de anel».

Identificações Schnorr: passaportes eletrônicos (protocolo PACE). Assinaturas Schnorr: Bitcoin Taproot, Monero (RingCT usa provas OR de Schnorr), protocolo Signal (acordo de chaves X3DH). Compromissos de Pedersen: Transações confidenciais, Bulletproofs e criptografia de notas Sapling do Zcash.

No protocolo de identificação de Schnorr, o que o verificador verifica na etapa final?

Protocolos Sigma: compromisso–desafio–resposta. Schnorr demonstra conhecimento de um logaritmo discreto. Fiat-Shamir torna o protocolo não interativo (assinatura Schnorr). A seguir: provas SNARK de conhecimento zero para provas não interativas sucintas.