Cryptography Reference
In-Depth Information
α
r
≡
sk
−
H
(
m
)(
mod
q
).
This relation reveals nothing about
α
when
k
is chosen truly at random in
Z
q
,but
when some bits of
k
are known, some information about
α
is leaked since all other
parameters are publicly known. Intuitively, knowing
bits of
k
should reveal
bits
of information about
α
,soif
q
is
N
bits long,
α
should be recoverable from about
N
/
faulty signatures. Moreover, the relation is affine in both
α
and
k
: that is why
we can hope to attack the problem with lattices.
Let us describe in more details how one can take advantage of the leaked infor-
mation. In our case, we know that the
least significant bits of
k
are 0, so we can
2
b
for some integer
b
write
k
=
≥
0. Writing
h
=
H
(
m
)
, we get
2
−
s
−
1
2
−
s
−
1
α
r
·
≡
b
−
h
·
(
mod
q
).
Now let
2
−
s
−
1
2
−
s
−
1
t
=
r
·
q
and
u
=−
h
·
q
q
denotes the only integer 0
≤
<
≡
(
)
where for any integer
z
,
z
a
q
such that
a
z
mod
q
.
Both
t
and
u
can be computed from public information, and the additional informa-
tion we have, namely that
b
2
, can be expressed in terms of
t
and
u
as
<
q
/
2
.
0
≤
α
t
−
u
q
<
q
/
Therefore, if we denote by
|·|
q
the distance to
q
Z
, i.e.
|
z
|
q
=
min
a
∈Z
|
z
−
aq
|
,we
have
2
+
1
2
+
1
|
α
t
−
u
−
q
/
|
q
≤
q
/
.
In other words, we know an approximation of
α
t
modulo
q
:
2
+
1
2
+
1
|
α
t
−
v
/
|
q
≤
q
/
where
v
is the integer 2
+
1
u
q
.
Given a number of faulty signatures
+
(
r
i
,
s
i
)
of various messages
m
i
,say
d
of
them, the same method yields pairs of integers
(
t
i
,
v
i
)
such that
2
+
1
2
+
1
|
α
t
i
−
v
i
/
|
q
≤
q
/
.
The goal is to recover
from this data. This problem is very similar to the hidden
number problem considered by Boneh and Venkatesan in [58], and is approached by
transforming it into a lattice closest vector problem.
More precisely, consider the
α
(
+
)
d
1
-dimensional lattice
L
spanned by the rows
of the following matrix:
