Method for provably secure erasure of data

Patent metadata

Field	Value
Publication number	US-9852305-B2
Application number	US-201515502506-A
Country	US
Kind code	B2
Filing date	Oct 21, 2015
Priority date	Oct 21, 2014
Publication date	Dec 26, 2017
Grant date	Dec 26, 2017

Abstract

A method for provably secure erasure of data, performed in a memory available to one or more computing devices, includes generating prover state information (PSI), verifier state information (VSI), and common reference information (CRI) based on security information, a pregiven time-constraint, and a pregiven space-constraint, the generating PSI, VSI, and CRI being performed interactively between a prover computing device (PCD), and a verifier computing device, (VCD); computing, by the VCD based on the VSI, a challenge; computing a proof-of-erasure (POE) by the PCD based on the PSI and the computed challenge, the POE having a size corresponding to the pregiven space-constraint; and verifying by the VCD based on the VSI and the POE.

First claim

The invention claimed is:

1. A method for provably secure erasure of data, performed in a memory available to one or more computing devices, the method comprising:
a) generating prover state information (PSI), verifier state information (VSI), and common reference information (CRI) based on security information, a pregiven time-constraint, and a pregiven space-constraint, the generating the PSI, the VSI, and the CRI being performed interactively between a prover computer (PCD) and a verifier computer (VCD),
b) computing, by the VCD based on the VSI, a challenge,
c) computing a proof-of-erasure (POE) by the PCD based on the PSI and the computed challenge, the POE having a size corresponding to the pregiven space-constraint, and
d) verifying, by the VCD based on the VSI and the POE, erasure of the data,
wherein in a) the CRI is computed by a succinct non-interactive argument of knowledge procedure,
wherein a space puzzle is computed based on a puzzle parameter (PRM) providing puzzle-specific trapdoor information (TI) and puzzle-specific verification information (VI),
wherein the PSI is computed based on the CRI and the TI,
wherein the VSI is computed based on the CRI and the VI,
wherein in b) the challenge is computed based on a tag computed by an evaluation of a pseudorandom tribe function with the PRM and the PRM,
wherein in c) the challenge is checked if being a valid challenge from the VCD by evaluating the pseudorandom tribe function with the PRM,
wherein if the challenge is valid, a solution for the space puzzle is computed and the pseudorandom tribe function is evaluated with the solution resulting in a second tag,
wherein the POE is generated as a zero-knowledge POE computed with the CRI, the PRM, the tags, the TI, the solution, and coins of the space puzzle, and
wherein in d) the pseudorandom tribe function is evaluated with the VI and the result is compared with the second tag, and the time-constraint is checked by comparing a time needed to compute the POE with the time constraint.

2. The method according to claim 1 , wherein in d) a bit is outputted indicating a successful verification or not.

3. The method according to claim 1 , wherein the space puzzle is generated based on a one-to-one pseudorandom function tribe (PFT).

4. The method according to claim 3 , wherein the computing the space puzzle comprises:
sampling at random at least two function keys out of a first PFT, the first PFT having a first size being exponential in k with basis 2, wherein k is polynomial to a security information parameter,
computing a second size k′ such that a basis 2 being exponential in k′+r+1, wherein r being polynomial to the security information parameter, equals the space constraint,
truncating the function keys based on the difference between the first size and the second size and including the truncated function keys in the TI
computing a sum of two functions having the same tribe key but different functions keys out of the at least two function keys with two different arguments sampled at random, and
setting said space puzzle as tuple including the computed sum, the two arguments and the tribe key.

5. The method according to claim 4 , wherein the time constraint and the at least two functions keys are included into the VI.

6. The method according to claim 1 , wherein the computing the solution for the space puzzle comprises:
generating two tables, a first table representing function values with a first argument for each index of an upper bound for a function key size and a second table representing function values with a second argument for each index of the upper bound, wherein the first argument and the second argument are different from each other,
sorting values in the first table in increasing order starting with a smallest value for some index of the upper bound,
sorting values in the second table in decreasing order starting with a highest value for some index, and
checking if a sum of a value of the first table and a value of the second table is a solution to the space puzzle and if yes setting the sum as a solution.

7. The method according to claim 6 , wherein if the sum is not a solution, the computing the solution for the space puzzle comprises:
if the sum is smaller than the solution, increasing the index of the value in the second table and performing checking the sum with the value with increased index,
if the sum is greater than the solution, decreasing the index of the value in the first table and performing checking of the sum with the value with decreased index.

8. The method according to claim 3 , wherein secret information is generated by computing parameters of the pseudorandom tribe function including a key space and then sampling the secret information from the key space.

9. A system for provably secure erasure of data, the system comprising:
a prover computer (PCD) and a verifier computer (VCD), the PCD and the VCD being configured to collectively execute one or more programs stored at computer readable media, wherein execution of the one or more programs by the PCD and the VCD causes the PCD and the VCD to perform a method for verifying secure erasure of data, the method comprising:
generating, by interaction between the PCD and the VCD, prover state information (PSI), verifier state information (VSI), and common reference information (CRI) based on security information, a pregiven time-constraint and a pregiven space-constraint;
computing, by the VCD based on the VSI, a challenge,
computing, bv the PCD a proof-of-erasure (POE) based on the PSI and the computed challenge, wherein the POE has a size corresponding to the space-constraint, and
verifying by the VCD based on the VSI and the POE, erasure of the data,
wherein the CRI is generated by a succinct non-interactive argument of knowledge procedure,
wherein a space puzzle is computed based on a puzzle parameter (PRM), providing puzzle-specific trapdoor information (TI) and puzzle-specific verification information (VI),
wherein the PSI is computed based on the CRI and the TI,
wherein the VSI is computed based on the CRI and the VI,
wherein the challenge is computed based on a tag computed by an evaluation of a pseudorandom tribe function with the PRM and the PRM,
wherein the computing the POE comprises determining whether the challenge is a valid challenge from the VCD by evaluating the pseudorandom tribe function with the PRM,
wherein if the challenge is valid, a solution for the space puzzle is computed and the pseudorandom tribe function is evaluated with the solution resulting in a second tag,
wherein the POE is generated as a zero-knowledge POE computed with the CRI, the PRM, the tags, the TI, the solution, and coins of the space puzzle, and
wherein the pseudorandom tribe function is evaluated with the VI and the result is compared with the second tag, and the time-constraint is checked by comparing the time needed to compute the POE with the time constraint.

10. A verifier computer (VCD) for verifying secure erasure of data, the VCD being configured to execute one or more programs stored at computer readable media, wherein execution of the one or more programs by the VCD causes the VCD to perform method for verifying secure erasure of data, the method comprising:
generating, by interaction with a prover computer (PCD), prover state information (PSI), verifier state information (VSI), and common reference information (CRI) based on security information, a pregiven time-constraint, and a pregiven space-constraint,
computing a challenge based on the VSI, and
verifying erasure of the data based on the VSI and a proof-of-erasure (POE),
wherein the CRI is computed by a succinct non-interact

Assignees

• Nec Europe Ltd
• Nec Corp

Inventors

• Gajek Sebastian

Classifications

• G06F2221/2143

  Clearing memory, e.g. to prevent the data from being stolen · CPC title

• G06F3/0623

  in relation to content · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F21/6218 Primary

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• G06F3/0683

  Plurality of storage devices · CPC title