CEILIDH

CEILIDH is a public key cryptosystem based on the discrete logarithm problem in algebraic torus. This idea was first introduced by Alice Silverberg and Karl Rubin in 2003; Silverberg named CEILIDH after her cat.^[1][2] The main advantage of the system is the reduced size of the keys for the same security over basic schemes.^[which?]

• 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 )}$.

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.

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

The CEILIDH scheme is based on the ElGamal scheme and thus has similar security properties.

If the computational Diffie-Hellman assumption holds the underlying cyclic group ${\displaystyle G}$, then the encryption function is one-way.^[3] If the decisional Diffie-Hellman assumption (DDH) holds in ${\displaystyle G}$, then CEILIDH achieves semantic security.^[3] Semantic security is not implied by the computational Diffie-Hellman assumption alone.^[4] See decisional Diffie-Hellman assumption for a discussion of groups where the assumption is believed to hold.

CEILIDH encryption is unconditionally malleable, and therefore is not secure under chosen ciphertext attack. For example, given an encryption ${\displaystyle (c_{1},c_{2})}$ of some (possibly unknown) message ${\displaystyle m}$, one can easily construct a valid encryption ${\displaystyle (c_{1},2c_{2})}$ of the message ${\displaystyle 2m}$.

• Rubin, K.; Silverberg, A. (2003). "Torus-Based Cryptography". In Boneh, D. (ed.). Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Vol. 2729. Springer, Berlin, Heidelberg. pp. 349–365. doi:10.1007/978-3-540-45146-4_21. ISBN 9783540406747.

• Torus-Based Cryptography: the paper introducing the concept (in PDF from Silverberg's university web page).