CEILIDH: Information from Answers.com

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.

1 Algorithms
2 Security
3 See also
4 References
5 External links

Algorithms

Parameters

Let $q$ be a prime power.
An integer n is chosen such that :
- The torus $T n$ has an explicit rational parametrization.
- $Φ n (q)$ is divisible by a big prime $l$ where $Φ n$ is the $n t h$ Cyclotomic polynomial.
Let $m = φ(n)$ where $φ$ is the Euler function.
Let $\rho : T_n(\mathbb{F}_q) \rightarrow {\mathbb{F}_q}^m$ a birational map and its inverse $ψ$ .
Choose $\alpha \in T_n$ of order $l$ and let $g = ρ(α))$ .

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= \rho(\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= \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$

$ψ o φ$ is the identity, thus we have : $ρ(ψ(P B)) a) = ρ(ψ(P A)) b) = ρ(ψ(g) a b)$ 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= \rho(\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 $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 $(γ,δ)$ to Alice.

Decryption
- Alice computes $M = ρ(ψ(δ)ψ(γ) - a)$ .

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 $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 $2 m$ .

References

^ ^a ^b CRYPTUTOR, "Elgamal encryption scheme"
^ 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).

v • d • e Public-key cryptography

Algorithms: Benaloh \| Blum-Goldwasser \| Cayley–Purser \| CEILIDH \| Cramer-Shoup \| Damgaard-Jurik \| DH \| DSA \| EPOC \| ECDH \| ECDSA \| EKE \| ElGamal encryption \| ElGamal signature scheme \| GMR \| Goldwasser-Micali \| HFE \| IES \| Lamport \| McEliece \| Merkle-Hellman \| MQV \| Naccache-Stern \| NTRUEncrypt \| NTRUSign \| Paillier \| Rabin \| RSA \| Okamoto-Uchiyama \| Schnorr \| SPEKE \| SRP \| STS \| Three-pass protocol \| XTR

Theory: Discrete logarithm \| Elliptic curve cryptography \| RSA problem

Standardization: ANS X9F1 \| CRYPTREC \| IEEE P1363 \| NESSIE \| NSA Suite B

Misc: Digital signature \| Fingerprint \| PKI \| Web of trust \| Key size

v • d • e Cryptography

History of cryptography · Cryptanalysis · Cryptography portal · Outline of cryptography

Symmetric-key algorithm · Block cipher · Stream cipher · Public-key cryptography · Cryptographic hash function · Message authentication code · Random numbers · Steganography

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	ceilidh
	Ceilidh Band Music: Celtic Collections, Vol. 3 (2001 Album by Various Artists)
	Celtic Pride, Vol. 2 (1997 Album by Various Artists)

	What is a ceilidh? Read answer...
	Is the Gaelic word Ceilidh Irish or Scots? Read answer...

	What is the biggest childrens ceilidh dance in Scotland?
	What is the history of Ceilidh dancing?
	When was Ceilidh dancing invented?

CEILIDH

Contents