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 {th} }$ Cyclotomic polynomial.
• Let $m=\phi (n)$ where $\phi$ is the Euler function.
• Let $\rho \colon 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$.

References

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

External links

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