
XTR
Encyclopedia
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.
, 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
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
Note also that 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
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
Lemma
Let
be given.
Definition Let
.
Algorithm 1 for computation of
given
and
When these iterations finish,
and
. If n is even use
to compute
.
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
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
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
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 .
. We will start first with Diffie-Hellman.
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:
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:
Upon receipt of
, Alice decrypts the message in the following way:
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
.
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 als 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
.
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:
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:
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
.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, XTR is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for public-key encryption
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
. 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
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
of a finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
. To do so, it uses the trace
Field trace
In mathematics, the field trace is a function defined with respect to a finite field extension L/K. It is a K-linear map from L to K...
over


From a security point of view, XTR relies on the difficulty of solving Discrete Logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
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








Fundamentals of XTR
XTR uses a subgroupSubgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
, commonly referred to as XTR subgroup or just XTR group, of a subgroup called XTR supergroup, of the multiplicative group of a finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...





Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...





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 
Cyclotomic polynomial
In algebra, the nth cyclotomic polynomial, for any positive integer n, is the monic polynomial:\Phi_n = \prod_\omega \,where the product is over all nth primitive roots of unity ω in a field, i.e...

is irreducible over



Normal basis
In mathematics, a normal basis in field theory is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis...
for



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 traceField trace
In mathematics, the field trace is a function defined with respect to a finite field extension L/K. It is a K-linear map from L to K...
in XTR is always considered over

Conjugate element (field theory)
In mathematics, in particular field theory, the conjugate elements of an algebraic element α, over a field K, are the roots of the minimal polynomialof α over K.-Example:The cube roots of the number one are:...
of






Note that


Consider now the generator












and thus

Note also that the product of the conjugates of


i.e., that

Field norm
In mathematics, the norm is a mapping defined in field theory, to map elements of a larger field into a smaller one.-Formal definitions:1. Let K be a field and L a finite extension of K...
1.
The crucial observation in XTR is that the minimal polynomial
Minimal polynomial (field theory)
In field theory, given a field extension E / F and an element α of E that is an algebraic element over F, the minimal polynomial of α is the monic polynomial p, with coefficients in F, of least degree such that p = 0...
of



simplifies to

which is fully determined by








and this polynomial is completely determined by

The idea behind using traces is to replace

Diffie-Hellman key exchange
Diffie–Hellman key exchange Synonyms of Diffie–Hellman key exchange include:*Diffie–Hellman key agreement*Diffie–Hellman key establishment*Diffie–Hellman key negotiation...
by








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


Definition Let






Properties of


-
-
-
-
- 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

- 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



- 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
.
- If
-
When these iterations finish,




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


Characteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
of the field





We denote with







A first easy algorithm to compute such primes


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



In particular if the search for






Note that in this case


On the other hand such

Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
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 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
Quadratic reciprocityIn number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers...
we can deduce thatand
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







However, we do not need to find an explicit








To find such a









An initial approach is to select

Lemma: For a randomly selected


Now the basic algorithm to find a suitable

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




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 encryptionElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
. We will start first with Diffie-Hellman.
XTR-DH key agreement
We suppose that both Alice and BobAlice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
have access to the XTR public key data

Shared secret
In cryptography, a shared secret is a piece of data, known only to the parties involved, in a secure communication. The shared secret can be a password, a passphrase, a big number or an array of randomly chosen bytes....
key

- 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
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...


Given Alice's XTR public key data


- 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 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
Hybrid cryptosystem
In cryptography, public-key cryptosystems are convenient in that they do not require the sender and receiver to share a common secret in order to communicate securely . However, they often rely on complicated mathematical computations and are thus generally much more inefficient than comparable...
version of the ElGamal encryption, where the secret key

In the more traditional ElGamal encryption the message is restricted to the key space, which would here be



Concretely this means if Bob wants to encrypt a message





Upon receipt of the encrypted message






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 problemDiscrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
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 


Diffie-Hellman problem
The Diffie–Hellman problem is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use mathematical operations that are fast to compute, but hard to reverse. For example, they...
of computing


There are two other problems related to the DH problem. The first one is the Diffie-Hellman Decision (DHD) problem to determine if




The DL problem is at least as difficult als the DH problem and it is generally assumed that if the DL problem in

Given the prime factorization of



Pohlig-Hellman algorithm
In number theory, the Pohlig–Hellman algorithm sometimes credited as the Silver–Pohlig–Hellman algorithm is a special-purpose algorithm for computing discrete logarithms in a multiplicative group whose order is a smooth integer....
. Hence

For a subgroup








Pollard's rho algorithm
Pollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective at splitting composite numbers with small factors.-Core ideas:...
.
For both approaches the difficulty of the DL problem in








The XTR parameters are now chosen in such a way that











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


