4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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, 2018 at 0:18

1 Answer 1

Reset to default
-1
$\begingroup$

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
Improve this answer
$\endgroup$
2
  • 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, 2018 at 3:00
  • $\begingroup$ thank you for the clarification and this suggested research article $\endgroup$
    – Hasan alabadi
    Apr 3, 2018 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.