Quantum Algorithm to Identify Division Property of a Multiset

Division property-based integral attack is the generalization of integral property developed by blending saturation attack and higher-order differential attack. This attack is considered as a chosen-plaintext attack because the cryptanalyst generates a multiset of plaintext which possesses a certain division property. However, in real-world applications, it is required to find the division property of a given multiset which turns the attack into a known-plaintext attack. The problem, finding the division property of a given multiset $$\mathbb {X}$$ of size $$|\mathbb {X}|$$ with each element of n-bit, when solved on a classical computer has the time complexity of $$O(n2^n|\mathbb {X}|)$$ (fixed in both average and worst cases). In this paper, a better and comparable algorithm using quantum computing is presented along with its quantum oracle designs that can find the correct division property of a multiset in the average case time complexity of $$O \left( \log (n)2^n\sqrt{|\mathbb {X}|} \right) $$ and worst case time complexity of $$O\left( \log (n) 2^n|\mathbb {X}| \right) $$ using $$\left( n + \lceil \log |\mathbb {X}|\rceil + p \right) $$ -qubits, where p are the precision qubits required by the quantum counting subroutine.