Cryptography Reference
In-Depth Information
Let
κ
be a security parameter. The scheme requires a symmetric encryption scheme, a
MAC scheme and a key derivation function. The symmetric encryption functions
Enc
and
Dec
take an
l
1
-bit key and encrypt messages of arbitrary length. The MAC function
MAC
takes an
l
2
-bit key and a message of arbitrary length and outputs an
l
3
-bit binary string.
The key derivation function is a function
kdf
:
G
l
1
+
l
2
. The values
l
1
,
l
2
and
l
3
depend on the security parameter. Note that it is important that the MAC is evaluated on
the ciphertext not the message, since a MAC is not required to have any confidentiality
properties. The DHIES encryption scheme is given in Box
23.1
.
→{
0
,
1
}
KeyGen
(
κ
): Generate an algebraic group or algebraic group quotient
G
whose order is
divisible by a large prime
r
(so that the discrete logarithm problem in the subgroup of prime
order
r
requires at least 2
κ
bit operations).
Choose a random
g
∈
G
of exact order
r
. Choose a random integer 0
<a<r
and set
h
=
g
a
.
The public key is (
G,g,h
) and the private key is
a
. Alternatively, (
G,g
) are system
parameters that are fixed for all users and only
h
is the public key.
The message space is
M
κ
={
0
,
1
}
∗
.
The ciphertext space is
C
κ
=
G
×{
0
,
1
}
∗
×{
0
,
1
}
l
3
.
Encrypt
(
m
,h
): (
m
∈{
0
,
1
}
∗
and
h
is the authentic public key of the receiver)
Choose a random 0
<k<r
and set
c
1
=
g
k
.
kdf
(
h
k
) and parse
K
as
K
1
K
2
where
K
1
and
K
2
are
l
1
and
l
2
bit binary strings
respectively.
Set
K
=
MAC
K
2
(
c
2
).
Transmit the ciphertext (
c
1
,
c
2
,
c
3
).
Set
c
2
=
Enc
K
1
(
m
)and
c
3
=
Decrypt
(
c
1
,
c
2
,
c
3
,a
):
Check that
c
1
∈
G
and that
c
3
is an
l
3
-bit string (if not then return
⊥
and halt).
Compute
K
=
kdf
(
c
1
) and parse it as
K
1
K
2
.
Check whether
c
3
=
MAC
K
2
(
c
2
) (if not then return
⊥
and halt).
Return
m
=
Dec
K
1
(
c
2
).
Box 23.1
DHIES public key encryption
Exercise 23.1.1
Show that decryption does return the message when given a ciphertext
produced by the DHIES encryption algorithm.
A variant of DHIES is to compute the key derivation function on the pair of group (or
algebraic group quotient) elements (
g
k
,h
k
) rather than just
h
k
. This case is presented in
Section 10 of Cramer and Shoup [
149
]. As explained in Section 10.7 of [
149
], this variant
can yield a tighter security reduction.
