What do we do about the quantum threat? There are multiple families of quantum-resistant algorithms being evaluated by the National Institute of Standards and Technology (NIST) through the Post-Quantum Cryptography (PQC) competition to secure against quantum computing attacks.
Hash-based cryptography is one of those cryptographic families being considered. But what is hash-based cryptography, why is it secure, and how is it being used today? And what is its future in a world where large-scale quantum computers exist?
What are Hash Functions?
Hash-based cryptography is a method to transform any piece of information into a jumbled code that is difficult to decipher. You enter your data, like an email, a password, or a document, and convert it into a fixed-size hash, which is a string of characters that looks nothing like the original input, but is a certain amount of characters in length. This process is one-way, which means that reversing the hash back to the original data is supposed to be impossible.
Properties of Cryptographic Hash Functions
To secure data, hash functions must be:
- Consistent: They must be deterministic, meaning the same input will always result in the same hash output, no matter how many times you add that input.
- Unique: No two different inputs should produce the same hash output.
- Sensitive: Even a small change in the input should produce a very different hash.
- Quick to Compute: As with all cryptography, tradeoffs between speed and security exist. But these computations should not slow down users.
- Hard to Reverse: For someone with only the hash output, figuring out the original input should be practically impossible.
You can see some of these properties yourself by using the SHA256 generator here.
For example, if you input
“Hello from BTQ!”
The output hash is:
f217b2e62017882bd5df14ba7cc2993f9ebd446ff4b89623e96cd97c1e9cecc6
As you add spaces or other characters, you see the hash changes. But, no matter how many characters you add, the hash length stays constant.
Practical Applications of Hash-Based Cryptography
Hash-based cryptography is already being used today to secure data in everyday activities. Some are used to make sure files are intact and unaltered, acting like a digital seal. Others are more used for secure password storage because they're especially resistant to reverse engineering. It's also the backbone of SSL certificates that secure websites and the integrity checks that ensure the software you download hasn't been tampered with. The hash function is a fundamental part of blockchain technology, helping to secure every data block and ensure the chain's integrity.
From finance to healthcare, industries that deal with sensitive information are using hash-based cryptography for certain applications. In finance, securing transactions and protecting against fraud is a big business, and hash functions provide a way to verify that the information has not been altered without needing a third party. In healthcare, patient records and other confidential data can be hashed to ensure privacy and compliance with regulations.
Because it has been in use for so long, hash-based cryptography is a known player in the cryptography realm. It has been used, attacked, and has stood the test of time in many industries.
The Quantum Computing Challenge
The rise of quantum computing is upending security in a way we haven’t seen before. Quantum computers aren't just faster versions of classical computers. They work on the principles of quantum mechanics, like superposition and entanglement to process information and use algorithms in completely different ways.
The problem is that some of these algorithms can break our encryption. For example, the security of RSA encryption relies on the difficulty of factoring large numbers. This means that encrypted information that would take thousands of years to crack with the biggest supercomputers could potentially be decrypted in just hours with a quantum computer.
With these new developments, there is a need for new forms of cryptography that can withstand quantum attacks. Hash-based cryptography is one of the methods that is, as far as we know today, resistant to quantum computing attacks.
Quantum Resistance of Hash Functions
Research into quantum computing algorithms suggests that while some RSA, ECC, and some other encryption algorithms are vulnerable to quantum computing, hash functions do not have a devastating exploit. The key advantage of hash functions is that they do not rely on the 'hard' mathematical problems that quantum computers can break, like factoring prime numbers.
Even with a quantum computer, as of now, there is no shortcut to unscramble a hash back to its original form. This is because hash functions are designed to be one-way operations. Quantum computers are great at problems that have underlying structures they can exploit, like Shor’s algorithms exploiting periodicity, but a good cryptographic hash function has outputs that appear random.
Theoretically, quantum computers could use Grover's algorithm to speed up searching for an input that matches a given hash output. However, this speedup is quadratic, not exponential. For instance, a quantum computer could potentially reduce a search that would take 2^128 operations to 2^64 operations, which is a significant reduction, but it’s still a large number of operations. For algorithms that are weakened by Grover’s algorithm, like AES, you would just need to double key size to get back to the same security level as before.
Worldwide regulators seem to agree. In 2022, NIST announced SPHINCS+, a stateless hash-based signature scheme, as one of three algorithms to be standardized for digital signatures.
Hash-based cryptography isn't the only approach being considered for quantum resistance. Other methods, such as lattice-based cryptography, code-based cryptography, and multivariate polynomial cryptography, are also in the running in the NIST Post-Quantum Cryptography competition. Each of these methods has its own advantages and challenges, but what sets hash-based cryptography apart is its simplicity and that it's already widely used and well-understood.
BTQ's Preon and Hash-Based Cryptography
Preon, by BTQ, also relies on the assumptions of hash functions and error-correcting codes. Chen-Mou Cheng, BTQ's Chief Cryptographer, emphasizes that the cryptographic community can’t function without secure hash functions, as they are fundamental to the design of any digital signature scheme. Preon's use of hash functions positions it well against quantum threats, as current understanding suggests that encoding hash functions into a quantum computer's algorithms is not an easy task. This is a layer of security against quantum attacks. Hash-based cryptography is widely used and has been battle-tested by securing web transactions and even scrambling blockchain wallet data, so it plays a critical role in the era of quantum computing.
The assumptions of Preon's security model are considered robust within the cryptographic community since hash functions are a known standard. Preon's development follows this by relying on the strength of these assumptions, as well as publishing openly for cryptographic researchers to evaluate these assumptions. Open and transparent standards align with the requirements of global cryptographic standards.
While quantum technologies bring a set of new algorithms to change the world for the better with advancements in medicine, materials, and energy, they also bring new security challenges. As quantum technology continues to advance, the importance of developing and implementing quantum-resistant cryptographic methods becomes increasingly important to protect sensitive data and communications.
