International Association
for Cryptologic Research

Algorithm hardness can be described by 5 categories: hardness in computation, in sequential computation, in memory, in energy consumption (or bandwidth), in code size. Similarly, hardness can be a concern for solving or for verifying, depending on the context, and can depend on a secret trapdoor or be universally hard. Two main lines of research investigated such problems: cryptographic puzzles, that gained popularity thanks to blockchain consensus systems (where solving must be moderately hard, and verification either public or private), and white box cryptography (where solving must be hard without knowledge of the secret key). In this work, we improve upon the classification framework proposed by Biryukov and Perrin in Asiacypt 2017 and offer a united hardness framework, PURED, that can be used for measuring all these kinds of hardness, both in solving and verifying. We also propose three new constructions that fill gaps previously uncovered by the literature (namely, trapdoor proof of CMC, trapdoor proof of code, and a hard challenge in sequential time trapdoored in verification), and analyse their hardness in the PURED framework.