XTR
In cryptography, XTR is an algorithm for public-key encryption. XTR stands for 'ECSTR', which is an abbreviation for Efficient and Compact Subgroup Trace Representation. It is a method to represent elements of a subgroup of a multiplicative group of a finite field. To do so, it uses the trace over  to represent elements of a subgroup of .

From a security point of view, XTR relies on the difficulty of solving Discrete Logarithm related problems in the full multiplicative group of a finite field. Unlike many cryptographic protocols that are based on the generator of the full multiplicative group of a finite field, XTR uses the generator  of a relatively small subgroup of some prime order   of a subgroup of . With the right choice of , computing Discrete Logarithms in the group, generated by  , is, in general, as hard as it is in   and thus cryptographic applications of XTR use  arithmetics while achieving full  security leading to substantial savings both in communication and computational overhead without compromising security. Some other advantages of XTR are its fast key generation, small key sizes and speed.

Fundamentals of XTR 
XTR uses a subgroup, commonly referred to as XTR subgroup or just  XTR group, of a subgroup called XTR supergroup, of the multiplicative group of a finite field  with  elements. The XTR supergroup is of order , where p is a prime such that a sufficiently large prime q divides . The XTR subgroup has now order q and is, as a subgroup of , a cyclic group  with generator g.  The following three paragraphs will describe how elements of the XTR supergroup can be represented using an element of  instead of an element of  and how arithmetic operations  take place in  instead of in .

Arithmetic operations in  
Let p be a prime such that p ≡ 2 mod 3 and p2 - p + 1 has a sufficiently large prime factor q. Since p2 ≡ 1 mod 3 we see that p generates  and thus the third cyclotomic polynomial

is irreducible over . It follows that the roots  and  form an optimal normal basis for  over  and 

Considering that p ≡ 2 mod 3 we can reduce the exponents modulo 3 to get

The cost of arithmetic operations is now given in the following Lemma labeled Lemma 2.21 in "An overview of the XTR public key system":

Lemma

 Computing xp is done without using multiplication
 Computing x2 takes two multiplications in 
 Computing xy takes three multiplications in 
 Computing xz-yzp takes four multiplications in .

Traces over  
The trace in XTR is always considered over . In other words, the conjugates of  over  are  and  and the trace of  is their sum:

Note that  since 

Consider now the generator  of the XTR subgroup of a prime order . Remember that  is a subgroup of the XTR supergroup of order , so . In the following section we will see how to choose  and , but for now it is sufficient to assume that . To compute the trace of  note that modulo  we have
 and

and thus

The product of the conjugates of  equals ,
i.e., that  has norm 1.

The crucial observation in XTR is that the minimal polynomial of  over 

simplifies to 

which is fully determined by . Consequently, conjugates of , as roots of the minimal polynomial of  over , are completely determined by the trace of . The same is true for any power of : conjugates of  are roots of polynomial

and this polynomial is completely determined by .

The idea behind using traces is to replace  in cryptographic protocols, e.g. the Diffie–Hellman key exchange by  and thus obtaining a factor of 3 reduction in representation size. This is, however, only useful if there is a quick way to obtain  given . The next paragraph gives an algorithm for the efficient computation of . In addition, computing  given  turns out to be quicker than computing  given .

Algorithm for the quick computation of  given  
A. Lenstra and E. Verheul give this algorithm in their paper titled The XTR public key system in. All the definitions and lemmas necessary for the algorithm and the algorithm itself presented here, are taken from that paper.

Definition For c in  define

Definition Let  denote the, not necessarily distinct, roots of  in  and let  be in . Define

Properties of  and  
 
 
 
 
 Either all  have order dividing  and  or all  are in . In particular,  is irreducible if and only if its roots have order diving  and .
  is reducible over  if and only if 

Lemma 
Let  be given.
 Computing  takes two multiplication in .
 Computing  takes four multiplication in .
 Computing  takes four multiplication in .
 Computing  takes four multiplication in .

Definition Let .

Algorithm 1 for computation of  given  and 
 If  apply this algorithm to  and , and apply Property 2 to the resulting value.
 If , then .
 If , then .
 If , use the computation of  and  to find  and thereby .
 If , to compute  define

and  if n is odd and  otherwise. Let  and compute  using the Lemma above and . Let further

with  and . For  in succession, do the following:
 If , use  to compute .
 If , use  to compute .
 Replace  by .
When these iterations finish,  and . If n is even use  to compute .

Parameter selection

Finite field and subgroup size selection

In order to take advantage of the above described representations of elements with their traces and furthermore ensure sufficient security, that will be discussed below, we need to find primes  and , where  denotes the characteristic of the field  with  and  is the size of the subgroup, such that  divides .

We denote with  and  the sizes of  and  in bits. To achieve  security comparable to 1024-bit RSA, we should choose  about 1024, i.e.  and  can be around 160.

A first easy algorithm to compute such primes  and  is the next Algorithm A:

Algorithm A

 Find  such that  is a -bit prime.
 Find  such that  is a -bit prime with .

Correctness of Algorithm A:

It remains to check that  because all the other necessary properties are obviously satisfied per definition of  and . We easily see that  which implies that .

Algorithm A is very fast and can be used to find primes  that satisfy a degree-two polynomial with small coefficients. Such  lead to fast arithmetic operations in . 
In particular if the search for  is restricted to , which means looking for an  such that both  are prime and such that , the primes  have this nice form.
Note that in this case  must be even and .

On the other hand, such  may be undesirable from a security point of view because they may make an attack with the Discrete Logarithm variant of the Number Field Sieve easier.

The following Algorithm B doesn't have this disadvantage, but it also doesn't have the fast arithmetic modulo  Algorithm A has in that case.

Algorithm B

 Select a -bit prime  so that .
 Find the roots  and  of .
 Find a   such that  is a -bit prime with  for 

Correctness of Algorithm B:
Since we chose   it follows immediately that   (because   and  ). From that and quadratic reciprocity we can deduce that   and  exist.
To check that  we consider again  for  and get that , since  and  are roots of  and hence .

Subgroup selection

In the last paragraph we have chosen the sizes  and  of the finite field  and the multiplicative subgroup of , now we have to find a subgroup  of  for some  such that .

However, we do not need to find an explicit , it suffices to find an element  such that  for an element  of order . But, given , a generator  of the XTR (sub)group can be found by determining any root of  which has been defined above. 
To find such a  we can take a look at property 5 of  here stating that the roots of  have an order dividing  if and only if  is irreducible. After finding such  we need to check if it really is of order , but first we focus on how to select  such that  is irreducible.

An initial approach is to select  randomly which is justified by the next lemma.

Lemma: For a randomly selected  the probability that  is irreducible is about one third.

Now the basic algorithm to find a suitable  is as follows:

Outline of the algorithm

 Pick a random .
 If  is reducible, then return to Step 1.
 Use Algorithm 1 to compute .
 If  is not of order , return to Step 1.
 Let .

It turns out that this algorithm indeed computes an element of  that equals  for some  of order .

More details to the algorithm, its correctness, runtime and the proof of the Lemma can be found in "An overview of the XTR public key system" in.

Cryptographic schemes 

In this section it is explained how the concepts above using traces of elements can be applied to cryptography. In general, XTR can be used in any cryptosystem that relies on the (subgroup) Discrete Logarithm problem. Two important applications of XTR are the Diffie–Hellman key agreement and the ElGamal encryption. We will start first with Diffie–Hellman.

XTR-DH key agreement 

We suppose that both Alice and Bob have access to the XTR public key data  and intend to agree on a shared secret key . They can do this by using the following XTR version of the Diffie–Hellman key exchange:

 Alice picks  randomly with , computes with Algorithm 1  and sends  to Bob.
 Bob receives  from Alice, selects at random  with , applies Algorithm 1 to compute  and sends   to Alice.
 Alice receives  from Bob, computes with Algorithm 1  and determines  based on .
 Bob analogously applies Algorithm 1 to compute  and also determines  based on .

XTR ElGamal encryption 

For the ElGamal encryption we suppose now that Alice is the owner of the XTR public key data  and that she has selected a secret integer , computed  and published the result.
Given Alice's XTR public key data , Bob can encrypt a message , intended for Alice, using the following XTR version of the ElGamal encryption:

 Bob selects randomly a  with  and computes with Algorithm 1 .
 Bob next applies Algorithm 1 to compute .
 Bob determines a symmetric encryption key  based on .
 Bob uses an agreed upon symmetric encryption method with key  to encrypt his message , resulting in the encryption .
 Bob sends  to Alice.

Upon receipt of , Alice decrypts the message in the following way:

 Alice computes .
 Alice determines the symmetric key  based on .
 Alice uses the agreed upon symmetric encryption method with key  to decrypt , resulting in the original message .

The here described encryption scheme is based on a common hybrid version of the ElGamal encryption, where the secret key  is obtained by an asymmetric public key system and then the message is encrypted with a symmetric key encryption method Alice and Bob agreed to.

In the more traditional ElGamal encryption the message is restricted to the key space, which would here be , because . The encryption in this case is the multiplication of the message with the key, which is an invertible operation in the key space .

Concretely this means if Bob wants to encrypt a message , first he has to convert it into an element  of  and then compute the encrypted message  as .
Upon receipt of the encrypted message  Alice can recover the original message  by computing , where  is the inverse of  in .

Security

In order to say something about the security properties of the above explained XTR encryption scheme, first it is important to check the security of the XTR group, which means how hard it is to solve the Discrete Logarithm problem there. The next part will then state the equivalency between the Discrete Logarithm problem in the XTR group and the XTR version of the discrete logarithm problem, using only the traces of elements.

Discrete logarithms in a general 

Let now  be a multiplicative group of order . The security of the Diffie–Hellman protocol in  relies on the Diffie–Hellman (DH) problem of computing . We write .
There are two other problems related to the DH problem. The first one is the Diffie–Hellman Decision (DHD) problem to determine if  for given  and the second one is the Discrete Logarithm (DL) problem to find  for a given .

The DL problem is at least as difficult as the DH problem and it is generally assumed that if the DL problem in  is intractable, then so are the other two.

Given the prime factorization of  the DL problem in  can be reduced to the DL problem in all subgroups of  with prime order due to the Pohlig–Hellman algorithm. Hence  can safely be assumed to be prime.

For a subgroup  of prime order  of the multiplicative group  of an extension field  of  for some , there are now two possible ways to attack the system. One can either focus on the whole multiplicative group or on the subgroup. To attack the multiplicative group the best known method is the Discrete Logarithm variant of the Number Field Sieve or alternatively in the subgroup one can use one of several methods that take  operations in , such as Pollard's rho method.

For both approaches the difficulty of the DL problem in  depends on the size of the minimal surrounding subfield of  and on the size of its prime order . If  itself is the minimal surrounding subfield of  and  is sufficiently large, then the DL problem in  is as hard as the general DL problem in .

The XTR parameters are now chosen in such a way that  is not small,  is sufficiently large and  cannot be embedded in a true subfield of , since  and  is a divisor of , but it does not divide  and thus  cannot be a subgroup of  for .
It follows that the DL problem in the XTR group may be assumed as hard as the DL problem in .

Security of XTR 

Cryptographic protocols that are based on Discrete Logarithms can use many different types of subgroups like groups of points of elliptic curves or subgroups of the multiplicative group of a finite field like the XTR group.
As we have seen above the XTR versions of the Diffie–Hellman and ElGamal encryption protocol replace using elements of the XTR group by using their traces. 
This means that the security of the XTR versions of these encryption schemes is no longer based on the original DH, DHD or DL problems. 
Therefore, the XTR versions of those problems need to be defined and we will see that they are equivalent (in the sense of the next definition) to the original problems.

Definitions:
We define the XTR-DH problem as the problem of computing  given  and  and we write .
The XTR-DHD problem is the problem of determining whether  for .
Given , the XTR-DL problem is to find , i.e.  such that .
 We say that problem  is (a,b)-equivalent to problem , if any instance of problem  (or ) can be solved by at most a (or b) calls to an algorithm solving problem  (or ).

After introducing the XTR versions of these problems the next theorem is an important result telling us the connection between the XTR and the non-XTR problems, which are in fact equivalent. This implies that the XTR representation of elements with their traces is, as can be seen above, faster by a factor of 3 than the usual representation without compromising security.

Theorem   The following equivalencies hold:
i. The XTR-DL problem is (1,1)-equivalent to the DL problem in .
ii. The XTR-DH problem is (1,2)-equivalent to the DH problem in .
iii. The XTR-DHD problem is (3,2)-equivalent to the DHD problem in .

This means that an algorithm solving either XTR-DL, XTR-DH or XTR-DHD with non-negligible probability can be transformed into an algorithm solving the corresponding non-XTR problem DL, DH or DHD with non-negligible probability and vice versa.
In particular part ii. implies that determining the small XTR-DH key (being an element of ) is as hard as determining the whole DH key (being an element of  ) in the representation group .

References 

Asymmetric-key algorithms
Finite fields