User verification by zero-knowledge interactive proof

• US 6,369,904 B1
• Filed: 12/01/1998
• Issued: 04/09/2002
• Est. Priority Date: 08/18/1998
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Ancin, Hakan, Bhattacharjya, Anoop
• Primary Examiner(s): Popovici, Dov
• Application Number:
  US09/204,608
• Time in Patent Office: 1,225 Days
• Field of Search: 380/51, 380/201-204, 380/54, 380/55, 283/113, 358/1.14, 358/1.15, 358/1.1, 358/1.2, 358/1.3, 358/1.4, 358/1.5, 358/1.6, 358/1.9, 358/1.11, 358/1.13, 358/1.18, 358/426, 358/261.1, 358/261.2, 358/261.3, 358/427, 358/262.1, 358/430, 358/431, 358/432-433, 358/468, 358/450, 358/448, 358/452, 358/438, 358/434, 382/100, 382/232, 713/176
• US Class Current: 358/1.14
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 2201/0091 Digital copier; digital 'photocopier' H04N2201/0093 and H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/3235 Checking or certification of the authentication information, e.g. by comparison with data stored independently
• CPC Class Codes: H04N 2201/3236 Details of authentication information generation
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

A scanner (12) derives a digital image of a document that it scans optically, an image-processing circuitry (14) extracts a representation of a non-planner graph. A small-processor “smart card” derives from the first graph a second graph that is isomorphic to it and related to it in accordance with a secret permutation matrix. The image processor 14 then embeds a representation of that graph into the image and sends the results to a printer (16) to generate a copy. A second scanner (30) generates a digital image of the copy, and processing circuitry (31) extracts the two isomorphic graphs, which it conveys to a verifier circuit (36) as well as the smart card (22). By repeatedly generating and submitting to the verifier (36) test graphs that are isomorphic to the extracted graphs, the smart card (22) can demonstrate, without revealing the secret permutation matrix, that it is in possession of that permutation matrix. It does so by sending the verifier a permutation matrix that relates the test graph to the extracted graph of the verifier'"'"'s choice.

Claims

1. For proving the provenance of a document copy, a method that includes the steps of:

A) taking an image of a source document;

B) embedding in the image an encoding of at least a first base graph that is related by a private permutation matrix to a second base graph whose encoding is embedded in the image;

C) generating output image signals that represent the image with the base graphs embedded in it;

D) repeatedly transmitting, to a verifier, test-graph signals representing successive test graphs, each test graph being related to the base graphs by respective test matrices associated with that test graph; and

E) for each test graph;

i) receiving from the verifier a challenge signal designating a respective chosen one of the base graphs; and

ii) sending the verifier a response signal representing the permutation matrix that relates the test graph to the base graph designated by the challenge signal.

2. A method as defined in claim 1 wherein the base graphs are nonplanar graphs.

3. A method as defined in claim 2 further comprising the steps of:

A) deriving the second base graph from the image taken of the source document, and

B) generating the first base graph from the second base graph in accordance with the private permutation matrix.

4. A method as defined in claim 3 wherein the base graphs are nonplanar graphs.

5. A method as defined in claim 3 wherein the embedding step includes:

A) identifying sites in the image that meet predetermined site criteria; and

B) setting to predetermined values constituent pixels included in sites selected in accordance with the encoding of the first base graph.

6. A method as defined in claim 1 wherein the embedding step includes:

A) identifying sites in the image that meet predetermined site criteria; and

B) setting to predetermined values constituent pixels included in sites selected in accordance with the encoding of the first base graph.

7. A method as defined in claim 6 wherein the base graphs are nonplanar graphs.

8. A method as defined in claim 6 wherein the step of identifying sites in the image comprises dividing the image into a grid of pixel-including cells and identifying as sites those cells in which at least a predetermined percentage of the included pixels meet predetermined text-region-indicating criteria.

9. A method as defined in claim 8 wherein:

A) the encoding of the first base graph consists of a sequence of code bits; and

B) the step of setting constituent pixels of selected sites to predetermined values includes;

i) associating each code bit with respective two-site sequences consisting of respective first and second sites;

ii) setting pixels of the first site but not of the second site when the associated code bit has one value; and

iii) setting pixels of the second site but not of the first site when the associated code bit has the other value.

10. A method as defined in claim 8 wherein:

A) the encoding of the first base graph consists of a sequence of code bits; and

B) the step of setting constituent pixels of selected sites to predetermined values includes;

i) associating each code bit with respective three-site sequences consisting of respective first, second, and third sites;

ii) setting pixels of the first and third sites but not of the second site when the associated code bit has one value; and

iii) setting pixels of the second site but not of the first and third sites when the associated code bit has the other value.

11. For verifying a document copy'"'"'s provenance, a method of that includes that steps of:

A) taking an image of the document copy and interpreting the image as including embedded encodings of a plurality of isomorphic base graphs;

B) repeatedly receiving, from a putative source, test-graph signals representing successive test graphs;

C) for each test graph;

i) sending the putative source a challenge signal designating a respective chosen one of the base graphs;

ii) receiving from the putative source a response signal representing a permutation matrix associated with that test graph; and

iii) deciding whether the permutation matrix is correct by determining whether it relates the chosen base graph to the test graph with which the permutation matrix is associated; and

D) generating a verification signal that indicates whether all of permutation matrices are correct.

12. A photocopier comprising:

A) an optical scanner for scanning a source document and generating electrical source-image signals representing a source image of the document;

B) image-processing circuitry responsive to the source-image signals for performing a sequence of at least one image-revision step, in which sequence each image-revision step receives an input image consisting of input pixels and produces therefrom an output image consisting of output pixels, the input image of a first image-revision step is the source image, the input image of any subsequent image-revision step is the output image of a preceding image-revision step, the image-processing circuitry generates electrical copy-image signals representing the output image of a last image-revision step, and one said image-revision step is an embedding operation that includes generating its output image by so modifying its input image as to embed therein an encoding of at least a first base graph that is related by a private permutation matrix to a second base graph whose encoding is embedded in its output image; and

C) a printer mechanism responsive to the copy-image signals for printing the output image of the last image-revision step represented thereby.

13. A photocopier as defined in claim 12 wherein the base graphs are nonplanar graphs.

14. A photocopier as defined in claim 13 wherein the embedding operation further comprises the steps of:

A) deriving the second base graph from the image taken of the source document; and

B) generating the first base graph from the second base graph in accordance with the private permutation matrix.

15. A photocopier as defined in claim 14 wherein the base graphs are nonplanar graphs.

16. A photocopier as defined in claim 14 wherein the embedding operation includes:

A) identifying sites in the embedding operation'"'"'s input image that meet predetermined site criteria; and

B) setting to predetermined values constituent pixels included in sites selected in accordance with the encoding of the first base graph.

17. A photocopier as defined in claim 12 wherein the embedding operation includes:

A) identifying sites in the embedding operation'"'"'s input image that meet predetermined site criteria; and

B) setting to predetermined values constituent pixels included in sites selected in accordance with the encoding of the first base graph.

18. A photocopier as defined in claim 17 wherein the base graphs are nonplanar graphs.

19. A photocopier as defined in claim 17 wherein the step of identifying sites in the image comprises dividing the embedding operation'"'"'s input image into a grid of pixel-including cells and identifying as sites those cells in which at least a predetermined percentage of the included pixels meet predetermined text-region-indicating criteria.

20. A photocopier as defined in claim 19 wherein:

A) the encoding of the first base graph consists of a sequence of code bits; and

B) the step of setting constituent pixels of selected sites to predetermined values includes;

i) associating each code bit with respective two-site sequences consisting of respective first and second sites;

ii) setting pixels of the first site but not of the second site when the associated code bit has one value; and

iii) setting pixels of the second site but not of the first site when the associated code bit has the other value.

21. A photocopier as defined in claim 19 wherein:

A) the encoding of the first base graph consists of a sequence of code bits; and

B) the step of setting constituent pixels of selected sites to predetermined values includes;

i) associating each code bit with respective three-site sequences consisting of respective first, second, and third sites; and

ii) setting pixels of the first and third sites but not of the second site when the associated code bit has one value; and

iii) setting pixels of the second site but not of the first and third sites when the associated code bit has the other value.

22. For verifying a document copy'"'"'s provenance, an apparatus that includes:

A) an optical scanner for scanning the document copy and generating electrical source-image signals representing a source image of the document copy; and

B) circuitry for;

i) interpreting the source image as including embedded encodings of a plurality of isomorphic base graphs;

ii) repeatedly receiving, from a putative source, test-graph signals representing successive test graphs;

iii) for each test graph;

a) sending the putative source a challenge signal designating a respective chosen one of the base graphs;

b) receiving from the putative source a response signal representing a permutation matrix associated with that test graph; and

c) deciding whether the permutation matrix is correct by determining whether it relates the chosen base graph to the test graph with which the permutation matrix is associated; and

iv) generating a verification signal that indicates whether all of permutation matrices are correct.

23. A storage medium containing instructions readable by a computer to configure the computer to function as an apparatus for:

A) receiving electrical signals representing an image of a source document;

B) embedding in the image an encoding of at least a first base graph that is related by a private permutation matrix to a second base graph whose encoding is embedded in the image;

C) generating output image signals that represent the image with the base graphs embedded in it;

D) repeatedly transmitting, to a verifier, test-graph signals representing successive test graphs, each test graph being related to the base graphs by respective test matrices associated with that test graph; and

E) for each test graph;

i) receiving from the verifier a challenge signal designating a respective chosen one of the base graphs; and

ii) sending to the verifier a response signal representing the permutation matrix that relates the test graph to the base graph designated by the challenge signal.

24. A storage medium as defined in claim 23 wherein the base graphs are nonplanar graphs.

25. A storage medium as defined in claim 24 further comprising the steps of:

A) deriving the second base graph from the image taken of the source document; and

B) generating the first base graph from the second base graph in accordance with the private permutation matrix.

26. A storage medium as defined in claim 25 wherein the base graphs are nonplanar graphs.

27. A storage medium as defined in claim 25 wherein the embedding step includes:

A) identifying sites in the image that meet predetermined site criteria; and

B) setting to predetermined values constituent pixels included in sites selected in accordance with the encoding of the first base graph.

28. A storage medium as defined in claim 23 wherein the embedding step includes:

A) identifying sites in the image that meet predetermined site criteria; and

B) setting to predetermined values constituent pixels included in sites selected in accordance with the encoding of the first base graph.

29. A storage medium as defined in claim 28 wherein the base graphs are nonplanar graphs.

30. A storage medium as defined in claim 28 wherein the step of identifying sites in the image comprises dividing the image into a grid of pixel-including cells and identifying as sites those cells in which at least a predetermined percentage of the included pixels meet predetermined text-region-indicating criteria.

31. A storage medium as defined in claim 30 wherein:

A) the encoding of the first base graph consists of a sequence of code bits; and

B) the step of setting constituent pixels of selected sites to predetermined values includes;

i) associating each code bit with respective two-site sequences consisting of respective first and second sites;

ii) setting pixels of the first site but not of the second site when the associated code bit has one value; and

iii) setting pixels of the second site but not of the first site when the associated code bit has the other value.

32. A storage medium as defined in claim 30 wherein:

A) the encoding of the first base graph consists of a sequence of code bits; and

B) the step of setting constituent pixels of selected sites to predetermined values includes;

i) associating each code bit with respective three-site sequences consisting of respective first, second, and third sites;

ii) setting pixels of the first and third sites but not of the second site when the associated code bit has one value; and

iii) setting pixels of the second site but not of the first and third sites when the associated code bit has the other value.