** Next:** Subset-Sum Problems and NP-Completeness
** Up:** Subset-Sum (Knapsack) problems and
** Previous:** Breaking Knapsack Cryptosystems
** Contents**

**Subsections**

The results mentioned at the end of the last section do *not*
contradict the presumed difficulty of subset-sum problems in
general. It is only the specially constructed problems which
are known to be easy. There are security problems other than
public-key codes for which subset-sum problems are useful.
A computer needs to verify a
user's identity before allowing him or her access to an account.
The simplest system would have the machine keep a copy of the
password in an internal file, and compare it with what the user
types. A drawback is that anyone who sees the internal file
could later impersonate the user.

I believe this alternative
is actually implemented on some systems: the computer generates
a large number (say 500) of . They are stored in the
internal file. A password is a subset of
.
(in practice, there is a program to convert a normal sequence-of-symbols password to such a subset.) Instead of having the
password for the user, the computer keeps the total associated
with the appropriate subset. When the user types in the subset,
the computer tests whether the total is correct. It does not
keep a record of the subset. Thus impersonation is possible
only if somebody can reconstruct the subset knowing the
and the total.

A sender (S) wants to send
messages to a receiver (R). Keeping the message secret
is not important. However, R wants to be sure that the message
he is receiving is not from an imposter and has not been tampered
with. and agree on a set of (say 500) and a
set of totals (say 200). These numbers may be publicly
known, but only knows which subsets of the correspond
to which . The message sent by is a subset of size 100
of
. He does this by sending 100 subsets of the
corresponding to the message he wants to send.

** Next:** Subset-Sum Problems and NP-Completeness
** Up:** Subset-Sum (Knapsack) problems and
** Previous:** Breaking Knapsack Cryptosystems
** Contents**
*Translated from LaTeX by Scott Sutherland *

2002-12-14