On 21-05-16 13:06, brno wrote:
>
> On 20-05-16 22:55, Rachele Grasshopper wrote:
>> 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.
> altro giocattolino utile per studiare
> https://github.com/corbett/QuantumComputing
>
> qui c'e' una ML che tratta nei dettagli il tema (comprendo si o no il
> 30% di quello che dicono, ma per chi ne sa di piu' puo' essere molto
> utile :) https://groups.google.com/forum/#!forum/boring-crypto
ops, sbagliato link
https://groups.google.com/forum/#!forum/cryptanalytic-algorithms
