Re: [Hackmeeting] [talk proposal] crittografia post-quantist…

Delete this message

Reply to this message
Autor: brno
Data:  
A: hackmeeting
Assumpte: Re: [Hackmeeting] [talk proposal] crittografia post-quantistica


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

ciao!