Targeting integer number of right pair in differential attacks

Question

As we know, purpose of attackers is finding some high probable differential characteristics in differential cryptanalysis. Then they construct some plaintext structures, plaintext pool and expect some right pairs that satisfy this characteristic with calculated probability. In this context, they determine the number of required right pair then they construct their plaintext- ciphertext pairs pool according to intended number of right pairs.

In other words, If probability of characteristic is equal to p and they need k right pairs for some key recovery process then their plaintext-ciphertext pools consist of $k*p^{-1}$ elements.

My question is, why they always need some integer number right pairs? For example, I was looking The Rectangle Attack – Rectangling the Serpent and in this article they target 8 right pairs then according to characteristic, they use $2^{72.8}$ pairs to obtain them.

In this example, they may use $2^{73}$ pairs and expect $2^{3.2}$ right pairs for key recovery. Is there any reason to pick expected number of right pairs as integer? Is it always optimal?

Answer 1

Because you need 8 right pairs for the attack, it is natural to use $k=8$ as a reference point. Then, the median (by the Binomial distribution) is exactly $p k/p=k$ points, suggesting the success rate at least 50%.

Then $k$ may indeed be varied (including fractional values) to decrease/increase the success probability, of course as long as the number of requested texts $k/p$ is integral.

There is no "optimal" value, it is a trade-off between the amount of data and the success probability. Setting $k$ exactly as needed for the attack is a simple reference point.

Answer 2

Two things. It is simpler to target an integer number of right pairs in terms of implementation. Otherwise you might need to keep a running average.

More importantly, it makes sense to round up to the next integer, to improve the probability of actually obtaining that average of right pairs since the procedure rests on statistical assumptions.