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
to represent elements of a subgroup of .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
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 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...
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 groupCyclic 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...
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 polynomialCyclotomic 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
. It follows that the roots and form an optimal normal basisNormal 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
over andConsidering 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
. In other words, the conjugatesConjugate 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
over are and and the trace of is their sum:Note that
sinceConsider 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 andand thus
Note also that the product of the conjugates of
equals ,i.e., that
has normField 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
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 polynomialand this polynomial is completely determined by
.The idea behind using traces is to replace
in cryptographic protocols, e.g. the Diffie-Hellman key exchangeDiffie-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
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
defineDefinition Let
denote the, not necessarily distinct, roots of in and let be in . DefineProperties 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 
.
- If
-
When these iterations finish,
and . If n is even use to compute .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 characteristicCharacteristic (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
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 LogarithmDiscrete 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 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 reciprocityQuadratic 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 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 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
and intend to agree on a shared secretShared 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
. 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 integerInteger
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...
, 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
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
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 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 be a multiplicative group of order . The security of the Diffie-Hellman protocol in relies on the Diffie-Hellman (DH) problemDiffie-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
. 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 algorithmPohlig-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
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 methodPollard'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
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 .