Cryptography Reference
In-Depth Information
with weights
pounds.)
Their algorithm created custom knapsacks that appeared to offer a
guarantee that they were hard to pack exactly. Only someone with
a secret value, the private key, could determine the right subset of
objects to put in the knapsack with ease. After some equally hard
work, a human, Adi Shamir found a general algorithm that will break
the system without threatening the general NP-complete problems.
It exploited the key generation process that tried but failed to find
enough complicated sizes for the knapsacks. [Sha82, Lag84, Odl84]
No one else has had luck with NP complete problems. They seem
theoretically secure because there's no general algorithms for solving
themquickly, there are a number of fast heuristics that find solutions
in almost all cases. Indeed, no one has a good mechanism for iden-
tifying a small subset of problems that are difficult enough to offer
some guarantees.
In one solution, Gang Qu imagines that the ability to create these
solutions is what is being protected by a watermark. A person who
knows how to solve the travelling salesman problem optimally may
market their solutions to airlines, businesses or traveling salesforces.
To protect against piracy of their custom itineraries, they could hide
some signature information in the file that proves the solutions are
theirs. A competing business may develop their own solutions, but
anyone can check the provenance by looking for this hidden infor-
mation.
The technique hides information in the solutions to the difficult
problems by forcing certainparameters to take certain values. [Qu01,
KQP01] Anyone can examine the solution and check the parameters,
but it should be difficult to assemble a new solution because the
problem is presumably hard. The approach does not really require
a set of bits labeled a “public key”, but it still behaves in much the
same way.
Information is hidden in the solution to the problemby introduc-
ing new constraints on the solution. The classic boolean satisfiabil-
ity problem, for instance, takes
{w 1 ,ldots,w n }
,findasubsetthatweighs
W
and
tries to assign true or false values to them so that a set of boolean
clauses are all true. Information can be encoded in the answer by
forcing some of the variables to take particular values— say
n
boolean variables,
{x 1 ,...,x n }
x 14 =
T,x 25 =
might encode the bitstring
10011 . Of course, adding this extra requirement may make a solution
impossible, but that is a chance the designers take.
The technique can be applied to many NP-complete problems
and other problems as well. Many problems have multiple solutions
and information can be hidden by choosing the appropriate solution
F, x 39 =
F, x 59 =
T
and
x 77 =
T
Search WWH ::




Custom Search