# Silverberg: Applications of Algebraic Tori to Crytography

In this lecture we discuss `torus-based cryptography', and counterexamples to conjectures in an article entitled Looking Beyond XTR, and compare TBC with Lucas-based cryptosystems and XTR, and understand LUC, XTR, and Beyond in terms of algebraic tori. This is joint work with Karl Rubin, and inspired by XTR.

The cryptosystem XTR (due to A. Lenstra and E. Verheul) concerns the extension : they consider the subgroup of of order with generator ; the public knowledge is , what is shared is , where and are transmitted. In this setup, you get the security of while transmitting only elements of .

Let be a finite cyclic extension with intermediate field . Let , and denote by the -conjugacy class of , so the characteristic polynomial of over is . For , , , the polynomial is , where , , and , where . If is in the subgroup of of order , then and . Therefore knowing is equivalent to knowing all the symmetric polynomials on which is equivalent to knowing as a set, so you know and this is equivalent to knowing . In other words, you can exponentiate, but you cannot multiply: and do not determine ; i.e. knowing and does not allow you to know .

Bosma-Hutton-Verheul conjecture that for all , there exists a divisor such that and for and , you can recover all the coefficients of the characteristic polynomial of over from the first of them for all in the subgroup of of order and not in any proper subfield.

We show that this is in fact false. In particular, when , it is false; for , , no symmetric polynomials determine all of them, and no determine any of the others (except the ones determined by the symmetry of the characteristic polynomial). For , , no symmetric polynomials determine all of them.

Fact. The order subgroup of is

for all

Let be an abelian degree extension of fields. Let

recall that , and . If is not cyclic, . If is cyclic, then is an algebraic torus over of dimension , i.e. is isomorphic over to . Here, .

Assume from now on that is cyclic. Then

for all

Conjecture. [Voskresenskii] is rational, i.e. there exists a birational map .

This is true if or (Klyachko 1988). It is not known for . Let us look at the case when , say, . Then , and which is a conic which can be parameterized, and we obtain

We have . (This is also just Hilbert's theorem 90.) Writing for when , this induces a way to do the multiplication in in .

We also give an explicit example when for , (e.g. with ). is dimension 2 and contained in where is the subextension of degree 3. But is dimension 1, and defines a hypersurface in . Therefore , so we can use the multiplication in but represent elements of by 2 elements of . This gives rise to the cryptosystem CEILIDH.

Open problems:

1. Improve the efficiency of multiplication and exponentiation for the system CEILIDH.
2. Repeat this analysis for , i.e.
1. Find explicit birational isomorphisms between and ,
2. Find prime powers of size bits such that has a -bit prime factor,
3. Are there special attacks on DL in ?

Now we look to understand LUC, XTR, and Beyond in terms of algebraic tori. For a subgroup of which is a direct factor, write for the group of permutations of . Then acts on

Let

For LUC and XTR, you look at

which is the image of under , where the latter map is a birational isomorphism.

Assume that is squarefree. Write where are cyclic of prime order.

Theorem. The action of on preserves and is birational to .

In XTR, we obtain birational to ; in the cases and , one gets , , which are not groups.

We have maps for every symmetric function . We have a surjection and an injection by the direct sum of these functions. A BHV conjecture implies that for the subset consisting of the first functions (where ), the map remains injective. Further, a BHF conjecture implies that every has a divisor so that also divides , and the map (induced by the first symmetric functions) is a birational isomorphism. This is true for (DH), (LUC), (XTR), and and where is prime (see Doing more with fewer bits, by Brouwer-Pellikaan-Verheul), but:

Theorem. This is false for () if lies outside a finite set.

To prove this, we first do a computer search for elements of with the same image but different images in . Using Hensel's Lemma, every lift of to has at least 2 inverse images in . Therefore the map is not generically one-to-one over , so it is not generically one-to-one over , hence over any field of characteristic 0. Then reduce modulo to get it over and therefore all fields of characteristic (outside of a finite set).

Back to the main index for Future directions in algorithmic number theory.