Cryptography Reference
In-Depth Information
encryption scheme is to let an element of
G
,say
h
, be the public key of a user and
encrypt
m
as
h
r
m
, where
r
is a randomly chosen integer. This way a system similar
to the private-key scheme above is being used, with
a
h
r
which, as a consequence
of
r
being random, will “look random” to an adversary. However, this is not suffi-
cient because then the legitimate receiver would be unable to decrypt (as she does
not know
r
). Thus the system is modified in a way similar to the one used to build
a CPA secure encryption scheme from a trapdoor one-way family of permutations
with a hard-core predicate (as we have seen in
8.4.3
for the Blum-Williams family
of permutations). The idea is to give the receiver additional information that will
allow her to decrypt using her private key. The private key will be a positive integer
x
such that
h
=
g
x
, where
g
is a publicly known element of
G
(so that
x
will be hard
to recover from
h
assuming the DL problem is hard) and the additional information
that allows the receiver to recover the message is simply the element
g
r
=
∈
G
.More
explicitly, this leads to the encryption scheme that we now describe.
The scheme will operate on a finite group
G
of order
t
, which is usually taken
to be a cyclic group with generator
g
, so that
G
we assume that we have a specification of the group in which group elements are
represented by strings in such a way that it is easy to check whether a string represents
the identity element and whether two strings represent the same element. In addition,
the specification includes efficient algorithms to compute the string representing the
product of two elements or the inverse of an element, as well as the order of the
group. Moreover, we will assume that there is a PPT algorithm
Gen
G
that, on input
1
k
, outputs a (specification of a) cyclic group
G
of order
t
with len
=
g
(
)
=
t
k
and a
∈
generator
g
G
. It is often the case that
G
and
g
are the same for all users, so that
they are system parameters and the key generation algorithm will take them as given
inputs. The Elgamal encryption scheme is then defined as follows:
Definition 8.16
Elgamal
is the public-key encryption scheme
(
Gen
,
Enc
,
Dec
)
defined by the following algorithms:
Gen
: On input 1
k
•
run
Gen
G
to obtain
(
G
,
g
)
, where
G
is a finite group of order
g
x
.The
t
, with len
(
t
)
=
k
and
G
=
g
. Then choose
x
← Z
t
and compute
h
:=
public key is the 3-tuple
.If
G
and
g
are
regarded as system parameters, then the public key is simply
h
and the private key
is
x
.
(
G
,
g
,
h
)
and the private key is
(
G
,
g
,
x
)
•
Enc
: On input a public key
pk
=
(
G
,
g
,
h
)
and a message
m
∈
G
, choose a
random element
r
← Z
t
and compute the ciphertext:
g
r
h
r
m
c
:=
Enc
(
pk
,
m
)
=
(
,
)
∈
G
×
G
.
•
Dec
: On input a private key
sk
=
(
G
,
g
,
x
)
and a ciphertext
c
=
(
c
1
,
c
2
)
∈
G
,
compute the message:
c
−
x
1
:=
(
,
)
=
c
2
.
m
Dec
sk
c