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 G F ( p 2 ) {displaystyle GF(p^{2})} to represent elements of a subgroup of G F ( p 6 ) ∗ {displaystyle GF(p^{6})^{*}} . 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 G F ( p 2 ) {displaystyle GF(p^{2})} to represent elements of a subgroup of G F ( p 6 ) ∗ {displaystyle GF(p^{6})^{*}} . 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 g {displaystyle g} of a relatively small subgroup of some prime order q {displaystyle q} of a subgroup of G F ( p 6 ) ∗ {displaystyle GF(p^{6})^{*}} . With the right choice of q {displaystyle q} , computing Discrete Logarithms in the group, generated by g {displaystyle g} , is, in general, as hard as it is in G F ( p 6 ) ∗ {displaystyle GF(p^{6})^{*}} and thus cryptographic applications of XTR use G F ( p 2 ) {displaystyle GF(p^{2})} arithmetics while achieving full G F ( p 6 ) {displaystyle GF(p^{6})} 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. 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 G F ( p 6 ) {displaystyle GF(p^{6})} with p 6 {displaystyle p^{6}} elements. The XTR supergroup is of order p 2 − p + 1 {displaystyle p^{2}-p+1} , where p is a prime such that a sufficiently large prime q divides p 2 − p + 1 {displaystyle p^{2}-p+1} . The XTR subgroup has now order q and is, as a subgroup of G F ( p 6 ) ∗ {displaystyle GF(p^{6})^{*}} , a cyclic group ⟨ g ⟩ {displaystyle langle g angle } with generator g. The following three paragraphs will describe how elements of the XTR supergroup can be represented using an element of G F ( p 2 ) {displaystyle GF(p^{2})} instead of an element of G F ( p 6 ) {displaystyle GF(p^{6})} and how arithmetic operations take place in G F ( p 2 ) {displaystyle GF(p^{2})} instead of in G F ( p 6 ) {displaystyle GF(p^{6})} . 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 ( Z / 3 Z ) ∗ {displaystyle (mathbb {Z} /3mathbb {Z} )^{*}} and thus the third cyclotomic polynomial Φ 3 ( x ) = x 2 + x + 1 {displaystyle Phi _{3}(x)=x^{2}+x+1} is irreducible over G F ( p ) {displaystyle GF(p)} . It follows that the roots α {displaystyle alpha } and α p {displaystyle alpha ^{p}} form an optimal normal basis for G F ( p 2 ) {displaystyle GF(p^{2})} over G F ( p ) {displaystyle GF(p)} 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 The trace in XTR is always considered over G F ( p 2 ) {displaystyle GF(p^{2})} . In other words, the conjugates of h ∈ G F ( p 6 ) {displaystyle hin GF(p^{6})} over G F ( p 2 ) {displaystyle GF(p^{2})} are h , h p 2 {displaystyle h,h^{p^{2}}} and h p 4 {displaystyle h^{p^{4}}} and the trace of h {displaystyle h} is their sum: Note that T r ( h ) ∈ G F ( p 2 ) {displaystyle Tr(h)in GF(p^{2})} since