MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 424 characters in body

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

1

# Torus based cryptography

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