Onde está a falha no método de Blum-Feldman-Micali

Blum, Micali e Feldman (BFM) propuseram um novo modelo (criptográfico), no qual todas as partes (honestas ou adversárias) têm acesso a alguma string. Presume-se que a sequência seja selecionada de acordo com alguma distribuição (geralmente, distribuição uniforme) por uma parte confiável. É chamado de cadeia de referência e o modelo é apropriadamente chamado de modelo de cadeia de referência comum (CSR).

O modelo nos permite executar muitos protocolos interativos interessantes de maneira não interativa , substituindo consultas por bits da cadeia de referência. Em particular, provas de conhecimento zero para qualquer linguagem NP podem ser conduzidas de maneira não interativa, dando origem à noção de conhecimento nulo não interativo (NIZK).

O NIZK possui muitos aplicativos, como fornecer um método para realizar sistemas de criptografia de chave pública seguros contra ataques de texto cifrado escolhido (adaptável) .

BFM primeiro provou a existência de uma versão de NIZK de um único teorema para todas as línguas NP ; isto é, dada uma cadeia de referência e uma língua L ∈ N P , pode-se revelar apenas um único teorema da forma x ∈ L . Além disso, o comprimento do teorema é delimitado em | p | . Se o provador tentar reutilizar alguns bits de ρ em provas posteriores, existe o risco de vazamento de conhecimento (e a prova não será mais NIZK).$\rho$$L \in \bf{NP}$$x \in L$$|\rho|$$\rho$

Para remediar isso, a BFM utilizou uma versão multitorema baseada no teorema NIZK. Para esse fim, eles usaram um gerador pseudo-aleatório para expandir e, em seguida, usaram os bits expandidos. Existem outros detalhes também, mas não vou me aprofundar.$\rho$

Feige, Lapidot e Shamir (na primeira nota de rodapé na primeira página do artigo) declararam:

O método sugerido na MAB para superar essa dificuldade foi considerado defeituoso.

(A dificuldade refere-se à obtenção de provas multi-teoremas, em vez de provas com um único teorema.)

Onde está a falha do BFM?

Eu não li os detalhes de seu protocolo defeituoso, mas já ouvi falar disso várias vezes. Minha impressão foi que o erro deles ocorreu em como eles usaram a semente PRG. O protocolo deles coloca a semente do gerador pseudo-aleatório (PRG) na cadeia de referência comum pública e eles tentam argumentar que a segurança da PRG força alguma propriedade estatística da saída da PRG a manter mesmo com uma semente conhecida. Embora seja possível fazer isso de uma maneira sólida (os esquemas de assinatura de Hohenberger e Waters aqui e aqui vêm à mente), algo deu errado em seu argumento.