Aggiunto qui:
https://wiki.eigenlab.org/index.php/Hackmeeting0x13:Talks
editate liberamente!
> In realtà non ce li ha nessuno. Per cui tipo dormite sogni tranquilli
> che RSA ancora è sicuro.
Questo è vero, anche rispetto alle considerazioni su D-Wave: ci stanno
tre articoli che spiegano come nonostante riescano a contenere la
decoerenza per periodi lunghi (il computer opera effettivamente in "modo
quantistico"), le prestazioni sono assai deludenti.
http://lists.autistici.org/message/20160517.004102.d1e3dd8b.en.html
Ho sbagliato a scrivere "ce li hanno loro"; intendevo piuttosto che non
lo possiamo sapere veramente. C'è una pletora di gente che lavora e fa
ricerca in questo campo rendendo pubblici i risultati e discutendoli in
comunità, ma c'è anche tutta una parte di ricerca privata, militare,
etc. che *non* rende pubblico niente e ci investe un mare di soldi. A me
questa roba inquieta abbestia e fa pure un po' incazzare, ma è una
questione che riguarda tutta la tecnoscienza in generale e penso prima o
poi sarebbe ganzo intavolare di nuovo una discussione ampia sull'argomento.
> Ah, ma lattice-based criptography? Che io sappia non si sa se un
> computer quantistici sanno risolvere il problema del vettore minimo in
> un reticolo (che è credo un po' tutto il punto della questione). Il
> che non vuol dire che siano sicuri. Ok, anche la fattorizzazioni in
> numeri primi non si sa se si può fare in maniera efficiente sui
> computer classici, e difatti ci stiamo basando sobra una buona parte
> dell'economia globale su questa cosa.
Gente, stiamo già spoilerando abbestia il contenuto del talk ;)
Brevemente: trovare un fattore sta nella classe BQP (Shor), quindi
dirigiamo l'attenzione altrove (lattice-based cryptography) considerando
SVP_\gamma e CVP_\gamma.
Classicamente, si credono "molto probabilmente" difficili, nel senso che
se esiste un algoritmo polinomiale che trova con probabilità non nulla
un'approssimazione \gamma < n^{c/log log n} allora P=NP.
Restano difficili anche per i computer quantistici? È vero che non si sa
con precisione, ma gli indizi dicono di si, per due motivi (il primo
innalza l'upper bound alla difficoltà, il secondo innalza il lower bound):
1) approssimazioni sub-esponenziali di SVP su reticoli q-ari sono
classicamente fuori portata, anche teoricamente; su una macchina
quantistica si potrebbero risolvere efficientemente questi problemi se
avessimo una soluzione efficiene di HSP nel caso non abeliano, ma
l'ipotesi più accettata è che questo resti intrinsecamente difficile
anche per la computazione quantistica.
2) le due costruzioni che presenterò io (una funzione hash e un cifrario
a chiave pubblica) hanno una riduzione caso medio -> caso pessimo ai
problemi di cui sopra, che è una garanzia piuttosto robusta: un
algoritmo che riuscisse a rompere una istanza casuale (con la distrib.
uniforme sulle chiavi private) della primitiva crittografica dovrebbe
risolvere *tutte* le istanze del sottostante problema su reticoli
(comprese quindi quelle al caso pessimo).
Chiaramente quanto affidarci a queste considerazioni è una questione che
va discussa e anch'io sento di volerlo fare insieme; del resto credo si
debba - anche per scegliere le prossime linee di ricerca - tener
presente quanto dicevo sopra, ossia del carattere non-pubblico di
Google, eserciti e compagnia bella quando studiano queste cose.
Bellalì
rakk
