MV3: A new word based stream cipher using rapid mixing and revolving buffers

Nathan Keller, Stephen D. Miller, Ilya Mironov, Ramarathnam Venkatesan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


MV3 is a new word based stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as rc4 into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like rc4’s, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast — it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size ≤ 256 bits.

Original languageEnglish (US)
Title of host publicationTopics in Cryptology
Subtitle of host publicationCT-RSA 2007 - The Cryptographers Track at the RSA Conference 2007, Proceedings
EditorsMasayuki Abe
PublisherSpringer Verlag
Number of pages19
ISBN (Print)9783540693277
StatePublished - 2007
EventCryptographers Track at the RSA Conference, CT-RSA 2007 - San Francisco, United States
Duration: Feb 5 2007Feb 9 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4377 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherCryptographers Track at the RSA Conference, CT-RSA 2007
Country/TerritoryUnited States
CitySan Francisco

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


  • Cryptanalysis
  • Expander graph
  • Random walks
  • Stream cipher


Dive into the research topics of 'MV3: A new word based stream cipher using rapid mixing and revolving buffers'. Together they form a unique fingerprint.

Cite this