liveBook · Manning

Grover's algorithm

As explained in Real-World Cryptography

Grover's algorithm is a quantum search algorithm that finds a marked item in an unstructured search space using approximately the square root of the classical search effort.

Imagine searching an unordered list for one marked item. Classical search takes about N/2 checks on average; Grover's algorithm reduces this to roughly √N checks on a quantum computer. section 14.1.3

In cryptography, the algorithm can:

  • Search for a symmetric key or value, reducing a 128-bit search from about 2^127 classical operations to 2^64 quantum operations. section 14.1.3
  • Find collisions in hash functions or extract symmetric keys, making larger security parameters advisable. section 14.1.3
  • Be countered by increasing symmetric security from 128 bits to 256 bits, such as choosing AES-256-GCM instead of AES-128-GCM or SHA-3-512 instead of SHA-3-256. section 14.1.3 section 14.5

How Real-World Cryptography covers it

How deep it goes
Defines the search advantage and cryptographic consequences but stops short of explaining the quantum circuit or proof.
Examples
Uses unordered-list search, 128-bit key search, AES-GCM choices, and SHA-3 parameter increases.
What it assumes
Assumes familiarity with symmetric cryptography and security-bit estimates while explaining the search comparison directly.
What you can do after
Evaluate quantum search risk and choose 256-bit symmetric parameters as a mitigation.
How it connects
Connects quantum computing with symmetric cryptography, hash functions, key search, and post-quantum cryptography.
Cover of Real-World Cryptography
liveBookmanning.com
Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

Compare how 3 books explain Grover's algorithm →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.