Cryptography Reference
In-Depth Information
Describe the property satisfied by the Dickson polynomial that allows Bob
to recover
m
in step 4, and verify that step 4 indeed does recover
m
as
suggested.
4.56. Dickson polynomials may also be used for multiple encryptions. The
notation and concepts used in this exercise were developed in Exercise
4.52.
Suppose that
D
(
s
n
(
x,a
) denotes the composition of
D
n
(
x,a
)
s
∈
N
times.
If
c
is a ciphertext, show that there are integers
r, s
such that
D
(
r
n
(
c,a
)
D
(
s
n
(
c,a
)
≡
≡
c
(mod
k
)
.
This implies the existence of an integer
t
such that
D
(
t
n
(
c,a
)
≡
c
(mod
k
)
(G.2)
Show how this may be used to recover the plaintext without factoring the
modulus. (It can be shown that the fixed point given by (G.2) may be
used as an attack to factor
k
(see [174]and [181)). For more information
on Dickson polynomials and their applications, see a topic devoted entirely
to this topic ([152]).
G.5 Chapter 5 Exercises
5.1.
This problem refers to the explanation of oblivious transfer covered in
Section 5.1 on pages 191-194.
Suppose that Alice and Bob are secret agents for two different countries
and Bob wants to buy a secret from Alice. Moreover, Bob wants to buy a
secret without Alice knowing which one.
Suppose that Alice has a list of
secrets
s
1
,s
2
,...,s
, all expressed as
bitstrings of equal bitlength. She also possesses a one-way function
f
for
which only she possesses
f
−
1
. She lets Bob know what each of the secrets
represent by giving him a list of questions
q
1
,q
2
,...,q
to which the
s
j
are
the answers. The oblivious transfer protocol is described as follows.
1. Bob selects
q
k
from the list of questions to which he wants to buy the
secret
s
k
. He chooses random numbers
r
1
,r
2
,...,r
from the domain
of
f
. Then he computes
c
j
=
r
j
=
k
,
f
(
r
j
) f
j
=
k
,
if
j
and sends (
c
1
,c
2
,...,c
) to Alice.
Search WWH ::
Custom Search