Cryptography Reference
In-Depth Information
of “primality checking” deserve much more attention. A probabilistic polynomial-time
algorithm for generating uniformly distributed primes together with corresponding
certificates of primality has been presented by Bach [9]. The certificate produced by
this algorithm for a prime
P
consists of the prime factorization of
P
1, together with
certificates for primality of these factors. This recursive form of certificates for primality
originates in Pratt's proof [184] that the set of primes is in
−
. However, the foregoing
procedure is not very practical. Instead, when using the RSA (or Rabin) function in
practice, one is likely to prefer an algorithm that generates integers at random and checks
them for primality using fast primality checkers, such as the algorithms presented in
[203, 185]. One should note, however, that these algorithms do not produce certificates
for primality and that with some (small) parameterized probability they may assert
that a composite number is a prime. Probabilistic polynomial-time algorithms (yet
not practical ones) that, given a prime, produce a certificate for primality have been
presented [121, 1].
The common belief that the RSA, Rabin, and DLP functions are one-way is based on
the failure of researchers to come up with probabilistic polynomial-time algorithms for
factoring and discrete logarithms. (It is debatable whether this record of failure should
be traced back a couple of centuries or “only” a few decades.) For a survey of the
best algorithms known for the factoring and discrete-logarithm problems, the reader is
directed to Odlyzko's surveys ([178] and [179], respectively).
The subset-sum problem is known to be easy in two special cases. One case is
that in which the input sequence is constructed based on a simple “hidden sequence.”
For example, Merkle and Hellman [163] suggested the construction of an instance of
the subset-sum problem based on a “hidden super-increasing sequence” as follows.
Let
s
1
,...,
NP
M
be a sequence satisfying
s
i
>
i
−
1
def
=
s
n
,
s
n
+
1
j
=
1
s
j
, for
i
=
2
,...,
n
+
1.
Such a sequence is called
super-increasing
.For
relatively prime to
M
, consider the
instance of the subset-sum problem consisting of (
x
1
,...,
x
n
) and
i
∈
I
x
i
, where
x
i
def
w
=
w
·
s
i
mod
M
and
I
⊆{
1
,...,
n
}
. Clearly, knowledge of both
w
and
M
allows one to
easily solve the subset-sum problem for the foregoing instance (e.g., simply retrieve the
super-increasing sequence and iteratively determine if
i
∈
I
for
i
=
n
,
n
−
1
,...,
1).
The hope was that when
w
and
M
were not given, solving the subset-sum problem
would be hard (even for instances generated based on a super-increasing sequence).
(That would have led to a trapdoor one-way function.) Unfortunately, that hope was not
realized. Shamir presented an efficient algorithm for solving the subset-sum problem
for instances with a hidden super-increasing sequence [197]. Another case for which the
subset-sum problem is known to be easy is the case of
low-density
instances. In these
instances, the lengths of the elements in binary representations are considerably larger
than the numbers of elements (i.e.,
|
x
1
|=···=|
x
n
|=
(1
+
ε
)
n
for some constant
ε>
0). For further details, consult the work of Lagarias and Odlyzko [145] and the
later survey of Brickell and Odlyzko [43].
Two computational problems that are seemingly related to the subset-sum problem
are the decoding of random linear codes and the finding of closest vectors in integer
lattices. In all three cases the problem is to find a linear combination of given ele-
ments such that the sum equals or is close to a target value. However, the similarity
is superficial, because the arithmetic is different in the three cases. In the case of the
