1. Importance of the project

Traditionally, applications of mathematics to science and engineering, or industry came mainly from analysis and hence those subjects like partial differential equations and numerical analysis were regarded as the main stream of applied mathematics. Recently, however, applications of mathematics come from all areas of mathematics like algebra and geometry. Especially, applications of algebra is getting spotlights thanks to the development of computer science and engineering.

As algebra, number theory and combinatorics take central roles in coding theory and cryptology, which are the core technologies of electronic communication and internet commercial transactions, resp., the new perception is due for Algebra that used to be regarded as the pure among pure mathematics. Applied Algebra now not only provides sound theoretic background to computer mathematics, coding theory and cryptology but also develops cutting edge technologies in coding and cryptosystem directly. And in turn, it enriches algebra. A few mathematicians in US and Europe has set up companies earning royalties for new technologies in coding and cryptosystem they invented.

But it's just a beginning. The market size of electronic communication and internet commercial transactions is being anticipated to explode, we have to start preparing for the increasing demand of qualified technicians and high level technologies in coding and cryptosystem. Since the areas of algebra, number theory and combinatorics related to coding and cryptosystem are relatively new, we believe that we can quickly catch up and even get better than the leading research groups of the world in these areas if we start now.

In this vein, courses on applied algebra are to be offered in both undergraduate and graduate programs in the new curriculum, which will be implemented in the restructuring process due to BK-21, and be naturally connected to research in coding and cryptosystem so that qualified researchers and technicians in the areas can be produced, which is very urgent at this time.

The team Applied Algebra and Cryptology will put emphasis on researches on number theory, group theory, and combinatorics. And then apply the results to coding theory and cryptology to develop useful technologies in coding and cryptosystem and to produce well qualified researchers that will be sought after by electronic communication and internet commercial transactions related industries. They will also be highly recruited for national security where cryptosystem plays a core role with no doubt.

2. Recent developments in this area

a. Industrial side

Since Shannon published his celebrated paper "Mathematical theory of communications" in 1948, coding theory became the center of electronic communication technology. Channel coding problem and sampling problems have been investigated by many mathematicians. Especially, error correcting code has been the hottest subject of research in coding theory and technology. Since Hamming started a systematic research on codes correcting errors or noises that occur during transmission, various error correcting codes have been developed. The ideal error correcting code system, however, is yet to come a long way. We believe that our team is capable of competing with the leading group of the world in this area. A new and efficient error correcting code, if its superiority over existing such codes is proven, will earn a huge sum of money from royalty because such an error correcting code can be not only used in electronic communications but also in wide range of technologies like manufacturing like compact disks and smart cards.

Existing error correcting codes are Hamming-code, Golay-code, BCH-code (by Bose, Chaudhury, Hocqunghem), RS-code (by Reed and Solomon), RM-code (by Reed and Muller), Goppa-code and geometric Goppa-code, etc. Competitive researches to improve the efficiency of these codes are under way. One notable fact is that most of these error correcting codes are developed by mathematicians.

On the other hand, the market size of internet commercial transactions is expected to reach several thousand billion dollars worldwide within 10-20 years and eventually replaces most of commercial transactions. Therefore, the demand for various cryptosystems, which used to be useful only in secret communications of military or industrial informations, will increase explosively. Cryptology has been studied in a new dimension since Diffie and Hellman suggested a public key cryptosystem. Cryptology then came into the realm of mathematics after Rivest, Shamir and Adleman invented RSA public key cryptosystem. Since then, various public key cryptosystems have been developed and suggested by using heaps of one-way functions investigated by mathematicians for thousands of years and have been attacked by using all kinds of mathematical theories.

So far, a few companies have been founded selling cryptosystems. They are RSA mentioned above, Certicom by Vanstone, Menezes and Koblitz, NTRU by Hoftstein and Silvermann, and NFC by Buchmann et al. But it is still a beginning stage. Most of these people are again mathematicians, which is natural if one understands how cryptosystems work.

b. Academic side

The core of coding theory is number theory, group theory and combinatorics. Recently, algebraic geometry is applied to develop codes. Is is well known that Hamming-code, Golay-code, BCH-code, RS-code, RM-code, Goppa-code and geometric Goppa-code, etc., are all stem from rich and deep researches on quadratic form theory, modular form theory, finite groups and representation theory, graph theory, discrete algebra, etc. It is not possible to develop new cutting edge coding technologies without perfect understanding and thorough investigation on rich and various algebraic structures. And these researches can be directly connected to new coding technologies. Research on lattice theory is particularly stressed thesedays concerning coding theory and technologies.

In internet commercial transactions, cryptosystems are required to own various functions like authentication, signature, key exchange, and so on, beside the traditional function of security in communicating secret messages. In advanced countries, a huge sum of money is invested in developing public key cryptosystems perfectly equipped with these functions.

The most popular cryptosystem approved as a standard system by United States is RSA public key cryptosystem, which is invented by Rivest, Shamir and Adleman. This system uses theorems of Fermat and Euler that enable us to compute powers of an integer modulo a positive integer without difficulty. This system is based on the fact that primality test is easy but prime factorization is much harder. It is a reliable cryptosystem enduring all kinds of attacks for more than 20 years.

The difficulty of discrete logarithm, in which one should find the number from its power, is used in other cryptosystems. One of such is El Gamal public key cryptosystem. This is based on the fact that powering of an element in a given finite multiplicative group is easy but discrete logarithm is very difficult.

Recently, the fact that every elliptic curve defined over a finite field has a group structure is used in constructing a new commercialized public key cryptosystem, called the elliptic curve cryptosystem.

Beside the public key cryptosystems mentioned above, public key cryptosystems using bases of lattices, graph theory, free generators of the special linear group, etc., are suggested and their security are investigated.

Each of these public key cryptosystems has good and bad points of its own. But the most important point is the security. No cryptosystem can be commercialized before the security of a proposed system is approved. So, computational mathematics to examine complexity and efficiency of algorithm has been emerged as an important research subject in connection with investigation of cryptosystem's security.

The realm of applied algebra is getting wider to various areas of information science such as hash functions for data storage and authentication, computer logic and algorithm for improving computing power, and model theory, etc.

3. Content of project

a. Research and development in coding theory and technology

We will perform research to improve existing codes by analysing their merits and demerits via lattice theoretic approach. In order to investigate Hamming-code, Golay-code related to Leech lattice, BCH-code, RS-code, RM-code, Goppa-code, QR-code, perfect code, cyclic code, etc., we will have to perform an extensive research on lattice theory, quadratic form theory, modular form theory, finite group and representation theory, graph theory, discrete algebra, etc., and then again turn to developing new practical coding technologies.

a-1. Error correcting code system

We will focus our interests on error correcting codes for the time being. A good error correcting code should correct more errors while it still is practical in usage. Better error correcting ability without being practical in time and cost is not acceptable, nor is the opposite case. The number of digits that can be corrected in an error correcting code system is known to be less than one half of the system's Hamming distance (the minimum distance between codewords). Concerning this, Hamming weight (the number of nonzero digits) of a codeword, Hamming weight enumerator that counts the number of codewords of same Hamming weight, and the number of codewords of minimal Hamming weight and so on are main objects of investigation. Theses problems are naturally connected to the minimum distance between lattice points (or vectors), theta-series that counts the number of lattice points of same distance from the origin, and the number of minimal vectors in a given lattice, and so on. Furthermore, these are closely related to sphere packing problem (in arbitrary dimension), which was proposed by Kepler (in 3-dimensional case). In this way, research in error correcting code system has deep connection to a long standing mysterious problem in the history of mathematics. For example, the densest sphere packing is achieved via Leech lattice (the even unimodular lattice whose minimal vector is of length 4, the longest among 24 possible even unimodular lattices) in 24-dimensional case and from this lattice can be constructed the famous Golay-code, which amazingly is able to correct upto 3 errors.

a-2. Extremal lattices. cyclic codes, and nonlinear codes

The rank of even unimodular lattice is always a multiple of 8. Among even unimodular lattices, one whose minimal length is the largest is called an extremal lattice. It is known that a good error correcting code can be constructed from such an extremal lattice. Finding an extremal lattice, however, is known to be very difficult. We are planning to extend our research to these extremal lattices. We will also investigate cyclic codes such as BCH-code, RS-code and RM-code, and nonlinear codes as well.

b. Research and development in cryptology and cryptosystem

We are planning to study a public key cryptosystem, hash functions, zero knowledge interactive proof (ZKIP), and secrete sharing scheme, and so on. A cryptosystem for message transmission means a map from ordinary texts to coded texts. The idea of using arithmetic operations to construct such a map goes back to the days of Roman Empire. But until about 20 years ago or so, only elementary algebra and number theory were used in cryptography. Until the late 1970's, all cryptographic message was encrypted by what can be called a private key. As a result, any two users of such a cryptosystem who want to communicate secretly must exchange keys in a safe way.

The face of cryptography was totally altered when Diffie and Hellman invented an entirely new type of cryptography, called a public key cryptosystem in 1976. In a public key cryptosystem, a receiver makes encryption keys public. A message sender encrypts his plain text by using the keys and the receiver decrypts the received cipher text by using his secret decryption key designed in advance.

At the heart of this concept is the idea of using a one-way function for encryption. Speaking roughly, a one-to-one function f from X to Y is 'one-way' if it is easy to compute f(x) for any x in X but very hard to compute x from the value of f(x). The functions used for encryption belong to a special class of one-way functions that remain one-way only if the decryption key is kept secret. But with the decryption key, one can easily compute x from f(x). This is why such a on-way function is called a trapdoor function. This means that everyone can send a message to a given user using the same encryption key, which they can find easily from a public directory. There is no need for a sender to make any secret arrangement with the receiver in advance; indeed, the receiver needs never have had any prior contact with the sender at all.

It was the invention of public key cryptography that led to a dramatic expansion of the role of number theory, group theory and combinatorics in cryptography. The reason is that these areas of mathematics seems to provide the best sources of one-way functions. RSA public key cryptosystem - the first commercialized public key cryptosystem - uses number theory. A public key cryptosystem based on NP-complete Knapsack problem was also suggested. Since many one-way functions can be constructed from combinatorial NP-complete problems, many public key cryptosystems based on various combinatorial NP-complete problems are suggested and developed.

NP problems are the problems that can be solved by nondeterministic algorithms in polynomial time, and P (polynomial) problems are the problems that can be solved by deterministic algorithms in polynomial time. Obviously P is a subset of NP but it is not known whether NP is a subset of P, that is, P = NP. No one has been able to find a single problem that can be proven to be in NP but not in P.

But people found certain problems having additional properties that provide convincing evidence that P cannot be equal to NP. Those problems satisfy: If any of such problems can be solved in polynomial time on a deterministic machine, so can be all the problems in NP, which implies P = NP. This means that the collective failure of all researchers to find efficient algorithms for all of these problems might be viewed as a collective failure to prove P = NP. Such problems are said to be NP-complete. It turns out that a large number of interesting practical problems are NP-complete. Satisfiability problem is the first problem that was shown to be an NP-complete problem, and it was discovered by Cook in 1971. He proved that if satisfiability problem can be solved in polynomial time on a deterministic machine, then one can find a polynomial time solution for any other problem in NP. After that, more than a thousand problems have been shown to be NP-complete. Many graph theoretic problems such as Hamilton cycle problem, traveling salesman problem, and longest path problem, etc., were turned out to be NP-complete. Also the graph isomorphic problem that can be used for zero knowledge is also an NP-complete problem.

b-1. Public key cryptosystem

Our team will analyze advantages and disadvantages of various public key cryptosystems using number theory and group theory, develop various attacking skills against those cryptosystems, and thereby improve them. RSA public key cryptosystem based on easy primality test and difficult prime factorization (not known yet whether it is NP or not), El Gamal public key cryptosystem based on difficult discrete logarithm in finite cyclic group, ECC based on difficult discrete logarithm in an elliptic curve over a finite field that possesses a quite complicate group structure, are our target. We are planning to analyze the underneath principles of these cryptosystems and to improve them to be securer and more practical cryptosystems.

Beside the public key cryptosystems discussed above, there are other public key cryptosystems that are under consideration. For examples, lattice reduction public key cryptosystem based on LLL-algorithm and special properties of a basis with big orthodefect (relatively close to an orthogonal basis), SL(2,Z) public key cryptosystem using free generators S and T of SL(2,Z), NF public key cryptosystem based on discrete logarithm in ideal class groups of number fields, NTRU public key cryptosystem using multiplicative structure and norm of a truncated polynomial ring, and so on. We will work on security problem to remedy their weak points and eventually to develop new public key cryptosystems.

Each of these public key cryptosystems has good and bad points of its own. But the most important point is the security. No cryptosystem can be commercialized before the security of a proposed system is approved. So, we will also work on computational mathematics to examine complexity and efficiency of algorithm that has been emerged as an important subject of research in connection with investigation of cryptosystem's security.

As was discussed above, Knapsack problem is NP-complete. But the public key cryptosystem based on Knapsack problem is shown to be unsecure by Shamir. Furthermore, Brassard showed that NP-complete problems satisfying certain conditions could not be safe in designing public key cryptosystems. In early 1990's though, Koblitz and Fellows proposed a public key cryptosystem based on an NP-complete problem that does not satisfy Brassard's conditions, which implies that Brassard's theorem cannot be applied to their cryptosystem. After that they proposed more public key cryptosystems based on certain general combinatorial NP-complete problems. Thanks to their effort, researches on public key cryptosystems based on combinatorial NP-complete problems seem to be rekindled.

In this vein, we are planning to study Koblitz and Fellow's proposal, and especially to work on graph theory to develop public key cryptosystems based on graph theory related NP-complete problems. A graph is called a cubic graph if the degree of each vertex is 3. It is known that finding a perfect dominating set (PDS) of a cubic graph is an NP-complete problem. In general, if the degree of each vertex of a graph is d, where d is bigger than or equal to 3, then it is proved by Kratochvil in 1991 that finding a PDS of the graph is an NP-complete problem. Notice that the concept of a perfect dominating set is similar to that of perfect code in coding theory.

One can construct a public key cryptosystem based on an NP-complete problem such as perfect dominating functions (PDF) and Polly cracker cryptosystem suggested by Koblitz and Fellows. For example, one can use a cubic graph and its K4-covering to make a complex graph of which perfect minus dominating function (PMDF) is hard to find, and then use Polly cracker cryptosystem to make a public key cryptosystem. The essential part of a public key cryptosystem based on PDF and Polly cracker cryptosystem is construction of a complex graph whose PMDF is hard to find by using a cubic graph and its K4-covering, on which we are planning to work. We will also work on improving practicality and security of such cryptosystems.

Most of the number theory based cryptosystems (or message transmission) are deterministic, in the sense that a given plain text will always be encrypted into the same cipher text by anyone. However, deterministic encryption has two disadvantages: First, if an eavesdropper knows that the plain text message belongs to a small set (for example, the message is either 'yes' or 'no'), then she can simply encrypt all possibilities in order to determine what the secret message corresponds to; Second, it seems to be very difficult to prove anything about the security of a cryptosystem if the encryption is deterministic. For these reasons, probabilistic encryption was introduced in early 1980's. In a probabilistic public key cryptosystem, a cipher text does not necessarily determined uniquely from a plain text. The public key cryptosystem based on a combinatorial NP-complete problem and Polly cracker cryptosystem, we mentioned earlier as one of our research subjects, for example, is a probabilistic public key cryptosystem.

b-2. Optional features of cryptosystems

In future research in cryptosystem, it is important to develop optional functions to meet various purpose of cryptosystems. We are planning to study the following optional features:

b-2-1. Authentication

There are two kinds of authentification: Firstly, verification that the message was sent by the person claimed; Secondly, verification that it hasn't been tampered with. One often uses hash functions, digital signatures, password and identification systems (proving that you have authorization to access to data or you are who you claim to be), and non-repudiation (guarding against one claiming not to have agreed to something that one really agreed to) for authentification.

b-2-2. Zero knowledge proof

This is the function that you convince someone that you have successfully solved a number-theoretic or combinatorial problem (for example, you have found the square root of an integer modulo a large unfactored integer, or you have a 3-colored map) without conveying any knowledge whatsoever of what the solution is.

b-2-3. Secrete sharing scheme

This is a very important function distributing secrets. For example, there is an occasion when it is dangerous for one person to possesse a whole secret information such as the password to launch missiles. In this case, it is safer to divide the password into smaller parts, say k smaller parts, and then to distribute these parts to users so that the password can be recovered when k parts are gathered but not when k-1 of them.

These functions are performed through various types of protocols. The word protocol simply means an ordered procedure in which people send messages. As listed above, a counter-plan against possible message interception by a third party, preventing document alteration and disguised user, authentification and signature, simultaneous signing on documents, etc., are important problems to be resolved in public key cryptosystems. In general, secure public key cryptosystems possess functions of identification of users and authentification. But since the security of these cryptosystems depends on secret keys, it is important to guarantee safe key distribution. One other important observation is that simultaneousness signing requires a new protocol that is different from protocols for authentification and signature.

Hash functions are used to check message authentication. Hash functions are widely related to such research subjects as RM-code and nonlinearity in coding theory, and random permutations, etc. in cryptology. Thus, to study hash functions, it is necessary to work together among the experts in those subjects. Hash function can be represented as a sum of a several Boolean coordinate functions. Therefore, it is important to study Boolean functions for better understanding of hash functions. Researches on Boolean functions is actively conducted by many mathematicians in connection with RM-code and finite geometry. The truth table of a Boolean function can be regarded as a binary code. Also, the nonlinearity of a Boolean function and Bent functions are related to covering radius and coset in coding theory. There are some implementations of hash functions using random permutations. Many proposed hash functions, however, still have some weakness, and we are planning to study hash functions from various directions such as coding theory, Boolean functions, random permutations, and finite geometry. Moreover, we will study hash functions based on group structures and lattice reduction, which suggested recently by Zemor and Ajtai et al.

Zero knowledge protocols are designed to arrow a prover to demonstrate knowledge of a secret while revealing no information whatsoever (beyond what the verifier was able to deduce prior to the protocol runs) to the verifier in conveying this demonstration of knowledge to others. There are also some protocols for authentications using zero knowledge proof. Fiat and Shamir's authentication system is one such. It is based on zero knowledge interactive proof (ZKIP) and identification concept of Shamir. Public key cryptosystems can be used to do ZKIP. For example, the proposed public key systems based on PMDF of a graph and Polly cracker are useful in doing ZKIP. Secret sharing schemes are multi-party protocols related to key establishment. The original motivation for secrete sharing was to safeguard cryptographic keys from loss. Then it is desirable to create backup copies but the greater the number of copies made, the greater the risk of security exposure. In short the idea of secret sharing scheme is to start with a secret, and divide it into pieces called shares which are distributed amongst users such that the pooled shares of specific subsets of users allow reconstruction of the original secret. It is interesting to make a secret sharing schemes applying coding theory, number theory, matroid theory, graph theory, etc.. We propose a study of secret sharing scheme and ZKIP protocols by studying graph theory, design theory, and number theory.

We also have research interests in various optional functions in public key cryptosystem such as confidential message transmission, key exchange that is useful when two people using the open airwaves want to agree upon a secret key for common use between the two in some private key cryptosystem, and coin flipping (or bit commitment) that is useful when you want to determine who plays first in an internet game, and so on.

c. Basic research in number theory, group theory and combinatorics

As we proposed above, our research plan is focusing on two main themes: coding theory and cryptology. But applied algebra covers vast part of computer and information sciences beyond coding and cryptography. And the success in researches on these subjects heavily depends upon basic researches on number theory, finite groups and representations, combinatorics, and other related mathematics. One good point of applied algebra is that the results from these basic researches can be directly connected to practical technologies.

Therefore, the key to success of our team is the basic research on the following subjects: theories of prime numbers, quadratic forms and modular forms, algebraic number fields, lattices, finite groups and representations, graphs, designs, combinatorics, and other related topics.

d. Cooperative research and education with industries and research institutes

We will offer courses on applied algebra in addition to the existing algebra and number theory courses in both undergraduate and graduate programs so that graduate students can start researches on applied algebra - coding theory, cryptology, and combinatorics from as early as their second year.

Furthermore, we are planning to attract (co-)project from KISA, ETRI, ADD, other research institutes for electronic communication and internet commercial market of banks and companies, computer and software industries so that graduate students (or even undergraduate students who are interested in research experience on applied algebra in working place) may join the project and if possible students can be dispatched to learn and work at those institutes or companies. We believe that in this way high level researchers can be brought up with experience in the working place.

The results of our research and development will be published in professional journals (of SCI level) in applied algebra, algebra, number theory, combinatorics, discrete mathematics, etc., or be applied for patents. We will also produce Ph. D.'s in applied algebra as well as in algebra.

Research and development in coding theory and cryptology is something we cannot postpone as the knowledge in information science and technology will emerge as the dominating value of society in the coming century. Not only the results we will achieve but also the qualified researchers we will produce will be of invaluable assets of our society in the era of computer and information to come.