Cryptography-based low distortion robust data authentication system and method therefor

• US 6,907,527 B1
• Filed: 10/17/2000
• Issued: 06/14/2005
• Est. Priority Date: 10/17/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Chai Wah
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ha, Leynna
• Application Number:
  US09/688,785
• Time in Patent Office: 1,701 Days
• Field of Search: 375/240.03, 375/240.2, 375/240.16, 375/240.22, 375/2, 382/197, 704/230, 725/19, 714/45, 714/732, 713/176, 713/200, 713/201, 713/165, 713/154, 707 9- 10, 707/101, 707/104.1, 380/701, 380/217, 380/216, 380/229, 380/232, 380/236, 380/237, 380/241
• US Class Current: 713/176
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/608 Watermarking
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method (and system) for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, includes constructing an index vector from the source file, quantizing the source file, generating an authentication mark from the quantized source file and the index vector, generating an authentication tag by appending the index vector to the authentication mark, and generating the output file by appending the authentication tag to the source file.

Claims

1. A method for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, comprising:

constructing an index vector from said source file;

creating quantization functions based on the index vector and quantizing said source file using said quantization functions;

generating an authentication mark from the quantized source file and said index vector;

generating an authentication tag by appending the index vector to said authentication mark; and

generating the output file by appending said authentication tag to said source file.

2. The method of claim 1, where said appending comprises:

inserting said authentication tag to said source file by a robust data hiding algorithm.

3. The method of claim 1, further comprising:

compressing said index vector.

4. The method of claim 1, further comprising:

applying a distortion to said source file, to form a distorted file,

wherein the generating of the output tile is performed by appending said authentication tag to said distorted file.

5. The method of claim 1, further comprising:

providing a reader for reading the source file.

6. The method of claim 1, wherein the source file is positioned in a smart card.

7. The method of claim 1, wherein said authentication mark is obtained by a digital signature algorithm.

8. The method of claim 1, wherein said authentication mark is obtained by a modification detection algorithm.

9. The method of claim 1, wherein said authentication mark is obtained by a message authentication algorithm.

10. The method of claim 1, wherein said source file comprises image data.

11. The method of claim 1, wherein said source file comprises video data.

12. The method of claim 1, wherein said source file comprises sound data.

13. The method of claim 1, wherein no distortion is added to the source file to generate the output file.

14. The method of claim 1, wherein said tag is created simultaneously with a creation of said source file.

15. The method of claim 1, wherein said authentication tag is created after the source file has been created, and is appended to the source file.

16. A method for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, comprising:

constructing an index vector from said source file;

constructing a feature vector of said source file;

creating quantization functions based on the index vector and quantizing said feature vector using said quantization functions;

generating an authentication mark from the quantized feature vector and said index vector;

generating an authentication tag by appending the index vector to said authentication mark; and

generating the output file by appending said authentication tag to said source file.

17. The method of claim 16, further comprising:

constructing said index vector from said feature vector of said source file.

18. The method of claim 16, further comprising:

generating a distorted file from said feature vector,

wherein the generating of the output file is performed by appending said authentication tag to said distorted file.

19. The method of claim 16, wherein said feature vector comprises discrete cosine transform coefficients.

20. A method for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, comprising:

constructing an index vector from said source file;

creating quantization functions based on the index vector and quantizing said source file using said quantization functions;

compressing said index vector;

generating an authentication mark from the quantized source file and said compressed index vector;

generating an authentication tag by appending the index vector to said authentication mark; and

generating the output file by appending said authentication tag to said source file.

21. A method for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, comprising:

constructing an index vector from said source file;

creating quantization functions based on the index vector and quantizing said source file using said quantization functions;

compressing said index vector;

generating an authentication mark from the quantized source file and said index vector;

generating an authentication tag by appending said compressed index vector to said authentication mark; and

generating the output file by appending said authentication tag to said source file.

22. A method for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, comprising:

constructing a feature vector from said source file;

constructing an index vector from a feature vector of the source file;

quantizing said feature vector according to the index vector;

generating an authentication mark from quantized feature vector and said index vector;

generating an authentication tag by appending the index vector to said authentication mark; and

generating the output file by appending said authentication tag to said source file.

23. The method of claim 22, further comprising:

compressing said index vector.

24. A method for authenticating a data file, comprising:

extracting an authentication tag from said data file;

extracting an index vector from said authentication tag;

extracting an authentication mark from said authentication tag;

creating quantization functions based on the index vector and quantizing said data file using said quantization functions; and

verifying said index vector and said quantized data file with said authentication mark.

25. The method of claim 24, wherein said index vector comprises a compressed index vector.

26. The method of claim 25, further comprising:

decompressing said compressed index vector prior to said quantizing of said data file.

27. The method of claim 24, wherein said authentication mark is obtained by a digital signature algorithm.

28. The method of claim 24, wherein said authentication mark is obtained by a modification detection algorithm.

29. The method of claim 24, wherein said authentication mark is obtained by a message authentication algorithm.

30. A method for authenticating a data file, comprising:

extracting an authentication tag from said data file;

extracting an index vector from said authentication tag;

extracting an authentication mark from said authentication tag;

constructing a feature vector from said data file;

creating quantization functions based on the index vector and quantizing said feature vector using said quantization functions; and

verifying said index vector and said quantized feature vector with said authentication mark.

31. A system for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, said system comprising:

means for constructing an index vector from said source file;

means for creating quantization functions based on the index vector and quantizing said source file using said quantization functions;

means for generating an authentication mark from the quantized source file and said index vector;

means for generating an authentication tag by appending the index vector to said authentication mark; and

means for generating the output file by appending said authentication tag to said source file.

32. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for generating an output file from a source file where benign modifications to a content of the output file still render the output file authentic, said method comprising:

constructing an index vector from said source file;

creating quantization functions based on the index vector and quantizing said source file using said quantization functions;

generating an authentication mark from the quantized source file and said index vector;

generating an authentication tag by appending the index vector to said authentication mark; and

generating the output file by appending said authentication tag to said source file.