Integrity verification in cloud key-value stores

A method for verifying integrity of data in a computerized key-value database, the method comprising:

• sending, by a computer processor, a request to retrieve a value from a key-value database, the request comprising the associated key;
• obtaining, by the computer processor, a response from the key-value database;
• if the response includes a value:
• verifying the correctness of the value using a digital signature of the value;
• and
• if the response does not include a value:
• obtaining, by the computer processor, from a keys database a bucket associated with the key;
• searching, by the computer processor, the bucket for a presence indicator associated with the key;
• if the presence indicator associated with the key is not found in the bucket determining, by the computer processor, that the response is legitimate;
• and
• if the presence indicator associated with the key is found in the bucket determining, by the computer processor, that the key-value database is not complete.

A system for verifying completeness of data in a computerized key-value database, the system comprising:

• a memory;
• and
• a processor configured to:
• assign each key that is supported by the computerized key-value database to one of a plurality of buckets in a computerized key database;
• and
• upon storing a pair of a value and an associated key in the computerized key-value database, storing in the bucket assigned to the associated key a presence indicator indicative of a presence of the associated key in the key-value database.