This article is about the cryptosystem. For the traditional Gaelic 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. The main advantage of the system is the reduced size of the keys for the same security over basic schemes.^{["which?]}
The name CEILIDH comes from the Scots Gaelic word "ceilidh which means a traditional Scottish Gathering.
Algorithms[edit]
Parameters[edit]
 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[edit]
This Scheme is based on the "DiffieHellman 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[edit]
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 l1$.
 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[edit]
The CEILIDH scheme is based on the ElGamal scheme and thus has similar security properties.
If the "computational DiffieHellman assumption holds the underlying cyclic group $G$, then the encryption function is "oneway.^{[1]}
If the "decisional DiffieHellman assumption (DDH) holds in $G$, then CEILIDH achieves "semantic security.^{[1]} Semantic security is not implied by the computational DiffieHellman assumption alone.^{[2]} See "decisional DiffieHellman 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$.
See also[edit]
References[edit]
 Karl Rubin, Alice Silverberg: TorusBased Cryptography. CRYPTO 2003: 349–365
External links[edit]

Algorithms 

Theory 

Standardization 

Topics 




)
)