Neural Network-Based Cryptographic System

Studying the Performance of Neural Networks on Problems Related to Cryptography

Studying the Performance of Neural Networks on Problems Related to Cryptography

Introduction

Public key cryptography has motivated a number of hard and complex mathematical problems. These problems are related to computational algebra (?nite ?elds, ?nite groups, ring theory), computational number theory, theory of probability, logic, Diophantine's complexity, and algebraic geometry among others. The ef?ciency of the contemporary cryptosystems relies on the assumption that these problems are computationally intractable, meaning that their computation cannot be completed in polynomial time. Such problems are factorization, the discrete logarithm and the knapsack problem (Boutsinas, 2001, pp.1-38).

Numerous techniques have been proposed to tackle these problems including algebraic and number theoretic methods, software oriented methods and interpolation techniques. In this paper we consider the arti?cial neural networks (ANNs) approach and study their performance on problems from the ?eld of cryptography. Speci?cally, we study the approximation of three problems (Canetti, 1999, pp.799-812). The ?rst problem under consideration is the discrete logarithm problem (DLP), and is de?ned as follows: compute the smallest integer x > 0 satisfying the relation gx = h, where g, h are elements of a ?nite cyclic group generated by g. The security of various public-key and private-key cryptosystems such as the Dif?e-Hellman exchange protocol, the El Gamal public key cryptosystem, as well as, the El Gamal digital signature scheme, is based on the assumption that DLP is computationally intractable. In the case of a ?nite ?eld of prime order p a primitive element a modulo p is ?xed. We assume that u is the smallest nonnegative integer with au = y (mod p). Then u is called the index, or the discrete logarithm of y.

The second problem at hand is the Dif?e-Hellman key-exchange protocol problem (DHP). Let G be a ?nite cyclic group of order? ¦ ????G??¦ = m. Consider g a generator of G; x, y integers satisfying 0=x, y =m - 1 be the private keys of two users, and u, ? ? G, with u=gx , v =gy stand for the corresponding public keys. Then the problem amounts to computing g xy from u and v, where gxy is the symmetric key for secret communication between the two users. Consider the special case of the DHP, where u = ?.

The term Dif?e-Hellman mapping refers to the function: gx ? gx2. The de?nition of the Dif?e-Hellman mapping problem (DHMP) follows naturally from the previous de?nition of DHP. Finally, we study the factorization problem related to the RSA cryptosystem. For the RSA cryptosystem to be secure, the factorization of N =p · q must be computationally intractable (Coppersmith, 2000, pp.339-360). The cryptanalyst has to compute p or q from N. To achieve this it is suf?cient to obtain Ø(N) from N, or equivalently to factorize N, since Ø(N) = (p - 1)·(q - 1).

Approximation Through Neural Networks

ANNs have been motivated by biological systems and more speci?cally by the human ...