Criptologia: els mons d’Impagliazzo
Fer que els codis secrets siguin irrompibles és el somni de tota la vida dels professionals de la seguretat. Des de l'antiguitat, els humans van inventar sistemes manuals i després mecànics abans de la revolució electrònica. Descobreix la criptologia i els seus usos, des del xifratge tradicional fins al xifratge RSA i la informàtica.
Sense problema difícil, no pot existir cap criptologia més enllà de la del xifrat d’un sol ús. A més, el titular de la clau ha de poder desxifrar fàcilment el missatge; per tant, els problemes de la criptologia han de ser fàcilment verificables.
Han de pertànyer a la classe NP. Un problema que pertanyi a la classe NP sense pertànyer a la classe P no seria necessàriament adequat. Es podria admetre l’existència d’un problema així, que seria difícil de resoldre en el pitjor dels casos, però fàcil en general. Aquest tipus de problema no permetria desenvolupar una criptologia aplicable. El criptograma ha de ser indesxifrable sigui quin sigui el missatge, i no només en el pitjor dels casos
Clic a la imatge per engrandir. El investigador nord-americà Russell
Impagliazzo va imaginar mons (llistats en el text i apilats a la
piràmide de la figura següent) segons els resultats futurs que la teoria
de la complexitat ens aportarà. Crèdit: Bohmmartin, wikimedia commons,
CC 4.0
Criptomanía
Criptomania és el món en què vivim virtualment. Hi existeixen funcions unidireccionals amb trampa. Es pot plantejar un problema difícil i donar una indicació només a alguns perquè el puguin resoldre. El problema continuarà sent difícil per als altres. És el que passa amb la funció RSA: el desxiframent és impossible, excepte per a aquells que coneixen la factorització del mòdul.
Minicrypt
Aquest món imaginari podria esdevenir real si es pogués demostrar que cap funció unidireccional no pot tenir trampa. Això posaria en qüestió el xifrat amb clau pública, però encara es podrien signar documents. La implementació d’una funció de signatura només requereix l’existència d’una funció unidireccional. En aquest món, un professor pot plantejar un problema difícil a la seva classe, però no pot donar una indicació només a alguns perquè el resolguin.
Pessiland
Segons Impagliazzo, aquest món imaginari seria el pitjor de tots. Hi existeixen problemes fàcils de verificar però difícils de resoldre, i no hi ha funcions unidireccionals. Totes les funcions fàcilment calculables també són fàcilment invertibles. Alguns problemes continuen sent difícils, però aquesta dificultat no es tradueix en cap avantatge per desenvolupar criptografia. En aquest món i en els següents, no és concebible cap criptologia més enllà del xifrat d’un sol ús.
Heurística
En aquest món, els problemes fàcils de verificar són de mitjana tan fàcils de resoldre, però poden continuar existint instàncies difícils. Això comença a ser satisfactori per a les aplicacions. Per exemple, en la majoria dels casos, el venedor de pomes podrà triar fàcilment els fruits de la seva parada per satisfer un client que li’n demana per a un cert pes.
Algorítmica
Aquest món és finalment aquell en què P = NP. Tot problema fàcil de verificar és fàcil de resoldre, inclòs en el pitjor dels casos
Aquests mons constitueixen una jerarquia de mons possibles o impossibles segons que la teoria de la complexitat demostri l’existència de problemes difícils o la desmenteixi descobrint algorismes eficients per resoldre’ls.
