Conséquences de l'affacturage dans P?

L'affacturage n'est pas connu pour être NP-complet. Cette question portait sur les conséquences de la factorisation de NP-complet. Curieusement, personne n’a demandé les conséquences de l’affacturage dans P (peut-être parce qu’une telle question est triviale).

Donc mes questions sont:

Quelles seraient les conséquences théoriques de l'affacturage en P? Comment l'image globale des classes de complexité serait-elle affectée par un tel fait?
Quelles seraient les conséquences pratiques de l'affacturage en P? S'il vous plaît ne dites pas que les transactions bancaires pourraient être en danger, je sais déjà cette conséquence triviale.

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

J'ai posé une question similaire il y a quelques jours: "Quelle est la puissance de P avec un oracle de factorisation entière?" cstheory.stackexchange.com/questions/4765/…

Marzio De Biasi

Également lié: Quelles sont les conséquences de l'affacturage étant NP-complet?

Kaveh

@Kaveh, la question est déjà liée à celle-là.

Peter Taylor le

Réponses:

La factorisation en P. n’a pratiquement aucune conséquence théorique sur la complexité. Cela signifie qu’il n’existe aucune justification valable pour justifier le fait que la factorisation est difficile, à part le fait que personne n’a été capable de la résoudre à ce jour.

La factorisation temporelle polynomiale permettrait de prendre des racines carrées sur (et également sur une classe d'anneaux beaucoup plus générale), et donnerait des algorithmes polynomiaux pour un certain nombre d'autres problèmes de la théorie des nombres pour lesquels le goulot algorithme est actuellement en factorisation. $Z_n$

En ce qui concerne les conséquences pratiques, les transactions bancaires ne posent probablement pas vraiment problème - dès que l’on savait que l’affacturage était en P, les banques basculeraient vers un autre système, ce qui ne causerait probablement qu’une brève période de retard. mis en œuvre. Le décodage des transactions bancaires passées ne causerait probablement pas de graves problèmes aux banques. Un problème beaucoup plus grave est que toutes les communications précédemment protégées par la RSA risquaient maintenant d'être lues.

Peter Shor
la source

Un peu hors sujet, mais as soon as it was known that factoring was in P, the banks would switch to some other systemc'est en grande partie un voeu pieux. En décembre, j’ai découvert qu’une société qui ne faisait rien, sauf traiter les détails de carte de crédit, utilisait une variante de Vigenère avec une clé plus courte que certaines exécutions de texte en clair connu. Pire encore, le directeur technique de la société ne me croirait pas insécurisé tant que je ne lui ai pas envoyé de code d'attaque. Le MD5, bien qu’il soit largement considéré comme cassé, est toujours très utilisé dans le secteur bancaire.

Peter Taylor

@PeterTaylor, dès que l’on savait que l’affacturage était en P, les banques basculeraient vers un autre système, ce serait un voeu pieux ". Avec le prix actuel peu élevé de la mémoire Flash, il est tout à fait possible de créer une solution One Time Pad pour les utilisateurs se tournent de temps en temps vers un guichet automatique pour télécharger des octets aléatoires supplémentaires. RSA est simplement plus économique et plus simple

Flávio Botelho, le

Avoir de puissants chiffrements symétriques ne remplace pas les chiffrements asymétriques, bien qu’il soit suffisant pour certaines tâches spécifiques. Vous rencontrez le problème de ne pas être capable d'utiliser des signatures numériques, etc.

Joe Fitzsimons

En fait, vous pouvez avoir des signatures numériques avec des chiffrements symétriques! C'est beaucoup plus lourd et vous avez besoin d'une plus grande confiance en la troisième partie de confiance. Consultez les chapitres 11.6 et 11.7 du Handbook of Applied Cryptography.

Flávio Botelho

@Flavio: Mais la non-répudiation ne fonctionne pas de la même manière, n'est-ce pas?

Joe Fitzsimons

RSA est l'un des schémas de chiffrement / signature les plus importants qui se brise si FACTORING est en P. Cependant, il en existe beaucoup plus. Plusieurs d'entre eux (mais pas tous) sont basés sur l'hypothèse qu'il est difficile de distinguer les carrés et les non-carrés d'un nombre composé :

Et beaucoup d'autres régimes. Notez cependant que les schémas basés sur la dureté du journal discret (par exemple, le protocole Diffie-Helmann ou le schéma de cryptage / signature Elgamal ) continueront à être sécurisés.

MS Dousti
la source

Il me semble très probable que si la factorisation est dans P, le problème du log discret l'est aussi. Certes, l'inverse est vrai.

Joe Fitzsimons

@ Joe: J'ai les mêmes sentiments, mais existe-t-il des preuves ou des preuves mathématiques?

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: très intéressant! Votre commentaire m'a motivé à approfondir cette question et a permis à Eric Bach de trouver un résultat qui indique que " résoudre le problème du logarithme discret pour un module composite est exactement aussi dur que factoriser et le résoudre modulo premiers. "

MS Dousti

La crypto basée sur le réseau devrait rester sécurisée, espérons-le.

Antimony

$P$

Mohammad Al-Turkistany
la source