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. The main advantage of the system is the reduced size of the keys for the same security over basic schemes.

Algorithms

Parameters
 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 scheme

This Scheme is based on the Diffie-Hellman key agreement.

 Alice chooses a random number .
 She computes  and sends it to Bob.
 Bob chooses 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 scheme

This scheme is based on the ElGamal encryption.

 Key Generation
 Alice chooses a random number  as her private key.
 The resulting public key is .
 Encryption
 The message  is an element of .
 Bob chooses a random integer  in the range .
 Bob computes  and .
 Bob sends the ciphertext  to Alice.
 Decryption
 Alice computes .

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 , then the encryption function is one-way. If the decisional Diffie-Hellman assumption (DDH) holds in , 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  of some (possibly unknown) message , one can easily construct a valid encryption  of the message .

References

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

Public-key encryption schemes
Key-agreement protocols