Английская Википедия:CEILIDH
Шаблон:Short description Шаблон:About
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.[1][2] The main advantage of the system is the reduced size of the keys for the same security over basic schemes.Шаблон:Which
Algorithms
Parameters
- Let <math>q</math> be a prime power.
- An integer <math>n</math> is chosen such that :
- The torus <math>T_n</math> has an explicit rational parametrization.
- <math>\Phi_n(q)</math> is divisible by a big prime <math>l</math> where <math>\Phi_n</math> is the <math>n^{th}</math> Cyclotomic polynomial.
- Let <math>m=\phi(n)</math> where <math>\phi</math> is the Euler function.
- Let <math>\rho : T_n(\mathbb{F}_q) \rightarrow {\mathbb{F}_q}^m</math> a birational map and its inverse <math>\psi</math>.
- Choose <math>\alpha \in T_n</math> of order <math>l</math> and let <math>g=\rho(\alpha)</math>.
Key agreement scheme
This Scheme is based on the Diffie-Hellman key agreement.
- Alice chooses a random number <math>a\ \pmod{\Phi_n(q)}</math>.
- She computes <math>P_A= \rho(\psi(g)^a) \in \mathbb{F}_q^m</math> and sends it to Bob.
- Bob chooses a random number <math>b\ \pmod{\Phi_n(q)}</math>.
- He computes <math>P_B= \rho(\psi(g)^b) \in \mathbb{F}_q^m</math> and sends it to Alice.
- Alice computes <math>\rho(\psi(P_B))^a) \in \mathbb{F}_q^m</math>
- Bob computes <math>\rho(\psi(P_A))^b) \in \mathbb{F}_q^m</math>
<math>\psi \circ \rho</math> is the identity, thus we have : <math>\rho(\psi(P_B))^a) = \rho(\psi(P_A))^b) = \rho(\psi(g)^{ab}) </math> 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 <math>a\ \pmod{ \Phi_n(q)}</math> as her private key.
- The resulting public key is <math>P_A= \rho(\psi(g)^a) \in \mathbb{F}_q^m</math>.
- Encryption
- The message <math>M</math> is an element of <math>\mathbb{F}_q^m</math>.
- Bob chooses a random integer <math>k</math> in the range <math>1\leq k \leq l-1</math>.
- Bob computes <math>\gamma = \rho(\psi(g)^k) \in \mathbb{F}_q^m</math> and <math>\delta = \rho(\psi(M)\psi(P_A)^k) \in \mathbb{F}_q^m</math>.
- Bob sends the ciphertext <math>(\gamma,\delta)</math> to Alice.
- Decryption
- Alice computes <math>M = \rho(\psi(\delta)\psi(\gamma)^{-a})</math>.
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 <math>G</math>, then the encryption function is one-way.[3] If the decisional Diffie-Hellman assumption (DDH) holds in <math>G</math>, then CEILIDH achieves semantic security.[3] Semantic security is not implied by the computational Diffie-Hellman assumption alone.[4] 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 <math>(c_1, c_2)</math> of some (possibly unknown) message <math>m</math>, one can easily construct a valid encryption <math>(c_1, 2 c_2)</math> of the message <math>2m</math>.
References
External links
- Torus-Based Cryptography: the paper introducing the concept (in PDF from Silverberg's university web page).
