A method performed in a memory available to a computation device, for providing a space puzzle, using functional encryption for key generation, encryption and decryption for a proof-of-erasure of a memory of a computation device, comprising the steps of a) Computing, by a puzzle generating entity, 'PGE', a master secret key, 'MSK', and a public key, 'PK' based on a security parameter, b) Computing, by said PGE, a random predicate, 'RP', wherein said predicate is a random string of size n bit, c) Computing, by said PGE, a secret key, 'SK', using said computed MSK and said computed RP, d) Providing, by said PGE, a challenge comprising said PK and said SK, to a proving computing entity, e) Computing, by said proving computing entity, a response to said challenge using the size of said RP comprising the steps of e1) Computing a higher dimensional virtual structure each dimension of said higher dimensional virtual structure being of said size of said RP, wherein said higher dimensional structure is a two dimensional matrix of n x n size, said n being the size of said RP, e2) Encrypting each row of said higher dimensional structure with said PK, e3) Decrypting each of said encrypted rows using said SK to obtain a decrypted predicate, e4) Recomputing said RP using said decrypted predicate and said higher dimensional virtual structure, f) Providing said recomputed RP as response to said challenge, g) Verifying said provided challenge by comparing said response with said random predicate and confirming erasure of said memory if said response equals said RP. a) Computing, by a puzzle generating entity, 'PGE', a master secret key, 'MSK', and a public key, 'PK' based on a security parameter, b) Computing, by said PGE, a random predicate, 'RP', wherein said predicate is a random string of size n bit, c) Computing, by said PGE, a secret key, 'SK', using said computed MSK and said computed RP, d) Providing, by said PGE, a challenge comprising said PK and said SK, to a proving computing entity, e) Computing, by said proving computing entity, a response to said challenge using the size of said RP comprising the steps of e1) Computing a higher dimensional virtual structure each dimension of said higher dimensional virtual structure being of said size of said RP, wherein said higher dimensional structure is a two dimensional matrix of n x n size, said n being the size of said RP, e2) Encrypting each row of said higher dimensional structure with said PK, e3) Decrypting each of said encrypted rows using said SK to obtain a decrypted predicate, e4) Recomputing said RP using said decrypted predicate and said higher dimensional virtual structure, e1) Computing a higher dimensional virtual structure each dimension of said higher dimensional virtual structure being of said size of said RP, wherein said higher dimensional structure is a two dimensional matrix of n x n size, said n being the size of said RP, e2) Encrypting each row of said higher dimensional structure with said PK, e3) Decrypting each of said encrypted rows using said SK to obtain a decrypted predicate, e4) Recomputing said RP using said decrypted predicate and said higher dimensional virtual structure, f) Providing said recomputed RP as response to said challenge, g) Verifying said provided challenge by comparing said response with said random predicate and confirming erasure of said memory if said response equals said RP.