Cryptographic Concept of the Day: Irreversible Transformations and their Applications

One of the most important and earliest concepts on computational cryptography is one way transformations. The primary method is the hash function.

Hash functions have two applications, I will describe the simpler one first, and then the more complex one.

Checksums

You may have heard the term "checksum" - often a short code that is compiled out of a big piece of data.

The simplest is just adding numbers out of the data, say 8 bits at a time, and for this simple checksum, only a piece of data with the exact same collection of bytes will make the same result, though in different sequence, or a small number of alternatives of lesser or greater size, that map. With data length combined with such a checksum, there would be very few other meaningful sequences of information that would share both simple checksum and size criteria. (But not so few that it can be considered secure).

As you may have realised reading that description, the subject of this post should be visible to you:

You can't take that number and practically (computational feasibility) regenerate the source from the result. But you can be quite confident if the data can be again used to regenerate the same number, that the data was not tampered with between you and the sender, which is the problem this scheme solves.

But this simple checksum is not as secure as it could be. There is possibilities for changing a lot of data for adding a malicious payload, for example, which necessarily would require corrupting part of the rest of the data, so it has been a long time since the simple checksum has been a verifier function.

Now we use MD5 and SHA1/256/512, and these use more complex methods to reduce the collision possibilities. These use instead of addition, or as well, bitwise transformations such as AND, OR, NOT and XOR (exclusive OR), when combining the pieces of the data, that diminishes the probability of matching hashes for different data of the same amount.

In general, hash functions are the generic building block of cryptography. Hashes allow you to mutate data in such a way that knowing the source is nearly impossible, but generating the hash from the true data is easy and quick.

Thus they are primarily used for verification. Of course it is not technically correct to call them "irreversible" in the absolute sense, obviously if you know the size of the data, and the hash, you can attempt to generate strings of data that produce that hash. The reason for more advanced schemes using bitwise operations is the reduction in the number of potential sources of the same size that hash the same, so-called collisions.

Proof of Work

This is something you most likely have heard of. You may also know that hash functions are central to it. But they are not maybe precisely what you thought.

Remember what I said about hash collisions? Well, a proof of work is about finding collisions. The scheme works like this:

  1. Grab a number, called a Nonce (not sure why but this is also British slang for a paedophile), of a specified length.

  2. This is our initial value, we then produce a hash, which is the target for our PoW.

  3. Then we must attempt to generate another number of specified size same as the Nonce, that hashes to produce our Nonce's hash. Making a nonce, and hashing it is cheap. But finding a hash collision is very expensive.

  4. Other participants can then quickly verify that we did the work to reverse the transformation, because we have a hash, and proof we found a collision value, in the form of a nonce and a collision that both make our hash value. Checking it is cheap, but making it is not.

Note that the primary function of a Proof of Work is running a rate limiter of some kind, within a group of untrusted nodes, that limits how frequently some prize is awarded, a lottery without an Authority.

In cryptocurrencies, this is primarily used to decide who prints the next block in the blockchain, the performance of which results in the issuance of a specified amount of fresh new currency.

It is very important because unrestricted issuance of bills of exchange destroys their value. (cryptocurrencies are bills of exchange that can be endorsed by the owner as being now owned by a new owner).

In fact it is a greater innovation in financial technology than anything dreamed up in hundreds of years. It allows a pure notional currency (based only on the intangible and very cheap ink and paper, or even cheaper, bits), to have the supply characteristics of a commodity currency like gold or silver... Without an Authority. It has the advantage of Fiat without a single point of failure.

Final Note

So, that wasn't so brainmeltingly complex as you expected perhaps. I will be covering a few other important concepts in subsequent posts, amongst them will be symmetric encryption, public key infrastructure, deterministic and nondeterministic public keys, secret shares, elliptic curves, and zero knowledge proofs. For good measure I will also explain proof of stake and delegated proof of stake.

Each post will be similarly simply presented, and hopefully it will help more people understand why cryptographic distributed network systems are so powerful and important.

The language of these terms is not exactly what it seems at first blush, but once you grasp it, you see how it became the name also.


We can't stop here! This is Whale country!

Loki was born in Australia, now is wandering Amsterdam again after 9 months in Sofia, Bulgaria. IT generalist, physics theorist, futurist and cyber-agorist. Loki's life mission is to establish a secure, distributed layer atop the internet, and enable space migration, preferably while living in a beautiful mountain house somewhere with a good woman, and lots of farm animals and gardens, where he can also go hunting and camping.

I'm a thoughtocaster, a conundrummer in a band called Life Puzzler. I've flipped more lids than a monkey in a soup kitchen, of the mind. - Xavier, Renegade Angel

*

All images in the above post are either original from me, or taken from Google Image Search, filtered for the right of reuse and modification, and either hotlinked directly, or altered by me

H2
H3
H4
Upload from PC
Video gallery
3 columns
2 columns
1 column
4 Comments