No capítulo 10 do HAC (10.4.2) , vemos o conhecido protocolo de identificação Feige-Fiat-Shamir com base em uma prova de zero conhecimento, usando a dificuldade (presumida) de extrair raízes quadradas do módulo de raízes quadradas de um composto que é difícil de fatorar. Darei o esquema com minhas próprias palavras (e espero acertar).
Vamos começar com um esquema mais simples: deixar ser um número inteiro Blum (assim e cada um de e é 3 mod 4) de tamanho suficientemente grande que factoring é intractible. Como é um número inteiro de Blum, metade dos elementos de possui o símbolo Jacobi +1 e a outra metade possui -1. Para os elementos +1, metade deles tem raízes quadradas e cada elemento que possui uma raiz quadrada possui quatro deles, exatamente um sendo um quadrado.
Agora Peggy seleciona um elemento aleatório de e define . Ela então envia para Victor. A seguir, o protocolo: Victor deseja verificar se Peggy conhece uma raiz quadrada de Peggy deseja provar isso a ele sem divulgar nada sobre além do fato de que ela conhece um .
- Peggy escolhe um aleatório em e envia para Victor.
- Victor equiprobably envia ou volta para Peggy.
- Peggy envia para Victor.
Victor pode verificar se Peggy enviou a resposta correta ao quadrado o que ele recebe e comparando com o resultado correto. Obviamente, repetimos essa interação para reduzir a chance de Peggy ser apenas um adivinho de sorte. Este protocolo é reivindicado ser ZK; uma prova pode ser encontrada em vários lugares (por exemplo, notas de aula de Boaz Barak ).
Quando estendemos esse protocolo para torná-lo mais eficiente, ele é chamado Feige-Fiat-Shamir; é muito parecido com o acima. Iniciamos o Peggy com valores aleatórios e sinais aleatórios ela publica seus quadrados como . Em outras palavras, negamos aleatoriamente alguns dos . Agoras 1 ⋯ s k t 1 = ± 1 , ⋯ t k = ± 1 v 1 = t 1 s 2 1 , ⋯ , v k = t k s 2 k v i
- Peggy escolhe um aleatório em e envia para Victor.Z ∗ n r 2
- Victor envia de forma valores de volta para Peggy.b i { 0 , 1 }
- Peggy envia para Victor.
Minha pergunta: Por que os bits do sinal são necessários? Entre parênteses, o HAC observa que eles existem como requisito técnico necessário para provar que nenhuma informação secreta vazou. A página da Wikipedia para Feige-Fiat-Shamir (que errou o protocolo) implica que, sem isso, um pouco vazou.
Não consigo encontrar um ataque que extraia algo de Peggy se ela omitir os sinais.