Rationality | neverendingbooks

Posts Tagged ‘rationality’

the crypto lattice

Saturday, January 12th, 2008

rationality & cryptography

Last time we have seen that tori are dual (via their group of characters) to lattices with a Galois action. In particular, the Weil descent torus $R_n=R^1{\mathbb{F}_{p^n}/\mathbb{F}p} \mathbb{G}_m$ corresponds to the permutation lattices $Rn^* = \mathbb{Z}[x]/(x^n-1)$ . The action of the generator $\sigma$ (the Frobenius) of the Galois group $Gal(\mathbb{F}_{p^n}/\mathbb{F}p)$ acts on the lattice by multiplication with .

An old result of Masuda (1955), using an even older lemma by Speiser (1919), asserts than whenever the character-lattice T^* of a torus is a permutation-lattice, the torus is rational, that is, the function-field of the torus $\mathbb{F}_p(T)$ is purely trancendental

$\mathbb{F}_p(y1,\hdots,y_d) = \mathbb{F}p(T) = (\mathbb{F}_{q^n}(T^*))^{Gal}$

(recall from last time that the field on the right-hand side is the field of fractions of the Gal -invariants of the group-algebra of the free Abelian group $T^* = \mathbb{Z} \oplus \hdots \oplus \mathbb{Z}$ where the rank is equal to the dimension of the torus).

The basic observation made by Rubin and Silverberg was that the known results on crypto-compression could be reformulated in the language of algebraic tori as : the tori (LUC-system) and (CEILIDH-system) are rational! So, what about the next cryptographic challenges? Are the tori $T_{30}$ , T{210} etc. also rational varieties?

Recall that as a group, the $\mathbb{F}_p$ -points of the torus Tn , is the subgroup of $\mathbb{F}_{p^n}^*$ corresponding to the most crypto-challenging cyclic subgroup of order $\Phin(p)$ where $\Phi_n(x)$ is the n-th cyclotomic polynomial. The character-lattice of this crypto-torus Tn we call the crypto-lattice and it is

$T_n^* = \mathbb{Z}[x]/(\Phin(x))$

(again the action of the Frobenius is given by multiplication with ) and hence has rank $\phi(n)$ , explaining that the torus T_n has dimension $\phi(n)$ and hence that we can at best expect a compression from -pits to $\phi(n)$ -pits. Note that the lattice Tn^* is no longer a permutation lattice, so we cannot use the Masuda-Speiser result to prove rationality of T_n .

What have mathematicians proved on T_n before it became a hot topic? Well, there is an old conjecture by V. E. Voskresenskii asserting that all Tn should be rational! Unfortunately, he could prove this only when is a prime power. Further, he proved that for all , the lattice T_n is at least stably-rational meaning that it is rational upto adding free parameters, that is

$\mathbb{F}_p(Tn)(z_1,\hdots,zl) = \mathbb{F}_p(y1,\hdots,y_{d+l})$

which, sadly, is only of cryptographic-use if is small (see below). A true rationality result on T_n was proved by A.A. Klyashko : Tn is rational whenever n=p^a.q^b a product of two prime powers.But then, $30=2 \times 3 \times 5$ the first unknown case…

At Crypto 2004, Marten van Dijk and David Woodruff were able to use an explicit form of Voskresenskii stable rationality result to get an asymptotic optimal crypto-compression rate of $n/\phi(n)$ , but their method was of little practical use in the $T_{30}$ , for what their method gave was a rational map

$T_{30} \times \mathbb{A}^{32}{\mathbb{F}_p} \rightarrow \mathbb{A}^{40}{\mathbb{F}_p}$

and the number of added parameters (32) is way too big to be of use.

But then, one can use century-old results on cyclotomic polynomials to get a much better bound, as was shown in the paper Practical cryptography in high dimensional tori by the collective group of all people working (openly) on tori-cryptography. The idea is that whenever q is a prime and a is an integer not divisible by q, then on the level of cyclotomic polynomials we have the identity

$\Phi_{aq}(x) \Phia(x) = \Phi_a(x^q)$

On the level of tori this equality implies (via the character-lattices) an ismorphism (with same assumptions)

$T_{aq}(\mathbb{F}p) \times T_a(\mathbb{F}p) \simeq (R^1_{\mathbb{F}{p^q}/\mathbb{F}_p} Ta)(\mathbb{F}_p) = Ta(\mathbb{F}_{p^q})$

whenever aq is not divisible by p. Apply this to the special case when q=5,a=6 then we get

$T_{30}(\mathbb{F}p) \times T_6(\mathbb{F}p) \simeq R^1_{\mathbb{F}{p^5}/\mathbb{F}_p} T6(\mathbb{F}_p)$

and because we know that T_6 is a 2-dimensional rational torus we get, using Weil descent, a rational map

$T_{30} \times \mathbb{A}^2{\mathbb{F}_p} \rightarrow \mathbb{A}^{10}{\mathbb{F}_p}$

which can be used to get better crypto-compression than the CEILIDH-system!

This concludes what I know of the OPEN state of affairs in tori-cryptography. I’m sure ‘people in hiding’ know a lot more at the moment and, if not, I have a couple of ideas I’d love to check out. So, when I seem to have disappeared, you know what happened…

Previous in series

Tags: cryptography, Galois, lattices, rationality, tori
Posted in geometry | No Comments »

ECSTR aka XTR

Saturday, January 5th, 2008

rationality & cryptography

The one thing that makes it hard for an outsider to get through a crypto-paper is their shared passion for using nonsensical abbreviations. ECSTR stands for “Efficient Compact Subgroup Trace Representation” and we are fortunate that Arjen Lenstra and Eric Verheul shortened it in their paper The XTR public key system to just XTR. As both of them speak Dutch, they will know why Ive chosen a magpie-picture on the left… Btw. there is a nice MSRI-talk by Lenstra, starting off with a couple of jokes on what ECSTR is NOT meant to abbreviate (one of them being ‘Elliptic Curve Systems Too Risky’…¹ ).

The XTR-system uses safety of $\mathbb{F}_{p^6}$ in the Diffie-Hellman key exchange while transmitting only $2=\phi(6)$ pits. The first question one asks is : why the jump from N=2 from last time to N=6 ? Well, remember that (conjecturally) we want to use safety of $\mathbb{F}q$ for q=p^N while using only $\phi(N)$ pits. That is, we want to have N log(p) large (for safety) while at the same time $\phi(N) log(p)$ small (for efficiency). Thus, the most useful N’s to consider are those in the sequence

$N=1,~2,~6=2.3,~30=2.3.5,~210=2,3,5,7,~\hdots$

that is, the products of the first so many prime numbers. The number of elements of the cyclic group $\mathbb{F}_q^*$ is equal to

p^6-1 = (p-1)(p+1)(p^2+p+1)(p^2-p+1)

and that the subgroup of order p-1 can be embedded in $\mathbb{F}_p^*$ , that of order p+1 can be embedded in $\mathbb{F}{p^2}^_$ , that of order p^2+p+1 can be embedded in $\mathbb{F}_{p^3}^$ , BUT that the subgroup of order $\Phi_6(p)=p^2-p+1$ CANNOT be embedded in any $\mahbb{F}{p^i}^_$ for i = 1,2,3 , or in other words, the p^2-p+1 subgroup is as hard as $\mathbb{F}_{p^6}^$ . So, let us take a generator of the subgroup T_6 of order p^2-p+1 and do the Diffie-Hellman trick with it in a modified manner.

Galois groups of finite fields are cyclic and generated by the Frobenius $x \mapsto x^p$ . In particular, the Galois group $Gal(\mathbb{F}_{p^6}/\mathbb{F}{p^2}) = C_3$ is cyclic of order three and consists of the auromorphisms $\{ 1=id, \sigma = (x \mapsto x^{p^2}), \sigma^2 = (x \mapsto x^{p^4}) \}$ , so the corresponding trace map is given by

$Tr~:~\mathbb{F}_{p^6} \rightarrow \mathbb{F}{p^2} \qquad Tr(x) = x + x^{p^2} + x^{p^4}$

So, how do we perform our key-exchange using my secret number and yours ? Well, I’ll send you Tr(g^a) and as this is an element of the quadratic extension $\mathbb{F}_{p^2}$ I’ll need just 2 pits instead of 6 and you will send me likewise Tr(g^b) . I claim that the common key we (and only we) can compute is $Tr(g^{ab})$ . How does this work?

Given any element $x \in T_6 \subset \mathbb{F}{p^6}^*$ we can compute the 3-element set $C_x = \{ x,\sigma(x),\sigma(x^2) \}$ and hence the characteristic polynomial $~(t-x)(t-\sigma(x))(t-\sigma^2(x))$

$= t^3 - (x+\sigma(x)+\sigma^2(x))t^2 + (x \sigma(x)+ x\sigma^2(x)+\sigma(x)\sigma^2(x))t - x \sigma(x)\sigma^2(x)$

The first coefficient $x+\sigma(x)+\sigma^2(x)$ is the trace Tr(x) and the second and third coefficients are respectively $Tr(x \sigma(x))$ and the norm N(x) . Now, if $x \in T_6$ one can show that

$Tr(x \sigma(x)) = Tr(x)^p$ and N(x)=1

That is, from knowing only Tr(x) we can compute the characteristic polynomial and hence recover the 3-element set $\{ h,\sigma(h),\sigma^2(h) \}$ !

If I give you Tr(g^a) you can compute from it the 3-set $\{ g^a,\sigma(g^a),\sigma^2(g^a) \}$ and raise them all the the b-th power (b being your secret number) to obtain

$\{ g^{ab},\sigma(g^a)^b,\sigma^2(g^a)^b \} = \{ g^{ab},\sigma(g^{ab}),\sigma^2(g^{ab}) \}$

but then you also know our shared key $Tr(g^{ab}) = g^{ab}+\sigma(g^{ab})+\sigma^2(g^{ab})$ … Done!

Previous in series Next in series

I may even start to share their passion… [↩]

Tags: cryptography, Galois, groups, lattices, rationality, tori
Posted in geometry | 1 Comment »

key-compression

Friday, January 4th, 2008

rationality & cryptography

The main application of tori to cryptography is to exchange keys more efficiently while preserving the same security standards.

In the Diffie-Hellman key-exchange one interchanges elements of the finite field $\mathbb{F}_q$ where q=p^N is a prime-power of a large prime number . If we call an element of the prime field $\mathbb{F}p$ a pit (similar to bit when p=2 ) then we can measure transmssions in pits. An element $h \in \mathbb{F}_q$ requires N pits, for we can write the finite field as the quotient of ring of polynomials $\mathbb{F}p[x]$

$\mathbb{F}_q = \frac{\mathbb{F}p[x]}{(f(x))}$

modulo an irreducible polynomial f(x) of degree N. Hence, any $h \in \mathbb{F}_q$ can be written as a polynomial of degree < N , $h = a1 + a_2 x + \hdots + aN x^{N-1}$ with all $a_i \in \mathbb{F}p$ , so we can represent $h=(a_1,a2,\hdots,a_N)$ as N pits. Now, we are going to limit this number of pits (from to about $\phi(N)$ where $\phi$ is the Euler totient function, that is the number of integers smaller than N and coprime to it) by restricting the elements to be transfered to a subgroup of the group of units of the finite field $\mathbb{F}q^_$ while not compromising on the security of the public key system (the large order of the basic element $g \in \mathbb{F}_q^$ of which is a power).

To see that this is indeed possible, let us consider the easiest case (that of N=2 ) and keep the discussion tori-free (those of you who know more will realize that Hilbert’s Satz 90 is never too far away…). If q=p^2 then the order of the cyclic group $\mathbb{F}_q^*$ is p^2-1 = (p-1)(p+1) so in order to get a safe system let us choose the large prime number such that also tex/2=r[/tex] is a prime number.

Right, now define T_2 to be the subgroup of $\mathbb{F}q^_$ of order p+1 and let be a generator of it that we will use in the Diffie-Hellman exchange. Can we describe the element of T_2 (our torus in disguise)? Take $d \in \mathbb{F}p^$ a non-square element, then we can write $\mathbb{F}_q = \mathbb{F}p(\sqrt{d})$ and $T_2 = \{ a+b\sqrt{d}~:~(a+b\sqrt{d})^{p+1}=1 \}$ (here, $a,b \in \mathbb{F}p$ ). But we claim that $~(a+b\sqrt{d})^p = a -b \sqrt{d}$ . Indeed, a^p=a,b^p=b and from Fermat’s little theorem we deduce that

$-1 = (\tfrac{d}{p}) \equiv d^{\tfrac{p-1}{2}}~mod(p)$

where the middle term is the Legendre symbol which is equal to -1 because d was a non-square modulo p. That is, we can then write T_2 as the algebraic variety of dimension one defined over $\mathbb{F}p$ and given by the equation

$T_2 = \{ a+b\sqrt{d} \in \mathbb{F}q^*~\mid~(a,b) \in \mathbb{F}^2~:~a^2-db^2=1 \}$

Because T_2 is of dimension one over $\mathbb{F}p$ we can hope that most of its elements can be represented by just one pit (instead of the two pits necessary to represent them as elements of $\mathbb{F}_q$ ). This is indeed the case, for we have explicit maps (in geometric terms, these maps show that T2 is a rational variety)

$j~:~\mathbb{F}_p \rightarrow T2~\quad~j(a) = \frac{a+\sqrt{d}}{a-\sqrt{d}}=\frac{a^2+d}{a^2-d}+\frac{2a}{a^2-d}\sqrt{d}$

which has a well-defined invers on the complement of $\{ 1,-1 \}$

$f~:~T_2 - \{ 1,-1 \} \rightarrow \mathbb{F}p~\quad~f(a+b\sqrt{d}) = \frac{1+a}{b}$

From the right-hand description of j(a) one deduces that indeed we have that f(j(a))=a . Using this we can indeed compress the Diffie-Hellman exchange by a factor 2.

Instead of giving you the element $g^a \in T_2$ computed using my secret number a, I’ll send you (using only one pit) the number $f(g^a) \in \mathbb{F}p$ . On this number, you can apply the j-function to recover g^a and then compute the common key $~(g^a)^b = g^{ab}$ using your secret number b). Still, we didnt compromise on security because we used the most difficult elements around in $\mathbb{F}_q^*$ . By going to higher dimensional tori one can even improve on the efficiency rate!

Previous in series Next in series

Tags: cryptography, lattices, public key, rationality, tori
Posted in geometry | 2 Comments »

tori & crypto : Diffie-Hellman or GCHQ?

Thursday, January 3rd, 2008

rationality & cryptography

Boris Kunyavskii arXived the paper Algebraic tori - thirty years after dedicated to the 80th anniversary of V. E. Voskresenskii. The goal is to give an overview of results of V. E. Voskresenskii on arithmetic and birational properties of algebraic tori which culminated in his monograph “Algebraic Tori” published in Russian 30 years ago. As Ive worked on this stuff a long time ago I glanced through the paper and it contains a nice summary of the work of V.E. Voskresenskii, and later of Jean-Louis Colliot-Thelene, Jean-Jacques Sansuc and David Saltman. To my surprise I also made a guest-appearance and even seem to have a conjecture (??!!). Fortunately the ‘conjecture’ turned out to be correct as was proved by Nicole Lemire and Martin Lorenz. But a much bigger surprise (at least to me) is contained in the final section of the paper where applications of (stable) rationality of certain tori are given to primality testing and public key cryptography!

In [GPS] the authors propose to use a similar idea of compression for using tori in an even more recent cryptographic protocol (so-called pairing-based cryptography). It is interesting to note that the efficiency (compression factor) of the above mentioned cryptosystems heavily depends on rationality of tori under consideration (more precisely, on an explicit rational parameterization of the underlying variety). As the tori used by Rubin and Silverberg are known to be stably rational, the seemingly abstract question on rationality of a given stably rational torus is moving to the area of applied mathematics. The first challenging problem here is to obtain an explicit rational parameterization of the 8-dimensional torus $T_{30}$ , deïfined over a finite field k and splitting over its cyclic extension L of degree 30.
This is a particular case of a problem posed by Voskresenskii [Vo77, Problem 5.12] 30 years ago. Let us hope that we will not have to wait another 30 years for answering this question on a degree 30 extension.

That’s all it takes to get me seriously side-tracked… so the last couple of hours I’ve been reading up on this connection between tori and cryptography. I will spend a couple of posts on these beautiful results. The latest seems to be that, while rationality of $T_{30}$ is still unknown, one can use an explicit stable-rationality description of it to get a better bound than the XTR-system (the system corresponding to the torus T{6} ) which in turn is better than the LUC-system (corresponding to T_2 ), which is turn is twice as efficient as the Diffie-Hellman key exchange system… So let us start gently with the latter one…

Whitfield Diffie (r.) and Martin Hellman (m.) published in 1976 their public key-exchange system. Take a large prime power q=p^N , make it public and consider the finite field $\mathbb{F}_q$ which is known to have a cyclic group of units $\mathbb{F}^*q$ of order q-1 . Now, take to be an element in it of large order (preferable a generator but that isnt necessary) and also make this element public.

Now choose a random integer (your hidden secret) and compute the element $g^a \in \mathbb{F}_q$ and publicize this element. Suppose someone else published his/her element g^b constructed from his/her secret integer then both you and this other person can compute from the published data and their secret numbers the element (the shared key)

$g^{ab}=(g^b)^a = (g^a)^b$

(because you know and the published g^b and your correspondent knows and the published g^a ) but nobody else can compute it from the public-available data only because discrete logarithms cannot be feasibly computed in the group $\mathbb{F}_q^*$ . Hellman suggests to call this system the Diffie-Hellman-Merkl key-exchange (via this link)

The first researchers to discover and publish the concepts of PKC were Whitfield Diffie and Martin Hellman from Stanford University, and Ralph Merkle from the University of California at Berkeley. As so often happens in the scientific world, the two groups were working independently on the same problem — Diffie and Hellman on public key cryptography and Merkle on public key distribution — when they became aware of each other’s work and realized there was synergy in their approaches. In Hellman’s words: “We each had a key part of the puzzle and while it’s true one of us first said X, and another of us first said Y, and so on, it was the combination and the back and forth between us that allowed the discovery.”

And that was the full story until 1997. In December, 1997, it was revealed that researchers at the GCHQ organization did some work in the early 1970’s in the field of “non-secret encryption”. The people involved are James Ellis, Clifford Cocks and Malcolm Williamson (r.).

Here is a note by Ellis on his recollection of the history of ‘Non-secret encryption” :

Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work, because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography is realised by minimising the information available to potential adversaries. Thus professional cryptographers normally work in closed communities to provide sufficient professional interaction to ensure quality while maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests of historical accuracy after it has been demonstrated clearly that no further benefit can be obtained from continued secrecy.
In keeping with this tradition it is now appropriate to tell the story of the invention and development within CESG of non-secret encryption (NSE) which was our original name for what is now called PKC. The task of writing this paper has devolved on me because NSE was my idea and I can therefore describe these early developments from personal experience. No techniques not already public knowledge, or specific applications of NSE will be mentioned…

The once secret notes of Williamson are also available. NON-SECRET ENCRYPTION USING A FINITE FIELD by M J Williamson, 21 January 1974 and THOUGHTS ON CHEAPER NON-SECRET ENCRYPTION M J Williamson, 10 August 1976.

Next in series

Tags: arxiv, cryptography, groups, lattices, puzzle, rationality, tori
Posted in general, geometry | 2 Comments »

neverendingbooks-geometry

Tuesday, June 12th, 2007

Here a list of saved pdf-files of previous NeverEndingBooks-posts on geometry in reverse chronological order.

(more…)

Tags: anabelian, arxiv, coalgebras, Connes, geometry, Klein, Manin, Marcolli, noncommutative, rationality, Riemann, topology
Posted in geometry | No Comments »

Posts Tagged ‘rationality’

the crypto lattice

rationality & cryptography

ECSTR aka XTR

rationality & cryptography

key-compression

rationality & cryptography

tori & crypto : Diffie-Hellman or GCHQ?

rationality & cryptography

neverendingbooks-geometry

Recent Posts

Recent Comments