Algoritmo Blum-Goldwasser
Template:Da tradurre L'algoritmo Blum-Goldwasser è un algoritmo di crittografia asimmetrica proposto da Manuel Blum e Shafi Goldwasser nel 1984. Si tratta di un algoritmo probabilistico semanticamente sicuro, e la dimensione del testo criptato aumenta di un fattore costante rispetto al testo in chiaro. Per criptare un messaggio, l'algoritmo utilizza come chiave uno stream di bit pseudo-casuali generati con l'algoritmo Blum Blum Shub (BBS). Per decrittare un messaggio si utilizza la chiave privata per trovare il seme iniziale con cui sono stati generati i bit della chiave.
Blum-Glodwasser è semanticamente sicuro, assumendo che la fattorizzazione di numeri interi sia un problema intrattabile; in particolare si considera il caso in cui dove sono numeri primi molto grandi. Quest'algoritmo ha diversi vantaggi su altri algoritmi di crittografia probabilistici. Primo, la sua sicurezza è basata solamente sul problema della fattorizzazione, senza bisogno di altre assunzioni (come l'intrattibilità del problema del residuo quadratico o dell'assunzione RSA). In secondo luogo, è molto più efficiente in termini di occupazione di spazio, perché introduce un aumento costante della dimensione rispetto ai dati in chiaro. È anche piuttosto efficiente in termini computazionali, perché non sfigura a confronto con altri algoritmi quali RSA. Tuttavia, è fortemente vulnerabile ad un attacco di tipo chosen cipher-text.
Poiché per criptare si utilizza un algoritmo probabilistico, uno stesso testo in chiaro può produrre risultati molto diversi ogni volta che viene criptato. Questo porta dei vantaggi significativi, poiché impedisce ad un avversario di riconoscere messaggi intercettati confrontandoli con altri intercettati precedentemente.