A QUANTUM ALGORITHM TO LOCATE UNKNOWN HASHES FOR KNOWN N-GRAMS WITHIN A LARGE MALWARE CORPUS

Abstract

Quantum computing has evolved quickly in recent years and is showing significant benefits in many fields. Malware analysis is one of those fields that could also take advantage of quantum computing. Combining software used to locate the most frequent hashes and $n$-grams between benign and malicious software (KiloGram)\cite{Kilograms_2019} with a quantum search algorithm, this could prove to have an improvement by being able to load the table of hashes and $n$-grams into a quantum computer to look up an unknown hash for a known $n$-gram. The first phase will be to classically use KiloGram\cite{Kilograms_2019} to find the top-$k$ hashes and $n$-grams for a large malware corpus. The resulting table is loaded into a quantum machine. A quantum search algorithm is used to search among every permutation of the entangled key and value pairs to find the unknown hash. This prevents the re-computation of hashes for a set of $n$-grams which can take on average $O(MN)$ time where the quantum algorithm could take $O(\sqrt{N})$ number of table lookups to find the unknown hash.