Neural synchronization and cryptography [Elektronische Ressource] / vorgelegt von Andreas Ruttor

Andreas Ruttor

Sujets

• Informatik

Informations

• Publié par: julius-maximilians-universitat_wurzburg
• Publié le: 01 janvier 2006
• Nombre de lectures: 27
• Langue: English

Extrait

Neural Synchronization
and Cryptography
Dissertation zur Erlangung des
naturwissenschaftlichen Doktorgrades
der Bayerischen Julius-Maximilians-Universitat Wurzburg
vorgelegt von
Andreas Ruttor
aus Wurzburg
Wurzburg 2006Eingereicht am 24.11.2006
bei der Fakultat fur Physik und Astronomie
1. Gutachter: Prof. Dr. W. Kinzel
2.hter: Prof. Dr. F. Assaad
der Dissertation.
1. Prufer: Prof. Dr. W. Kinzel
2. Prufer: Prof. Dr. F. Assaad
3. Prufer: Prof. Dr. P. Jakob
im Promotionskolloquium
Tag des Promotionskolloquiums: 18.05.2007
Doktorurkunde ausgehandigt am:Abstract
Neural networks can synchronize by learning from each other. For that pur-
pose they receive common inputs and exchange their outputs. Adjusting discrete
weights according to a suitable learning rule then leads to full synchronization in
a nite 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 e ect is caused by di eren t 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 syn-
chronization and successful learning are derived using analytical models. They
indicate that the di erence 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 expo-
nentially, if information is transmitted in one direction only.
Because of this e ect neural synchronization can be used to construct a cryp-
tographic key-exchange protocol. Here the partners bene t from mutual inter-
action, so that a passive attacker is usually unable to learn the generated key
in time. The success probabilities of di eren t attack methods are determined by
numerical simulations and scaling laws are derived from the data. If the synap-
tic depth is increased, the complexity of a successful attack grows exponentially,
but there is only a polynomial increase of the e ort needed to generate a key.
Therefore the partners can reach any desired level of security by choosing suit-
able parameters. In addition, the entropy of the weight distribution is used to
determine the e ectiv e number of keys, which are generated in di eren t 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 di cult y of the
key exchange and the attacks. Therefore they can improve the security without
increasing the average synchronization time.
3Zusammenfassung
Neuronale Netze, die die gleichen Eingaben erhalten und ihre Ausgaben austau-
schen, konnen voneinander lernen und auf diese Weise synchronisieren. Wenn
diskrete Gewichte und eine geeignete Lernregel verwendet werden, kommt es in
endlich vielen Schritten zur vollstandigen Synchronisation. Mit den dabei erzeug-
ten Beispielen lassen sich weitere neuronale Netze trainieren. Es werden mehrere
Algorithmen fur beide Aufgaben vorgestellt und untersucht.
Attraktive und repulsive Zufallskrafte treiben bei Tree Parity Machines so-
wohl den Synchronisationsvorgang als auch die Lernprozesse an, so dass sich
alle Ablaufe 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 uberspringen und so repulsive Schritte teilweise
zu vermeiden. Deshalb konnen Tree Parity Machines schneller synchronisieren als
lernen. Aus analytischen Modellen abgeleitete Skalengesetze zeigen, dass der Un-
terschied zwischen beiden Vorgangen von der synaptischen Tiefe abhangt. Wenn
die beiden neuronalen Netze sich gegenseitig beein ussen konnen, steigt die Syn-
chronisationszeit nur proportional zu diesem Parameter an; sie wachst jedoch
exponentiell, sobald die Informationen nur in eine Richtung ie en.
Deswegen lasst sich mittels neuronaler Synchronisation ein kryptographisches
Schlusselaustausc hprotokoll realisieren. Da die Partner sich gegenseitig beein us-
sen, der Angreifer diese Moglichkeit aber nicht hat, gelingt es ihm meistens nicht,
den erzeugten Schlussel rechtzeitig zu nden. Die Erfolgswahrscheinlichkeiten der
verschiedenen Angri e werden mittels numerischer Simulationen bestimmt. Die
dabei gefundenen Skalengesetze zeigen, dass die Komplexitat eines erfolgreichen
Angri s exponentiell mit der synaptischen Tiefe ansteigt, aber der Aufwand fur
den Schlusselaustausch selbst nur polynomial anwachst. Somit konnen die Partner
jedes beliebige Sicherheitsniveau durch geeignete Wahl der Parameter erreichen.
Au erdem wird die e ektiv e Zahl der Schlussel berechnet, die das Schlusselaus-
tauschprotokoll bei vorgegebener Zeitreihe der Eingaben erzeugen kann.
Der neuronale Schlusselaustausch funktioniert auch dann, wenn die Zufalls-
eingaben durch Queries ersetzt werden. Jedoch haben die Partner in diesem Fall
mehr Kontrolle uber die Komplexitat der Synchronisation und der Angri e. Des-
halb gelingt es, die Sicherheit zu verbessern, ohne den Aufwand zu erhohen.
5Contents
1 Introduction 9
2 Neural synchronization 13
2.1 Tree Parity Machines . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Learning rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Order parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Neural cryptography . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.1 Simple attack . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Geometric attack . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 Majority attack . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.4 Genetic attack . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Dynamics of the neural synchronization process 21
3.1 E ect of the learning rules . . . . . . . . . . . . . . . . . . . . . . 22
3.1.1 Distribution of the weights . . . . . . . . . . . . . . . . . . 22
3.1.2 Attractive and repulsive steps . . . . . . . . . . . . . . . . 25
3.2 Transition probabilities . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 Simple attack . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Synchronization . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.3 Geometric attack . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Dynamics of the weights . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.1 Waiting time for a re ection . . . . . . . . . . . . . . . . . 36
3.3.2 Synchronization of two random walks . . . . . . . . . . . . 38
3.3.3 Probability distribution . . . . . . . . . . . . . . . . . . . 39
3.3.4 Extreme order statistics . . . . . . . . . . . . . . . . . . . 42
3.4 Random walk of the overlap . . . . . . . . . . . . . . . . . . . . . 43
3.4.1 Synchronization on average . . . . . . . . . . . . . . . . . 44
3.4.2 Sync by uctuations . . . . . . . . . . . . . . . 46
3.5 Synchronization time . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5.1 Number of hidden units . . . . . . . . . . . . . . . . . . . 50
3.5.2 Learning rules . . . . . . . . . . . . . . . . . . . . . . . . . 52
78 CONTENTS
4 Security of neural cryptography 55
4.1 Success probability . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.1 Attacks using a single neural network . . . . . . . . . . . . 56
4.1.2 Genetic attack . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.1.3 Majority attack . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.4 Comparison of the attacks . . . . . . . . . . . . . . . . . . 65
4.2 Security by interaction . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.1 Version space . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.2 Mutual information . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Number of keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.1 Synchronization without interaction . . . . . . . . . . . . . 69
4.3.2 E ectiv e key length . . . . . . . . . . . . . . . . . . . . . . 72
4.4 Secret inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.4.1 Feedback mechanism . . . . . . . . . . . . . . . . . . . . . 76
4.4.2 Synchronization with feedback . . . . . . . . . . . . . . . . 77
4.4.3 Key exchange with authentication . . . . . . . . . . . . . . 80
5 Key exchange with queries 81
5.1 Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2 Synchronization time . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.3 Security against known attacks . . . . . . . . . . . . . . . . . . . 87
5.3.1 Dynamics of the overlap . . . . . . . . . . . . . . . . . . . 88
5.3.2 Success probability . . . . . . . . . . . . . . . . . . . . . . 89
5.3.3 Optimal local eld . . . .