Supersingular Isogeny Elliptic-Curve Cryptography (Draft)

43 m

1. Algebraic Prerequisites

We start with a brief overview of the tools from abstract algebra we shall need for the study of cryptographic techniques. The exposition here is necessarily brief, and readers are encouraged to consult a standard textbook in abstract algebra for a detailed treatment.

Our overview of abstract algebra focuses on a few generalizations of number systems and their properties as abstract mathematical structures. In particular, we consider generalizations of real and complex numbers, of polynomials, and of integers and modular arithmetic. The section culminates in the complete study of finite fields, a versatile tool in the study of cryptographic techniques.

  • 1.1 introduces fields, an abstraction of the number-system concept.
  • 1.2 introduces the notion of field characteristics, which plays an important role in the study of finte files.
  • 1.3 introduces polynomials with coefficients in a field and establishes various tools from elementary mathematics in this general setting.
  • 1.4 introduces the notion of algebraic closure, a generalization of the fundamental theorem of algebra in the context of fields.
  • 1.5 introduces Abelian groups, a generalization of integer arithmetic and modular arithmetic.
  • 1.6 introduces quotient groups, which formalizes the connection between integer arithmetic and modular arithmetic.
  • 1.7 introduces cyclic groups, a particularly simple kind of Abelian groups that serve as building blocks for other Abelian groups.
  • 1.8 introduces Cauchy’s theorem on Abelian groups, an existence theorem concerning elements of an Abelian group with a special structural property.
  • 1.9 introduces the notion of direct sums of Abelian groups, a way to piece together Abelian groups to construct larger Abelian groups.
  • 1.10 introduces quotients of polynomial rings, an adaptation of the quotient-group concept in the context of polynomial rings. This, in particular, allows us to construct new fields from existing ones.
  • 1.11 collects together techniques introduced in 1.2, 1.3, 1.9, and 1.10 to classify finite fields completely.

1.1. Fields

A field is an abstraction of the number-system concept, such as the real numbers and the complex numbers. Every field is equipped with an addition operation and a multiplication operation that satisfies the usual arithmetic properties, i.e., commutativity, associativity, invertibility, and distributivity. In particular, a field always has an additive identity a multiplicative identity .

Formally, a field is a set F equipped with an addition operation and a multiplication operation such that the following properties hold:

  • addition is commutative, viz., for all ;
  • multiplication is commutative, viz., for all ;
  • addition is associative, viz., for all ;
  • multiplication is associative, viz., for all ;
  • addition and multiplication are distributive, viz., and for all ;
  • an additive identity exists, so that for all ;
  • a multiplicative identity exists, so that for all ;
  • addition is invertible, viz., each admits such that ;
  • multiplication is invertible, viz., each admits such that .

The set of real numbers with usual addition and multiplication is a field. Similarly, the set of complex numbers and the set of rational numbers with usual addition and multiplication are also fields.

A field is called a subfield of another field if and if the arithmetic operations of and agree on . For example, is a subfield of , and is a subfield of .

We say that a field is a field extension of another field if is a subfield of . For example, is a field extension of both , and .

We often speak of structure-preserving mappings in abstract algebra. A field homomorphism from a field to another field is a function such that

  • ,
  • ,
  • for all , and
  • for all . In other words, is a field homomorphism if preserves the algebraic structures of a field.

A field homomorphism is said to be a field isomorphism if is an invertible function. In this case, the inverse function is also a field isomorphism. We say that two fields and with a field isomorphism are said to be isomorphic. Any field-theoretic property of a field is shared by its isomorphic fields, and so we often regard isomorphic fields to be essentially the same.

1.2. Field characteristic

Given an element of a field , we often write as a shorthand for the -fold addition . A field is of characteristic in case is the smallest positive integer such that in . If no such positive integer exists, then we say that is of characteristic zero. , , and are fields of characteristic zero.

Let us now construct some fields of finite charateristic. Let denote the set of integers equipped with addition and multiplication modulo . Since

for all choices of , we see that only contains unique elements (identified modulo ).

Now, for each , Euclidean algorithm furnishes two integers and such that

the greatest common divisor of and . If is a prime number, then , and so we see that

modulo . It follows that is a field if is prime.

We observe that for a prime is of characteristic . Indeed, , which does not equal modulo for . Moreover, modulo .

Let us now show that is a field only if is prime.

Suppose that is not prime. If , then consists of one element and is thus not a field. If , then has at least two prime factors, and so we can find a positive prime number strictly less than that divides . We can then find such that .

If for some , then , and so

for some . Since , we see that

Since , it follows that , which contradicts the assumption that is an integer. We thus conclude that has no multiplicative inverse in , and fails to be a field.

Generalizing this phenomenon, we now show that every field of positive characteristic must be of prime characteristic.

Let be the characteristic of a field . We suppose for a contradiction that for some integers . Since and , we can find elements and of such that and , respectively. We then have

Now, is a field, and so both and have multiplicative inverses. It follows that

which is evidently absurd. It follows that must be prime.

We shall build on the above results to classify all finite fields in Section 1.11

1.3. Polynomial rings over a field

The polynomial ring over a field is the set of polynomials

with coefficients from , equipped with the usual polynomial addition and multiplication. We remark that cannot, in general, be a field. To see this, we suppose for a contradiction that the first-degree mononial has a multiplicative inverse , i.e.,

Substituting , we obtain , which is absurd. It follows that does not have a multiplicative inverse.

Many properties of polynomials from elementary mathematics generalize readily to polynomials over a field. For one, it is possible to perform polynomial long division. In this context, dividing by another polynomial with results in the identity

where . This condition implies that .

A consequence of polynomial long division is polynomial Euclidean algorithm, which, produces, for each pair of polynomials , a pair of polynomials such that

Here is the polynomial with the highest degree among the polynomials with leading coefficient 1 that divide both and .

Analogous to polynomial factorization from elementary mathematics, a polynomial is said to be reducible if there are polynomials such that , , and . A polynomial is said to be irreducible if there are no such polynomials. For example,

and so is reducible in . Nevertheless, neither nor is an element of , and so is irreducible in .

We can also generalize the concept of the root of a polynomial from elementary mathematics. Here, a root of a polynomial is an element of such that in . We now divide by to obtain

where . It follows that must be a constant. Since

it follows that , whence

.

A consequence of the above factor theorem is that cannot have more roots than .

1.4. Algebraic closure

Recall that a root of a polynomial is an element of the base field such that . We note that not every polynomial has a root. Indeed, the roots of the are and , neither of which is in . If every non-constant polynomial in has a root in , then the base field is said to be algebraically closed. For example, the complex field is algebraically closed by the fundamental theorem of algebra.

Recall now that we were able to obtain the roots of by considering a larger base field, say, . In fact, given a field , it is always possible to construct a field extension of that is algebraically closed. We say that is an algebraic closure of . For example, is an algebraic closure of .

A polynomial is said to be separable if its roots are distinct in . For example, , an element of , is a separable polynomial, as its roots are and .

A field is said to be perfect if every irreducible polynomial in is separable. Examples of perfect fields include fields of characteristic zero, finite fields, and algebraically closed fields. The perfect field condition often serves as a simplifying assumption in field theory.

1.5. Abelian groups

Sometimes, we do not need to consider both multiplication and addition. For example, studying the arithmetic of a 12-hour clock only requires hour addition (addition modulo 12). While multiplication modulo 12 makes perfect sense, it does not any meaning in the context of clock arithmetic.

For such a case, we make use of an Abelian group, which comes equipped only with the addition operation. Formally, an Abelian group is a set with an addition operation such that

  • for all ,
  • for all ,
  • there exists an additive identity in such that for all , and
  • for each , there exists an additive inverse in such that .

, , and the usual addition operation are abelian groups. In addition, the set of integers with the usual addition operation is an abelian group.

We say that an abelian group is a subgroup of another abelian group if and if the addition operations of and agree on . For example,

where denotes the subgroup relation.

A group homomorphism from an abelian group to another abelian group is a function such that

  • and
  • for all . A group homomorphism is a group isomorphism if is an invertible function. In this case, is also a group isomorphism, and we say that and are isomorphic as abelian groups.

1.6. Quotient groups.

The kernel of a group homomorphism is the subgroup

The kernel measures how close to an isomorphism is. Indeed, is one-to-one if and only if . In general, we have that

In other words, if and differ by an element of the kernel, then and are essentially the same as far as is concerned.

In light of this observation, we define the quotient group of an abelian group by its subgroup to be the set of cosets

with the addition operation defined by the formula

We note that cosets of divide into equal-sized, non-intersecting partitions. Indeed, the size of each coset is precisely the size of . Moreover, if there exists , then

for some . It follows that and , whence . We conclude that distinct cosets do not intersect.

Cosets allow us to can establish a combinatorial restriction on the structure of Abelian groups. To this end, we define the order of an element of an Abelian group to be the smallest positive integer such that , where denotes the -fold sum of . We often write to denote the order of .

We now fix and define the subgroup of generated by :

Here, with denotes the -fold sum of . Evidently, is the order of .

Since cosets of divide into equal-sized, non-intersecting partitions, we see that

In particular, the order of must divide the cardinality of . This fact is commonly known as Lagrange’s theorem.

Since quotient groups collapse a subgroup into one element by declaring equivalence, we can do away with the kernel of a group homomorphism by considering its induced homomorphism , defined by the formula

Indeed, observe that

whence It now follows that is isomorphic to

a subgroup of . This fact is referred to as the first isomorphism theorem.

1.7. Cyclic groups

The first isomorphism theorem can be used to furnish a complete classification of a special type of groups, called cyclic groups. An abelian group is said to be cyclic if there exists an element , called a generator of , such that every element of can be written as an -fold sum of for some . The standard example of a cyclic group is , the group of integers.

Given a cyclic group , we can construct a group homomorphism by setting

where is the -fold sum of a generator of . This mapping is necessarily surjective, as all elements of are of the form .

If is one-to-one, then is an isomorphism, and so

If fails to be injective, then the first isomorphism theorem implies that

Now, every subgroup of must be of the form

and so

for some . We remark that has precisely elements:

It follows that every cyclic group is isomorphic to either or for some .

We now establish a condition under which an Abelian group must be cyclic: if the size of is prime, then must be cyclic. To see this, we recall Lagrange’s theorem from Section 1.6, which states that the order of each element must divide the size of the group. If is prime, then every element of must be either of order or . Since only the additive identity can be of order 1, it follows that at least one element of is of order , which is a generator of .

1.8. Cauchy’s Theorem on Abelian groups

Using the theory of cyclic groups, we can show that every finite Abelian group whose order is dividible by a prime number contains an element of order . This result, known as Cauchy’s theorem, is to be understood as a partial converse to Lagrange’s theorem.

We proceed by induction on the order of the group. Let be an Abelian group of order . If , then is a group of prime order, hence cyclic. (See Section 1.7) It follows that contains an element of order .

Fix and suppose that every Abelian group of order for each contains an element of order . Let be a non-identity element of . If the order of is divisible by , then for some is of order .

If not, then is an Abelian group of order for some , whence it contains an element of order . This implies that , i.e., for some . We observe that

where is the least common multiple function. Therefore,

and so is a multiple of . In particular, the primality of implies that for some , whence is an element of of order . By induction, every Abelian group whose order is divisible by contains an element of order .

This completes the proof of Cauchy’s theorem.

1.9. Direct sums of Abelian groups

Complex groups can be built from simpler groups by piecing them together. This is the main idea of the direct sum of Abelian groups.

Given Abelian groups and , their direct sum is the cartesian product

with the addition operation defined coordinatewise:

We note that if and , then .

The main theorem about direct sums of Abelian groups is that every finite Abelian group is a direct sum of cyclic groups. Specifically, if is an Abelian group with elements, then

where are powers of prime numbers such that . The proof of this fact is long and technical, and so we omit it.

We now establish a condition under which the direct sum of two cyclic groups is cyclic. The theorem is commonly referred to as the Chinese remainder theorem and states that

if and are relatively prime. Indeed, if and are generators of and , respectively, then must be of order in , as and are relatively prime. This implies that is a generator of , which is then a cyclic group of order . Since we have seen in Section 1.7 that there is, up to an isomorphism, only one cyclic group of each order, the isomorphism result follows.

1.10. Quotients of polynomial rings

The quotient structure on Abelian groups we have studied in Sections 1.6 through 1.9 can be adopted to study rings of polynomials, introduced in Section 1.3.

Let be a field. We note that , equipped just with polynomial addition, is an Abelian group. Which subgroups of the additive Abelian group play nicely with the multiplicative structure of the polynomial ring ?

We define the ideal of the polynomial ring generated by a polynomial to be the set

We observe that is a subgroup of the additive Abelian group . Moreover, if and , then the products and also belong to .

Analogous to the Abelian-group case, we define a coset of to be a set of the form

for some . We define addition of cosets

and multiplication of cosets

The quotient ring is defined to be the set of all cosets of , equipped with coset addition and coset multiplication.

is an Abelian group, and is a subgroup, we see that is also an Abelian group. When is a field? Answering this question boils down to checking when coset multiplication is invertible.

We recall from Section 1.3 that a polynomial is irreducible if there are no non-constant polynomials such that . We shall show that is a field if is irreducible.

Let ; in other words, let be a nonzero element of . The polynomial Euclidean algorithm, introduced in Section 1.3, furnishes polynomials such that

is irreducible, and is not a multiple of , and so . It follows that

the multiplicative identity in . It follows that every nonzero element in is invertible, whence is a field.

1.11. Classification of finite fields

We are finally equipped to exhibit all finite fields, up to isomorphisms.

To start off, we show that every finite field must be of size , where is a prime and .

We first remark that every finite field must have positive characteristic. Indeed, if a field is of characteristic 0, then is an infinite subset of , whence must be infinite.

We have established in Section 1.2 that every field of positive characteristic must be of prime characteristic. We therefore let be a finite field of characteristic , a prime. Then

is of size . Now, if we consider as an Abelian group with respect to its addition operation, then is a subgroup of size . It follows from Lagrange’s theorem that the size of must be divisible by .

We now suppose for a contradiction that another prime also divides the cardinality of . Considering, once again, as an Abelian group with respect to its addition operation, we invoke Cauchy’s theorem to find an element of order . This means that , and that . Since is of characteristic , we also have that .

The Euclidean algorithm furnishes two integers and such that

the greatest common divisor of and . Since and are distinct primes, .

It now follows that

which contradicts the fact that . We conclude that no other prime divides the cardinality of ; in other words, for some .

We now show that, up to an isomorphism, there is precisely one field of each size. For this reason, we write to denote the field of size .

To this end, we define the multiplicative group of a field to be the set

equipped with the multiplication operation. Every element is invertible with respect to the multiplicative identity . And, of course, it follows from the properties of the multiplication operation on that

  • for all , and
  • for all . Therefore, is an Abelian group, despite the apparent lack of an addition operation.

We recall that every finite Abelian group is a direct sum of cyclic groups. Specifically, we have that

where are powers of prime numbers such that . This decomposition implies that, if is the least common multiple of , then for all .

By the factor theorem, the polynomial cannot have more than roots, and so . Now , and so . It follows that .

Now, for each , we let be a generator of , so that . The -tuple is an element of whose order is . Observe that implies that is a cyclic group. It follows that is a cylic group of order , whence

We have shown that every field of order can admit only one multiplicative structure, from which it follows that every field of size is isomorphic.

It remains to construct for each and every . We have established in Section 1.2 that

We shall construct from by taking a quotient of the polynomial ring , a method introduced in Section 1.10. We take for granted the existence of an irreducible polynomial of degree . We omit the long, technical proof. Interested readers can consult, for example, a blog post over at everything2.com.

We claim that is a field of size . We have shown in Section 1.10 that the irreducibility of implies that is a field. It suffices to show that has elements.

Let . If , then polynomial long division yields

where . Therefore,

whence it suffices to consider polynomials of degree less than . Since there are possible field elements for each coefficient, we conclude that there are unique polynomials of degree less than . It now follows that the size of is , as was to be shown.

2. Classical Cryptography

2.1. Perfect secrecy and the one-time pad

Cryptography is the science of designing systems that can withstand malicious attempts to abuse them. Every cryptographic scenario can be illustrated by the story of security’s inseparable couple, Alice and Bob: Alice and Bob want to send messages to each other, while deterring various unwanted interlocutors, eavesdroppers, and tamperers from participating.

In the simplest model, Alice sends Bob a secret message, and Eve the eavesdropper attempts to decode Alice’s message. Alice’s goal is to encrypt the message in such a way that Bob can decrypt but Eve cannot. The formal study of such communication protocols must begin with the construction of a cryptographic model, which we can then analyze to determine its functionality and security.

The formalization of the Alice–Eve–Bob secnario consists of the following:

  • A set of messages, and another set of ciphertexts;
  • Alice has an encryption algorithm that takes and outputs ;
  • Bob has a decryption algorithm that takes and outputs ;
  • Eve has her own decryption algorithm that takes and outputs .

In order for the above model to be functional, we expect to have for all . Security would mean that for all , or, at least, for a large portion of .

This naïve definition of functionality and security quickly turns out to be hopeless. History has shown that one party can often find out which encryption method the other party is using through espionage and other tactics. For Alice to guarantee the security of her communication with Bob, it is imperative for her to use an encryption method that produces messages that cannot be decrypted even when the encryption algorithm is leaked to Eve.

To this end, we construct an encryption method with a secret key, without which encryption messages cannot be decrypted with ease. We update the above cryptographic model accordingly:

  • We now have a set of messages, a set of ciphertexts, and a set of keys.
  • There is a key-generation algorithm that outputs an element of .
  • Alice is equipped with an encryption algorithm that takes and outputs .
  • Bob is equipped with a decryption algorithm that takes and outputs .
  • Even is equipped with another decryption algorithm that takes and outputs .

In this context, it is reasonable to say that the model is functional if

for all . In other words, Bob should be able to decrypt any message that Alice encrypted, so long as both of them use the same key.

Is this new model secure? We should hope that Eve cannot, in general, guess the key that Alice and Bob choose to use. Therefore, it is reasonable to assume that is a randomized algorithm.

Moreover, if Eve fails to obtain the correct key, then she should not be able to recover the original message. For this, a typical ciphertext must not carry any inherent meaning on its own, thereby deterring Eve from deciphering it without a key.

We formalize these observations as follows:

Definition 2.1.1 (Shannon, 1949). A cryptographic system is perfectly secret if, for each probability distribution over , we have the identity

for all choices of . In other words, the probability of recovering a fixed message does not depend on the choice of the ciphertext .

An implementation of Shannon’s perfect secrecy model is the one-time pad algorithm. To state the algorithm, we recall from Section 1.10 that denotes the finite field of size 2.

Theorem 2.1.2 (Shannon one-time pad, 1949). Fix and let , the -fold cartesian product of . We define to be the algorithm that chooese uniformly from . Let denote the coordinatewise addition on

and define

for all . The resulting system , called the one-time pad, is a perfectly secret cryptographic system.

The one-time pad algorithm (OTP) is one of the earliest known examples of encryption methods with a secret key. Miller was the first person to describe OTP formally (Miller 1882). Shannon, on the other hand, was the first to prove formally the security of OTP (Shannon 1949.

OTP is an example of a symmetric-key encryption scheme, as the same key is used both for the encryption process and the decryption process. The above theorem shows that OTP is essentially unbreakable, but OTP is not without problems. We first note that a key must be just as large as the message is used. In fact, this condition cannot be altered:

Theorem 2.1.3 (Shannon, 1949). In every perfectly secret cryptographic system, .

Worse, a key can never be recycled. Indeed, if and , then

From , the individual messages can be obtained with reasonable certainty. A historical example is the Venona project:

One-time pads used properly only once are unbreakable; however, the KGB’s cryptographic material manufacturing center in the Soviet Union apparently reused some of the pages from one-time pads. This provided Arlington Hall with an opening. Very few of the 1942 KGB messages could be solved because there was very little duplication of one-time pad pages in those messages. The situation was more favorable in 1943, even more so in 1944, and the success rate improved accordingly. (Benson 2011)

In short, it is hopeless to aim for perfect secrecy. We shall have to settle for something less while maintaining reasonable level of security, which is the underlying theme of cryptography.

We conclude the section with proofs of the above theorems. To this end, we shall make use of a technical lemma.

Lemma 2.1.4. The perfect secrecy condition holds if and only if

for all choices of and . In other words, the probabilities of obtaining the same ciphertext from two different messages and are the same.

We defer the proof of the lemma and establish the theorems.

For OTP,

for all choices of , whence OTP is functional.

To check that OTP is ecure, we observe that, for an arbitrary choice of a probability distribution over ,

regardless of the choice of . Therefore,

for all choices of and . Perfect secrecy of OTP now follows from the lemma.

To show that any perfectly secret cryptographic system must have keys at least as large as the message, we suppose that . We fix , set and consider the set

Since

we can find . Now,

but

and so it follows from the lemma that the cryptographic system in question is not perfectly secret.

Let us return to the proof of the technical lemma, which we restate below for convenience.

Lemma 2.1.4. The perfect secrecy condition holds if and only if

for all choices of and . In other words, the probabilities of obtaining the same ciphertext from two different messages and are the same.

For any choice of , we have that

Therefore,

if and only if

To this end, we observe that

and that

Since probabilities are always nonnegative,

if and only if

regardless of the choice of . This holds if and only if

and the proof of the lemma is now complete.

2.2. Computational complexity

We have seen in Section 2.1 that perfect secrecy is exceedingly difficult to achieve. Nevertheless, it is merely sufficient to prevent Eve the eavesdropper from efficiently decrypting the message. To formalize this notion, we must make sense of what it means for Eve to be computationally bounded.

Computational boundedness is, in essence, the restriction on the ability to carry out computations that take too long to run. What, then is computation? We turn to Alan Turing, the father of theoretical computer science (Turing 1950):

The idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer. The human computer is supposed to be following fixed rules; he has no authority to deviate from them in any detail. We may suppose that these rules are supplied in a book, which is altered whenever he is put on to a new job. He has also an unlimited supply of paper on which he does his calculations. He may also do his multiplications and additions on a “desk machine,” but this is not important.

If we use the above explanation as a definition we shall be in danger of circularity of argument. We avoid this by giving an outline of the means by which the desired effect is achieved. A digital computer can usually be regarded as consisting of three pats:

  • Store
  • Executive unit
  • Control

The store is a store of information, and corresponds to the human computer’s paper, where this is the paper on which he does his calculations or that on which his book of rules is printed. In so far as the human computer does calculations in his bead a part of the store will correspond to his memory.

The executive unit is the part which carries out the various individual operations involved in a calculation. What these individual operations are will vary from machine to machine. Usually fairly lengthy operations can be done such as “Multiplicy 3540675445 by 7076345687” but in some machines only very simple ones such as “Write down 0” are possible.

We have mentioned that the “book of rules” supplied to the computer is replaced in the machine by a part of the store. It is then called the “table of instructions.” It is the duty of the control to see that these instructions are obeyed correctly and in the right order. The control is so constructed that this necessarily happens.

In short, computation can be modeled with a theoretical machine consisting of three parts:

  • infinitely-long tapes with discrete cells, one of which containing input values and the rest providing read-write workspace areas,
  • a state register that specifies the state of the machine at each step, and
  • heads that can, in accordance with the state of the machine and the recorded symbols on tapes, read and write symbols on tapes, as well as moving tapes left or right one cell at a time.

On such a model, computational boundedness is merely a restriction on how many times the tapes can be moved before a computational task is considered too difficult. It is, then, worthwhile to formalize the model into a precise mathematical construct:

Definition 2.2.1 (Turing, 1950). For a fixed , a -tape Turing machine is defined to be an ordered triple consisting of the following:

  • A set of symbols, called the alphabet of . Typically, we assume that contains, at least, 0, 1, blank, and start.
  • A set of states for . Typically, we assume that contains, at least, start and halt.
  • A transition function

that, based on the current state of and the symbols at the current locations of the heads, produces output to be recorded on the workspace tapes and moving instructions for the heads.

We are, of course, interested in computational processes that terminate in a finite number of steps.

Definition 2.2.2. A -tape Turing Machine is said to be a deterministic algorithm, or simply an algorithm, if, for each input that starts off at the start state, there exists a positive integer such that

produces the halt state. In other words, a deterministic algorithm always halts after following the instructions provided by the transition function finitely many times, regardless of the initial configuration of the input tapes.

The image to keep in mind is as follows: we put tapes into the Turing machine as the input, modifies the tapes until it hits the halt state, and the final configuration of the tapes is printed as the output.

We recall, however, that we are interested in computational efficiency, not mere computability. In order to formalize the notion of computational boundedness, we must work out what it means for an algorithm to have a certain running time.

It is typical to consider bit strings such as

as representations of data. Therefore, it makes sense to be able to refer to the collection of all finite bit strings:

Definition 2.2.3. Let denote the -fold cartesian product of the bit set . We define

the set of all finite bit strings. Given a bit string , we define its length to be the unique such that

With bit strings as our representation of data, it makes sense to think of a computational task as a function on , i.e., a process that outputs a unique bit string for each input bit string. This turns out to be a sufficient abstraction for defining the notion of computational efficiency.

Definition 2.2.4. Let and . We say that a Turing machine computes in -time if, for every , the Turing machine initialized to the start configuration on input halts with as its output within steps.

In other words, we can use a function to provide an upper bound on the run time of a Turing machine computing . Computational tasks in real life often takes longer with larger input data, and so it makes sense to have the -time depends on the size of the input bit string.

In fact, it would make sense to have grow with its input size, at a rate sufficiently fast that the Turing machine is always given the time to read the input. Moreover, we would want itself to be efficiently computable as well, for otherwise we cannot make use of the information on computational boundedness with ease. We collect these desirable properties into the following definition:

Definition 2.2.5. A function is time constructible if for all and if there exists a Turing machine that computes the function , the binary representation of , in -time.

Examples of time constructible functions include , , and .

Let us now define what it means for a function to be efficiently computable.

Definition 2.2.6. We define to be the set of all time-constructible functions such that for some . A function is said to be computable in polynomial time, or efficiently computable, if there exists a Turing machine and a function such that computes in -time.

We often write to denote a fixed, unspecified element of .

Examples of efficiently computable functions include the usual sorting algorithms, primality testing, Fast Fourier transform, and so on.

It is often useful to allow our model for computation to make use of randomness. For example, quicksort with a randomized pivot often performs a lot better than quicksort with a median-of-medians pivot, even though the latter has better worst-case runtime than the former. Some widely-used computational methods, such as the Monte Carlo methods, are always probabilistic in nature and do not have non-probabilistic analogues.

In light of this, we define a probabilistic analogue of the Turing machine.

Definition 2.2.7 (de Leeuw–Moore–Shannon–Shapiro, 1970). A probabilistic Turing machine is an ordered quadruple consisting of a set of symbols, a set of states, and two transition functions and : see Definition 2.2.1. Given an input, probabilistic Turing machine is executed by randomly applying and with equal probability.

Probabilistic Turing machine is said to be a probabilistic algorithm if, for each input

there exists a positive integer such that

produces the halt state. Here, each is randomly chosen to be either 1 or 2.

The concept of computational efficiency for Turing machines can be carried over to the context of probabilistic Turing machines with minor modifications.

Definition 2.2.8. A probabilistic Turing machine computes in -time for some if, for every choice of bit string , the probabilistic Turing machine initialized to the start state on input halts after at most steps with as the output, regardless of the random choices made within .

Definition 2.2.9. A function is said to be computable in probabilistic polynomial time if there exists a probabilistic Turing machine and a function such that computes in -time.

Regular Turing machines are sometimes called deterministic Turing machines to emphasize their difference with probabilistic Turing machines. Similarly, computability in polynomial time is often referred to as deterministic polynomial time.

2.3. One-way functions

With the language of computational complexity theory at hand, we now turn to a central question of cryptography: how do we create an encryption scheme that is difficult to revert without authorized access?

We begin tackling this question by first formalizing the notion of a process that is easy to carry out but difficult to revert. To this end, we introduce two preliminary definitions.

Definition 2.3.1. denotes a random variable distributed uniformly over , i.e.,

whenever and equals zero otherwise.

Definition 2.3.2. refers to a bit string of length , consisting entirely of 0. Similarly, refers to a bit string of length , consisting entirely of 1.

We are now ready to give the definition of a one-way function.

Definition 2.3.2 (Diffie–Hellman, 1976). A function is said to be one-way if the following conditions hold:

  • is easy to compute, i.e., is computable in deterministic polynomial time.
  • is difficult to invert, i.e., for each probabilistic polynomial-time algorithm and every polynomial ,

for all sufficiently large .

Why is the auxiliary input needed? Without it, a function can be considered one-way by merely shrinking its input: if the image is very small, an inverting algorithm simply would not have enough time with respect to the size of its input—i.e., the shrunk output of the original function—to have good computational complexity.

The existence of a one-way function has not been proven. In fact, an existence proof would settle the famous P versus NP problem. There are, however, plausible candidates for one-way functions, having withstood many attempts at producing efficient inverting algorithms.

The most famous example is the integer factorization problem, which is widely believed to be difficult. State-of-the-art factoring algorithms such as general number field sieve runs in subexponential time. In the language of one-way functions, the multiplication function

is conjectured to be a one-way function.