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/>)



Torus based cryptography
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.)


