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; 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 $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 \rho$ 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})$ .

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.^[3] If the decisional Diffie-Hellman assumption (DDH) holds in $G$ , 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 $(c_{1},c_{2})$ of some (possibly unknown) message $m$ , one can easily construct a valid encryption $(c_{1},2c_{2})$ of the message $2m$ .

References

^ Silverberg, Alice (November 2006). "Alice in NUMB3Rland" (PDF). Focus. Mathematical Association of America. Retrieved 12 July 2018.
^ Kirsch, Rachel (December 2010). "Cryptography: How to Keep a Secret". Mathematical Association of America. Retrieved 12 July 2018.
^ ^a ^b "El-gamal Encryption Scheme". CRYPTUTOR. Archived from the original on 2009-04-21. Retrieved 2009-04-21.
^ Abdalla, M.; Bellare, M.; Rogaway, P. (September 1998). "DHIES: An encryption scheme based on the Diffie-Hellman Problem (Appendix A)" (PDF).

Rubin, K.; Silverberg, A. (2003). "Torus-Based Cryptography". In Boneh, D. (ed.). Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Vol. 2729. Springer, Berlin, Heidelberg. pp. 349–365. doi:10.1007/978-3-540-45146-4_21. ISBN 9783540406747.

External links

Torus-Based Cryptography: the paper introducing the concept (in PDF from Silverberg's university web page).

[1] Silverberg, Alice (November 2006). "Alice in NUMB3Rland" (PDF). Focus. Mathematical Association of America. Retrieved 12 July 2018.

[maa-2] Kirsch, Rachel (December 2010). "Cryptography: How to Keep a Secret". Mathematical Association of America. Retrieved 12 July 2018.

[cryptutor-3] "El-gamal Encryption Scheme". CRYPTUTOR. Archived from the original on 2009-04-21. Retrieved 2009-04-21.

[DHAES-4] Abdalla, M.; Bellare, M.; Rogaway, P. (September 1998). "DHIES: An encryption scheme based on the Diffie-Hellman Problem (Appendix A)" (PDF).

[1]

[2]

[3]

[4]

Fahrer / Team für die Suche eingeben: