Cryptography Reference
In-Depth Information
publicly known and shared by all users. Usually,
G
will be a subgroup of order
q
of
Z
p
, where
p
is also prime and
q
|
−
1. A good way to select such a group is to take
q
to be a sufficiently large Sophie Germain prime, so that
p
p
=
2
q
+
1 is a safe prime
and
G
=
QR
p
the subgroup of the quadratic residues modulo
p
which, as we know,
has order
q
. In what follows we will assume that
G
is of this form.
Another required ingredient is a collision resistant hash function
H
which outputs
elements of
Z
q
(so that we may assume that
H
outputs bit strings of length len
(
q
)
=
). Alternatively, a weaker concept may be used, namely a
universal one-
way family of hash functions
, meaning that it is infeasible for an adversary to choose
an input
x
, draw a random hash function
H
from the family, and then find a different
input
y
such that
H
log
2
(
q
)
.
In the following description we will assume that
G
is generated by an algorithm
Gen
G
on input a security parameter 1
k
(
x
)
=
H
(
y
)
) and
G
will be fixed as
a system parameter so its specification will not be explicitly included in the public
and private keys.
7
We will use generic notation for both the group operation (which
in case
G
is as described above is just multiplication modulo
p
) and the operations
in
(where
k
=
len
(
q
)
Z
q
involving the exponents that appear below (operations modulo
q
).
Definition 8.17
The
Cramer-Shoup
public-key encryption scheme
(
Gen
,
Enc
,
)
Dec
is defined by the following algorithms:
•
Gen
:
1. Choose randomelements
g
1
,
1 theywill be both generators
since
G
has prime order; observe that the probability of choosing 1 will be
negligible but it can be reduced to 0 by explicitly excluding it).
2. Choose, also uniformly at random, elements
x
1
,
g
2
←
G
(if they are
=
x
2
,
y
1
,
y
2
,
z
← Z
q
(
z
will play
a role similar to that of an Elgamal private key).
3. Compute
c
g
y
1
1
g
y
2
2
g
x
1
1
g
x
2
2
g
1
(
h
will be used like an Elgamal
=
,
d
=
and
h
=
public key).
4. Output the public key
(
g
1
,
g
2
,
c
,
d
,
h
,
H
)
and the private key
(
x
1
,
x
2
,
y
1
,
y
2
,
z
)
.
•
Enc
:Let
m
∈
G
be a message. The following operations are performed:
1. Choose a random element
r
← Z
q
.
2. Compute the following values:
g
1
,
u
1
:=
g
2
,
u
2
:=
h
r
m
e
:=
,
α
:=
H
(
u
1
||
u
2
||
e
),
c
r
d
r
α
.
v
:=
3. The ciphertext corresponding to the message
m
is then the 4-tuple
(
u
1
,
u
2
,
e
,
v
)
.
7
If the group
G
is generated by each user by calling
Gen
G
from the key generation algorithm, then
such a specification—for example, the parameters
p
,
q
which describe the group in case
G
=
QR
p
and
p
=
2
q
+
1—should be included in both the public and the private key.
