Golden
Cryptographic hash function

Cryptographic hash function

Mathematical hash function that is cryptographically secure and has the properties of collision resistance, hiding, and puzzle friendliness

A cryptographic hash function is a hash function that takes an arbitrary amount of data as input, applies some algorithm, and generates a fixed-sized output data. This alphanumeric string output value is also referred to as "hash value", "checksum", or "digital fingerprint." Hash functions - regardless of whether or not they are cyrptographically secure - also have the property of being efficiently computable, meaning that an output of the hash function can be found in a reasonable time period for any given input. 



There are three main properties that differentiate ordinary hash functions from cryptographic hash functions:

  • Collision resistance
  • Hiding
  • Puzzle friendliness

Collision Resistance

In order for a hash function to be collision resistant, it must be infeasible to find two unique data inputs that produce the same data output. The event of two inputs having an identical output is called a "collision."



This property is critical for maintaining data integrity because it ensures that data cannot be changed retroactively without leaving an obvious indication of the change occurring. In other words, anybody can easily verify that data has not changed if that data was run through a cryptographic hash function and the output hash value is the same. This is because the only way to produce that specific output is with the specific input initially used.

Hiding

The hiding property of cryptographic hash functions states that for any given hash output, there's no feasible way to figure out what the input was. The input is hidden despite the output being visible to anybody.



A more mathematical way to describe this hiding property is to say that for any given probability distribution that contains a secret value 'r', there is no way to taken a random sample from the distribution that's any more likely to be the secret value 'r' than any other random data sample. Given an adequately spread out probability distribution (i.e. one that has a high min-entropy), the probability of randomly finding 'r' by sampling the data set is infinitesimally small, thus making it infeasible to learn a data input just by knowing the hash output.

Puzzle Friendliness

In order for a hash function to be considered puzzle friendly, it must be true that there is not a strategy for solving a computational puzzle based on the hash function that's more effective than simply trying random values from a set of possible solutions until one of them works. 



The mathematical description for this puzzle friendliness property is somewhat complicated. It says that for every possible n-bit (e.g. n = 256 for SHA-256) output value of a hash function, if possible solutions are chosen from a probability distribution with high min-entropy, then it is infeasible to find the solution for the given output value in a time significantly less than 2^n.

Applications of Cryptographic Hash Functions

Cryptographic hash functions have a variety of uses in different areas of cryptography. For example, they are used in password protection, message authentication, key derivation functions, and in pseudo-random number generators, among other applications.



Bitcoin and other cryptocurrencies rely heavily on cryptographic hash functions for data security. Public-key cryptography uses cryptographic hash functions to enable users to have public wallet addresses that they can share in order to receive transactions along with corresponding private keys that are used for digital signatures to authenticate outgoing transactions. Additionally, cryptographic hash functions are an integral part of the various cryptocurrency mining consensus systems that exist such as proof-of-work, proof-of-stake, etc.



Timeline

People

Name
Role
Related Golden topics







Further reading

Title
Author
Link
Type

An Overview of Cryptographic Hash Functions andTheir Uses

John Edward Silva



Bitcoin and Cryptocurrency Technologies

Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Goldfeder, Jeremy Clark

Book

Cryptographic Hash Functions Explained: A Beginner's Guide

Daniel Pigeon

Web

Documentaries, videos and podcasts

Title
Date
Link

(MIT OpenCourseWare)

March 4, 2016

Bitcoin - Cryptographic hash function (Khan Academy)

May 1, 2013

Lecture 1 -- Intro to Crypto and Cryptocurrencies

February 16, 2015

Companies

Company
CEO
Location
Products/Services









References