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
Let be an abelian degree extension of fields. Let
Assume from now on that is cyclic. Then
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 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.
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
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.