World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0014050287
Reproduction Date:

Title: Ceilidh  
Author: World Heritage Encyclopedia
Language: English
Subject: Scottish country dance, Music of Ireland, Troyl, Irish dance, Reel (dance)
Publisher: World Heritage Encyclopedia


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 the system is the reduced size of the keys for the same security over 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 \rho : T_n(\mathbb{F}_q) \rightarrow {\mathbb{F}_q}^m a birational map and its inverse \psi.
  • Choose \alpha \in T_n of order l and let g=\rho(\alpha)).

Key agreement scheme

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

  • Alice chooses a random number a\ \pmod{\Phi_n(q)}.
  • She computes P_A= \rho(\psi(g)^a) \in \mathbb{F}_q^m and sends it to Bob.
  • Bob chooses a random number b\ \pmod{\Phi_n(q)}.
  • He computes P_B= \rho(\psi(g)^b) \in \mathbb{F}_q^m and sends it to Alice.
  • Alice computes \rho(\psi(P_B))^a) \in \mathbb{F}_q^m
  • Bob computes \rho(\psi(P_A))^b) \in \mathbb{F}_q^m

\psi \circ \phi is the identity, thus we have : \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 chooses a random number a\ \pmod{ \Phi_n(q)} as her private key.
    • The resulting public key is P_A= \rho(\psi(g)^a) \in \mathbb{F}_q^m.
  • Encryption
    • The message M is an element of \mathbb{F}_q^m.
    • Bob chooses a random integer k in the range 1\leq k \leq l-1.
    • Bob computes \gamma = \rho(\psi(g)^k) \in \mathbb{F}_q^m and \delta = \rho(\psi(M)\psi(P_A)^k) \in \mathbb{F}_q^m.
    • Bob sends the ciphertext (\gamma,\delta) to Alice.
  • Decryption
    • Alice computes M = \rho(\psi(\delta)\psi(\gamma)^{-a}).


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 G, then the encryption function is one-way.[1]

If the decisional Diffie-Hellman assumption (DDH) holds in 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 (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.

See also


  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).
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.