# 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. The main advantage of the system is the reduced size of the keys for the same security over basic schemes.[which?]

## Algorithms

### Parameters

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

### Key agreement scheme

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

• Alice chooses a random number $a\ {\pmod {\Phi _{n}(q)}}$ .
• She computes $P_{A}=\rho (\psi (g)^{a})\in \mathbb {F} _{q}^{m}$ and sends it to Bob.
• Bob chooses a random number $b\ {\pmod {\Phi _{n}(q)}}$ .
• He computes $P_{B}=\rho (\psi (g)^{b})\in \mathbb {F} _{q}^{m}$ and sends it to Alice.
• Alice computes $\rho (\psi (P_{B}))^{a})\in \mathbb {F} _{q}^{m}$ • Bob computes $\rho (\psi (P_{A}))^{b})\in \mathbb {F} _{q}^{m}$ $\psi \circ \rho$ is the identity, thus we have : $\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 $a\ {\pmod {\Phi _{n}(q)}}$ as her private key.
• The resulting public key is $P_{A}=\rho (\psi (g)^{a})\in \mathbb {F} _{q}^{m}$ .
• Encryption
• The message $M$ is an element of $\mathbb {F} _{q}^{m}$ .
• Bob chooses a random integer $k$ in the range $1\leq k\leq l-1$ .
• Bob computes $\gamma =\rho (\psi (g)^{k})\in \mathbb {F} _{q}^{m}$ and $\delta =\rho (\psi (M)\psi (P_{A})^{k})\in \mathbb {F} _{q}^{m}$ .
• Bob sends the ciphertext $(\gamma ,\delta )$ to Alice.
• Decryption
• Alice computes $M=\rho (\psi (\delta )\psi (\gamma )^{-a})$ .

## Security

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 $G$ , then the encryption function is one-way. If the decisional Diffie-Hellman assumption (DDH) holds in $G$ , then CEILIDH achieves semantic security. Semantic security is not implied by the computational Diffie-Hellman assumption alone. 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 $(c_{1},c_{2})$ of some (possibly unknown) message $m$ , one can easily construct a valid encryption $(c_{1},2c_{2})$ of the message $2m$ .