Uno dei problemi della crittografia simmetrica è che ogni utente dovrebbe avere una chiave per ogni altro utente del sistema. In pratica se il sistema ha N utenti devono esserci N*(N-1)/2 chiavi per fare in modo che ogni utente possa comunicare in sicurezza con ogni altro utente.
È quindi evidente il problema logistico del sistema: se ogni chiave occupa 16 byte (128 bit), più altri (poniamo) 32 per identificare l'interlocutore, in un sistema con 1000 utenti OGNUNO dovrà memorizzare quasi 48KB di informazioni durante un "incontro faccia a faccia". All'aumentare del numero di partecipanti aumenta linearmente la quantità di dati da memorizzare. A rendere la cosa ancora più complessa ci si mette il fatto che si potrebbero desiderare chiavi a sicurezza diversa per utenti diversi e che le chiavi, di tanto in tanto, vanno cambiate.

I sistemi proposti nel tempo per ovviare a questi problemi sono stati numerosi e più o meno ingegnosi.

Il più banale è l'incontro faccia a faccia quando ci sia da stabilire una nuova chiave. Metodo costoso ma che permette una verifica periodica dell'identità dell'interlocutore.

Un altro metodo prevede dei "certificatori". In pratica si decide di riporre la propria fiducia in alcune entità che gestiranno le chiavi. Tutti gli utenti di un determinato gruppo, inizialmente, incontrano solo il proprio certificatore per stabilire una chiave. Se A vuole parlare con B, ma non ha una chiave, può chiedere al certificatore C (con cui può comunicare in modo sicuro) di inviare a B una chiave di sessione. In pratica B riceverà da C un pacchetto tipo:
E(Kbc, A|Kab|E(Kac, B|Kab))
Ovvero un pacchetto criptato con la chiave sicura stabilita tra B e C (per "certificare" la provenienza del messaggio) che indica chi è l'interlocutore (A), la chiave da usare (Kab) ed un "token" da passare ad A per fargli conoscere la chiave da usare (questo token può ovviamente essere generato solo da C, dato che è criptato con Kac, ed A potrà verificare l'identità di B appena decodificato il token). Un sistema di questo tipo (con parecchie modifiche) è quello usato da Kerberos. Ovviamente il sistema è molto ben scalabile creando un "albero" di certificatori. Ma più entità sono a conoscenza della chiave, più è facile che tale chiave entri in possesso di un attaccante.

Un altro modo ancora è l'uso della crittografia asimmetrica. In questo caso, se si opta per avere comunque dei certificatori (metodo usato per SSL, per esempio) questi comunque NON VENGONO a conoscenza della chiave segreta dell'utente, ma semplicemente firmano la sua chiave pubblica. Così un utente basta che abbia la chiave pubblica di un certificatore di cui si fida per poter verificare la chiave pubblica di ogni altro utente.
Leggermente più complesso il caso in cui si opti per una "web of trust" (come in PGP/GPG): non essendoci una struttura fissata ma una "rete" è necessario eseguire molte più verifiche su vari keyserver. Comunque, generalmente, è sufficiente avere le poche chiavi delle entità di cui ci si fida molto per poter verificare quasi ogni altra chiave.

E fin qui sono metodi "classici". E richiedono una fiducia implicita di cui spesso non ci si rende neppure conto: quella nel problema su cui si basa l'algoritmo usato. Se per esempio si usano certificati SSL con RSA, oltre che dell'entità che ha firmato il certificato stiamo decidendo di fidarci dell'assunto su cui RSA si basa, ovvero che fattorizzare grandi numeri sia un problema difficile. Se qualcuno mettesse a punto un calcolatore quantistico in grado di fattorizzare un numero di 1024 bit in poche ore invece che in secoli, i certificati basati su RSA sarebbero "carta straccia"! Sarebbe infatti possibile risalire alla chiave segreta di un qualunque certificatore e generare certificati con dati "a piacere".

Per ovviare a questo scenario sempre meno fantascientifico (i primi esemplari di computer quantistici sono in giro da più di 10 anni, anche se la potenza di calcolo è ancora bassissima) sono stati proposti altri metodi che non si basano su assunti non dimostrabili (come "la complessità della fattorizzazione è elevatissima") ma su problemi della teoria dell'informazione dimostrabilmente intrattabili.

Un primo esempio (di cui non ricordo al momento la fonte) prevede un canale pubblico ad elevatissima capacità (tipo una rete a 10Gbit) su cui è attivo un generatore di pacchetti casuali. Per stabilire in modo sicuro una chiave, Alice e Bob iniziano a memorizzare pacchetti con campionamenti casuali. Quando hanno riempito i loro buffer, sul canale sarà transitata una quantità X di pacchetti. Se A e B ne hanno memorizzato (poniamo) il 10%, ne avranno in comune grosso modo l'1%. Questo 1% possono usarlo come chiave (direttamente o indirettamente). L'assunto è che Eve non può memorizzare tutto il flusso, ma al più una determinata percentuale. Anche se questa percentuale è alta, non avrà comunque la certezza di aver intercettato quell'1% che Alice e Bob hanno in comune. Se poi si aggiunge che le percentuali indicate sono volutamente esagerate (magari Alice e Bob hanno la possibilità di memorizzare lo 0,01% dei messaggi ed Eve può arrivare al 5%) chi è più bravo di me in calcolo delle probabilità può divertirsi a verificare che Eve non ha certo vita facile

Un altro sistema, proposto dal Prof. Ueli Maurer prevede una fonte remota di "rumore" (una stella o un satellite) da usare come generatore di numeri casuali. Le letture effettuate da Alice, Bob ed Eve saranno in gran parte correlate ma comunque affette da un certo errore. Non importa se Eve dispone di strumentazione molto migliore rispetto a quella utilizzata da Alice e Bob: avrà comunque un certo tasso di errore. Dopo aver ricevuto una certa quantità di dati, Alice e Bob possono verificare quali hanno in comune e, da questi, "distillare" una chiave segreta che Eve non potrà conoscere (questo lavoro di Maurer fornisce anche tutte le formule per calcolare le probabilità di successo di Eve).

Un ulteriore metodo si basa sulla differenza di velocità tra mutua sincronizzazione ed apprendimento delle reti neurali. È stato inizialmente studiato da I.Kanter-W.Kinzel-E.Kanter ed approfondito da Andreas Ruttor. Il metodo è molto facilmente implementabile e non richiede particolare potenza di calcolo (solo poche somme e sottrazioni). Si può variare L (la "profondità" delle sinapsi) come si varierebbe la lunghezza della chiave in alcuni algoritmi a chiave segreta. Ma aumentando L aumenta anche il numero di passi necessari alla sincronizzazione. Il vantaggio è che si possono generare stream lunghissimi di bit pseudo-casuali, oppure usare direttamente i pesi per derivare una chiave condivisa. Se si utilizza la "random walk rule" per aggiornare i pesi durante la sincronizzazione, il sistema risulta molto robusto e sicuro. Richiede comunque lo scambio di una discreta quantità di informazioni, ma si può ridurre di molto effettuando una prima sincronizzazione poco sicura ma veloce ed utilizzando poi la rete risultante come generatore di numeri pseudo-casuali locale per generare i pattern di training per la rete più sicura (quindi si trasmette solo il bit di uscita, risparmiando la trasmissione del vettore di input).