Historically, encryption has been considered the most important part of cryptography. So it is not surprising that there is a vast literature about public key encryption. It is important to note that, in practice, public key encryption is not usually used to encrypt documents. Instead, one uses public key encryption to securely send keys, and the data is encrypted using symmetric encryption.

It is beyond the scope of this book to discuss all known results on public key encryption, or even to sketch all known approaches to designing public key encryption schemes. The goal of this chapter is very modest. We simply aim to give some definitions and to provide two efficient encryption schemes (one secure in the random oracle model and one secure in the standard model). The encryption schemes in this chapter are all based on Elgamal encryption, the “textbook” version of which has already been discussed in Sections 20.3 and 20.4.

Finally, we emphasise that this chapter only discusses confidentiality and not simultaneous confidentiality and authentication. The reader is warned that naively combining signatures and encryption does not necessarily provide the expected security (see, for example, the discussion in Section 1.2.3 of Joux [283]).

CCA secure Elgamal encryption

Recall that security notions for public key encryption were given in Section 1.3.1. As we have seen, the textbook Elgamal encryption scheme does not have OWE-CCA security, since one can easily construct a related ciphertext whose decryption yields the original message.

In Section 4.1 a number of basic computational tasks for an algebraic group G were listed. Some of these topics have been discussed already, especially providing efficient group operations and compact representations for group elements. But some other topics (such as efficient exponentiation, generating random elements in G and hashing from or into G) require further attention. The goal of this chapter is to briefly give some details about these tasks for the algebraic groups of most interest in the book.

The main goal of the chapter is to discuss exponentiation and multi-exponentiation. These operations are crucial for efficient discrete logarithm cryptography and there are a number of techniques available for specific groups that give performance improvements.

It is beyond the scope of this book to present a recipe for the best possible exponentiation algorithm in a specific application. Instead, our focus is on explaining the mathematical ideas that are used. For an “implementors guide” in the case of elliptic curves we refer to Bernstein and Lange [51].

Let G be a group (written in multiplicative notation). Given g ∈ G and a ∈ ℕ we wish to compute ga. We assume in this chapter that a is a randomly chosen integer of size approximately the same as the order of g, and so a varies between executions of the exponentiation algorithm. If g does not change between executions of the algorithm then we call it a fixed base and otherwise it is a variable base.

Isogenies are a fundamental object of study in the theory of elliptic curves. The definition and basic properties were given in Sections 9.6 and 9.7. In particular, they are group homomorphisms.

Isogenies are used in algorithms for point counting on elliptic curves and for computing class polynomials for the complex multiplication (CM) method. They have applications to cryptanalysis of elliptic curve cryptosystems. They also have constructive applications: prevention of certain side-channel attacks; computing distortion maps for pairing-based cryptography; designing cryptographic hash functions; relating the discrete logarithm problem on elliptic curves with the same number of points. We do not have space to discuss all these applications.

The purpose of this chapter is to present algorithms to compute isogenies from an elliptic curve. The most important result is Vélu's formulae, which compute an isogeny given an elliptic curve and a kernel subgroup G. We also sketch the various ways to find an isogeny given an elliptic curve and the j-invariant of an elliptic curve ℓ-isogenous to E. Once these algorithms are in place we briefly sketch Kohel's results, the isogeny graph and some applications of isogenies. Due to lack of space we are unable to give proofs of most results.

Algorithms for computing isogenies on Jacobians of curves of genus 2 or more are much more complicated than in the elliptic case. Hence, we do not discuss them in this book.

Information Transmission Theorem

The reliable transmission of information-bearing signals over a noisy communication channel is at the heart of what we call communication. Information theory, founded by Claude E. Shannon in 1948 [Sha48], provides a mathematical framework for the theory of communication. It describes the fundamental limits to how efficiently one can encode information and still be able to recover it with negligible loss.

At its inception, the main role of information theory was to provide the engineering and scientific communities with a mathematical framework for the theory of communication by establishing the fundamental limits on the performance of various communication systems. Its birth was initiated with the publication of the works of Claude E. Shannon, who stated that it is possible to send information-bearing signals at a fixed code rate through a noisy communication channel with an arbitrarily small error probability as long as the code rate is below a certain fixed quantity that depends on the channel characteristics [Sha48]; he “baptized” this quantity with the name of channel capacity (see the discussion in Chapter 6). He further proclaimed that random sources – such as speech, music, or image signals – possess an irreducible complexity beyond which they cannot be compressed distortion-free. He called this complexity the source entropy (see the discussion in Chapter 5). He went on to assert that if a source has an entropy that is less than the capacity of a communication channel, then asymptotically error-free transmission of the source over the channel can be achieved.

Systems dedicated to the communication or storage of information are commonplace in everyday life. Generally speaking, a communication system is a system which sends information from one place to another. Examples include telephone networks, computer networks, audio/video broadcasting, etc. Storage systems, e.g. magnetic and optical disk drives, are systems for storage and later retrieval of information. In a sense, such systems may be regarded as communication systems which transmit information from now (the present) to then (the future). Whenever or wherever problems of information processing arise, there is a need to know how to compress the textual material and how to protect it against possible corruption. This book is to cover the fundamentals of information theory and coding theory, to solve the above main problems, and to give related examples in practice. The amount of background mathematics and electrical engineering is kept to a minimum. At most, simple results of calculus and probability theory are used here, and anything beyond that is developed as needed.

Information theory versus coding theory

Information theory is a branch of probability theory with extensive applications to communication systems. Like several other branches of mathematics, information theory has a physical origin. It was initiated by communication scientists who were studying the statistical structure of electrical communication equipment and was principally founded by Claude E. Shannon through the landmark contribution [Sha48] on the mathematical theory of communications. In this paper, Shannon developed the fundamental limits on data compression and reliable transmission over noisy channels.

The theory of error-correcting codes comes from the need to protect information from corruption during transmission or storage. Take your CD or DVD as an example. Usually, you might convert your music into MP3 files for storage. The reason for such a conversion is that MP3 files are more compact and take less storage space, i.e. they use fewer binary digits (bits) compared with the original format on CD. Certainly, the price to pay for a smaller file size is that you will suffer some kind of distortion, or, equivalently, losses in audio quality or fidelity. However, such loss is in general indiscernible to human audio perception, and you can hardly notice the subtle differences between the uncompressed and compressed audio signals. The compression of digital data streams such as audio music streams is commonly referred to as source coding. We will consider it in more detail in Chapters 4 and 5.

What we are going to discuss in this chapter is the opposite of compression. After converting the music into MP3 files, you might want to store these files on a CD or a DVD for later use. While burning the digital data onto a CD, there is a special mechanism called error control coding behind the CD burning process. Why do we need it? Well, the reason is simple. Storing CDs and DVDs inevitably causes small scratches on the disk surface.

Up to this point we have been concerned with coding theory. We have described codes and given algorithms of how to design them. And we have evaluated the performance of some particular codes. Now we begin with information theory, which will enable us to learn more about the fundamental properties of general codes without having actually to design them.

Basically, information theory is a part of physics and tries to describe what information is and how we can work with it. Like all theories in physics it is a model of the real world that is accepted as true as long as it predicts how nature behaves accurately enough.

In the following we will start by giving some suggestive examples to motivate the definitions that follow. However, note that these examples are not a justification for the definitions; they just try to shed some light on the reason why we will define these quantities in the way we do. The real justification of all definitions in information theory (or any other physical theory) is the fact that they turn out to be useful.

Motivation

We start by asking the question: what is information?

Let us consider some examples of sentences that contain some “information.”

• The weather will be good tomorrow.

• The weather was bad last Sunday.

• The president of Taiwan will come to you tomorrow and will give you one million dollars.

We end this introduction to coding and information theory by giving two examples of how coding theory relates to quite unexpected other fields. Firstly we give a very brief introduction to the relation between Hamming codes and projective geometry. Secondly we show a very interesting application of coding to game theory.

Hamming code and projective geometry

Though not entirely correct, the concept of projective geometry was first developed by Gerard Desargues in the sixteenth century for art paintings and for architectural drawings. The actual development of this theory dated way back to the third century to Pappus of Alexandria. They were all puzzled by the axioms of Euclidean geometry given by Euclid in 300 BC who stated the following.

1. (1) Given any distinct two points in space, there is a unique line connecting these two points.

2. (2) Given any two nonparallel lines in space, they intersect at a unique point.

3. (3) Given any two distinct parallel lines in space, they never intersect.

The confusion comes from the third statement, in particular from the concept of parallelism. How can two lines never intersect? Even to the end of universe?

In your daily life, the two sides of a road are parallel to each other, yet you do see them intersect at a distant point. So, this is somewhat confusing and makes people very uncomfortable. Revising the above statements gives rise to the theory of projective geometry.

Most of the books on coding and information theory are prepared for those who already have good background knowledge in probability and random processes. It is therefore hard to find a ready-to-use textbook in these two subjects suitable for engineering students at the freshmen level, or for non-engineering major students who are interested in knowing, at least conceptually, how information is encoded and decoded in practice and the theories behind it. Since communications has become a part of modern life, such knowledge is more and more of practical significance. For this reason, when our school requested us to offer a preliminary course in coding and information theory for students who do not have any engineering background, we saw this as an opportunity and initiated the plan to write a textbook.

In preparing this material, we hope that, in addition to the aforementioned purpose, the book can also serve as a beginner's guide that inspires and attracts students to enter this interesting area. The material covered in this book has been carefully selected to keep the amount of background mathematics and electrical engineering to a minimum. At most, simple calculus plus a little probability theory are used here, and anything beyond that is developed as needed. Its first version has been used as a textbook in the 2009 summer freshmen course Conversion Between Information and Codes: A Historical View at National Chiao Tung University, Taiwan. The course was attended by 47 students, including 12 from departments other than electrical engineering.

In this chapter we will consider a new type of coding. So far we have concentrated on codes that can help detect or even correct errors; we now would like to use codes to represent some information more efficiently, i.e. we try to represent the same information using fewer digits on average. Hence, instead of protecting data from errors, we try to compress it such as to use less storage space.

To achieve such a compression, we will assume that we know the probability distribution of the messages being sent. If some symbols are more probable than others, we can then take advantage of this by assigning shorter code-words to the more frequent symbols and longer codewords to the rare symbols. Hence, we see that such a code has codewords that are not of fixed length.

Unfortunately, variable-length codes bring with them a fundamental problem: at the receiving end, how do you recognize the end of one codeword and the beginning of the next? To attain a better understanding of this question and to learn more about how to design a good code with a short average codeword length, we start with a motivating example.

A motivating example

You would like to set up your own telephone system that connects you to your three best friends. The question is how to design efficient binary phone numbers. In Table 4.1 you find six different ways of how you could choose them.