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.



* 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 ho : T_n(mathbb{F}_q) ightarrow {mathbb{F}_q}^m a birational map and its inverse psi.
* Choose alpha in T_n of order l and let g= ho(alpha)).

Key agreement scheme

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

* Alice choses a random number a pmod{Phi_n(q)}.
* She computes P_A= ho(psi(g)^a) in mathbb{F}_q^m and sends it to Bob.

* Bob choses a random number b pmod{Phi_n(q)}.
* He computes P_B= ho(psi(g)^b) in mathbb{F}_q^m and sends it to Alice.

* Alice computes ho(psi(P_B))^a) in mathbb{F}_q^m
* Bob computes ho(psi(P_A))^b) in mathbb{F}_q^m

psi o phi is the identity, thus we have : ho(psi(P_B))^a) = ho(psi(P_A))^b) = ho(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 a pmod{ Phi_n(q)} as her private key.
** The resulting public key is P_A= ho(psi(g)^a) in mathbb{F}_q^m.

* Encryption
** The message M is an element of mathbb{F}_q^m.
** Bob choses a random integer k in the range 1leq k leq l-1.
** Bob computes gamma = ho(psi(g)^k) in mathbb{F}_q^m and delta = ho(psi(M)psi(P_A)^k) in mathbb{F}_q^m.
** Bob sends the ciphertext (gamma,delta) to Alice.

* Decryption
** Alice computes M = ho(psi(delta)psi(gamma)^{-a}).


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 G, then the encryption function is one-way"CRYPTUTOR", " [http://crypto.cs.uiuc.edu/wiki/index.php/Elgamal_encryption_scheme Elgamal encryption scheme] "] .

If the decisional Diffie-Hellman assumption (DDH) holds in G, thenCEILIDH achieves semantic security. Semantic security is not implied by the computational Diffie-Hellman assumption aloneM. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the Diffie-Hellman Problem" (Appendix A)] . 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 (c_1, c_2) of some (possibly unknown) message m, one can easily construct a valid encryption (c_1, 2 c_2) of the message 2m.


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

External links

* [http://www.math.uci.edu/~asilverb/bibliography/ceilidh.pdf Torus-Based Cryptography] — the paper introducing the concept (in PDF).

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Céilidh — Saltar a navegación, búsqueda Una céilidh (pronunciación irlandesa: /ˈceːlʲiː/), en el sentido actual de la palabra, es una danza tradicional gaélica procedente de Irlanda y Escocia, aunque hoy en día es muy común en muchos otros países con… …   Wikipedia Español

  • CEILIDH — криптосистема с открытым ключом, в основе которой лежат задачи дискретного логарифмирования и алгебраические группы. Впервые эта идея была предложена Алисой Силверберг и Карлом Рубин в 2003 году. Главное преимущество схемы уменьшенный размер… …   Википедия

  • ceilidh — 1875, from Ir. ceilidhe, from O.Ir. cele companion …   Etymology dictionary

  • ceilidh — ► NOUN ▪ a social event with Scottish or Irish folk music and singing, traditional dancing, and storytelling. ORIGIN Old Irish céilide visit, visiting …   English terms dictionary

  • Céilidh — In modern usage, a céilidh or ceilidh (English pronunciation: /ˈkeɪlɪ/) is a traditional Gaelic social gathering, which usually involves playing Gaelic folk music and dancing. It originated in Ireland, but is now common throughout the Irish and… …   Wikipedia

  • ceilidh — UK [ˈkeɪlɪ] / US noun [countable] Word forms ceilidh : singular ceilidh plural ceilidhs a social event at which people sing and dance to traditional Scottish or Irish music …   English dictionary

  • ceilidh — also ceili noun Etymology: Irish céilí & Scottish Gaelic cèilidh visit, social evening, party with music and dancing, from Old Irish céilide visit, from céile servant, companion, neighbor; akin to Welsh cilydd companion, Old Breton kiled Date:… …   New Collegiate Dictionary

  • ceilidh — /kay lee/, n. Irish, Scot., and Canadian (chiefly Prince Edward Island). a party, gathering, or the like, at which singing and storytelling are the usual forms of entertainment. [ < Ir céilidhe, ScotGael cèilidh, MIr célide, deriv. of OIr céile… …   Universalium

  • ceilidh — [[t]ke͟ɪli[/t]] ceilidhs N COUNT A ceilidh is an informal entertainment, especially in Scotland or Ireland, at which there is folk music, singing, and dancing …   English dictionary

  • ceilidh — [ keɪli] noun a social event with Scottish or Irish folk music and singing, traditional dancing, and storytelling. Origin C19: from Sc. Gaelic ceilidh and Ir. célidhe (earlier form of céilí), from Old Ir. céilide visit, visiting , from céile… …   English new terms dictionary