Cryptosystem
This article is about the cryptosystem. For traditional Scottish and Irish social gathering, see
Cèilidh .
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
{\displaystyle q}
be a prime power.
An integer
n
{\displaystyle n}
is chosen such that :
The torus
T
n
{\displaystyle T_{n}}
has an explicit rational parametrization.
Φ Φ -->
n
(
q
)
{\displaystyle \Phi _{n}(q)}
is divisible by a big prime
l
{\displaystyle l}
where
Φ Φ -->
n
{\displaystyle \Phi _{n}}
is the
n
t
h
{\displaystyle n^{th}}
Cyclotomic polynomial .
Let
m
=
ϕ ϕ -->
(
n
)
{\displaystyle m=\phi (n)}
where
ϕ ϕ -->
{\displaystyle \phi }
is the Euler function .
Let
ρ ρ -->
:
T
n
(
F
q
)
→ → -->
F
q
m
{\displaystyle \rho :T_{n}(\mathbb {F} _{q})\rightarrow {\mathbb {F} _{q}}^{m}}
a birational map and its inverse
ψ ψ -->
{\displaystyle \psi }
.
Choose
α α -->
∈ ∈ -->
T
n
{\displaystyle \alpha \in T_{n}}
of order
l
{\displaystyle l}
and let
g
=
ρ ρ -->
(
α α -->
)
{\displaystyle g=\rho (\alpha )}
.
Key agreement scheme
This Scheme is based on the Diffie-Hellman key agreement .
Alice chooses a random number
a
(
mod
Φ Φ -->
n
(
q
)
)
{\displaystyle a\ {\pmod {\Phi _{n}(q)}}}
.
She computes
P
A
=
ρ ρ -->
(
ψ ψ -->
(
g
)
a
)
∈ ∈ -->
F
q
m
{\displaystyle P_{A}=\rho (\psi (g)^{a})\in \mathbb {F} _{q}^{m}}
and sends it to Bob.
Bob chooses a random number
b
(
mod
Φ Φ -->
n
(
q
)
)
{\displaystyle b\ {\pmod {\Phi _{n}(q)}}}
.
He computes
P
B
=
ρ ρ -->
(
ψ ψ -->
(
g
)
b
)
∈ ∈ -->
F
q
m
{\displaystyle P_{B}=\rho (\psi (g)^{b})\in \mathbb {F} _{q}^{m}}
and sends it to Alice.
Alice computes
ρ ρ -->
(
ψ ψ -->
(
P
B
)
)
a
)
∈ ∈ -->
F
q
m
{\displaystyle \rho (\psi (P_{B}))^{a})\in \mathbb {F} _{q}^{m}}
Bob computes
ρ ρ -->
(
ψ ψ -->
(
P
A
)
)
b
)
∈ ∈ -->
F
q
m
{\displaystyle \rho (\psi (P_{A}))^{b})\in \mathbb {F} _{q}^{m}}
ψ ψ -->
∘ ∘ -->
ρ ρ -->
{\displaystyle \psi \circ \rho }
is the identity, thus we have :
ρ ρ -->
(
ψ ψ -->
(
P
B
)
)
a
)
=
ρ ρ -->
(
ψ ψ -->
(
P
A
)
)
b
)
=
ρ ρ -->
(
ψ ψ -->
(
g
)
a
b
)
{\displaystyle \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
(
mod
Φ Φ -->
n
(
q
)
)
{\displaystyle a\ {\pmod {\Phi _{n}(q)}}}
as her private key.
The resulting public key is
P
A
=
ρ ρ -->
(
ψ ψ -->
(
g
)
a
)
∈ ∈ -->
F
q
m
{\displaystyle P_{A}=\rho (\psi (g)^{a})\in \mathbb {F} _{q}^{m}}
.
Encryption
The message
M
{\displaystyle M}
is an element of
F
q
m
{\displaystyle \mathbb {F} _{q}^{m}}
.
Bob chooses a random integer
k
{\displaystyle k}
in the range
1
≤ ≤ -->
k
≤ ≤ -->
l
− − -->
1
{\displaystyle 1\leq k\leq l-1}
.
Bob computes
γ γ -->
=
ρ ρ -->
(
ψ ψ -->
(
g
)
k
)
∈ ∈ -->
F
q
m
{\displaystyle \gamma =\rho (\psi (g)^{k})\in \mathbb {F} _{q}^{m}}
and
δ δ -->
=
ρ ρ -->
(
ψ ψ -->
(
M
)
ψ ψ -->
(
P
A
)
k
)
∈ ∈ -->
F
q
m
{\displaystyle \delta =\rho (\psi (M)\psi (P_{A})^{k})\in \mathbb {F} _{q}^{m}}
.
Bob sends the ciphertext
(
γ γ -->
,
δ δ -->
)
{\displaystyle (\gamma ,\delta )}
to Alice.
Decryption
Alice computes
M
=
ρ ρ -->
(
ψ ψ -->
(
δ δ -->
)
ψ ψ -->
(
γ γ -->
)
− − -->
a
)
{\displaystyle 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
{\displaystyle G}
, then the encryption function is one-way .[3] If the decisional Diffie-Hellman assumption (DDH) holds in
G
{\displaystyle 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
)
{\displaystyle (c_{1},c_{2})}
of some (possibly unknown) message
m
{\displaystyle m}
, one can easily construct a valid encryption
(
c
1
,
2
c
2
)
{\displaystyle (c_{1},2c_{2})}
of the message
2
m
{\displaystyle 2m}
.
References
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
Algorithms
Theory Standardization Topics