Memory-Hard Hashes and Time-Lock Puzzles, an explanation #68
Description
This is an explanation of practical conceptual differences between Memory-Hard Hashes (hencefoward MHHs) and Time-Lock Puzzle (henceforward TLP) and the nuances of what each is used for in the context of Great Wall protocol (GW), according to their respective properties.
Both MHHs and TLP are cryptossystems that, in the context of GW are used to impose a requirement of time. This is possible because both consist of a sequence of tasks that, by their nature, can only be computed, in fact, sequentially (not in parallel). For that effect, one can utilize the final result of the sequence as a key for encrypting a critical piece of information of some sort (in order to access such piece of information, one has to, therefore, compute the sequence of tasks, and therefore, wait the prescribed amount of time). The size of such sequences of tasks can be set up to be as large as desired. Additionally, both MHHs and TLP can be set up to require memory allocation as large as desired for the duration of their entire computation (more about that later).
The efficacy of a sequence of non-parallelizable tasks as time barrier derives from the fact of limitedness of frequency scaling. Though it sounds a bit too technical, essentially this means that there are hard technical limits on how fast any given single thread of task computing can run. As a practical, concrete example, the world's fasted cycling CPU at the time of writing just barely broke 9 GHz, which is (even in extremely controlled lab conditions, including Helium cooling...) only about 3 times faster than a decent commercial setup. This marginal out-performance factor can be easily worsen in realistic comparisons when the computation time-intensive task at analysis, for instance, is made to be memory intensive. Since mid 2000's, the paradigm of only marginal increments in CPU frequency consolidated, which eventually lead to the widespread adoption of MMHs like Argon2, among many other applications, as schemes to enhance the security of passwords against brute-force attacks, for example.
A MHH is what is called a trapdoor function, and can be classified as symmetric cryptosystem. A TLP, on the other hand is what is called an asymmetric cryptosystem aka public-key cryptosystem aka key-pair cryptosystem. TLP has the same mathematical basis as the RSA and, therefore, the same cryptographic strength as an RSA cryptosystem with keys of same size (more about that later).
The crucial difference between them, which explains application in different parts of the protocol is that TLP, by design, admits 2 paths to reach the same result, one consisting of only 2 mathematical operations, the other consisting of as many as arbitrarily determined during setup. In order to use the 2-operations path, one has to use the so called private key of the TLP instance. With only its public key only the many-tasks path is possible. The typical use of TLP has the owner instantiating the key pair, using private key to quickly produce the result ---and its correspondent encryption key--- using the latter to encrypt target piece of information to be time-locked, then proceeding to delete encryption key, result and private key --- but not public key. As a result, accessing (plaintext of) target information is only possible by using the public-key to perform the the many-operations path to encryption key and using that key to decrypt ciphertext of time-locked information.
On the other hand, MHHs only admit one computational path. This means that, in order to create a time barrier anew, one has to spend the same amount of time and computational resources as it takes to solve / traverse that time barrier. At this point, attentive reader might be wondering whether that means MHHs as time barriers are obsolete, seeing that they have a clear disadvantage over TLP. The answer to it is "no", and the reason is precisely MHHs not being a key-pair cryptosystem. For reasons that go beyond the scope of this document, it is humanly possible, through mnemonic techniques, to memorize a brute-force resistance MHH input, while it's decidedly unrealistic to expect a neurotypical end-user to do the same with a TLP public key with equivalent cryptographic strength (it would take the user the equivalent of reading, memorizing and typing thousands of random words). That is particularly relevant when, as it's the case of GW, a deviceless protocol is sought: in order to allow a hard reset from a fresh device, from human memory only, and no physical backup, a time intensive key derivation scheme, cannot, therefore, consist of a TLP.
Because, in GW's case, the MHH takes only a human-memorized input, it is, for the user and a coersive attacker, always possible. In order to afford user greater flexibility, TLP instances of shorter duration can be used for setting up a memorization schedule, as well as routine, non-emergency access. By logic, a TLP instance of longer time doesn't make sense because, by design, the MHH is always possible. Finally TLPs can also be used in inheritance protocols.