Consequências da Factoring estar em P?

O fatoramento não é conhecido por ser NP-completo. Esta pergunta pediu consequências do fato de o Factoring ser NP-completo. Curiosamente, ninguém pediu consequências do fato de o Factoring estar em P (talvez porque essa pergunta seja trivial).

Então, minhas perguntas são:

Qual seria o teórico conseqüências do fatorial estar em P? Como o quadro geral das classes de complexidade seria afetado por esse fato?
Quais seriam as conseqüências práticas do fator de estar em P? Por favor, não diga que as transações bancárias podem estar em risco, eu já conheço essa conseqüência trivial.

cc.complexity-theory cr.crypto-security conditional-results factoring Giorgio Camerani
fonte

Fiz uma pergunta semelhante há alguns dias: "Qual é o poder de P com um oráculo de fatoração inteira?" cstheory.stackexchange.com/questions/4765/…

Marzio De Biasi

Também relacionado: Quais são as consequências de fatorar o NP-completo?

24411 Kaveh

@ Kaveh, a pergunta já está vinculada a essa.

Peter Taylor

Respostas:

Praticamente não há consequências teóricas da complexidade do fato de o fator fator estar em P. Isso significa que não há boas justificativas para o fator ser difícil, exceto que ninguém foi capaz de decifrá-lo até agora.

A fatoração em tempo polinomial tornaria possível estabelecer raízes quadradas sobre $Z_n$ (e também mais de uma classe muito mais geral de anéis também), e algoritmos dar polinômio de tempo para uma série de outros problemas de número da teoria para a qual o gargalo no o algoritmo está atualmente fatorando.

Quanto às consequências práticas, as transações bancárias provavelmente não são tão problemáticas - assim que se sabia que o fatorial estava em P, os bancos mudariam para outro sistema, provavelmente causando apenas um breve período de atraso enquanto isso estava sendo realizado. implementado. A decodificação de transações bancárias passadas provavelmente não causaria sérios problemas para os bancos. Um problema muito mais sério é que toda a comunicação anteriormente protegida pela RSA correria o risco de ser lida.

Peter Shor
fonte

Um pouco fora de tópico, mas as soon as it was known that factoring was in P, the banks would switch to some other systemé em grande parte uma ilusão. Descobri em dezembro que uma empresa que não faz nada além de processar detalhes do cartão de crédito estava usando uma variante do Vigenère com uma chave mais curta do que algumas execuções de texto simples conhecido. Pior, o diretor técnico da empresa não acreditaria em mim como inseguro até que eu lhe enviasse algum código de ataque. O MD5, apesar de ser amplamente considerado quebrado, ainda é muito utilizado no setor bancário.

Peter Taylor

@PeterTaylor, assim que se soubesse que o factoring estava em P, os bancos mudariam para algum outro sistema, em geral, é uma ilusão ". Com o preço barato atual da memória Flash, é completamente viável criar uma solução One Time Pad para banking, os usuários poderiam ir de vez em quando para um caixa eletrônico para baixar bytes aleatórios extras RSA é apenas mais barato e mais simples..

Flávio Botelho

Ter cifras simétricas fortes não substitui cifras assimétricas, embora seja suficiente para determinadas tarefas específicas. Você se depara com a questão de não poder usar assinaturas digitais etc.

Joe Fitzsimons

Na verdade, você pode ter assinaturas digitais com cifras simétricas! É muito mais complicado e você precisa de uma confiança muito maior na terceira parte confiável. Veja os capítulos 11.6 e 11.7 do Handbook of Cryptography Aplicado.

Flávio Botelho

@Flavio: Mas o repúdio não funciona da mesma maneira, funciona?

Joe Fitzsimons

O RSA é um dos mais importantes esquemas de criptografia / assinatura que são interrompidos se FACTORING estiver em P. No entanto, existem muitos outros. Vários (mas não todos) deles são baseados no pressuposto de que a distinção entre quadrados e não quadrados é um número composto :

E muitos outros esquemas. No entanto, observe que os esquemas baseados na dureza do log discreto (por exemplo, o protocolo Diffie-Helmann ou o esquema de criptografia / assinatura Elgamal ) continuarão seguros.

MS Dousti
fonte

Parece-me muito provável que, se o fatoramento estiver em P, o mesmo ocorre com o problema de log discreto. Certamente o inverso é verdadeiro.

Joe Fitzsimons

@ Joe: Eu tenho os mesmos sentimentos, mas há alguma prova ou evidência matemática?

MS Dousti

a^{p q} \equiv a^{p + q - 1} (mod p q)

$a^{pq} \equiv a^{p+q-1}~(\mbox{mod } pq)$

c_{a} = \log_{N} (a^{N} mod N)

$c_a = \log_N(a^N \mbox{mod }N)$

p = x + y

$p = x + y$

q = x - y

$q = x - y$

x = \frac{c_{a} + 1}{2}

$x = \frac{c_a + 1}{2}$

y = \sqrt{x^{2} - N}

$y = \sqrt{x^2 - N}$

@ Joe: Muito interessante! Seu comentário me motivou a aprofundar isso e encontrou um resultado de Eric Bach, que afirma que " resolver o problema do logaritmo discreto para um módulo composto é exatamente tão difícil quanto fatorar e resolver o módulo primos " .

MS Dousti

Espera-se que a criptografia baseada em treliça permaneça segura.

Antimony

$P$

Mohammad Al-Turkistany
fonte