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

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

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