Por que Feige-Fiat-Shamir não é zero conhecimento sem bits de sinal?

12

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.nn=pqpqnZn

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 .sZnv=s2vvss

  1. Peggy escolhe um aleatório em e envia para Victor.rZnr2
  2. Victor equiprobably envia ou volta para Peggy.b=0b=1
  3. Peggy envia para Victor.rsb

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 1s k t 1 = ± 1 , t k = ± 1 v 1 = t 1 s 2 1 , , v k = t k s 2 k v iks1skt1=±1,tk=±1v1=t1s12,,vk=tksk2vi

  1. Peggy escolhe um aleatório em e envia para Victor.Z n r 2rZnr2
  2. Victor envia de forma valores de volta para Peggy.b i { 0 , 1 }kbi{0,1}
  3. Peggy envia para Victor.rΠi=1ksibi

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.ti

Não consigo encontrar um ataque que extraia algo de Peggy se ela omitir os sinais.

Fixee
fonte

Respostas:

8

O protocolo de identificação Feige-Fiat-Shamir (FFS) é uma prova de conhecimento (PoK), na qual a provadora (Peggy) comprova seu conhecimento das raízes quadradas da entrada fornecida ao verificador (Victor).

O FFS deseja discriminar o PoK das provas de associação ao idioma , nas quais Peggy prova que a entrada possui alguma propriedade (mais formalmente, a entrada pertence a um determinado idioma).

Se não usarmos os sinais negativos, é possível que as entradas não possuam raiz quadrada. Por exemplo, o número 20 não possui raízes quadradas mod 21. Como distinguir quadrados e não quadrados é um problema difícil famoso , o FFS evita isso, permitindo que a entrada seja o mais ou menos de algum número ao quadrado. Em suas próprias palavras (mudaram um pouco):

Ao permitir que seja mais ou menos um módulo quadrado de um número inteiro de Blum , que possa variar sobre todos os números com o símbolo de Jacobi e, assim, o existe (do ponto de vista de V) independentemente de caractere, conforme exigido na entrada irrestrita provas de conhecimento com zero conhecimento.vivi +1modnsivi

Por entrada irrestrita provas de conhecimento com zero conhecimento , elas significam um ZK PoK cuja prova correspondente de associação ao idioma é trivial; isto é, V pode decidir por si mesmo que a entrada é o mais ou menos de algum quadrado (apenas verificando o símbolo de Jacobi).

MS Dousti
fonte
Obrigado pela resposta, mas ainda não sigo: sem sinais, o símbolo Jacobi é +1. Com os sinais, o símbolo Jacobi é +1. Você diz acima "se não usarmos os sinais negativos, é possível que as entradas não possuam raiz quadrada". Como isso é possível? A entrada para o verificador é uma lista de quadrados que (assumindo um provador honesto) sempre têm raízes quadradas.
Fixee
Segunda pergunta: você está dizendo que os sinais estão presentes apenas para a prova passar? Ou existe um ataque real se eles forem omitidos?
Fixee
@Fixee: Suponha que um provador de trapaça escolha suas chaves públicas ( 's) não de acordo com o protocolo; diga um valor aleatório cujo símbolo de Jaccobi seja +1. O verificador (ruim) não tem como dizer se tem raízes quadradas ou não. A única maneira é executar o protocolo e obter a ajuda do provador. Ou seja, o provador está provando seu conhecimento dos e dando uma prova de associação ao idioma (ou seja, os pertencem ao QR de linguagem dos resíduos quadráticos.) Por alguma razão, o FFS gostava de separar esse tipo de prova de provas de "entrada irrestrita". Eu vejo isso como um mero tecnicismo. vivisivi
MS Dousti