↑ arvau

Wikipedia / 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.

From a security point of view, XTR relies on the difficulty of solving Discrete Logarithm 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, where p is a prime such that a sufficiently large prime q. The XTR subgroup has now order q, a cyclic group with generator g.

GF(p^2)

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 and thus the third cyclotomic polynomial is irreducible. It follows that the roots form an optimal normal basis 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

  • Computing xy

  • Computing xz-yzp.

GF(p^2)

The trace. In other words, the conjugates is their sum:

since

. In the following section we have

  1. and

and thus

has norm 1.

The crucial observation in XTR is that the minimal polynomial

simplifies to

are roots of polynomial

.

in cryptographic protocols, e.g. the Diffie–Hellman key exchange.

Tr(g^n)Tr(g)

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 define

Definition. Define

  1. .

Lemma be given.

  1. .

  2. .

  3. .

  4. .

Definition.

  • , and apply Property 2 to the resulting value.

  • .

  • .

  • .

  • define

    1. . Let further

in succession, do the following:

  • .

  • .

  • .

.

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 denotes the characteristic.

in bits. To achieve security comparable to 1024-bit RSA can be around 160.

is the next Algorithm A:

Algorithm A

  1. -bit prime.

  2. .

  3. Correctness of Algorithm A:

    .

.

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.

Algorithm A has in that case.

Algorithm B

  1. .

  2. .

  3. Correctness of Algorithm B:

  4. ). From that and quadratic reciprocity exist.

  5. .

Subgroup selection

.

which has been defined above here is irreducible is irreducible.

randomly which is justified by the next lemma.

Lemma: is irreducible is about one third.

is as follows:

Outline of the algorithm

  1. .

  2. is reducible, then return to Step 1.

  3. .

  4. , return to Step 1.

  5. .

.

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

  1. , computes with Algorithm 1 to Bob.

  2. to Alice.

  3. .

  4. .

XTR ElGamal encryption

and that she has selected a secret integer, intended for Alice, using the following XTR version of the ElGamal encryption:

  1. and computes with Algorithm 1.

  2. .

  3. .

  4. .

  5. to Alice.

, Alice decrypts the message in the following way:

  1. .

  2. .

  3. .

The here described encryption scheme is based on a common hybrid 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.

.

.

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.

GF\left(p^t\right)

. The security of the Diffie–Hellman protocol relies on the Diffie–Hellman (DH) problem. There are two other problems related to the DH problem. The first one is the Diffie–Hellman Decision (DHD) problem and the second one is the Discrete Logarithm (DL) problem.

is intractable, then so are the other two.

Given the prime factorization with prime order due to the Pohlig–Hellman algorithm can safely be assumed to be prime.

, 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, such as Pollard's rho method.

.

.

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.

  • The XTR-DHD.

  • , the XTR-DL.

  • ).

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:

  1. i. The XTR-DL problem is (1,1)-equivalent to the DL.

  2. ii. The XTR-DH problem is (1,2)-equivalent to the DH.

  3. iii. The XTR-DHD problem is (3,2)-equivalent to the DHD.

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

References