Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bvb:20-opus-23618
URL: http://www.opus-bayern.de/uni-wuerzburg/volltexte/2007/2361/

Neural Synchronization and Cryptography

Neuronale Synchronisation und Kryptographie

Ruttor, Andreas

---

Freie Schlagwörter (Deutsch):		Neuronale Netze , Synchronisation , Kryptographie , Statistische Physik , Nichtlineare Dynamik
Freie Schlagwörter (Englisch):		neural networks , synchronization , cryptography , statistical physics , nonlinear dynamics
PACS - Klassifikation:		05.40.Fb , 05.45.Xt , 89.70.+c , 87.18.Sn , 84.35.+i
Institut:		Institut für Theoretische Physik und Astrophysik
Fakultät:		Fakultät für Physik und Astronomie
DDC-Sachgruppe:		Physik
Dokumentart:		Dissertation
Erstgutachter:		Kinzel, Wolfgang (Prof. Dr.)
Sprache:		Englisch
Tag der mündlichen Prüfung:		18.05.2007
Erstellungsjahr:		2006
Publikationsdatum:		23.07.2007
Kurzfassung auf Englisch:		Neural networks can synchronize by learning from each other. For that purpose they receive common inputs and exchange their outputs. Adjusting discrete weights according to a suitable learning rule then leads to full synchronization in a finite number of steps. It is also possible to train additional neural networks by using the inputs and outputs generated during this process as examples. Several algorithms for both tasks are presented and analyzed. In the case of Tree Parity Machines the dynamics of both processes is driven by attractive and repulsive stochastic forces. Thus it can be described well by models based on random walks, which represent either the weights themselves or order parameters of their distribution. However, synchronization is much faster than learning. This effect is caused by different frequencies of attractive and repulsive steps, as only neural networks interacting with each other are able to skip unsuitable inputs. Scaling laws for the number of steps needed for full synchronization and successful learning are derived using analytical models. They indicate that the difference between both processes can be controlled by changing the synaptic depth. In the case of bidirectional interaction the synchronization time increases proportional to the square of this parameter, but it grows exponentially, if information is transmitted in one direction only. Because of this effect neural synchronization can be used to construct a cryptographic key-exchange protocol. Here the partners benefit from mutual interaction, so that a passive attacker is usually unable to learn the generated key in time. The success probabilities of different attack methods are determined by numerical simulations and scaling laws are derived from the data. If the synaptic depth is increased, the complexity of a successful attack grows exponentially, but there is only a polynomial increase of the effort needed to generate a key. Therefore the partners can reach any desired level of security by choosing suitable parameters. In addition, the entropy of the weight distribution is used to determine the effective number of keys, which are generated in different runs of the key-exchange protocol using the same sequence of input vectors. If the common random inputs are replaced with queries, synchronization is possible, too. However, the partners have more control over the difficulty of the key exchange and the attacks. Therefore they can improve the security without increasing the average synchronization time.
Kurzfassung auf Deutsch:		Neuronale Netze, die die gleichen Eingaben erhalten und ihre Ausgaben austauschen, können voneinander lernen und auf diese Weise synchronisieren. Wenn diskrete Gewichte und eine geeignete Lernregel verwendet werden, kommt es in endlich vielen Schritten zur vollständigen Synchronisation. Mit den dabei erzeugten Beispielen lassen sich weitere neuronale Netze trainieren. Es werden mehrere Algorithmen für beide Aufgaben vorgestellt und untersucht. Attraktive und repulsive Zufallskräfte treiben bei Tree Parity Machines sowohl den Synchronisationsvorgang als auch die Lernprozesse an, so dass sich alle Abläufe gut durch Random-Walk-Modelle beschreiben lassen. Dabei sind die Random Walks entweder die Gewichte selbst oder Ordnungsparameter ihrer Verteilung. Allerdings sind miteinander wechselwirkende neuronale Netze in der Lage, ungeeignete Eingaben zu überspringen und so repulsive Schritte teilweise zu vermeiden. Deshalb können Tree Parity Machines schneller synchronisieren als lernen. Aus analytischen Modellen abgeleitete Skalengesetze zeigen, dass der Unterschied zwischen beiden Vorgängen von der synaptischen Tiefe abhängt. Wenn die beiden neuronalen Netze sich gegenseitig beeinflussen können, steigt die Synchronisationszeit nur proportional zu diesem Parameter an; sie wächst jedoch exponentiell, sobald die Informationen nur in eine Richtung fließen. Deswegen lässt sich mittels neuronaler Synchronisation ein kryptographisches Schlüsselaustauschprotokoll realisieren. Da die Partner sich gegenseitig beeinflussen, der Angreifer diese Möglichkeit aber nicht hat, gelingt es ihm meistens nicht, den erzeugten Schlüssel rechtzeitig zu finden. Die Erfolgswahrscheinlichkeiten der verschiedenen Angriffe werden mittels numerischer Simulationen bestimmt. Die dabei gefundenen Skalengesetze zeigen, dass die Komplexität eines erfolgreichen Angriffs exponentiell mit der synaptischen Tiefe ansteigt, aber der Aufwand für den Schlüsselaustausch selbst nur polynomial anwächst. Somit können die Partner jedes beliebige Sicherheitsniveau durch geeignete Wahl der Parameter erreichen. Außerdem wird die effektive Zahl der Schlüssel berechnet, die das Schlüsselaustauschprotokoll bei vorgegebener Zeitreihe der Eingaben erzeugen kann. Der neuronale Schlüsselaustausch funktioniert auch dann, wenn die Zufallseingaben durch Queries ersetzt werden. Jedoch haben die Partner in diesem Fall mehr Kontrolle über die Komplexität der Synchronisation und der Angriffe. Deshalb gelingt es, die Sicherheit zu verbessern, ohne den Aufwand zu erhöhen.