Patent ID: 8254569

Claim:
A method of verifying data integrity comprising: fingerprinting data, by a client, by: dividing the data into N blocks M i , i=1, 2 . . . , N; combining each of n B blocks into a super block to obtain n=[N/n B ] super blocks; selecting n B elements h j , i=1, 2, . . . , n B , from a finite cyclic group G 1 =<g 1 >, and generating a fingerprint T k for the k th super block respectively, k=1, 2, . . . , n, by using a locator W k for the k th super block, the selected n B elements h j and a first private key χ; generating and sending, by a client, a challenge comprising at least a first randomness defining key κ 1 and a second randomness defining key κ 2 ; generating and sending, by a server, a transformed fingerprint and a knowledge proof of the transformed super block by: constructing Φ boxes; randomly assigning the n fingerprints into the Φ boxes in a first random manner defined by the first randomness defining key κ 1 , each fingerprint being put into one box; generating Φ packed super blocks and corresponding packed fingerprints based on the above assignment of the n fingerprints; randomly transforming the Φ packed super blocks and corresponding packed fingerprints in a second random manner defined by the second randomness defining key κ 2 to generate a transformed super block and a transformed fingerprint; generating a knowledge proof of the transformed super block; and verifying data integrity, by the client, by: constructing Φ boxes; randomly assigning the n locators W k into the Φ boxes in the first random manner, each locator being put into one box; generating Φ packed locators based on the above assignment of the n locators; randomly transforming the Φ packed locators in the second random manner to generate a transformed locator; generating an alleged knowledge proof of the transformed super block from the transformed fingerprint and the transformed locator; and comparing the alleged knowledge proof of the transformed super block with the received knowledge proof of the transformed super block.