I am trying to use Grover's algorithm to find Differential characteristic of Feistel and SPN structures block ciphers. basically, which is Finding a good differential characteristic with high probability in the (related-key) differential attack

For example, using Matsui’s Algorithm to Search for related-key differential characteristics in DES-like ciphers by Alex Biryukov, Ivica Nikolic.: FSE 2011

also using Integer programming-based method ( Differential and linear cryptanalysis using mixed-integer linear Programming ) by Nicky Mouha, Qingju Wang, Dawu Gu, Bart Preneel Inscrypt 2011.

my question

can construct Grover's algorithm to find Differential characteristic of Feistel and SPN structures block ciphers?

  • 1
    $\begingroup$ I recommend to read Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia "Quantum Differential and Linear Cryptanalysis" doi.org/10.13154/tosc.v2016.i1.71-94 $\endgroup$
    – xagawa
    Apr 3 '18 at 0:18

Grover's algorithm is a probabilistic quantum algorithm that finds (with high probability) the unique input to a black box function that produces a particular output value, using $$ O({\sqrt {N}}) $$ evaluations of the function, where the fuction has domain of size $N$. is the size of the function's domain.

Keeping in mind the fact that the spedup is only quadratic, unlike Shor's algorithm which provides exponential speedups on a different problem, it can be applied to any search problem over a finite domain.

The normally suggested countermeasure to this algorithm in the symmetric crypto setting is quite mild: symmetric key lengths can be doubled to compensate for the risk.

Edit: For multiobject search for $\ell$ objects, Boyer et. al. in 1 proved the following theorem, which as pointed out by @poncho in the comments, is a bit counterintuitive.

Theorem: (paraphrased) Assume that $\ell/N$ is small. Then any search algorithm for $\ell$ objects, in the form of [grover search] takes on average $O(\sqrt{N/\ell})$ iterations in order to be successful with positive probability $>1/2$ independent of $N$ and $\ell.$

  1. M. Boyer, G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, Fortsch. Phys. 46 (1998), 493–506. See related paper on arXiv here
  • 1
    $\begingroup$ Actually, Grover's algorithm can handle the case where there are multiple 'winning' entries; however counterintuitively enough, you must decrease the number of iterations. Not "you can reduce the number of iterations, you have to; too many actually reduces the probability of the algorithm finding the solution. $\endgroup$
    – poncho
    Apr 3 '18 at 3:00
  • $\begingroup$ thank you for the clarification and this suggested research article $\endgroup$ Apr 3 '18 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.