User verification by zero-knowledge interactive proof

Details User verification by zero-knowledge interactive proof User verification by zero-knowledge interactive proof

1998-12-01

2002-04-09

Popovici, Dov (Department: 2622)

Facsimile and static presentation processing

Static presentation processing

Data corruption, power interruption, or print prevention

C358S001150, C382S100000, C382S232000

Reexamination Certificate

active

06369904

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention is directed to producing document copies and in particular to verifying a copy's provenance.
The ubiquity of photocopies and telecopiers in businesses and other environments has afforded a great deal of information-transfer convenience. Unfortunately, there are a number of situations in which this convenience is not entirely beneficial. It can make it hard to restrict copying when a confidentiality agreement, for instance, requires such a restriction. Also, photocopying can mask the fact that a document has been altered. That is, an erasure or “white-out” clearly visible in an original document may not be apparent at all in a photocopy or telecopy.
In policing photocopier or telecopier use, it would be helpful to be able to verify that a given photocopy or telecopy was actually produced by its purported source. This would help in complying with agreements not to copy and may have forensic applicability in enforcing laws against fraud.
SUMMARY OF THE INVENTION
I have developed a way of verifying document-copy provenance that is secure and easy to apply. The inventive method is a type of zero-knowledge interactive proof. Proofs of this general type are described, for instance, in Goldwasser, “The Knowledge Complexity of Interactive Proof Systems,”
Proc. STOC
1985.
The type of proof involved here is based on the concept of non-planar isomorphic graphs related by a secret permutation matrix. In this context, the graph can be envisioned conceptually as a set of points in space that are interconnected by “edges.” For the purposes of the inventive method, such a graph can be represented simply as pairs of numbers, each number being a label that uniquely identifies one of the graph's interconnected points, or “nodes.” A second graph is isomorphic to the first if it would be the result of, say, simply renaming the various nodes.
Now, it is a simple matter to generate a second graph isomorphic to the first graph: one simply devices a set of unique substitutions for all of the node labels. But the reverse problem, namely, determining the “permutation matrix” that specifies the replacements by which one isomorphic graph is derived from another, rapidly becomes computationally intractable with increases in the number of nodes and edges, at least if is the graphs are nonplanar, i.e., if they cannot be represented as co-planar nodes without having intersecting edges.
According to the invention, the copy machine embeds graph-defining information in the copy, preferably in a manner that is not readily detectable by human vision. Possibly together with information already existing in the document, the information specifies at least two isomorphic graphs that are related by a private permutation matrix. The permutation matrix is preferably known only to the copy-machine operator or, more typically, a “smart card” that the operator owns. As another alternative, it may be stored in the copier by the copier vendor.
To verify the copy's provenance, the verifying entity employs a publicly known technique for extracting the graphs from an image of the document copy. Then a “prover,” i.e., a purported source, provides a series of test graphs that should be isomorphic to the graphs extracted from the document. For each test graph, the verifier ramdomly chooses between the (typically two) extracted graphs and thereby challenges the prover to generate the permutation matrix that relates the test graph to the chosen graph. If the prover is able to produce such a permutation matrix consistently over a large number of challenges, then the verifier can have a high level of confidence that the prover is in possession of the secret permutation matrix and should therefore be the document copy's source.
This method is highly secure, since it requires no transmission of any secret key. And, with the exception of the need for a standard method by which to extract the graphs, it requires no complicated infrastructure, such as a private-key registry.


REFERENCES:
patent: 5257119 (1993-10-01), Funada et al.
patent: 5315098 (1994-05-01), Tow
patent: 5541741 (1996-07-01), Suzuki
patent: 5699427 (1997-12-01), Chow et al.
patent: 5710636 (1998-01-01), Curry
patent: 5710834 (1998-01-01), Rhoads
patent: 5734752 (1998-03-01), Knox

Affiliated with

Also associated with

Rating

User verification by zero-knowledge interactive proof does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with User verification by zero-knowledge interactive proof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and User verification by zero-knowledge interactive proof will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2918906