chapter 1 artificial neural networks and neural cryptography [PDF]

CHAPTER 1

ARTIFICIAL NEURAL NETWORKS AND NEURAL CRYPTOGRAPHY

1.1

ORIGINS OF ARTIFICIAL NEURAL NETWORK An Artificial Neural Network (ANN) is a mathematical tool which was

originally inspired by the neuron structure in the brain. The brain consists of billions of interconnected neurons, which accounts for the complex features of human beings, such as memory, creativity, language and consciousness. Computational neural networks exploit the potentially vast and compelled processing power of such a parallel interconnected architecture. The brain is an organ that builds appropriate decisions based on analysis of information received from the environment (Kabundi 2002).

The

information input is communicated between different neurons each of which sends and receives signals from neighboring neurons. The basic element of the nervous system is the neuron as shown in Figure 1.1. The neuron is composed of the dendrites (which receive signals from other neurons), cell body or soma (which add impulses received from different dendrites) and axons which serve as channels through which signals are transmitted to other neurons. Each neuron is connected to others through synaptic junctions or synapses. The information is transmitted from one neuron to another through the synapses. The synapse can be viewed as a point of contact between two neurons.

2

Figure 1.1 A Structure of Biological Neuron The transmission on of signals from one neuron to another is the t activation of the receiving neuro ron effectively by means of electrical im mpulses.

The

activated neuron sendss iimpulses onto others. This process takes place p among a large number of neuro rons, it is simultaneously activated. This is leads to the creation of thoughts orr actions. The brain performs this task onn a continuous basis. The particular characteristic ch of the human is its ability to learn le from the past, which is facilitate ated by the complex system of sending and a receiving electrical impulses amon ong neurons. 1.2

HEAVISIDE AC ACTIVATION FUNCTION The transfer fun unction changes the network to execute tasks ta like the

human brain. The data ta is sent to the next neuron, if it is activate ted. In Neural Network (NN) models data d are carried from the input layer to the he output layer only after the input activity ac communicates a specific threshold old.

Past this

3

threshold, a further increase in input has negligible additional effect. Hence, there is a nonlinear relationship between input units and output units.

f(x) +1

0

x

Figure 1.2 Heaviside Activation Function The early versions of NN introduced by McCulloch and Pitts could only switch suddenly from on to off depending on whether the output function is equal to 1 or 0. n

Let

zj =

∑xα i

ij

and an activation function f is given by

i= 0

Yj = f(zj)

(1.1)

where, X0=1 is a bias unit, ‘z’ is the output of weighted sum of input units, f(z) = 1 if z > 0 and f(z) = 0 if z ≤ 0. The activation function f depends on a threshold value α0. The output function is turned on when f(z) > α0, otherwise, it is not activated (Kabundi 2002).

This activation function used by

McCulloch and Pitts is known as the Heaviside or UnitStep function. The Heaviside function is illustrated in Figure 1.2. 1.3

THE PERCEPTRON

The perceptron is the simplest type of neural network. It consists of a neuron with a step function and one output. Figure 1.3 given below is a

4

graphical representation of a perceptron with inputs x1, x2, ….., xn and output Y (Jonas Spjoberg 2005) 1 x1 x2 . . xn

w1 w2

∑

Y

wn

Figure 1.3 A perceptron classifier

The input vectors, weights vectors and bias are summed and then processed by a step function to yield the output. The UnitStep function is given by

Y(x, w, b) =UnitStep (w1 ⋅ x1 + w2 ⋅ x2 +...... + wn ⋅ xn + b)

(1.2)

where, {w1, w2, …., wn} are the weight vectors to the inputs and b is the bias weight. Also, the UnitStep function value is 0 for arguments less than 0 and 1 elsewhere. The output of Y is 0 or 1 depending on the value of the sum of the weight vectors.

1.4

AN OVERVIEW OF NEURAL CRYPTOGRAPHY

In the area of cryptography, people are interested in methods to transmit secret messages between two partners A and B through network (Kinzel 2002 and Kinzel and Kanter 2002). An opponent E who is able to listen to the communication should not be able to recover the secret message.

5

All cryptographic methods relied on secret key for encryption which was transmitted between A and B over a secret channel not accessible to any opponent and this happened before 1976. This type of common secret key can be used for example, as a seed for a random bit generator by which the bit sequence of the message is added.

Diffie and Hellman have shown in the year 1976 that a common secret key could be created over a public channel accessible to any opponent. It is not possible to calculate the discrete logarithm of sufficiently large numbers for a given limited computer power and this method is based on number theory. Recently, it has been shown how interacting neural networks can produce a common secret key by exchanging bits over a public channel and by learning from each other. The key exchange ranges within milliseconds for realistic channels and can be performed in parallel (or multiplexed) to encryption and the encrypted communication process.

1.5

A STRUCTURE OF TREE PARITY MACHINE

A Tree Parity Machine (TPM) is a tree structured graph of artificial neuron. The height of a TPM is two and leaves of a TPM are input units, intermediately nodes are hidden units and root is the output of a TPM.

The general structure of TPM is shown in Figure 1.4.

It consists of

‘K’ hidden units, each of them being a perceptron with an N-dimensional weight vector w (Ruttor et al 2004).

When ‘K’ hidden units receive an

N-dimensional input vector x, these units produce an output bit. All the input values are binary (Volkmer and Wallner 2005a)

6

x ij ∈ { − 1, + 1}

(1.3)

and the weights are discrete numbers within -L and +L (Mislovaty et al 2002, Kinzel and Kanter 2002a).

wij ∈ {−L, − L +1,...,0,..., L −1, L}

(1.4)

τ

σ w

x

Figure 1.4

A Structure of Tree Parity Machine with Feedback for K=3 and N=4

The index i = 1, 2,…., K and j = 1, 2,…., N denotes the ith hidden units of TPM and ‘j’ is the element of each vector respectively (Ruttor 2006 and Ruttor et al 2006). The output of the international representations layer is defined as the function sign of the scalar product of inputs and weights and it is given by

N  σ i = sign  ∑ wij • xij   j =1 

(1.5)

7

where, the equation (1.5) represents the transfer function (Klimov et al 2003) of the hidden units of a TPM. The total output of a TPM is given by the product (parity) of the hidden units.

K

τ =

∏

σi

(1.6)

i =1

where, the equation (1.6) represents the output vector of the output unit of a TPM.

As in other neural network, the weighted sum over the current input

values are used to determine the output of the hidden units. Therefore, the full state of each hidden neuron is given by its local field. The local field of the each hidden neuron is given by

hi =

1 N

N

∑

w ij • x ij

(1.7)

j =1

At the starting of the synchronization process, A and B initialize the weights of their neural networks randomly. This initial state is maintained in secret. In each time step t, K random input vectors xi are generated publicly and the partners calculate the outputs τA and τB of their TPMs.

After

communicating the output bits to each other, they update the weight vectors according to one of the following learning rules as given below

(a) Hebbian learning rule

wiA (t +1) = wiA (t) + xiτ AΘ(τ AσiA )Θ(τ Aτ B )

wiB (t +1) = wiB (t) + xiτ BΘ(τ BσiB )Θ(τ Aτ B )

(1.8)

8

(b) Random walk learning rule

wiA (t +1) = wiA (t ) + xi Θ(τ Aσ iA )Θ(τ Aτ B )

wiB (t +1) = wiB (t) + xiΘ(τ BσiB )Θ(τ Aτ B )

(1.9)

(c) Anti-Hebbian learning rule

wiA (t +1) = wiA (t) - τ AxiΘ(τ AσiA )Θ(τ Aτ B ) wiB (t +1) = wiB (t) - τ BxiΘ(τ BσiB )Θ(τ Aτ B )

(1.10)

After some time, synchronization time (tsync) of the partners have synchronized their TPMs, the process is stopped if both the weights are equal. Since, A and B can use the weight vector as a common secret key.

The process of synchronization by standard order parameters, which are also used for the analysis of online learning, is as follows (Ruttor et al 2005). These order parameters are given below

Qim =

1 m m Rm,n = 1 wm ⋅ wn wi ⋅ wi , i i i N N

(1.11)

where, the indices m, n ∈ {A, B, E} denote A’s, B’s or E’s TPM respectively. The level of synchronization between two corresponding hidden units is defined by the (normalized) overlap and it is given below

ρim, n = (1.12)

wim ⋅ win wim ⋅ wim win ⋅ win

=

Rim ,n Qim Qin

9

The overlap between two corresponding hidden units increases if the weights of both neural networks are updated in the same manner. Coordinated moves, which occur for identical σi, have an attractive effect.

Changing the weights in only one hidden unit decreases the overlap on average (Ruttor et al 2006). These repulsive steps can happen if the two output values are different (σi). The probability for this event is given by the well known generalization error of the perceptron and it is given by

εi =

1

π

arccos (ρ i )

(1.13)

which itself is a function of the overlap ρi between the hidden units.

For an

attacker E who simply trains a third TPM using the examples generated by A and B, repulsive steps occur with probability PrE = ε i , because E cannot determine the process of synchronization.

The partners A and B communicate with each other and are able to interact. If they disagree on the total output, there is at least one hidden unit with σ iA ≠ σ iB . The partners do not change the weights because an update would have a repulsive effect. So, A and B reduce the probability of repulsive steps in their hidden units. The probability of repulsive step for K=3 and identical generalization error ε i = ε is given by

2 (1 − ε )ε 2 Pr = (1 − ε )3 + 3 (1 − ε )ε 2 B

≤ ε = PrE

(1.14)

10

Therefore, the partners have a clear advantage over an attacker using only simple learning.

An attacker E may use the same learning rule as the two partners A and B.

Obviously, it will move its weights only if the output bits of the two

partners are identical. In this case, a repulsive step between E and A occurs with probability Pr = ε where, ε is the distance between the hidden units of E and A.

1.6 SYNCHRONIZATION WITH FEEDBACK

A TPM cannot learn the bit sequence generated by another TPM since the two input vectors are completely separated by the feedback mechanism. This also holds for synchronization by mutual learning. That is, the two networks cannot be attracted to an identical time dependent state with feedback. Hence, to achieve synchronization, an additional mechanism has to be introduced, which occasionally resets the two inputs to a common vector. This reset occurs whenever the system has produced R (reset of the input vectors) different output bits τ A (t ) ≠ τ B (t ) .

The two TPMs start with different random weights and same random inputs (Ruttor et al 2004 and Godhavari et al 2005). The feedback mechanism is defined as follows: 1. After each step ‘t’ the input is shifted, xi, j(t+1)=xi, j-1(t) for j ≥ 2. 2. If τA(t) = τB(t) then xi,1(t+1) = σi(t), else xi,1(t+1) are set to common values. 3. If τA(t) ≠ τB(t) for R steps, then all xiA, j (t +1) and xiB, j (t + 1) to common values.

are

reset

11

1.7

A SECRET KEY GENEARTION The synchronization of the two TPMs is accomplished in the following

steps: 1. Initialize random weight values. 2. Execute the following steps until the full synchronization is achieved 2.1 Generate random input vector x 2.2 Compute the output values of the hidden neurons 2.3 Compute the value of a output neuron 2.4 Compare the values of both TPMs: 2.4.1 If the outputs are different then go to step 2.1 2.4.2 It the outputs are same then one of the suitable learning rules is applied to the weight vectors. After the full synchronization is achieved (the weights of both A’s and B’s TPMs are same), A and B can use their weights as secret keys.

1.8

ATTACKS

The neural key-exchange protocol is an application of neural synchronization. Both partners A and B use a TPM with the same structure. The parameters K, L and N are public. randomly chosen weight vectors.

Each neural network starts with

These initial conditions are kept secret.

During the synchronization process the input vectors xi and the total outputs τ A and τ B are transmitted over the public channel. Therefore, each participant knows the internal representations (IRs) of the hidden units (σ 1 , σ 2 ,..., σ k ) of

12

her TPM. Keeping this information secret is the necessity for the security of the key-exchange protocol.

The main problem of the attacker E is that the internal representations (σ 1 , σ 2 ,..., σ k ) of A’s and B’s TPM are not known to the participant. As the

movement of the weights depends on σ i , it is important for a successful attack to guess the state of the hidden units correctly.

The four different types of attacks are given by (i) Simple Attack (ii) Geometric Attack (iii) Majority Attack and (iv) Genetic Attack

1.8.1 Simple Attack

An attacker E’s TPM has the same structure as A’ or B’s TPM and starts with random initial weights.

A simple attack (Ruttor 2006) E exactly trains a TPM with the examples consisting of input vectors xi and output bits τ A . These can be obtained easily by intercepting the messages communicated by the partners over the public channel. An attacker E’s TPM has the same structure as A’s and B’s TPM and starts with random initial weights.

In each time step, the attacker calculates the output of her TPM. Afterwards, E uses the same learning rule as the partners, but τ E is replaced by

τ A . Thus, the update of the weights is given below by one of the following equations. (i)

Hebbian learning rule wiE, j+ = g ( wiE, j + xi , jτ A Θ (σ iEτ A ) Θ (τ Aτ B ))

(1.15)

13

(ii)

Anti-Hebbian learning rule wiE, j+ = g ( wiE, j − xi , jτ A Θ (σ iEτ A ) Θ (τ Aτ B ))

(iii)

(1.16)

Random walk learning rule w iE, j+ = g ( w iE, j + x i , j Θ (σ iEτ A ) Θ (τ Aτ B ))

(1.17)

This is achieved by the function g(w) in each learning rule:

sgn(w)L g(w) =   w

for w > L otherwise

(1.18)

So, E uses the IR of hidden units (σ 1E , σ 2E ,..., σ KE ) of her TPM in order to estimate A’s, even if the total output is different. As τ A ≠ τ B indicates that there is at least one hidden unit with σ iA ≠ σ iE , this is certainly not the best algorithm available for an attacker.

1.8.2 Geometric Attack An attacker E takes the total network output τE and the hidden units of local fields using only one TPM.

The geometric attack performs better than

the simple attack, because E takes τ E and the local fields of her hidden units into account.

Similar to the simple attack, E tries to imitate B without being able to interact with A. As long as τ A = τ E , this can be done by just applying the same learning rule as the partners A and B. But in the case of τ A ≠ τ E , E cannot stop A’s update of the weights. Instead the attacker tries to correct the internal representation of own TPM using the local fields h1E , h2E ,..., hKE . These quantities can be used to determine the level of confidence associated with the output of

14

each hidden unit. As a low absolute value hiE

indicates high probability of

σ iA ≠ σ iE , the attacker changes the output σ iE of the hidden unit with minimal hiE and the total output τ E before applying the learning rule.

1.8.3 Majority Attack

An attacker E can improve her ability to predict the internal representation of A’s TPM. The attacker uses an ensemble of ‘M’ TPMs instead of a single TPM.

At the starting of the synchronization process the weight vectors of all attacking networks are selected randomly, so that their average overlap is zero.

Similar to other attacks, E does not change the weight in time steps with τ A ≠ τ B , because the partners skip these input vectors, too. But for τ A = τ B , an

update is necessary and the attacker calculates the output bits τ E ,m of her TPMs. If the output bit τ E ,m of the mth attacking network disagrees with τ A , E searches the hidden unit i with minimal absolute local field hiE , m . Then the output bits σ iE ,m and τ E ,m are inverted similarly to the geometric attack. Afterwards, the attacker counts the internal representations (σ 1E ,m ,..., σ KE ,m ) of her TPMs and chooses the most common one.

1.8.4 Genetic Attack

An attacker E starts with only one randomly initialized TPM, but she uses upto ‘M’ TPM. The genetic attack offers an alternative approach for the

15

opponent, which is not based on optimizing the prediction of the internal representation (IR), but on an evolutionary algorithm.

Whenever the partners update the weights because of τ A = τ B in a time step the following genetic algorithm is applied:

• As long as E has at most M/2K-1 TPMs, she determines all 2K-1 internal representations

(σ1E ,σ 2E ,...,σ KE )

which reproduce the output

τA.

Afterwards, these are used to update the weights in the attacking networks according to the learning rule. By doing so, E creates 2K-1 variants of each TPM in this mutation step.

• But if E already has more than M/2K-1 neural networks, only the fittest TPMs should be kept. This is achieved by discarding all networks which predicted less than U outputs τ A in the last V learning steps with

τ A = τ B successfully. A limit of U=10 and a history of V=20 are used as default values for the selection step. Additionally, E keeps at least 20 of her TPMs.

1.9

LITERATURE REVIEW

Ruttor et al. (2004) ‘Neural cryptography with feedback’, proved that the security of neural cryptography is improved by feedback in the training algorithm for hidden units. After synchronization, the system generates a pseudo-random bit sequence, which passed all test on random numbers.

Ruttor et al. (2005) ‘Neural cryptography with queries’, proved the keyexchange protocol by replacing random inputs with queries for hidden units.

16

This method obtains a new public parameter which can be adjusted to give optimal security. The success probability can be reduced without increasing the average synchronization.

Ruttor et al. (2006) ‘Genetic attack on neural cryptography’, proved that the success probability of all known methods only if the synaptic depth L is not too large. The attackers gain more by using the majority attack for higher values of L (synaptic depth of the network). But, both methods are unable to break the security of the neural key-exchange protocol in the limit L→∞.

Ruttor et al. (2006) ‘Dynamic of neural cryptography’, proved that the correlations restrict the number of different keys nkey, which can be generated by the neural key-exchange protocol using to certain input sequence and random initial weights. Both the configuration space nconf = (2L+1)KN and nkey grow exponentially with increasing number of weights per hidden unit. A large value of N guarantees the security of neural cryptography against bruteforce attacks.

Godhavari et al. (2005) ‘Cryptography using neural networks’, proved the synchronization by mutual learning can be applied to a secret key exchange protocol over a public channel. The generation of secret key over a public channel is used for encrypting and decrypting the given message using Data Encryption Standard (DES) algorithm which simulated and synthesized using Veri-log High Definition Language (VHDL).

Kanter et al. (2002) ‘Secure exchange of information by synchronization of neural networks’, proved the synchronized weights are used to construct an ephemeral key exchange protocol for a secure transmission of secret data. It is

17

shown that an opponent who knows the protocol and all details of any transmission of the data has no chance to decrypt the secret message, since tracking the weights is a hard problem compared to synchronization. The complexity of the generation of the secure channel is linear with the size of the network.

Puech et al. (2006) ’Crypto-compression of medical images by selective encryption of Fourier Discrete Cosine Transform (FDCT)’, presents a method of partial or selective encryption for Joint Photographic Expert Group (JPEG) images. It is based on encryption of some quantified FDCT coefficients in low and high frequencies. Also, they have combined compression and encryption in order to fully dissimulate the visual information of the image and to see the image in low quality resolution.

1.10

ORGANIZATION OF THE THESIS In chapter 2, neural cryptography of TPM of feedback mechanism with

hidden units, left-dynamic and right-dynamic hidden units is described. The analysis of the security, probability of successful attack of the majority flipping attacker with simulation results are shown.

Chapter 3 presents the interacting neural networks and cryptography for neural synchronization with feedback mechanism, lower layer spy unit, upper layer spy unit and definitions of the order parameters of TPMs are shown. The analysis of the effective number of keys against the brute-force attack with simulation results is presented. The most known attacks are genetic attacks, geometric attacks and majority attacks. These attacks are shown.

18

Chapter 4 focuses the neural synchronization with feedback mechanism of TPM with hidden units, left-dynamic hidden units and right-dynamic hidden units in hidden layer and only one output unit with left-dynamic and rightdynamic output unit in output layer. Also, lower layer spy unit and upper layer spy unit and order parameters of TPM are explained.

Telemedicine and

principles of Electronic Medical Records (EMR) are discussed. The Huffman compression technique is briefly explained.

The Rijndael algorithm is

presented. The security of Compressed and Encrypted Electronic Medical Record (CEEMR) is described.

Chapter 5 is organized as follows. A structure of Multi-Feedback Tree Parity Machine (MFTPM) is explained. The Multi-Feedback input units, the definition of learning rules, transition probabilities and synchronization with multi-feedback are discussed. Here, the generation of sequence bit is shown. The simulation results against geometric attack are described.

Chapter 6 describes the basic algorithm for neural synchronization with queries. Also, lower layer spy unit, upper layer spy unit for protecting CryptoCompressed and Encrypted Medical Images (CCEMI), definition of the order parameters and transition probabilities of TPM are explained. The advanced attacks of known local field and information about weight vectors are discussed.

The generation of queries is described. The crypto-compression

technique and Rijndael algorithm of medical images are presented.

The

security of CCEMI is discussed. Finally, chapter 7 provides the conclusions and future enhancements.