Subset Sum (SS), and Public Key Cryptography:
Historically, SS was the basis for the first proposal of
a practical public-key cryptosystem (PKC). NP-complete problems were
thought to be a rich source of possible bases for PKCs.
Subset Sum (SS), New Notation:
As before, start with an array A of positive integers, say
a "toy" instance:
Public-Key Cryptography:
Now suppose Alice chooses an array A consisting
of 100 200-bit
integers (um, 60-digit). She publishes these numbers
in a public directory
as her public key. Bob wants to send her a 100-bit message.
He lets X be the vector of his bits and calculates A*X,
which he sends to Alice. Now Alice would need to solve the
NP-complete SS problem in order to determine the message
inside X. With a "normal" vector A, say a random one
satisfying reasonable conditions, Alice would not be able
to recover the X. But Alice instead has chosen a clever
set of numbers that contains a secret "trapdoor", one that
will let her solve the SS problem efficiently.
Let's continue the above "toy" SS instance using 4-digit numbers.
Suppose Alice had originally choosen a
secret instance:
A' = {171,196,457,1191,2410}.
This is a super-increasing sequence, for which the SS problem
is easy to solve. Then Alice chooses secret numbers
m = 8443 and w = 2550.
All the arithmetic will be done
mod m (that is, % m). There is a way to calculate a
number w-1 with the property that
(w * w-1) mod m = 1, that is w-1 = 3950 is the inverse of w = 2550, mod 8443, or (2550 * 3950) % 8443 = 1
Alice lets A = w*A' mod m, which is the A above.
Now Bob has sent the number s = 15115, which is
a sum from the A array. Alice transforms s by
calculating:
s' = w-1 * s mod m
= 3950*15115 mod 8443 = 3797..
s' = 3797 is the corresponding sum in the A' array,
and Alice easily calculates that
s' = 2410 + 1191 + 196 = X*A', where
X = {0,1,0,1,1}..
This last is Bob's message to Alice.
Revision date:2012-11-16.
(Please use ISO 8601,
the International Standard Date and Time Notation.)