Custo mínimo de comunicação para zero provas de conhecimento de três cores

11

A prova de Goldreich et al. De que três cores têm zero provas de conhecimento usa pouco comprometimento para uma coloração inteira do gráfico em cada rodada [1]. Se um gráfico possui vértices e e arestas, um hash seguro possui b bits e buscamos a probabilidade de erro p , o custo total da comunicação énebp

O(benlog(1/p))

mais de rodadas. Usando uma árvore Merkle gradualmente revelada, a comunicação total pode ser reduzida para O ( b e log n log ( 1 / p ) ) com o custo de aumentar o número de rodadas para O ( log n ) .O(1)O(belognlog(1/p))O(logn)

É possível fazer melhor do que isso, em termos de comunicação total ou número de rodadas?

  1. http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

Edit : Obrigado a Ricky Demer por apontar o fator ausente de .e

Geoffrey Irving
fonte

Respostas:

3

Então, aqui está o artigo certo para meus propósitos:

Joe Kilian, "Uma observação sobre provas e argumentos eficientes de conhecimento zero." http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf

Para obter o resultado mais forte, precisamos aceitar zero argumentos de conhecimento em vez de provas (comprovador limitado computacionalmente); é nisso que estou interessado, mas não conhecia a terminologia.

Assumindo suposições criptográficas suficientes, o artigo fornece zero argumentos de conhecimento com comunicação total para c = O ( 1 ) .O(blogcnlog(1/p))c=O(1)

Este resultado é apertado para rodadas por Ishai et al., "Em PCPs eficientes de conhecimento zero", http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf .O(1)

Geoffrey Irving
fonte
Eu acho que é melhor excluir esta resposta e atualizar a original para ser a resposta correta.
Kaveh
2

Atualização : Esta resposta é obsoleta pela minha outra resposta, com limites totalmente polilogarítmicos a partir das referências apropriadas.

Pensando bem, não há necessidade de revelar a árvore Merkle gradualmente, portanto a versão de comunicação inferior não precisa de rodadas extras. As etapas de comunicação são

  1. O provador P randomiza sua coloração, transforma-a em uma árvore Merkle (salgada) e envia a raiz ao verificador V.
  2. V pega uma vantagem aleatória e envia para P.e
  3. P envia os caminhos da árvore Merkle da raiz para cada ponto final de a V.e

Isso fornece comunicação durante as rodadas O ( 1 ) .O(belognlog(1/p))O(1)

Atualização: Aqui estão os detalhes da construção da árvore Merkle. Para simplificar, expanda o gráfico para ter exatamente vértices adicionando alguns nós desconectados (eles não afetam três cores ou zero conhecimento). Assuma uma função hash segura, recebendo entradas de qualquer tamanho e produzindo saídas de bits b . Para cada árvore Merkle, o provador escolhe 2 a + 1 - 1 nonces aleatórios de bits b , um para cada folha e não folha da árvore binária. Nas folhas, misturamos a cor concatenada com o nonce para produzir o valor da folha. Em cada nonleaf, usamos o valor dos dois filhos com o nonce do nonleaf para produzir o valor do nonleaf.2ab2a+11b

Na primeira rodada, o provador envia apenas o valor raiz, que não fornece informações, pois é hash com o nonce da raiz. Na terceira rodada, nenhuma informação é transmitida sobre qualquer nó não expandido na árvore binária, pois esse nó foi hash com um nonce nesse nó. Aqui, estou assumindo que o provador e o verificador são limitados computacionalmente e não podem quebrar o hash.

Edit : Obrigado a Ricky Demer por apontar o fator ausente de .e

Geoffrey Irving
fonte
A etapa 1 daria ao verificador uma maneira de alta precisão para testar qualquer palpite na coloração do fornecedor, usando apenas 6 vezes o trabalho da etapa 1 do paletó por palpite. Além disso, não vejo nenhuma maneira de usar uma árvore Merkle calculada pelo provador sem passar de uma prova para um argumento .
Como uma árvore Merkle salgada pode ser usada para adivinhar uma coloração?
Geoffrey Irving
1
Postei uma resposta dizendo por que acho que a idéia salgada da árvore Merkle não funciona. Em vez disso, você deve transformar os compromissos com as randomizações das cores em uma árvore Merkle. Percebo também que você parece estar perdendo um fator number_of_edges na complexidade da comunicação.
1
Bem, pode-se considerar a promessa de que a tarefa é de 3 cores válidas ou [pelo menosδe arestas têm vértices da mesma cor]. Isso diminui a complexidade da comunicação para O(((bn)/δ)log(n)). (continuação ...)
1
(... contínuo) Em seguida, pode-se aplicar máquinas PCP para reduzir a relação padrão de 3 cores para essa relação de promessa.Então, levar essa idéia ao extremo dá argumentos universais de conhecimento zero .
1

Há uma recente onda de atividade em argumentos sucintos e não interativos de conhecimento zero. Sabe-se como, por exemplo, construir um argumento NIZK para Circuit-SAT, em que o tamanho do argumento é um número constante muito pequeno de elementos de grupo (ver Groth 2010, Lipmaa 2012, Gennaro, Gentry, etc, Eurocrypt 2013, etc). Com base em uma redução de NP, é possível construir claramente um argumento para a 3 cores com a mesma comunicação.

É claro que este é um modelo diferente comparado à sua pergunta original - por exemplo, nesses argumentos, o comprimento do CRS é linear no tamanho do circuito e, em certo sentido, pode ser pensado como parte da comunicação (embora possa ser reutilizado em muitos argumentos diferentes).

cryptocat
fonte
0

(Isso não cabe em um comentário.)

Acho que agora vejo como mostrar que a sua salga não fornece necessariamente
zero conhecimento do verificador honesto.H0
H0H1H0
H1H0
||H2


xz((3b)+6)y
mm=x||111...[b of them]...111||y||z,
Um temH2(m)=x||111...[b of them]...111||H1(m)||z



xrmxrm
H2(m)=x||111...[b of them]...111||H1(m)||x



m
H2(m)=
[b+3 bits whose values don't matter]||H1(m)||[3 bits whose values don't matter].


.



H1H2H1H1
H0H0H2


1/(2(b1))


fonte
Não sei se sigo sua anotação, mas parece que você está argumentando que pode pegar meu esboço e preencher os detalhes de uma maneira obviamente boba, produzindo assim um sistema inseguro. Vou adicionar a versão mais limpa e segura dos detalhes à minha resposta.
Geoffrey Irving
H2 Tudo o resto estava o que eu sinceramente pensei que você quis dizer.
Informe-me se os detalhes adicionados à minha resposta deixam claro. É bem possível que eu esteja perdendo alguma coisa e minha construção esteja realmente quebrada.
Geoffrey Irving