Cryptography Reference
In-Depth Information
We will use this to solve CDH. Let the CDH instance be (
g,g
1
,g
2
). Then choose a random
element
c
2
∈
and call
A
(
g,g
1
,g
2
,
c
2
) to get
m
. Return
c
2
m
−
1
g
as the solution to the
CDH instance.
One can also consider a non-perfect adversary (for example, maybe an adversary can
only decrypt some proportion of the possible ciphertexts). It might be possible to develop
methods to “self-correct” the adversary using random self-reductions, but this is considered
to be the adversary's job. Instead, it is traditional to simply give a formula for the success
probability of the algorithm that breaks the computational assumption in terms of the
success probability of the adversary. In the context of Theorem
20.4.2
, if the adversary can
decrypt with noticeable probability
then we obtain a CDH algorithm that is correct with
probability
.
≤
R
CDH for semi-textbook Elgamal. Explain why the
Exercise 20.4.3
Prove OWE-CPA
≤
R
OWE-CPA cannot be applied in this case.
proof CDH
20.4.2 OWE security under CCA attacks
We now show that both variants of textbook Elgamal do not have OWE security against
an adaptive (CCA) attacker (and hence not IND-CCA security either). Recall that such
an attacker has access to a decryption oracle that will decrypt every ciphertext except the
challenge.
Lemma 20.4.4
Let
(
c
1
,
c
2
)
be a ciphertext for classic textbook Elgamal with respect to the
public key
(
G,g,h
)
. Suppose A is a decryption oracle. Then under a CCA attack, one can
compute the message corresponding to
(
c
1
,
c
2
)
.
Proof
Assume that
A
is perfect. Call
A
on the ciphertext (
c
1
,
c
2
g
)
(
c
1
,
c
2
) to obtain a
message
m
. Then the message corresponding to the original ciphertext is
m
=
m
g
−
1
.
More generally, if
A
succeeds only with noticeable probability
then we have a CCA2
attack that succeeds with noticeable probability
.
=
Another version of this attack follows from Exercises
23.3.3
and
23.3.2
.
Exercise 20.4.5
Show that semi-textbook Elgamal encryption does not have the OWE
security property under a CCA attack.
We have seen how a CCA attack can lead to an adversary learning the contents of
a message. Exercise
20.4.6
gives an example of a general class of attacks called
small
subgroup attacks
or
invalid parameter attacks
that can allow a CCA (even a CCA1)
adversary to obtain the private key of a user. Such attacks can be performed in many
scenarios. One example is when working in a prime order subgroup of
F
p
where
p
−
1 has
many small factors. Another example is when using elliptic curves
E
:
y
2
x
3
a
6
;
since the addition formula does not feature the value
a
6
one can pass an honest user a point
of small order on some curve
E
(
=
+
a
4
x
+
F
p
). A related example is when using
x
-coordinate only
