Greedy distinguishers and nonrandomness detectors

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingPeer review

415 Nedladdningar (Pure)


We present the concept of greedy distinguishers and show how some simple observations and the well known greedy heuristic can be combined into a very powerful strategy (the Greedy Bit Set Algorithm) for efficient and systematic construction of distinguishers and nonrandomness detectors. We show how this strategy can be applied to a large array of stream and block ciphers, and we show that our method outperforms every other method we have seen so far by presenting new and record-breaking results for Trivium, Grain-$128$ and Grain v1.

We show that the greedy strategy reveals weaknesses in Trivium reduced to $1026$ (out of $1152$) initialization rounds using $2^{45}$ complexity -- a result that significantly improves all previous efforts. This result was further improved using a cluster; $1078$ rounds at $2^{54}$ complexity. We also present an $806$-round distinguisher for Trivium with $2^{44}$ complexity.

Distinguisher and nonrandomness records are also set for Grain-$128$. We show nonrandomness for the full Grain-$128$ with its $256$ (out of $256$) initialization rounds, and present a $246$-round distinguisher with complexity $2^{42}$.

For Grain v1 we show nonrandomness for $96$ (out of $160$) initialization rounds at the very modest complexity of $2^7$, and a $90$-round distinguisher with complexity $2^{39}$.

On the theoretical side we define the Nonrandomness Threshold, which explicitly expresses the nature of the randomness limit that is being explored.
Titel på värdpublikationProgress in Cryptology - INDOCRYPT 2010 / Lecture Notes in Computer Science
RedaktörerGuang Gong, Kishan Chand Gupta
Antal sidor17
ISBN (tryckt)978-3-642-17400-1
StatusPublished - 2010
EvenemangINDOCRYPT 2010, 11th International Conference on Cryptology in India - Hyderabad, Indien
Varaktighet: 2010 dec. 122010 dec. 15


ISSN (tryckt)1611-3349
ISSN (elektroniskt)0302-9743


KonferensINDOCRYPT 2010, 11th International Conference on Cryptology in India

Ämnesklassifikation (UKÄ)

  • Elektroteknik och elektronik


Utforska forskningsämnen för ”Greedy distinguishers and nonrandomness detectors”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här