CEILIDH

This article is about the cryptosystem. For traditional Scottish and Irish social gathering, see Cèilidh.

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.

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^{\mathrm{t}\mathrm{h}}$ Cyclotomic polynomial.
• Let $m=\varphi (n)$ where $\varphi$ is the Euler function.
• Let $\rho :T_n({𝔽}_q)\to {{𝔽}_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(\mathrm{mod}{\Phi }_n(q))$.
• She computes $P_A=\rho (\psi (g{)}^a)\in {𝔽}_q^m$ and sends it to Bob.
• Bob chooses a random number $b(\mathrm{mod}{\Phi }_n(q))$.
• He computes $P_B=\rho (\psi (g{)}^b)\in {𝔽}_q^m$ and sends it to Alice.
• Alice computes $\rho (\psi (P_B{)}^a)\in {𝔽}_q^m$
• Bob computes $\rho (\psi (P_A{)}^b)\in {𝔽}_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(\mathrm{mod}{\Phi }_n(q))$ as her private key.
  • The resulting public key is $P_A=\rho (\psi (g{)}^a)\in {𝔽}_q^m$.
• Encryption
  • The message $M$ is an element of ${𝔽}_q^m$.
  • Bob chooses a random integer $k$ in the range $1\le k\le l-1$.
  • Bob computes $\gamma =\rho (\psi (g{)}^k)\in {𝔽}_q^m$ and $\delta =\rho (\psi (M)\psi (P_A{)}^k)\in {𝔽}_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$.

External links

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