Category: featured

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 first challenging
problem here is to obtain an explicit rational parameterization of the
8-dimensional torus $T_{30} $ , deïfined over a finite field 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 $g $ 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 $a $ (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 $b $ 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 $a $ and the published $g^b $ and your correspondent knows $b $ 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.