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.

This article is about the cryptosystem. For the traditional Gaelic social gathering, see Céilidh.

Algorithms

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

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 ${\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}$.

References

1. Silverberg, Alice (November 2006). "Alice in NUMB3Rland" (PDF). Focus. Mathematical Association of America. Retrieved 12 July 2018.
2. Kirsch, Rachel (December 2010). "Cryptography: How to Keep a Secret". Mathematical Association of America. Retrieved 12 July 2018.
3. "El-gamal Encryption Scheme". CRYPTUTOR. Archived from the original on 2009-04-21. Retrieved 2009-04-21.
4. Abdalla, M.; Bellare, M.; Rogaway, P. (September 1998). "DHIES: An encryption scheme based on the Diffie-Hellman Problem (Appendix A)" (PDF). Cite journal requires |journal= (help)

• Rubin, K.; Silverberg, A. (2003). "Torus-Based Cryptography". In Boneh, D. (ed.). Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. 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).