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

Algorithms

Parameters

• Let Failed to parse (Missing texvc executable; please see math/README to configure.): q

be a prime power.

• An integer Failed to parse (Missing texvc executable; please see math/README to configure.): n

is chosen  such that :

• • The torus Failed to parse (Missing texvc executable; please see math/README to configure.): T_n

has an explicit rational parametrization.

• • Failed to parse (Missing texvc executable; please see math/README to configure.): \Phi_n(q)

is divisible by a big prime Failed to parse (Missing texvc executable; please see math/README to configure.): l
where Failed to parse (Missing texvc executable; please see math/README to configure.): \Phi_n
is the Failed to parse (Missing texvc executable; please see math/README to configure.): n^{th}
Cyclotomic polynomial.

• Let Failed to parse (Missing texvc executable; please see math/README to configure.): m=\phi(n)

where Failed to parse (Missing texvc executable; please see math/README to configure.): \phi
is the Euler function.

• Let Failed to parse (Missing texvc executable; please see math/README to configure.): \rho : T_n(\mathbb{F}_q) \rightarrow {\mathbb{F}_q}^m

a birationnal map and its inverse Failed to parse (Missing texvc executable; please see math/README to configure.): \psi

.

• Choose Failed to parse (Missing texvc executable; please see math/README to configure.): \alpha \in T_n

of order Failed to parse (Missing texvc executable; please see math/README to configure.): l
and let Failed to parse (Missing texvc executable; please see math/README to configure.): g=\rho(\alpha))

.

Key agreement scheme

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

• Alice choses a random number Failed to parse (Missing texvc executable; please see math/README to configure.): a\ \pmod{\Phi_n(q)}

.

• She computes Failed to parse (Missing texvc executable; please see math/README to configure.): P_A= \rho(\psi(g)^a) \in \mathbb{F}_q^m

and sends it to Bob.

• Bob choses a random number Failed to parse (Missing texvc executable; please see math/README to configure.): b\ \pmod{\Phi_n(q)}

.

• He computes Failed to parse (Missing texvc executable; please see math/README to configure.): P_B= \rho(\psi(g)^b) \in \mathbb{F}_q^m

and sends it to Alice.

• Alice computes Failed to parse (Missing texvc executable; please see math/README to configure.): \rho(\psi(P_B))^a) \in \mathbb{F}_q^m

• Bob computes Failed to parse (Missing texvc executable; please see math/README to configure.): \rho(\psi(P_A))^b) \in \mathbb{F}_q^m

Failed to parse (Missing texvc executable; please see math/README to configure.): \psi o \phi

is the identity, thus we have : 

Failed to parse (Missing texvc executable; please see math/README to configure.): \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 choses a random number Failed to parse (Missing texvc executable; please see math/README to configure.): a\ \pmod{ \Phi_n(q)}

as her private key.

• • The resulting public key is Failed to parse (Missing texvc executable; please see math/README to configure.): P_A= \rho(\psi(g)^a) \in \mathbb{F}_q^m

.

• Encryption
  • The message Failed to parse (Missing texvc executable; please see math/README to configure.): M

is an element of Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{F}_q^m

.

• • Bob choses a random integer Failed to parse (Missing texvc executable; please see math/README to configure.): k

in the range Failed to parse (Missing texvc executable; please see math/README to configure.): 1\leq k \leq l-1

.

• • Bob computes Failed to parse (Missing texvc executable; please see math/README to configure.): \gamma = \rho(\psi(g)^k) \in \mathbb{F}_q^m

and Failed to parse (Missing texvc executable; please see math/README to configure.): \delta = \rho(\psi(M)\psi(P_A)^k) \in \mathbb{F}_q^m

.

• • Bob sends the ciphertext Failed to parse (Missing texvc executable; please see math/README to configure.): (\gamma,\delta)

to Alice.

• Decryption
  • Alice computes Failed to parse (Missing texvc executable; please see math/README to configure.): M = \rho(\psi(\delta)\psi(\gamma)^{-a})

.

Security

CEILIDH scheme is base on ElGamal scheme and thus is based on the same security properties.

If the computational Diffie-Hellman assumption holds the underlying cyclic group Failed to parse (Missing texvc executable; please see math/README to configure.): G , then the encryption function is one-way^[1].

If the decisional Diffie-Hellman assumption (DDH) holds in Failed to parse (Missing texvc executable; please see math/README to configure.): G , then CEILIDH achieves semantic security.^[1] Semantic security is not implied by the computational Diffie-Hellman assumption alone^[2]. 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 Failed to parse (Missing texvc executable; please see math/README to configure.): (c_1, c_2)

of some (possibly unknown) message Failed to parse (Missing texvc executable; please see math/README to configure.): m

, one can easily construct a valid encryption Failed to parse (Missing texvc executable; please see math/README to configure.): (c_1, 2 c_2)

of the message Failed to parse (Missing texvc executable; please see math/README to configure.): 2m

.

References

1. ^ ^{a b} CRYPTUTOR, "Elgamal encryption scheme"
2. ^ M. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the Diffie-Hellman Problem" (Appendix A)

• Karl Rubin, Alice Silverberg: Torus-Based Cryptography. CRYPTO 2003: 349–365

External links

• Torus-Based Cryptography — the paper introducing the concept (in PDF).