Approximately how many inputs are required to find a collision in a hash function with an n‑bit output by the birthday bound?

• A. 2^(n/2)
• B. 2^n
• C. n
• D. 2^(n/4)

Answer: (A)

When assessing how many inputs are needed to find a collision in an n‑bit hash, the key idea is the birthday bound. The hash output space has 2^n possible values, and collisions become likely once you’ve sampled enough inputs that the probability of at least one pair sharing a value becomes significant. The number of input samples needed grows with the square root of the number of possible outputs, because the number of possible pairs grows quadratically while each pair has a 1 in 2^n chance of matching. Setting m^2 ~ 2^n and solving for m gives m ~ 2^(n/2). So about 2^(n/2) inputs are required to expect a collision with high probability. This is why the birthday bound points to the square-root scale of the output space. The other options are far from this threshold: 2^n would mean exhaustively checking all inputs, n is far too small, and 2^(n/4) is not enough to reach the collision likelihood predicted by the birthday paradox.