Cryptography Reference
In-Depth Information
Exercise 23.2.5
Show that the final stage of Decrypt in the Cramer-Shoup scheme can be
efficiently performed using multi-exponentiation as
eu
r
−
z
1
1
u
r
−
z
2
2
=
.
m
F
p
.
Example 23.2.6
Let
p
=
311,
r
=
31 and denote by
G
the subgroup of order
r
in
Take
g
1
=
169 and
g
2
=
121. Suppose (
x
1
,x
2
,y
1
,y
2
,z
1
,z
2
)
=
(1
,
2
,
3
,
4
,
5
,
6) so that the
public key is
(
g
1
,g
2
,c,d,h
)
=
(169
,
121
,
13
,
260
,
224)
.
g
1
=
g
2
=
To encrypt
m
=
265
∈
G
choose, say,
k
=
15 and set
u
1
=
24
,u
2
=
113 and
m
h
k
e
126. Finally, we must compute
α
. Since we do not want to get into the details
of
H
, suppose
α
=
=
c
k
d
kα
(mod
r
)
c
15
d
21
=
H
(
u
1
,u
2
,e
)
=
20 and so set
v
=
=
=
89. The
ciphertext is (
u
1
,u
2
,e,v
)
(24
,
113
,
126
,
89).
To decrypt, one first checks that
u
r
1
=
=
u
r
2
=
e
r
=
1. Then one recomputes
α
and checks
equation (
23.1
). Since
u
x
1
+
y
1
α
(mod
r
)
1
u
x
2
+
y
2
α
(mod
r
)
2
u
3
1
u
2
2
=
=
89
the ciphertext passes this test. One then computes
eu
r
−
z
1
u
r
−
z
2
24
26
113
25
=
126
·
·
=
265.
2
Exercise 23.2.7
Using the same private keys as Example
23.2.6
, which of the following
ciphertexts are valid, and for those that are, what is the corresponding message? Assume
that
H
(243
,
83
,
13)
=
2.
(243
,
83
,
13
,
97)
,
(243
,
83
,
13
,
89)
,
(243
,
83
,
13
,
49)
.
We now turn to the security analysis. Note that the condition of equation (
23.1
) does
not imply that the ciphertext (
u
1
,u
2
,e,v
) was actually produced by the Encrypt algorithm.
However, we now show that, if
u
1
and
u
2
are not of the correct form, then the probability
that a randomly chosen
v
satisfies this condition is 1
/r
. Indeed, Lemma
23.2.8
shows that
an adversary who can solve the discrete logarithm problem cannot even construct an invalid
ciphertext that satisfies this equation with probability better than 1
/r
.
Lemma 23.2.8
Let G be a cyclic group of prime order r. Let g
1
,g
2
,c,d,v
∈
G and
g
k
+
k
2
g
1
and u
2
=
where k
≡
α
∈ Z
/r
Z
be fixed. Suppose u
1
=
0(mod
r
)
. Then the
g
y
1
g
y
2
, that
g
x
1
g
x
2
2
and d
=
=
probability, over all choices
(
x
1
,x
2
,y
1
,y
2
)
such that c
u
x
1
+
αy
1
1
u
x
2
+
αy
2
2
=
v
is
1
/r.
g
w
1
1
g
w
2
1
g
1
,c
Proof
Write
g
2
=
=
and
d
=
for some 0
≤
w,w
1
,w
2
<r
with
w
=
0. The
w
2
.Now
u
x
1
+
αy
1
u
x
2
+
αy
2
2
values
c
and
d
imply that
x
1
+
wx
2
=
w
1
and
y
1
+
wy
2
=
equals
1
g
1
to the power
k
)
w
(
x
2
+
k
w
(
x
2
+
k
(
x
1
+
αy
1
)
+
(
k
+
αy
2
)
=
k
((
x
1
+
wx
2
)
+
α
(
y
1
+
wy
2
))
+
αy
2
)
k
w
(
x
2
+
=
k
(
w
1
+
αw
2
)
+
αy
2
)
.
