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.