Torus based cryptography

Question

In cryptography one needs finite groups $G$ in which the discrete logarithm problem is infeasible. Often they use the multiplicative group $\mathbb{G}_m(\mathbb{F}_p)$ where $p$ is a prime number of bit length $500$, say.

Rubin and Silverberg suggested (cf. [1]) to use certain tori instead, if the goal is to minimize the key size. In the easiest case, this comes down to using the group $$T_2(p)=ker(Norm: \mathbb{F}_{p^2}^\times\to \mathbb{F}_p^\times).$$

If I understood correctly, then the underlying philosopy seems to be: The group $T_2(p)$ should be as secure as $\mathbb{F}_{p^2}^\times$, but its size is only $p+1$. (So, if you use groups of type $T_2(p)$ instead of groups of type $\mathbb{G}_m(\mathbb{F}_p)$, then you can achive the same security with half the key size.)

Question. What are the reasons, be they heurisical or strictly provable, to believe in this philosopy?

Denote by $\mathbb{G}'_m$ the quadratic twist of the algebraic group $\mathbb{G}_m$. It is easy to see that $T_2(p)$ is isomorphic to $\mathbb{G}'_m(\mathbb{F}_p)$. (This isomorphism is easy to compute). The philosophy predicts: The quadratic twist of the multiplicative group should be better than the multiplicative group itself.

(Compare with elliptic curves: If $E/\mathbb{F}_p$ is an elliptic curve, then I would certainly not expect its quadratic twist to be better than $E$ itself.)

Remark: I concentrated on the simplest case above. One also considers certain groups $T_n(p)$ which are expected to be as secure as $\mathbb{F}_{p^n}^\times$, while their size is only $\approx\varphi(n)p$. Lemma 7 in [1] is meant to explain this. However, I would be keen on a more detailed explanation.

[1] Lect. Notes in Comp. Sci. 2729 (2003) 349-365. (available at http://math.stanford.edu/~rubin/)

Answer 1

The discrete log problem in the multiplicative group of a finite field may be solved using the index calculus, not the number field sieve (although sieves are used to speed the process of checking numbers for smoothness during the index calculus algorithm). Anyway, the idea is as follows.

Using index calculus on a field $\mathbb{F}_q^*$ has running time $L(q,1/3)$, which is a subexponential function of $q$ that is approximately $\exp((\log q)^{1/3})$. Now suppose that we work in a subgroup $G\subset \mathbb{F}_q^*$ of order $N$. Then operations in $G$ may be much faster to compute, so we get a more efficient system. And to solve the discrete log problem in $G$, we have two options. We can use a collision algorithm such as Pollard's $\rho$ method, which has running time proportional to $\sqrt{N}$, or we can use the index calculus. But the index calculus doesn't work directly on $G$, so even though we're using elements of $G$, no one knows how to do the index calculus faster than $L(q,1/3)$.

So balancing $N$ and $q$ appropriately, one can get a secure cryptosystem that is more efficient than if one worked with arbitrary elements of $\mathbb{F}_q^*$.

Note that I'm not claiming that one can't do the DLP in $G$ faster than the minimum of $O(\sqrt{N})$ and $L(q,1/3)$, I'm simply saying that at present, no one knows how to do it. (But that's true of the security of all the problems being used in cryptography, we have no proofs that they are actually difficult.)

Answer 2

Can I refer you to my paper `On the Discrete Logarithm Problem on Algebraic Tori', Advances in Cryptology – CRYPTO 2005, Lecture Notes in Computer Science, 2005, Volume 3621/2005, 66-85, in which myself and Frederik Vercauteren studied this very problem.

In particular, we showed that the compression mechanism afforded by the birationality of some algebraic tori may be exploited to obtain a faster discrete logarithm algorithm for some cryptographically practical field sizes. In these instances, attacking the discrete logarithm in $\mathbb{F}_{p^n}^{\times}$ via its decomposition

$\prod_{d \mid n} T_d(\mathbb{F}_p)$ is faster than using L[1/3] index calculus techniques.

Since then, other work has improved the L[1/3] index calculus techniques. However, our work demonstrates that it is naive to argue that the DLP in algebraic tori must be hard purely because the DLP in the multiplicative group of the extension field is hard, precisely because an attack on the former provides an attack on the latter.

Answer 3

The philosophy, as stated, seems off:

The multiplicative groups of finite fields have discrete logarithm problems that are vulnerable to the number field sieve. On the other hand, the best known method in an 'abstract' cyclic group is a variant of the Shanks baby-step-giant-step method -- this is much slower than the number field sieve, since its worst-case (and average) running time in a cyclic group of order $n$ are about the size of $\sqrt{n}$ (and this worst case includes the assumption than $n$ is prime).

What applies to the multiplicative groups of finite fields carries over to their large quotients as long as computing lifts is easy, and carries over to their large subgroups. (Here, "large" means 'large enough that the number field sieve is faster than any variant of baby-step-giant-step'.)

How can baby-step-giant-step be sped up when $n$ is not prime? Let $n = p_{1}^{e_{1}}\ldots p_{k}^{e_{k}}$ be the prime factorization of $n$. Then the idea is to break up the discrete logarithm problem in the cyclic group of order $n$ into $e_{1}$ problems in cyclic groups of order $p_{1}$, $\ldots$, and $e_{k}$ problems in cyclic groups of order $p_{k}$. In more detail:

$g^{x} = m$ implies $(g^{L})^{x} = g^{Lx} = m^{L}$ for any integer $L$.

Choose $L_{i}$, where $1 \leq i \leq k$, so that $L_{i} \equiv 1 \mod{p_{i}^{e_{i}}}$ and $L_{i} \equiv 0 \mod{p_{j}^{e_{j}}}$ when $j \neq i$. Then $g$ such that $g^{x} = m$ is obtained as $g^{L_{1} + \ldots + L_{k}} = g^{L_{1}}\ldots g^{L_{k}}$.

Each $g^{L_{i}}$ solves $ ( g^{ L_{i} } )^{x} = g^{L_{i} x} = m^{L_{i}} $, which is a discrete logarithm problem in the cyclic subgroup of order $p_{i}^{e_{i}}$ in our cyclic group of order $n$.

As for solving the discrete logarithm problem in a cyclic group of order $p_{i}^{e_{i}}$ (here we write $g^{L_{i}} = h$ and $m^{L_{i}} = M$):

If $e_{i} > 1$, then $h^{x} = M$ implies $(h^{L})^{x} = h^{Lx} = M^{L}$, where this time $L = p_{i}^{e_{i}-1}$. This is a discrete logarithm problem in a cyclic group of order $p_{i}$, and its solution (call it $x^{'}$) is the solution to $h^{x} = M$, reduced modulo $p_{i}$. Then $h^{x} = M$ implies $h^{x-x^{'}} = M h^{-x^{'}}$, which implies $(h^{p_{i}})^{\frac{x-x^{'}}{p_{i}}} = M h^{-x^{'}}$. This is a discrete logarithm problem in a cyclic group of order $p_{i}^{e_{i}-1}$.

Finally, the variant of the basic baby-step-giant-step method when $e_{i} = 1$ (still write this discrete logarithm problem as $h^{x} = M$ for simplicity):

Compute $h^{1}, h^{2}, \ldots, h^{S}$ and store that as a sorted list (so that searches can be made using a logarithmic time binary search). Then compute $M, Mh^{-S}, Mh^{-2S}, \ldots$ until a $t$ is found such that $Mh^{-tS}$ is on the list. Then one obtains $Mh^{-tS} = h^{u}$ for some $u$ with $1 \leq u \leq S$, which gives $M = h^{u + tS}$, so that $x = u + tS$. Here, for maximum speed, choose $S$ to be the result of rounding $\sqrt{p_{i}}$ to the nearest integer.