Anzeige
Erschienen in:
01.03.2015
Quantum algorithm to find invariant linear structure of MD hash functions
Erschienen in: Quantum Information Processing | Ausgabe 3/2015
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper, we consider a special problem. “Given a function \(f\): \(\{0, 1\}^{n}\rightarrow \{0, 1\}^{m}\). Suppose there exists a n-bit string \(\alpha \in \{0, 1\}^{n}\) subject to \(f(x\oplus \alpha )=f(x)\) for \(\forall x\in \{0, 1\}^{n}\). We only know the Hamming weight \(W(\alpha )=1\), and find this \(\alpha \).” We present a quantum algorithm with “Oracle” to solve this problem. The successful probability of the quantum algorithm is \((\frac{2^{l}-1}{2^{l}})^{n-1}\), and the time complexity of the quantum algorithm is \(O(\log (n-1))\) for the given Hamming weight \(W(\alpha )=1\). As an application, we present a quantum algorithm to decide whether there exists such an invariant linear structure of the \(MD\) hash function family as a kind of collision. Then, we provide some consumptions of the quantum algorithms using the time–space trade-off.