Method for provably secure erasure of data

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.

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-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, and
• wherein the pseudorandom tribe function is evaluated with the VI and the result is compared with a second tag provided by the PCD, the time-constraint is checked by comparing the time needed to compute the POE with the time constraint.

A method for verifying secure erasure of data, performed on a verifier computing device (VCD), the method comprising:

• a) generating, by interaction with a prover computing device (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,
• b) computing a challenge based on the VSI, and
• c) verifying erasure of the data based on the VSI and a proof-of-erasure (POE), wherein 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), and
• 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, and
• wherein the pseudorandom tribe function is evaluated with the VI and the result is compared with a second tag provided by the PCD, and the time-constraint is checked by comparing the time needed to compute the POE with the time constraint.

A prover computer (PCD), for providing a proof of secure erasure of data, the PCD being configured to execute one or more programs stored at computer readable media, wherein execution of the one or more programs by the PCD causes the PCD to perform a method for verifying secure erasure of data, the method comprising:

• generating, by interaction with verifier computing device (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, and
• computing a proof-of-erasure (POE) based on the PSI and a challenge provided by the VCD, the POE having a size corresponding to the space-constraint,
• wherein the VCD verifies, 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 a space puzzle is computed, and the pseudorandom tribe function is evaluated with the solution resulting in a second tag, and
• 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.

A method for providing a proof of secure erasure of data, performed on a prover computing device (PCD), the method comprising:

• a) generating by interaction with a verifier computing device (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, and
• b) computing a proof-of-erasure (POE) based on the PSI and a challenge provided by the VCD, the POE having a size corresponding to the space-constraint,
• wherein the VCD verifies, 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 a 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.

A non-transitory computer readable medium storing a program causing a computer to execute a method for provably secure erasure of data, 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 PSI, VSI, and CRI is being performed interactively between a prover computing device (PCD), and a verifier computing device, (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.