[gull] Is Encryption Doomed?

[Frederic Schutz]

Selon Daniel Cordey <dc at mjt.ch>:

> Ce n'est sans doute pas pour la semaine prochaine, mais il s'agit d'un sujet
> interessant :-)

Voire meme passionant, selon les interets de chacun ;-)

Mais meme si ca arrivait la semaine prochaine, il n'y aurait pas trop de
soucis a se faire -- c'est une question qui est largement theorique. Sans
compter que les mathematiciens sont plutot en faveur de "P != NP" que
l'inverse.

Cite de l'article:

> That means that if a solution for any NP-complete problem could be found
> that could be solved in polynomial time, then a short-cut solution could be 
> found for every NP problem.

"polynomial time" et "short-cut" ne veulent pas dire grand chose; si on
trouvait un tel raccourci, il y a tres peu de chances pour qu'il soit 
facile a utiliser. Comme bien resume dans le paragraphe ci-dessus, la beaute
du probleme P ?= NP est qu'il a ete montre qu'un grand nombre de problemes
calculatoires difficiles sont equivalents. Ca veut dire que enormement de
chercheurs ont essaye d'attaquer le meme probleme, mais sous des angles
differents, et n'ont pas trouve de solution simple -- il est donc peu
probable que quelqu'un trouve une solution simple qui les resolve tous d'un
coup. Et meme s'il est montre que P = NP, (1) ca ne veut pas dire que la
preuve sera constructive (c'est bien beau de savoir qu'il existe un 
algorithme polynomial pour resoudre un probleme, ce n'est pas tres utile
si on n'est pas capable de le trouver !), (2) si l'algorithme necessite
un temps de calcul O(n^10000), il sera impossible a appliquer, meme s'il
est polynomial.

> In practical terms, that would spell the end of encryption as we know it. The

> Internet would be vulnerable to hackers and computer viruses. 
 
Ce genre de phrase bidon est assez decevante de la part de quelqu'un comme
Simson Garfinkel...

Frederic