International Association for Cryptologic Research

International Association
for Cryptologic Research


Stephen D. Miller


MV3: A new word based stream cipher using rapid mixing and revolving buffers
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.
Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves
David Jao Stephen D. Miller Ramarathnam Venkatesan
Cryptographic applications using an elliptic curve over a finite field filter curves for suitability using their order as the primary criterion: e.g. checking that their order has a large prime divisor before accepting it. It is therefore natural to ask whether the discrete log problem (DLOG) has the same difficulty for all curves with the same order; if so it would justify the above practice. We prove that this is essentially true by showing random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). Our reduction proof works for curves with (nearly) the same endomorphism rings, but it is unclear if such a reduction exists in general. This suggests that in addition to the order, the conductor of its endomorphism ring may play a role. The random self-reducibility for dlog over finite fields is well known; the non-trivial part here is that one must relate non-isomorphic algebraic groups of two isogenous curves. We construct certain expander graphs with elliptic curves as nodes and low degree isogenies as edges, and utilize the rapid mixing of random walks on this graph. We also briefly look at some recommended curves, compare ?random? type NIST FIPS 186-2 curves to other special curves from this standpoint, and suggest a parameter to measure how generic a given curve is.