Cryptography Reference
In-Depth Information
The proof of security hinges (among other things) on the following result.
∈
=
Lemma 23.2.1
Let Gbe a group of prime order r. Let g
1
,g
2
,u
1
,u
2
,h
Gwith
(
g
1
,g
2
)
(1
,
1)
. Consider the set
g
z
1
g
z
2
}
)
2
X
g
1
,g
2
,h
={
(
z
1
,z
2
)
∈
(
Z
/r
Z
:
h
=
.
g
1
.Ifu
2
=
g
2
then u
z
1
u
z
2
=
X
g
1
,g
2
,h
=
≤
k<rbe such that u
1
=
h
k
for
Then
#
r. Let
0
g
2
then
all
(
z
1
,z
2
)
∈
X
g
1
,g
2
,h
.Ifu
2
=
u
z
1
u
z
2
{
:(
z
1
,z
2
)
∈
X
g
1
,g
2
,h
}=
G.
Exercise 23.2.2
Prove Lemma
23.2.1
.
Box
23.3
presents the basic
Cramer-Shoup encryption scheme
. The scheme requires
a group
G
of prime order
r
and the message
m
is assumed to be an element of
G
. Of course,
it is not necessary to “encode” data into group elements, in practice one would use the
Cramer-Shoup scheme as a KEM; we briefly describe a Cramer-Shoup KEM at the end of
this section. The scheme requires a target collision resistant hash function
H
:
G
3
→ Z
/r
Z
(see Definition
3.1.2
) chosen at random from a hash family.
KeyGen
(
κ
): Generate a group
G
of prime order
r
as in Box
23.1
. Choose random
g
1
,g
2
∈
G
−{
1
}
. Choose integers 0
≤
x
1
,x
2
,y
1
,y
2
,z
1
,z
2
<r
uniformly at random and set
c
=
g
x
1
g
x
2
,d
=
g
y
1
g
y
2
,h
=
g
z
1
g
z
2
.
Choose a target collision resistant hash function
H
. The public key is
pk
=
(
G,H,g
1
,g
2
,c,d,h
). The private key is
sk
=
(
x
1
,x
2
,y
1
,y
2
,z
1
,z
2
).
Encrypt
(
m
,
pk
): Choose 0
≤
k<r
uniformly at random, compute
u
1
=
g
1
,u
2
=
g
2
,e
=
h
k
m
,α
=
H
(
u
1
,u
2
,e
)and
v
=
c
k
d
kα
(mod
r
)
. The ciphertext is
c
=
(
u
1
,u
2
,e,v
).
Decrypt
(
u
1
,u
2
,e,v,
sk
): First check that
u
1
,u
2
,e
∈
G
and output
⊥
if this is not the case.
Next, compute
α
=
H
(
u
1
,u
2
,e
) and check whether
v
=
u
x
1
+
y
1
α
(mod
r
)
1
u
x
2
+
y
2
α
(mod
r
)
2
.
(23.1)
Return
⊥
if this condition does not hold. Otherwise output
=
eu
−
z
1
u
−
z
2
.
m
Box 23.3
Basic Cramer-Shoup encryption scheme
=
c
k
d
kα
computed in the Encrypt algorithm does
Exercise 23.2.3
Show that the value
v
satisfy equation (
23.1
).
Exercise 23.2.4
Show that the tests
u
1
,u
2
∈
G
and equation (
23.1
) imply that
v
∈
G
.
