A method for providing a space puzzle includes computing, by a puzzle generating entity (PGE), a master secret key (MSK), a public key (PK), a random predicate (RP), and a secret key (SK) using the computed MSK and the computed RP; providing, by the PGE, a challenge comprising the PK and the SK to a proving computing entity; computing, by the proving computing entity, a response to the challenge using a size of the RP by computing a higher dimensional virtual structure; encrypting each row of the higher dimensional structure with the PK; decrypting the encrypted rows using the SK to obtain a decrypted predicate; recomputing the RP using the decrypted predicate and the higher dimensional virtual structure to provide a recomputed random predicate; and verifying the provided challenge by comparing the recomputed random predicate with the RP.