Research

APN functions in Coding and Cryptography

Almost Perfect Nonlinear functions are Boolean functions that are candidates for use in S-boxes in certain cryptographic systems. They have optimal resistance to differential cryptanalysis. Researchers at the Claude Shannon Institute study constructions of new APN functions, the nonlinearity of APN functions, and properties of known APN functions. Functions which are close to being APN, in a certain sense, are also studied, as are APN functions on the integers modulo n. The properties of APN functions are often studied using the related error-correcting codes, where the study goes back much further.

Costas Arrays and Finite Fields

Costas arrays are used in radar, sonar, and frequency hopping multiaccess communications systems. Such codes also have application in watermarking and optical communication. Shannon Institute researchers have made the following advances in the field of Costas arrays: (1) Determined a new method for finding Costas arrays of large order (for example, N=29, 36, 43). These are the first 'new' Costas arrays to be determined in recent years, excepting those found by exhaustive search for of size less than 26. (2) Enumerated the number of Costas arrays of size 27 on a grid computer. (3) Established regularity properties of Golomb Costas arrays using the theory of quadratic forms. (4) Proved that the regularity properties of Welch Costas arrays are described by the class number, a classical and deep concept in number theory. This result links a very pure area of mathematics with a seemingly unrelated engineering application.

Elliptic/Hyperelliptic Curve Cryptography

Cryptosystems based on elliptic and hyperelliptic curves have gained a lot of popularity in recent years. The main reason is that no fast algorithm for computing discrete logarithms on small genus curves is currently available, except in very special cases. Therefore curve-based cryptosystems require much smaller key sizes than RSA to attain the same security level. This makes them particularly attractive for implementations on memory-restricted devices like smart cards and in high-security applications. The researchers in the Claude Shannon Institute study the theory, algorithms and hardware implementations of cutting edge elliptic curve cryptography.

Groebner Bases in Coding/List Decoding

The search for good practical codes has occupied a major portion of the effort of coding theorist over the past 50 years. Such codes should not only have high minimum distance but also should have easily implemented decoding algorithms. Among the most popular classes of block codes are 
the BCH, Reed-Solomon (RS), cyclic, quasicyclic, and in more recent years Algebraic Geometry (AG) codes and codes over Galois rings have made an appearance. Although there are many classes of codes with better theoretical decoding properties, for reasons of practicality the market 
remains dominated by BCH and RS codes. The search for theoretically better codes, for which efficient decoding algorithms can be found, leads to further consideration of the classes of cyclic, quasicyclic codes and AG codes. This is the main problem addressed in this work package. 


In particular, AG codes are particularly appropriate in applications where the input data has bit error rate of the order of 10^(-3) , and where data of very high reliability is desired by the user (bit error rate below 10^(-15) ). One possible application is optical communication of data. The channel here is relatively good, but end users desire essentially perfect data. In contrast to LDPC codes, which exhibit an error floor, AG codes have very steep performance curves, making them very suitable for the applications mentioned. 


Gröbner bases have been recognized as the most powerful computational techniques in commutative algebra and its applications. They have been used in algebraic coding theory in a number of ways in the effort to solve our main problem In this project we continue to use the tools of modern computational algebra including Gröbner bases to advance the search for good codes.

Information Security

The information security landscape has many levels, including cryptographic aspects, technical aspects, legal aspects and management. Topics of research include network security, software development and key agreement protocols.

LDPC Codes

LDPC codes have been attracting attention over the recent decade. Originally introduced in the seminal work of Gallager in the sixties, they were (re)discovered soon after the famous TURBO codes. Among several developments, the workgroup at the Claude Shannon Institute has come up with a family of LDPC codes that are derived from what are called 0-1-geometries. Testing the performance of several members of this family has led to results suggesting that these codes might be useful in various applications like general communications as well as data storage.

Network Coding

Network information flow concerns the transmission of data from a number
of source nodes to a collection of sink nodes via a network of point-to-point communication channels linked by intermediate nodes. Each channel has a specified capacity and it is desirable to obtain a flow of information with throughput as close as possible to the capacity of the network. The standard method applied is known as store and forward, whereby intermediate nodes store and forward a copy of incoming data to some adjacent nodes. The publication of the seminal paper showed that allowing coding or mixing of data to occur at the nodes, rather than simply routing would result in improved network throughput for many networks. This is most easily demonstrated in the simple butterfly network. Network coding has since generated much interest from experts in information theory, coding theory, complexity theory, cryptography and wireless communications. It is an extremely general theory and can be applied to any communications network. Efficient network coding techniques are most sought where there is a need to optimize the thoughput of a network, where there is a need to correct network errors, where power resources are scare and where receivers are mobile. Moreover, network security is given a completely different perspective in the presence of coding. It also offers a new paradigm when resources are shared: the Microsoft Avalanche distribution system offers several advantages over P2P.
Researchers at the Claude Shannon Institute study bounds on network codes, the random network coding model, and minimizing noiseless broadcasts from a server where each receiver has side information.

Space-Time Codes

It is well known that multiple antenna wireless communication can potentially achieve a very high data rate. One way to achieve this is via space-time block codes. The basic design criteria for space-time block codes can be met using codes constructed using algebraic number theory. Researchers at the Claude Shannon Institute have studied constructions of multi-block space-time codes, and constructions of space-time codes using quadratic forms.

back to research mainpage