Simon's Algorithm and Symmetric authentication schemes

Caute_cautim — Mon, 14 Jul 2025 05:18:05 GMT

Hi All

There are three current algorithms that can break conventional cryptography schemes:

Shor's algorithm is a quantum algorithm developed by Peter Shor in a quantum algorithm developed by Peter Shor in 1994 that efficiently factors large numbers into their prime components.This is a significant speedup compared to the best known classical algorithms, particularly for numbers used in cryptography like those used in RSA encryption. It achieves this by converting the factoring problem into a period-finding problem and leveraging the quantum Fourier transform for a dramatic speed increase.

Grover's algorithm is a quantum algorithm that provides a quadratic speedup for searching unsorted database or solving unstructured search problems. It achieves this by using quantum superposition and interference to significantly reduce the number of queries needed compared to classical search algorithms.

Then I found Simon's algorithm: Simon's algorithm is a quantum algorithm that can efficiently find the period of a function that has a hidden periodicity. In simpler terms, if a function has a repeating pattern, Simon's algorithm can find that pattern much faster than any classical algorithm.

How does it relate to authentication?

Many authentication schemes rely on symmetric key cryptography, where both the sender and receiver share a secret key. Some of these schemes, like CBC-MAC, PMAC, GMAC, GCM, and OCB, have been shown to be vulnerable to attacks using Simon's algorithm in a quantum setting.

Quantum Attacks on Symmetric Cryptography:

CBC-MAC, PMAC, etc.:
Simon's algorithm can be used to find collisions in these message authentication codes, allowing an attacker to forge authentication tags.

Feistel Networks:
The 3-round Feisty network, a common building block in many symmetric ciphers, has also been shown to be vulnerable.

Slide Attacks:
Simon's algorithm can exponentially speed up classical slide attacks, which are a type of cryptanalytic attack.

Post-Quantum Security:

While these attacks are theoretical, they highlight the potential vulnerability of classical symmetric cryptography to quantum computers.
This is why NIST and other organizations are working on developing and standardizing post-quantum cryptography (PQC) algorithms, which are designed to be secure against both classical and quantum attacks.
PQC algorithms are not based on quantum mechanics but rather on mathematical problems that are believed to be hard to solve even for quantum computers.

So prepare now, and don't leave until 2030 to even think about it.

Regards

Caute_Cautim

topic Simon's Algorithm and Symmetric authentication schemes in Tech Talk

Simon's Algorithm and Symmetric authentication schemes