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 X of size |X| with each element of n-bit, when solved on a classical computer has the time complexity of O(n2~n|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 (log(n)2~n |X|~(1/2)) and worst case time complexity of O (log(n)2~n|X|) using (n + [log |X|] + p)-qubits, where p are the precision qubits required by the quantum counting subroutine.