Time and Space Complexity Reduction of a Cryptanalysis Algorithm

Binary Decision Diagram (in short BDD) is an efficient data structure whichhas been used widely in computer science and engineering. BDD-based attack inkey stream cryptanalysis is one of the best forms of attack in its category. In thispaper, we propose a new key stream attack which is based on ZDD(Zero-suppressedBDD). We show how a ZDD-based key stream attack is more efficient in time andspace complexity over its BDD-based variant against the E0 type of the Bluetoothsecurity mechanism. We implemented it by using the CUDD - Colorado UniversityDecision Diagram package. Experimental results show great improvements. Wehave also derived a mathematical proof, which shows that it is better than the BDDbasedattack method even for the worst case analysis.

کلیدواژه ها:

Binary Decision Diagram ، Cryptanalysis ، Algorithm complexity