Conhecimento zero não interativo não clonável no modelo Quantum Random Oracle

Tabela de links

Resumo e introdução

Visão geral técnica

Preliminares

Conhecimento zero não interativo não clonável no modelo CRS

NIZK não clonável no modelo Quantum Ramdon Oracle

Assinaturas de conhecimento não clonáveis

Referências

5 NIZK não clonáveis no modelo Quantum Random Oracle

5.1 Um Protocolo Sigma Modificado

Começaremos introduzindo um protocolo sigma ligeiramente modificado. Nas próximas seções, nossa construção envolverá a aplicação do Fiat-Shamir a este protocolo modificado.

Prova. Completude perfeita Isso decorre diretamente da completude perfeita de Π.

e qualquer x com associado λ ∈ N satisfatório

Nós temos

Definimos Ext 3 com acesso oracle a Π.Ext e alguns A da seguinte forma:

Entrada: x, S.

(1) Dado (x, α, s) de AΠ: envie α para Π.Ext, receba β de Π.Ext e envie β para AΠ.

(2) Ao receber γ de AΠ: envie γ para Π.Ext.

(3) Produza o resultado de Π.Ext como w.

Definimos o seguinte conjunto de parâmetros: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) e negl1 (·) = negl1,Π(·).

Seja o circuito quântico de tamanho polinomial A = (A 0, A 1) e (x, S) tal que

Agora definimos AΠ = (A0,Π, A1,Π) com acesso oracle para A. A0,Π é conectado com S, recebe a entrada x, envia (x, S) para A0, recebe ((x, α, s ), |sti) de A0 e saídas (α, |sti). A1,Π é conectado com S, recebe a entrada (x, |sti, β), envia ((x, S), |sti, β) para A1, recebe γ de A1, gera γ. Pela estrutura da nossa prova e definição do nosso verificador, isso significa que

que satisfaz a restrição na Equação (15). Isto significa que temos, quando combinado com a nossa definição de Ext, que

Mostrando assim que nosso protocolo é um protocolo de prova de conhecimento.

Conhecimento zero do verificador honesto computacional com simulador quântico . Seja Π.Sim o simulador quântico computacional de conhecimento zero, verificador honesto, para Π. Definimos Sim com acesso oracle a Π.Sim da seguinte forma:

Entrada: x, S.

(1) Calcule (α, β, γ) ← Π.Sim(1λ , x)

(2) Amostras de S.

(3) Saída ((x, α, s), β, γ).

Seja um polinômio p(·), um circuito quântico de tamanho polinomial D, λ ∈ N, e ((x, S), w) ∈ R tal que

Definimos uma redução à propriedade de conhecimento zero de Π da seguinte forma:

Redução: ao conhecimento zero de Π dado acesso do oráculo a D.

Conectado com: x, S.

(1) Receber (real ou simulado) (α, β, γ) do desafiante.

(2) Amostras de S.

(3) Envie ((x, α, s), β, γ) para D. Receba b de D.

(4) Saída b.

Quando o desafiante envia uma prova real (ou simulada) para Π, a redução gera uma prova idêntica à prova real (resp. simulada). Como tal, esta redução preserva a vantagem distintiva de D . Isto chega a uma contradição contra a propriedade de conhecimento zero de Π. Portanto, nosso protocolo deve ser de conhecimento zero.

Pela definição do provador honesto P.Com,

o que é uma contradição. Portanto, o nosso protocolo deve ter compromissos imprevisíveis.

Corolário 5.2. A heurística Fiat-Shamir aplicada ao protocolo sigma pós-quântico definido no Teorema 5.1 produz um NIZKPoK Π′ pós-quântico clássico no QROM (Definição 3.11).

Prova . Isto segue pelo Teorema 5.1 e Teorema 3.12.

5.2 Definições de Inclonabilidade

NIZKs não clonáveis no modelo oracle aleatório quântico são definidos de forma análoga ao modelo CRS – repetimos essas definições no modelo QRO para completar abaixo.

Definição 5.3. (Segurança não clonável para instâncias difíceis). Uma prova (P,V) satisfaz a segurança não clonável em relação a um oráculo aleatório quântico O se para cada linguagem L com relação correspondente RL, para cada família de circuitos quânticos de tamanho polinomial {Cλ}λ∈N, e para cada distribuição rígida {Xλ ,Wλ}λ∈N sobre RL, existe uma função desprezível negl1 (·) tal que para cada λ ∈ N,

Definição 5.4 ((k−1)-to-k-Unclonable NIZK extraível em QROM). Seja dado o parâmetro de segurança λ ∈ N e a relação NP R com a linguagem correspondente L. Seja Π = (P,V) dado tal que P e V são algoritmos quânticos de tamanho poli(λ). Temos que para qualquer (x, ω) ∈ R, P recebe uma instância e um par de testemunhas (x, ω) como entrada e produz π, e V recebe uma instância x e prova π como entrada e produz um valor em {0, 1}.

Π é um protocolo NIZKPoK não interativo (k - 1) para k não clonável para a linguagem L em relação a um oráculo aleatório O se o seguinte for válido:

• Π é um protocolo NIZKPoK para a linguagem L no modelo oracle aleatório quântico (Definição 3.11).

• (k−1)-para-k-Não clonável com extração: Existe um circuito quântico E de tamanho polinomial auxiliado por oráculo tal que para cada circuito quântico A de tamanho polinomial, para cada tupla de k − 1 pares de instância-testemunha ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, para cada x onde definimos

tal que existe um polinômio p(·) onde

então também existe um polinômio q (·) tal que

Semelhante à seção anterior, temos o seguinte lema.

Lema 5.5. Seja Π = (Setup, P,V) um protocolo quântico de conhecimento zero não interativo 1 para 2 não clonável (Definição 5.4). Então, Π satisfaz a Definição 5.3.

Para uma prova do Lema 5.5, referimo-nos ao Apêndice A.

5.3 NIZK não clonável implica dinheiro quântico de chave pública em QROM

Teorema 5.6. Seja O um oráculo quântico aleatório. Seja (X ,W) uma distribuição rígida sobre uma linguagem L ∈ NP. Seja Π = (P,V) um protocolo de conhecimento computacionalmente zero, não clonável, 1 para 2, não interativo, perfeitamente completo, para L no modelo QRO (Definição 5.4).

Então (P,V) implica um mini-esquema de dinheiro quântico de chave pública no modelo QRO (Definição 3.15), conforme descrito na Figura 4.

Prova . Correção Perfeita . Isto decorre diretamente da completude perfeita de Π. Impossível de forjar. Seja p(·) um polinômio e A um adversário quântico de tempo polinomial tal que para um número infinito de λ ∈ N +,

Construímos uma redução que quebra a definição de não clonabilidade (Definição 5.3) que mostramos (no Apêndice A) estar implícita em nossa definição (Definição 5.4). O desafiante, com acesso ao oráculo aleatório O, amostra um par instância-testemunha difícil (x, w) ← (X ,Y) e uma prova π ← PO(x, w). O desafiante então encaminha (x, π) para a redução, que também tem acesso oráculo a O. A redução então define |$i = π e s = x. A redução envia (|$i, s) para o adversário A que retorna (|$0, s0, |$1, s1). A redução então analisa e define πi = |$ii para i ∈ {0, 1}. A redução então envia π0 e π1 de volta ao desafiante.

5.4 Construção e Análise

Lema 5.7. Sejam λ, k ∈ N e um mini-esquema de dinheiro quântico de chave pública ( NoteGen,Ver ). Sejam os pontos q1, . . . , qk com a seguinte estrutura: um ponto q contém um número de série s amostrado de acordo com NoteGen (1λ ).

Os pontos q1, . . . , qk deve ser distinto com probabilidade esmagadora.

Prova . Cada ponto contém um número de série amostrado de acordo com o algoritmo de geração de dinheiro quântico, NoteGen (1λ). Pela imprevisibilidade dos números de série do dinheiro quântico (Definição 3.13), todos os k números de série gerados honestamente devem ser distintos com uma probabilidade esmagadora. Conseqüentemente, esses k pontos serão distintos com probabilidade esmagadora.

Apresentamos agora nossa construção na Figura 5 e provamos o teorema principal desta seção.

Teorema 5.8. Seja k(·) um polinômio. Seja dada a relação NP R com a linguagem correspondente L.

Seja ( NoteGen, Ver ) um mini-esquema de dinheiro quântico de chave pública (Definição 3.13) e Π = (P,V) um protocolo sigma pós-quântico (Definição 3.4).

(P,V), conforme definido na Figura 5, será um som de conhecimento não interativo, conhecimento computacionalmente zero e (k - 1)-para-k-não clonável com protocolo de extração para L no modelo oracle aleatório quântico (Definição 3.11 ).

Prova. Deixe os parâmetros e primitivos serem os dados na declaração do teorema. Argumentamos que a completude decorre da construção do protocolo na Figura 5 e provamos as propriedades restantes abaixo.

Nós temos

Seja o circuito quântico A e x de tamanho polinomial dado tal que

Seja AF S definido com acesso oracle a alguns A e O da seguinte maneira:

Entrada: x, S.

(1) Dada uma consulta (x, α, s) de A: envie (x, α, s) para O, receba β de O e envie β para A.

(2) Ao receber π = (|$i, s, α, β, γ) de A: saída πF S = ((x, α, s), β, γ).

Pela estrutura da nossa prova e definição do nosso verificador, isso significa que

que satisfaz a restrição na Equação (16). Isto significa que temos, quando combinados com a nossa definição de Ext e S, que

Mostrando assim que nosso protocolo é um protocolo de prova de conhecimento.

Conhecimento Zero. Seja SimF S o simulador para Π′ no Corolário 5.2 (onde Π instancia o Teorema 5.1). Seja RF S a relação para Π′ em relação a R. Definimos Sim com acesso de oráculo a SimF S e acesso de programa a algum oráculo aleatório O como segue:

Entrada: x (ignora quaisquer testemunhas que possa receber).

Seja um diferenciador D auxiliado por oráculo que só pode fazer consultas (x, w) ∈ R, e um polinômio p(·) tal que

Definimos uma redução à propriedade de conhecimento zero de Π′ da seguinte forma:

Redução: ao conhecimento zero de Π′ dado acesso oracle a D e acesso de programa a O.

Para cada (x, w) de D:

A visão de D corresponde à do nosso protocolo na Figura 5 ou Sim. Como tal, a nossa redução deveria ter a mesma vantagem em quebrar a propriedade de conhecimento zero de Π′. Chegamos a uma contradição, portanto nosso protocolo deve ser de conhecimento zero.

Extratabilidade não clonável. Seja Ext o circuito quântico do extrator que definimos anteriormente (em nossa prova de que a Figura 5 é uma prova de conhecimento). Seja Sim o circuito quântico do simulador que definimos anteriormente (em nossa prova de que a Figura 5 é um protocolo de conhecimento zero). Definimos um extrator E com acesso oracle a algum A da seguinte forma:

Conectado com: alguma escolha de I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x.

(1) Amostras ℓ ∈ J uniformemente ao acaso.

(2) Instancia um oráculo aleatório simulável e extraível O. Executa Ext em O durante toda a interação com A (o que pode envolver retrocesso, caso em que retrocederíamos A e repetiríamos as etapas a seguir). Exija que Ext extraia em relação à ℓ-ésima prova produzida por A.

(3) Calcule πι ← Sim(xι) para ι ∈ [k − 1] onde armazenamos todos os pontos que Sim programaria em uma lista P.

(4) Envie {πι}ι∈[k−1] para A.

(5) Para cada consulta de A, se a consulta estiver em P, então responda com a resposta de P. Caso contrário, encaminhe a consulta para O e envie a resposta de volta para A. Deixe Ob denotar este oráculo aleatório modificado.

(7) Produz o resultado de Ext como w.

Dada a Equação (24), podemos estar em um dos dois seguintes casos: ou A gera duas provas de aceitação que possuem o mesmo número de série que uma prova gerada honestamente, ou A não. Consideramos estes dois cenários separadamente e mostramos que cada um chega a uma contradição.

Cenário Um

Digamos que A gere duas provas de aceitação que possuem o mesmo número de série de uma prova gerada honestamente. Aplicando uma união vinculada à Equação (24), temos que este evento poderia acontecer com pelo menos 1/2p(λ) de probabilidade. Simbolicamente,

Cenário Dois

Alternativamente, digamos que A não gera duas provas de aceitação que tenham o mesmo número de série que uma prova gerada honestamente. Pelo princípio do pombo, isso significa que A gera uma prova de aceitação com um número de série que não está entre os que recebeu. Aplicando uma união vinculada à Equação (24), temos que este evento poderia acontecer com pelo menos 1/2p(λ) de probabilidade. Em resumo, temos que

Através de um argumento de média, podemos fixar o índice j ∈ J que nos dá o mesmo evento com uma vantagem de 1/(2kp(λ)). Agora mudaremos para um híbrido onde forneceremos a A provas simuladas nos índices I.

Reivindicação 5.9. Existe um polinômio q (·) tal que

Mais tarde veremos uma prova da Reivindicação 5.9. Por enquanto, assumindo que esta afirmação seja válida, podemos definir um adversário do qual Ext pode extrair uma testemunha válida para x.

Reivindicação 5.10. Existe um polinômio q ′ (·) tal que

Em breve veremos uma prova para a reivindicação 5.10. Entretanto, se esta afirmação for verdadeira, então teremos uma contradição direta com a Equação (19). Assim, tudo o que resta a ser provado são as duas alegações: Alegação 5.9 e Alegação 5.10. Começamos provando a afirmação anterior.

Prova de Reivindicação 5.9. Primeiro precisamos argumentar que a nossa estratégia está bem definida, que seremos capazes de programar independentemente estes k pontos. Então podemos argumentar a indistinguibilidade de mudar uma por uma para provas simuladas. Argumentaremos que nosso simulador será executado no tempo polinomial esperado. Pelo Lema 5.7, os k pontos que nosso simulador irá programar serão distintos com probabilidade esmagadora. Além disso, como assumimos que nosso oráculo quântico aleatório pode ser programado em múltiplos pontos distintos, Definição 3.10, nosso simulador está bem definido.

Argumentamos agora a indistinguibilidade das provas simuladas das provas geradas honestamente através de um argumento híbrido. Suponha, por contradição, que a diferença de probabilidade entre a Equação (21) e a Equação (22) fosse 1/p′ (λ) para algum polinômio p ′ (·). Construímos uma série de híbridos consecutivos para cada i ∈ [k − 1] onde trocamos a i-ésima prova do provador gerado para o simulado. Por este argumento híbrido, deve haver alguma posição ℓ ∈ [k − 1] onde mudar a ℓ-ésima prova tem uma diferença de probabilidade de pelo menos 1/(kp′ (λ)). Formalizamos agora uma redução que pode distinguir entre estas duas configurações:

Argumentamos primeiro que a visão que a redução fornece a A corresponde a um dos jogos: onde todas as provas até o ℓ-ésimo são simuladas ou onde todas as provas até e incluindo o ℓ-ésimo são simuladas. Pelo Lema 5.7, o ponto computado ou programado pelo desafiante será distinto dos pontos dos programas de redução. Como tal, a redução pode modificar 5 o oráculo com o qual A faz interface (ver etapa (4)). Em resumo, A terá acesso a um oráculo que seja consistente com todas as provas que receber.

Dado que A tem uma visão que corresponde diretamente à sua visão esperada em qualquer jogo, então a vantagem da redução é igual à vantagem de A, que é pelo menos 1/(kp′ (λ)). Isto é uma contradição com a propriedade de conhecimento zero do nosso protocolo. Portanto, nossa afirmação original deve ser verdadeira.

Agora, continuamos a provar a última afirmação.

Prova de Reivindicação 5.10. Dado que a reivindicação 5.9 é válida, isso implica que

Primeiro devemos argumentar que a visão de A permanece idêntica ao jogo que aparece tanto na Equação (24) quanto na Equação (25). O oráculo com o qual A faz interface (veja a etapa (4)) será consistente com todas as provas que receber.

Através da Equação (25), chegamos à conclusão que

Pela definição de uma prova de conhecimento (Definição 3.11) que possui alguns parâmetros polinômios p ∗ (·) e funções desprezíveis negl0 (·) e negl1 (·), temos que existe algum polinômio q ′ (·) tal que

o que completa a prova da nossa afirmação.

Ao completar as provas das nossas afirmações, concluímos a prova da afirmação do nosso teorema.

Corolário 5.11. Supondo que existam funções unidirecionais injetivas e que exista iO pós-quântico, existe um som de conhecimento não interativo, conhecimento computacionalmente zero e (k - 1) -to-kunclonável com protocolo de extração para NP no oráculo aleatório quântico modelo (Definição 5.4).

Prova. Isto segue do Teorema 3.14 e do Teorema 5.8.

Mostramos assim que a Figura 5 é um NIZK PoK não clonável no modelo ROM conforme definido de acordo com nossa definição de não clonabilidade, Definição 5.4.