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

• be a prime power.

An integer is chosen such that :

• has an explicit rational parametrization.

• Cyclotomic polynomial.

• is the Euler function.

• .

• .

Key agreement scheme

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

• .

• and sends it to Bob.

• .

• and sends it to Alice.

, which is the shared secret of Alice and Bob.

Encryption scheme

This scheme is based on the ElGamal encryption.

Key Generation

• as her private key.

• .

Encryption

• .

• .

• .

• to Alice.

Decryption

• .

Security

The CEILIDH scheme is based on the ElGamal scheme and thus has similar security properties.

If the computational Diffie-Hellman assumption, then the encryption function is one-way. If the decisional Diffie-Hellman assumption, 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.

References

External links

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