Parameters

• Let ${\displaystyle q}$ be a prime power.
• An integer ${\displaystyle n}$ is chosen such that :
  • The torus ${\displaystyle T_{n}}$ has an explicit rational parametrization.
  • ${\displaystyle \Phi _{n}(q)}$ is divisible by a big prime ${\displaystyle l}$ where ${\displaystyle \Phi _{n}}$ is the ${\displaystyle n^{th}}$ Cyclotomic polynomial.
• Let ${\displaystyle m=\phi (n)}$ where ${\displaystyle \phi }$ is the Euler function.
• Let ${\displaystyle \rho :T_{n}(\mathbb {F} _{q})\rightarrow {\mathbb {F} _{q}}^{m}}$ a birational map and its inverse ${\displaystyle \psi }$.
• Choose ${\displaystyle \alpha \in T_{n}}$ of order ${\displaystyle l}$ and let ${\displaystyle g=\rho (\alpha )}$.

Key agreement scheme

This Scheme is based on the Diffie-Hellman key agreement.

• Alice chooses a random number ${\displaystyle a\ {\pmod {\Phi _{n}(q)}}}$.
• She computes ${\displaystyle P_{A}=\rho (\psi (g)^{a})\in \mathbb {F} _{q}^{m}}$ and sends it to Bob.
• Bob chooses a random number ${\displaystyle b\ {\pmod {\Phi _{n}(q)}}}$.
• He computes ${\displaystyle P_{B}=\rho (\psi (g)^{b})\in \mathbb {F} _{q}^{m}}$ and sends it to Alice.
• Alice computes ${\displaystyle \rho (\psi (P_{B}))^{a})\in \mathbb {F} _{q}^{m}}$
• Bob computes ${\displaystyle \rho (\psi (P_{A}))^{b})\in \mathbb {F} _{q}^{m}}$

${\displaystyle \psi \circ \rho }$ is the identity, thus we have : ${\displaystyle \rho (\psi (P_{B}))^{a})=\rho (\psi (P_{A}))^{b})=\rho (\psi (g)^{ab})}$ which is the shared secret of Alice and Bob.

Encryption scheme

This scheme is based on the ElGamal encryption.

• Key Generation
  • Alice chooses a random number ${\displaystyle a\ {\pmod {\Phi _{n}(q)}}}$ as her private key.
  • The resulting public key is ${\displaystyle P_{A}=\rho (\psi (g)^{a})\in \mathbb {F} _{q}^{m}}$.
• Encryption
  • The message ${\displaystyle M}$ is an element of ${\displaystyle \mathbb {F} _{q}^{m}}$.
  • Bob chooses a random integer ${\displaystyle k}$ in the range ${\displaystyle 1\leq k\leq l-1}$.
  • Bob computes ${\displaystyle \gamma =\rho (\psi (g)^{k})\in \mathbb {F} _{q}^{m}}$ and ${\displaystyle \delta =\rho (\psi (M)\psi (P_{A})^{k})\in \mathbb {F} _{q}^{m}}$.
  • Bob sends the ciphertext ${\displaystyle (\gamma ,\delta )}$ to Alice.
• Decryption
  • Alice computes ${\displaystyle M=\rho (\psi (\delta )\psi (\gamma )^{-a})}$.