Ataque quântico às funções de hash

A linha de questionamento é inspirada no truque escolhido na Seção 4 da versão em PDF do artigo Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding (Ambainis et al. , 2014) . Slides disponíveis aqui . Eu não sigo completamente o argumento, então talvez eu tenha perdido algo importante, mas aqui está a minha interpretação do truque deles.

$x \rightarrow H(x)$$H(x) = H(x') \land x\neq x'$$m$$u$$c = H(m\Vert u)$$(m',u')$C = H ( m ' ‖ u ' ) ( m , U )tal que devido à natureza livre de colisões dos hashes. Minha única opção é abrir o compromisso com .$c = H(m'\Vert u')$$(m,u)$

Agora, atacamos esse protocolo com um circuito quântico da função hash.

1. Faça uma superposição sobre todas as entradas possíveis e consulte a função hash com esse estado para obter o estado .$x_i$$\vert\psi\rangle = \sum_{i}\vert x_i\rangle\vert H(x_i)\rangle$

2. Meça o segundo registro para obter um compromisso aleatório. A medição escolhe aleatoriamente para alguns . O primeiro registro então possui modo que .$c = H(x_i)$$i$$\vert\phi\rangle = \sum_j \vert x_j\rangle$$\forall j, c = H(x_j)$

3. Eu gostaria de abrir o compromisso com alguns que me são dados pelo oponente. Use a pesquisa de Grover no primeiro registro para encontrar um do estado que satisfaça alguma propriedade especial. Especificamente, a propriedade especial é que o primeirobits de são . Ou seja, procurarei encontrar .$m'$$x_{\text{sol}}$$\vert\phi\rangle = \sum_j\vert x_j\rangle$$|m'|$$x_{\text{sol}}$$m'$$x_{\text{sol}} = m'\Vert u'$

Usando os slides postei anteriormente (Slide 8) e sua terminologia, é eficiente para encontrar um valor a partir da interseção de dois conjuntos e . Aqui é o conjunto de todos os de modo a que e é o conjunto de todos os , onde o primeirobits de são exatamente .$x$$S$$P$$S$$x$$H(x) = c$$P$$x$$|m'|$$x$$m'$

Minhas perguntas sobre este ataque são as seguintes:

1. Corrigi a idéia básica do ataque? Se estiver errado, ignore o restante da postagem!

2. Quantos elementos existem na superposição depois que nos comprometemos com um certo ? Para que eu possa abrir o compromisso com qualquer mensagem, parece que eu deveria ter elementos (o tamanho do intervalo da função hash). Mas isso é muito grande.$\vert\phi\rangle$$c$$O(N)$

3. A velocidade da pesquisa Grover - isso está relacionado ao ponto anterior - é a outra coisa. A complexidade computacional da pesquisa em uma superposição tão grande não seria a mesma que tentar adivinhar uma pré-imagem para uma determinada saída da função hash, já que é preciso pesquisar sobre todo o ? Nesse caso, onde está a vantagem?$\vert\phi\rangle$$u$

Estou procurando a intuição mais do que provas matemáticas, para que qualquer ajuda seja muito apreciada!

Corrigi a idéia básica do ataque? Se estiver errado, ignore o restante da postagem!

Na maioria das vezes. Da maneira como a descreve, você realmente obterá o estado , mas não poderá executar a transformação unitária . Mas na etapa 3, quando você executa o Grover no estado , na verdade você precisa aplicar como parte do algoritmo de Grover. A razão é a seguinte: Normalmente, Grover é apresentado como um algoritmo que procuras um valor que satisfaz um predicado . Nesse caso, o algoritmo de Grover inicializa primeiro o estado para$\lvert\phi\rangle$I - | & Phi; ⟩ ⟨ & Phi; | | & Phi; ⟩ I - | & Phi; ⟩ ⟨ & Phi; | x ∈ { 0 , 1 } n P | & Phi; ⟩ : = Σ x ∈ { 0 , 1 } n 2 - n / 2 | x ⟩ I - | & Phi; ⟩ ⟨ & Phi; |$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$x\in\{0,1\}^n$$P$$\lvert\phi\rangle:=\sum_{x\in\{0,1\}^n}2^{-n/2}\lvert x\rangle$. E, durante o loop principal, aplica o operador flip . Esse operador é muito fácil de construir se , portanto, normalmente não é mencionado como requisito do algoritmo. No entanto, em vez de procurar , você poderia procurar para algum conjunto . (Afinal, não há nada de especial nas cadeias de bits de comprimento .) Então você precisa alterar a descrição de Grover: O estado inicial será , e precisamos aplicar$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle=\sum_{x\in\{0,1\}^n}2^{-n/2}\lvert x\rangle$$x\in\{0,1\}^n$$x\in X$$X$$n$$\lvert\phi\rangle=\sum_{x \in X}2^{-\lvert X\rvert/2}\lvert x\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$Xdurante o loop principal. Para muitos conjuntos (por exemplo, números módulo ), será bastante fácil construir e . No entanto, no caso geral, pode ser que seja difícil construir qualquer um deles. Na sua descrição do algoritmo, temos uma situação semelhante. Ou seja, para alguns pontos . Mas para esse conjunto , não há como construir ou . É por isso que seu algoritmo não funciona (mas ainda dá a idéia certa). Em vez disso, no artigo que você cita, ambos$X$$N$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$X=\{x:H(x)=c\}$$c$$X$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle$I - | & Phi; ⟩ ⟨ & Phi; | | & Phi; ⟩e são fornecidos por oráculos especiais construídos apenas para esse fim. Usando esses oráculos, você pode executar o algoritmo Grovers no estado .$I-\lvert\phi\rangle\langle\phi\rvert$$\lvert\phi\rangle$

Quantos elementos existem na superposição depois que nos comprometemos com um certo ?$\lvert\phi\rangle$$c$

Isso vai depender dos parâmetros que você escolheu. Esperamos aproximadamente se é o tamanho do domínio e o tamanho da gama de . Para que as coisas sejam interessantes, você deve escolher para que exponencialmente haja muitos elementos na superposição (e pelo menos para que todas as mensagens sejam possíveis). No entanto, suponho que a razão pela qual você esteja se perguntando sobre isso seja porque você acha que o número de elementos deve ser pequeno para Grover funcionar, o que não é o caso, veja abaixo:$M/N$$M$$N$$H$$M\gg N$$2^{\lvert m\rvert}$

A velocidade da pesquisa de Grover - esse é o principal problema e não tenho certeza de como o truque deles realmente funciona. A complexidade computacional não seria a mesma que tentar adivinhar uma pré-imagem para uma determinada saída da função hash, já que é preciso pesquisar sobre todos os u? Nesse caso, onde está a vantagem?

Aqui parece estar um equívoco. Lembre-se de minhas explicações sobre o algoritmo de Grover no início desta resposta. Pesquisas Grover alguns , satisfazendo algum predicado . No nosso caso, pode ser enorme ( elementos ) porque é o conjunto de todas as pré-imagens de . Mas aquilo não importa. Lembre-se de que o Grover original funciona em que também é enorme, mas funciona rápido, enquanto procuramos por que possua alguma propriedade comum . Por exemplo, se pesquisarmos Grover por que satisfaça esse (o predicado$x\in X$$P$$X$$M/N$$c$$\{0,1\}^n$$x\in\{0,1\}^n$$P$$x\in\{0,1\}^n$$33\mid x$$P$), temos que existem muitos que satisfazem , a cada 33. satisfaz! E o tempo de execução será algo como . Portanto, como regra geral, se um predicado for satisfeito para cada ésimo elemento de , o algoritmo de Grover que pesquisa que satisfaz leva cerca de etapas. Aqui, não importa qual é o conjunto ou qual o seu tamanho! (Desde que tenhamos uma maneira de construir e para este conjunto$x$$P$$x$$\sqrt{33}$$P$$i$$X$$x\in X$$P$$\sqrt i$$X$$\lvert\phi\rangle$$I-\lvert\phi\rangle\langle\phi\rvert$$X$.) Agora, na configuração que você descreve, . E é o predicado que diz que começa com . Para analisar o tempo de execução do algoritmo de Grover, neste caso, não se preocupam com , mas precisamos saber quantas vezes um satisfaz elemento . Isso é fácil: todo elemento faz. Portanto, o tempo de execução do Grover será . Isso é um problema se for longo, mas se for, por exemplo, apenas um pouco, isso funcionará bem. Por exemplo, se usarmos a função hash para confirmar as mensagens de um bit, podemos abrir o compromisso para qualquer valor de$X=\{x:H(x)=c\}$$P$$x$$m'$$X$$P$$2^{\lvert m'\rvert}$$O(\sqrt{2^{\lvert m'\rvert}})$$m'$$m'$$m'$.

Se você quiser um exemplo em que seja maior, precisará variar a construção. Basicamente, você se compromete individualmente e concatena os compromissos. Em seguida, cada compromisso pode ser quebrado usando o método descrito acima, e você precisa executar os do algoritmo .$m'$$\lvert m'\rvert$