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 those schemes is the reduced size of the keys for the same security than the basic schemes.
The name CEILIDH comes from the Scots Gaelic word ceilidh which means a traditional Scottish Gathering.
AlgorithmsEdit
ParametersEdit
 Let be a prime power.
 An integer is chosen such that :
 The torus has an explicit rational parametrization.
 is divisible by a big prime where is the Cyclotomic polynomial.
 Let where is the Euler function.
 Let a birational map and its inverse .
 Choose of order and let .
Key agreement schemeEdit
This Scheme is based on the DiffieHellman key agreement.
 Alice choses a random number .
 She computes and sends it to Bob.
 Bob choses a random number .
 He computes and sends it to Alice.
 Alice computes
 Bob computes
is the identity, thus we have : which is the shared secret of Alice and Bob.
Encryption schemeEdit
This scheme is based on the ElGamal encryption.
 Key Generation
 Alice choses a random number as her private key.
 The resulting public key is .
 Encryption
 The message is an element of .
 Bob choses a random integer in the range .
 Bob computes and .
 Bob sends the ciphertext to Alice.
 Decryption
 Alice computes .
SecurityEdit
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 , then the encryption function is oneway^{[1]}.
If the decisional DiffieHellman assumption (DDH) holds in , 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 of some (possibly unknown) message , one can easily construct a valid encryption of the message .
See alsoEdit
ReferencesEdit
 ↑ ^{1.0} ^{1.1} CRYPTUTOR, "Elgamal encryption scheme"
 ↑ M. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the DiffieHellman Problem" (Appendix A)
 Karl Rubin, Alice Silverberg: TorusBased Cryptography. CRYPTO 2003: 349–365
External linksEdit
 TorusBased Cryptography — the paper introducing the concept (in PDF).
