Cryptography Reference
In-Depth Information
3.5 Number-theoretic hash functions
We briefly mention some compression functions and hash functions that are based on
algebraic groups and number theory. These schemes are not usually used in practice as the
computational overhead is usually much too high.
An early proposal for hashing based on number theory, due to Davies and Price, was to
use the function
H
(
x
)
x
2
(mod
N
) where
N
is an RSA modulus whose factorisation is
not known. Inverting such a function or finding collisions (apart from the trivial collisions
H
(
x
)
=
=
H
(
±
x
+
yN
)for
y
∈ Z
) is as hard as factoring
N
. There are a number of papers
that build on this idea.
Another approach to hash functions based on factoring is to let
N
be an RSA mod-
ulus whose factorisation is unknown and let
g
∈
Z
Z
)
∗
be fixed. One can define the
(
/N
)
∗
by
compression function
H
:
N →
(
Z
/N
Z
g
x
(mod
N
)
.
H
(
x
)
=
H
(
x
) is equivalent to finding a multiple of the order of
g
.This
can be shown to be hard if factoring is hard. Finding preimages is the discrete logarithm
problem modulo
N
, which is also as hard as factoring. Hence, we have a collision resistant
compression function. More generally, fix
g,h
Finding a collision
H
(
x
)
=
∈
Z
Z
)
∗
and consider the compression
(
/N
g
x
h
y
(mod
N
). A collision leads
to either finding the order of
g
or
h
, or essentially finding the discrete logarithm of
h
with
respect to
g
, and all these problems are as hard as factoring.
One can also base hash functions on the discrete logarithm problem in any group
G
.Let
g,h
N × N →
Z
Z
)
∗
defined by
H
(
x,y
)
=
function
H
:
(
/N
∈
G
having order
r
. One can now consider the compression function
H
:
2
g
x
h
y
(mod
p
). It is necessary to fix the domain of
{
0
,...,r
−
1
}
→
G
by
H
(
x,y
)
=
the function since
H
(
x,y
)
r
). If one can find collisions in this
function then one can compute the discrete logarithm of
h
to the base
g
. A reference for
this scheme is Chaum, van Heijst and Pfitzmann [
121
].
=
H
(
x
+
r,y
)
=
H
(
x,y
+
3.6 Full domain hash
Hash functions usually output binary strings of some fixed length
l
. Some cryptosystems,
such as full domain hash RSA signatures, require hashing uniformly (or, at least, very close
to uniformly) to
, where
N
is large.
Bellare and Rogaway gave two methods to do this (one in Section 6 of [
35
] and another
in Appendix A of [
38
]). We briefly recall the latter. The idea is to take some hash function
H
with fixed length output and define a new function
h
(
x
) using a constant bitstring
c
and
a counter
i
as
Z
/N
Z
h
(
x
)
=
H
(
c
0
x
)
H
(
c
1
x
)
···
H
(
c
i
x
)
.
For the RSA application, one can construct a bitstring that is a small amount larger than
N
and then reduce the resulting integer modulo
N
(as in Example
11.4.2
).
