# US 2021/0173903 A1 · Resilient watermarking

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0173903 A1
- Document ID: US20210173903A1
- Status: Published application
- Kind: A1
- Application number: 16/708,518
- Filed: 2019-12-10
- Published: 2021-06-10
- Earliest claimed: 2019-12-10
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Olivia Choudhury; ARIS GKOULALAS-DIVANIS
- Web page: https://patentgrep.com/patent/US20210173903A1

## CPC

- G06F 21/16: Program or content traceability, e.g. by watermarking
- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- G06F 16/2255: {Hash tables}
- G06F 16/2322: {using timestamps}
- G06F 16/284: {Relational databases}
- G06F 16/9014: {hash tables}
- G06F 21/1063: {Personalisation}
- G06F 21/602: {Providing cryptographic facilities or services}
- G06F 21/64: Protecting data integrity, e.g. using checksums, certificates or signatures
- H04L 9/0637: {Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]}
- H04L 9/50: {using hash chains, e.g. blockchains or hash trees}
- H04L 2209/608: Watermarking
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method, system, and computer program product for detecting data tampering with resilient watermarking is provided. The method accesses a first relational data set on a data repository. The first relational data set includes a plurality of data elements. The first relational data set is sorted to generate a first sorted list and a second sorted list of the plurality of data elements. The method generates a watermark from the first sorted list and the second sorted list. The watermark contains a hash corresponding to the first sorted list and the second sorted list of the plurality of data elements. In response to an access request for the first relational data set, the method verifies an integrity of the first relational data set based on the watermark.

## Claims

### Claim 1

A computer-implemented method, comprising:
accessing a first relational data set on a data repository having a plurality of relational data sets, the first relational data set including a plurality of data elements;
sorting the first relational data set to generate a first sorted list and a second sorted list of the plurality of data elements;
generating a watermark from the first sorted list and the second sorted list, the watermark containing a hash corresponding to the first sorted list and the second sorted list of the plurality of data elements; and
in response to an access request for the first relational data set, verifying an integrity of the first relational data set based on the watermark.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein generating the watermark from the first sorted list and the second sorted list further comprises:
selecting a subset of data elements from the first sorted list and the second sorted list;
generating an element template from the subset of data elements and the first and second sorted lists; and
generating the hash from the element template and the subset of data elements.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein selecting the subset of data elements from the first sorted list and the second sorted list provide a list of index values for the subset of data elements and wherein the element template contains a sequence of tuples, each tuple having a list value, for the first sorted list or the second sorted list, and an index value.

### Claim 4 (depends on 2)

The computer-implemented method of claim 2, further comprising:
generating a block in a blockchain framework of the data repository, the block storing the watermark and the element template.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, wherein the watermark is a first watermark and the block is a first block, the method further comprising:
identifying a modification request indicating one or more data elements to be added to the first relational data set, the modification request generating a modified relational data set;
generating a second watermark from the modified relational data set; and
generating a second block in the blockchain framework of the data repository, the second block storing the second watermark corresponding to the modified relational data set.

### Claim 6 (depends on 2)

The computer-implemented method of claim 2, wherein verifying the integrity of the first relational data set further comprises:
generating a current watermark for the first relational data set, the current watermark generated based on accessing the first relational data set at a time subsequent to generating the watermark; and
comparing the watermark with the current watermark.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the watermark is generated by a probabilistic selection of data elements from the first sorted list and the second sorted list.

### Claim 8

A system, comprising:
one or more processors; and
a computer-readable storage medium, coupled to the one or more processors, storing program instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
accessing a first relational data set on a data repository having a plurality of relational data sets, the first relational data set including a plurality of data elements;
sorting the first relational data set to generate a first sorted list and a second sorted list of the plurality of data elements;
generating a watermark from the first sorted list and the second sorted list, the watermark containing a hash corresponding to the first sorted list and the second sorted list of the plurality of data elements; and
in response to an access request for the first relational data set, verifying an integrity of the first relational data set based on the watermark.

### Claim 9 (depends on 8)

The system of claim 8, wherein generating the watermark from the first sorted list and the second sorted list further comprises:
selecting a subset of data elements from the first sorted list and the second sorted list;
generating an element template from the subset of data elements and the first and second sorted lists; and
generating the hash from the element template and the subset of data elements.

### Claim 10 (depends on 9)

The system of claim 9, wherein selecting the subset of data elements from the first sorted list and the second sorted list provide a list of index values for the subset of data elements and wherein the element template contains a sequence of tuples, each tuple having a list value, for the first sorted list or the second sorted list, and an index value.

### Claim 11 (depends on 9)

The system of claim 9, further comprising:
generating a block in a blockchain framework of the data repository, the block storing the watermark and the element template.

### Claim 12 (depends on 11)

The system of claim 11, wherein the watermark is a first watermark and the block is a first block, the operations further comprising:
identifying a modification request indicating one or more data elements to be added to the first relational data set, the modification request generating a modified relational data set;
generating a second watermark from the modified relational data set; and
generating a second block in the blockchain framework of the data repository, the second block storing the second watermark corresponding to the modified relational data set.

### Claim 13 (depends on 9)

The system of claim 9, wherein verifying the integrity of the first relational data set further comprises:
generating a current watermark for the first relational data set, the current watermark generated based on accessing the first relational data set at a time subsequent to generating the watermark; and
comparing the watermark with the current watermark.

### Claim 14 (depends on 8)

The system of claim 8, wherein the watermark is generated by a probabilistic selection of data elements from the first sorted list and the second sorted list.

### Claim 15

A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions being executable by one or more processors to cause the one or more processors to perform operations comprising:
accessing a first relational data set on a data repository having a plurality of relational data sets, the first relational data set including a plurality of data elements;
sorting the first relational data set to generate a first sorted list and a second sorted list of the plurality of data elements;
generating a watermark from the first sorted list and the second sorted list, the watermark containing a hash corresponding to the first sorted list and the second sorted list of the plurality of data elements; and
in response to an access request for the first relational data set, verifying an integrity of the first relational data set based on the watermark.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein generating the watermark from the first sorted list and the second sorted list further comprises:
selecting a subset of data elements from the first sorted list and the second sorted list;
generating an element template from the subset of data elements and the first and second sorted lists; and
generating the hash from the element template and the subset of data elements.

### Claim 17 (depends on 16)

The computer program product of claim 16, wherein selecting the subset of data elements from the first sorted list and the second sorted list provide a list of index values for the subset of data elements and wherein the element template contains a sequence of tuples, each tuple having a list value, for the first sorted list or the second sorted list, and an index value.

### Claim 18 (depends on 16)

The computer program product of claim 16, further comprising:
generating a block in a blockchain framework of the data repository, the block storing the watermark and the element template.

### Claim 19 (depends on 18)

The computer program product of claim 18, wherein the watermark is a first watermark and the block is a first block, the operations further comprising:
identifying a modification request indicating one or more data elements to be added to the first relational data set, the modification request generating a modified relational data set;
generating a second watermark from the modified relational data set; and
generating a second block in the blockchain framework of the data repository, the second block storing the second watermark corresponding to the modified relational data set.

### Claim 20 (depends on 16)

The computer program product of claim 16 wherein verifying the integrity of the first relational data set further comprises:
generating a current watermark for the first relational data set, the current watermark generated based on accessing the first relational data set at a time subsequent to generating the watermark; and
comparing the watermark with the current watermark.
