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.
Open problems:
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.